Subject: [Cfrg] Hashes beyond signatures?

From: Dan Brown <[email-masked]>
Date: Wed, 14 Oct 2015 19:06:12 +0000

Dear CFRG,

Should CFRG recommend some general-purpose hash function choices?
Specifically, should the hash choices now being made for EdDSA also be
recommended more broadly for non-signature purposes?  

For larger (or securer than SHA256), several people have proposed different
hashes, for a variety of reasons.  For message digesting in signatures, I've
seen SHA-384, SHA-512, SHA3/SHAKE (Keccak), Blake2, and so on.  For extended
length hashes (i.e. PRF/KDFs), there's HMAC, HKDF, SHAKE, SHA2-912(?), and
others (ANSI and NIST KDFs in the key agreement applications). 

Generally, it seems safer to have a small set of commonly used primitives:
easier interoperability; clearer path for upgrading of protocols; crypto
primitive implementations re-usable across protocols; safer to implement
fewer crypto primitives (less code, less bugs); less re-inventing the wheel;
less reviewing.  (All that said, I'll soon send out a slight variation on
this approach.)

What are some other major hash applications (requiring interoperability)?
The days of hash-based MACs seem almost over (due to AEAD). Simple password
hashing is being obsoleted (and maybe should be localized, not networked,
that is, network only post-hash).  Hash-based DRBGs are not an
inter-operability issue.  

Nonetheless, many protocols, and even schemes (e.g. EdDSA, RSA-PSS), still
adopt a hash-more strategy, supported by intuition, practice, experience
(aegis), random oracle model proofs, and even lately, nod, standard model
proofs.  In most of these cases, the hash usage can still be classified as
message digesting (public in and out, but still oracle-like), or PRF/KDF
(secrets in and out).  Since deterministic signatures need both these types
of hash usage (but only a limited PRF/KDF), it seems resolving the hashing
issues now might lead to a good general-purpose recommendation.  

Of course, suitability for signatures does not guarantee general-purpose
suitability, so I would understand not wanting to commit now to a broader
recommendation.  Nonetheless, CFRG might want to anticipate this choice now,
and try for something general-purpose.

Best regards,

Dan,

Certicom/BlackBerry

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 14 Oct 2015 22:47:47 +0300

> recommended more broadly for non-signature purposes?  
  
Well, I don't think any of the proposals are actually hashes. Those are
KDFs and XOFs (which FIPS202 specifically warns are not hashes).

Actual 912-bit analyzed hash is pretty much (but not completely)
unobtabnium. 1056-bit? There's nothing.

> others (ANSI and NIST KDFs in the key agreement applications). 

Well, if you want hash function security above SHA-256, there are SHA-384 and
SHA-512 plus other seems-to-be-becoming-popular like Blake2b.

Seems like current hash functions cap at 512 bits (I'm only aware of one
that doesn't and has extensive analysis[1]).

For anything above, there only seems to be KDFs and XOFs.

As for reasons for lukewarm reception for SHA-3, I see a few reasons:
- When SHA-3 project was started, there was fear that SHA-2 would be weak.
  SHA-2 got lots of cryptoanalysis, and the conclusion was it wasn't weak.
- Keccak is hardware-oriented design (heck, it doesn't seem to have
  additions anywhere!), not software-oriented.
- No real technical advantages (as hash).

Furthermore, if one takes view of XOFs as KDFs, those suffer the problems
of nonstandard constructs (how you turn hash with a native MAC construct
into a MAC? Well, with HMAC).

Native MAC or KDF constructs (or using "special features" of some hash
function) seem to be mostly used in custom designs.

> less reviewing.  (All that said, I'll soon send out a slight variation on
 
Agreed. Plus hash functions aren't actually easy to implement (getting
Valgrind to shut up and test vectors pass is the easy part).  

> that is, network only post-hash).  Hash-based DRBGs are not an

Well, HMAC still gets lots of use inside other primitives. It seems like
almost every KDF construction uses HMAC inside.

[1] That's right, I'm only awarare of only one extensively analyzed
912-bit "hash function" that doesn't obviously fail hash function
security (but it is too exotic to actually use).

-Ilari

---

From: Tony Arcieri <[email-masked]>
Date: Wed, 14 Oct 2015 13:00:30 -0700

On Wednesday, October 14, 2015, Dan Brown <[email-masked]> wrote:

>  For extended length hashes (i.e. PRF/KDFs), there’s HMAC, HKDF, SHAKE,
> SHA2-912(?), and others (ANSI and NIST KDFs in the key agreement
> applications)
>
Given the recent discussion about Blake2, is there a particular reason you
don't list it as a PRF/KDF?

The keyed mode and "personalization string" features seems rather nice for
deriving multiple keys for a master secret, and it performs quite well in
software on most CPU architectures.

-- 
Tony Arcieri

---

From: Gilles Van Assche <[email-masked]>
Date: Fri, 16 Oct 2015 12:05:16 +0200

On 10/14/2015 09:47 PM, Ilari Liusvaara wrote:
> - When SHA-3 project was started, there was fear that SHA-2 would be
> weak. SHA-2 got lots of cryptoanalysis, and the conclusion was it
> wasn't weak.

On the other hand, SHA-2 does not have a thick safety margin. The SHA-3
competition showed that it was possible to make a function that has more
safety margin than SHA-2, that does not rely again on the same ideas as
MD4, MD5 and SHA-1 (narrow-pipe, ARX) and that has an open cryptographic
design (not designed by NSA).

> additions anywhere!), not software-oriented.

I think it is more nuanced. Unlike SHA-2 and other designs that are
*only* software-oriented, Keccak takes a more balanced approach w.r.t.
performance across software on 32-bit and 64-bit platforms, hardware
designs and side-channel-protected implemementations.

> - No real technical advantages (as hash).

Most applications use more than just hashing, beyond which the sponge
construction has shown quite some flexibility.

Kind regards,
Gilles