Maybe you shouldn't skip SHA-3 3 weeks ago
Adam Langley from Google wrote a blogpost yesterday called Maybe Skip SHA-3. It started some discussions both on HN and on r/crypto
Speed drives adoption, Daniel J. Bernstein (djb) probably understand this more than anyone else. And this is what led Adam Langley to decide to either stay on SHA-2 or move to BLAKE2. Is that a good advice? Should we all follow his steps?
I think it is important to remember that Google, as well as the other big players, have an agenda for speed. I'm not saying that they do not care about security, it would be stupid for me to say that, especially seeing all of the improvements we've had in the field thanks to them in the last few years (Project Zero, Android, Chrome, Wycheproof, Tink, BoringSSL, email encryption, Key Transparency, Certificate Transparency, ...)
What I'm saying is that although they care deeply about security, they are also looking for compromises to gain speed. This can be seen with the push for 0-RTT in TLS, but I believe we're seeing it here as well with a push for either KangarooTwelve (K12) or BLAKE2 instead of SHA-3/SHAKE and BLAKE (which are more secure versions of K12 and BLAKE2).
Adam Langley even went as far as to recommend folks to stay on SHA-2.
But how can we keep advising SHA-2 when we know it can be badly misused? Yes I'm talking about length extension attacks. These attacks that prevent you from using SHA-2(key|data)
to create a Message Authentication Code (MAC).
We recently cared so much about misuses of AES-GCM (documented misuses!) that Adam Langley's previous blog post to the SHA-3 one is about AES-GCM-SIV. We cared so much about simple APIs, that recently Tink simply removed the nonce argument from AES-GCM's API.
If we cared so much about documented misusage of crypto APIs, how can we not care about this undocumented misuse of SHA-2? Intuitively, if SHA-2 was to behave like a random oracle there would be no problem at all with the SHA-2(key|data)
construction. Actually, none of the more secure hash functions like Blake and SHA-3 have this problem.
If we cared so much about simple APIs, why would we advise people to "fix" SHA-2 by truncating 256 bits of SHA-512's output (SHA-512/256)?
The reality is that you should use SHA-3. I'm making this as a broad recommendation for people who do not know much about cryptography. You can't go wrong with the NIST's standard.
Now let's see how we can dilute a good advice.
If you care about speed you should use SHAKE or BLAKE.
If you really care about speed you should use KangarooTwelve or BLAKE2.
If you really really care about speed you should use SHA-512/256. (edit: people are pointing to me that Blake2 is also faster than that)
If you really really really care about speed you should use CRC32 (don't, it's a joke).
How big of a security compromise are you willing to make? We know the big players have decided, but have they decided for you?
Is SHA-3 that slow?
Where is a hash function usually used? One major use is in signing messages. You hash the message before signing it because you can't sign something that is too big.
Here is a number taken from djb's benchmarks on how many cycles it takes to sign with ed25519: 187746
Here is a number taken from djb's benchmarks on how many cycles it takes to hash a byte with keccak512: 15
Keccak has a page with more numbers for software performance
Spoiler Alert: you probably don't care about a few cycles.
Not to say there are no cases where this is relevant, but if you're doing a huge amount of hashing and you're hashing big messages, you should rather switch to a tree-hashing mode. KangarooTwelve, BLAKE2bp and BLAKE2sp all support that.
EDIT: The Keccak team just released a response as well.
My name
Hi!
Ron Garret
Re: 187746 cycles to sign with Ed25519 vs 15 cycles to hash a byte with keccak512: this is true but very misleading. You can't compare a fixed cost to an amortized one. The hashing cost grows with message length, and starts to dominate at about 10k bytes. So unless you're signing only very small messages, hashing cost still matters.
david
This is very true Ron, thanks for pointing that out.
I'm thinking a better metric would be the size of a few handshake messages, which is mostly what is being hashed in TLS for example.
I've seen large numbers being used to compare hash functions, which I think can be misleading too as of course the bigger the numbers the bigger the difference between the slower and faster hash functions. This does not mean in the end that your users, or even your system would notice a difference.
Aaron Toponce
<blockquote>But how can we keep advising SHA-2 when we know it can be badly misused? Yes I'm talking about length extension attacks. These attacks that prevent you from using SHA-2(key|data) to create a Message Authentication Code (MAC).</blockquote>
SHA-224, SHA-384, SHA-512/224, and SHA-512/256 are not vulnerable to length extension attacks. That's 2/3 of the SHA-2 portfolio.
<blockquote>We recently cared so much about misuses of AES-GCM (documented misuses!) that Adam Langley's previous blog post to the SHA-3 one is about AES-GCM-SIV.</blockquote>
Sure, although a better (the best?) alternative to AES-GCM-SIV would be AES-OCB. Philip Rogaway opened the patent to allow for Free Software and Open Source use, and granted a license to OpenSSL explicitly.
Further, with AES-NI, and the upcoming Intel SHA extensions, IMNSHO, it's not great advice to advise against the use of AES and SHA-2. In addition to security, if speed is a top priority, and you have the latest-and-greatest Intel chipsets with both AES and SHA instructions sets, then it seems wise to use AES-OCB with SHA-2-HMAC.
However, it also make sense to support lightweight cryptographic primitives for clients that don't have the AES and SHA hardware instructions sets. ChaCha20-Poly1305 operates at less than 2 cpb for long messages, and BLAKE2 at 3 cpb. A keyed BLAKE2 (or KangarooTwelve) does not need a separate MAC primitive, so ChaCha20-Poly1305 with keyed BLAKE2 seems to be wise advice for clients without Intel AES and SHA instruction sets.
Cloudflare wrote a great post on this (complete with graphs!) - https://blog.cloudflare.com/it-takes-two-to-chacha-poly/
Alex Elsayed
> Sure, although a better (the best?) alternative to AES-GCM-SIV would be AES-OCB.
No, it's not. They are very different algorithms with VERY different security properties.
In particular, AES-OCB is _not_ nonce-misuse-resistant, in any way shape or form. It's just as bad as GCM on that count.
Rogaway (the author of AES-OCB) has defined the AES-SIV (and AEZ) nonce-misuse-resistant AEAD modes _exactly because_ that security definition is _frequently insufficient_. In particular, there are many cases where nonce reuse is likely enough that the _catastrophic_ failure AES-GCM and AES-OCB undergo is completely unacceptable.
AES-GCM-SIV, meanwhile, is yet another such "compromise in the name of speed" just like AGL's post about SHA-3. Initially, the term "nonce-misuse-resistant" was used to describe it, but it _does not actually meet_ the definition of that property - it meets a much weaker property.
Strictly speaking, nonce-misuse-resistance/MRAE means that so long as one never encrypts the same (key, nonce, AD, plaintext) tuple twice, there is _zero_ information leaked, and _zero_ loss of integrity protection. If the tuple _is_ repeated, there is still _zero_ loss of integrity, and the _only_ information leak is that _the duplicate messages can be identified **as** duplicates_.
AES-GCM-SIV, meanwhile, suffers security losses at 2^8 repeated nonces, violating the MRAE security property in the name of speed. See this email from AGL himself: https://www.ietf.org/mail-archive/web/cfrg/current/msg08921.html
Zooko
I don't agree with the implication that BLAKE2 is less secure than SHA-3, nor the implication that it is slower than SHA-512/256. (Disclosure: I'm a co-author of BLAKE2.)
Andy
It's based on byte, and with a avalanche of, 1.64,extending the output doesn't help as the input is fixed, it's like changing the code from 16 to 32, the ibox needs to be flushed with a key
david
Zooko:
I meant that BLAKE2 is less secure than BLAKE. My first recommendation is an "easy" recommendation. Since it's a standard, SHA-3 is just easy to recommend. People have used SHA-2 in the past they will find it natural to update to SHA-3.
As for it being faster than SHA-512/256, I should probably correct that.