david wong

Hey! I'm David, a security consultant at Cryptography Services, the crypto team of NCC Group . This is my blog about cryptography and security and other related topics that I find interesting.

Maybe you shouldn't skip SHA-3

posted June 2017

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.

Well done! You've reached the end of my post. Now you can leave me a comment :)

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.

spooked

In 2010, both Adi Shamir and Brian Snow at RSA Cryptographers Panel were of the opinion that the SHA-3 competition should last longer. Snow was not confident the result would be positive.

Also, implementation always remains the issue, at every level.

Mentioning cloudflare in any connection with security would be scoffed at in many circles (remember cloudbleed?)...

In 2013 and 2014, Brian Snow stated he was doubtful that robust post-quantum pkcs would arrive and be implemented before quantum computing arrives.

And really, hardware (i.e. CPU) accelerators and entropy sources as a good thing? These implementations are not open, and if tampered with be catastrophic. Intel has a long history of cooperation, and equally of poor implementations (this having come to the surface quite clearly in the past two years). Speed should always be second to security, always. If you want speed, you must invest in or seek open crypto hardware.

The external crypto and more broadly security world is so far behind NSA, and continuing to lag further and further behind (especially when it comes to actual implemented systems)...that one wonder what the future holds...

Most data that is exchanged is now going on cloud servers (and many cloud services rent server infrastructure at the edge from the telcos - cloud squared?), i.e. the ultimate example of an insecure endpoint, and most commercial or civilian systems are not locked down using hard, well-defined containerization and hardening strategies on all axes (whether it be network, file system, kernel, firmware, hardware, etc.), and almost all commercial systems (at multiple levels) by default (or are designed to force the user to) upload so much metadata to servers that themselves are not secure endpoints, that no data, even if end to end encrypted can be considered safe when exchanged with a third party with whom you don't have an agreed, well-defined security policy. Even if data is encrypted in transit, unless it is encrypted using a well-defined, open process, and only manually decrypted in a secure environment, the data is not able to be considered secure at any level.

cloudflare

And also an aside on cloudflare. You do realize that cloudflare MITMs the connection to your website...the CN is sni63268.cloudflaressl.com, and the Cert Subject Alt Name list:

sni63268.cloudflaressl.com
*.234eax.tk
*.3pages.fr
*.activehealthcareandrehab.com
*.baikaleminer.com
*.beautyjordan.com
*.beautylatvia.com
*.beautyliechtenstein.com
*.beautymartinique.com
*.beautymauritania.com
*.beautymm.com
*.beautymorocco.com
*.beautymunich.com
*.beautynepal.com
*.beautyniue.com
*.beautypanama.com
*.beautyportugal.com
*.beautyrwanda.com
*.beautysaintpierreandmiquelon.com
*.beautysaopaulo.com
*.beautyserbia.com
*.beautyshanghai.com
*.beautysintmaarten.com
*.beautysomalia.com
*.beautysouthkorea.com
*.beautysuriname.com
*.comfortspotmassage.com
*.cryptoisnotcryptocurrency.com
*.cryptologie.net
*.davidwong.fr
*.discocrypto.com
*.errant.me.uk
*.kgobisa.com
*.kinowcy.pl
*.maxfiles.pl
*.meczowe.pl
*.motoriruggenti.altervista.org
*.p1x3l.com
*.parkovka.co
*.starlincs.co.uk
234eax.tk
3pages.fr
activehealthcareandrehab.com
baikaleminer.com
beautyjordan.com
beautylatvia.com
beautyliechtenstein.com
beautymartinique.com
beautymauritania.com
beautymm.com
beautymorocco.com
beautymunich.com
beautynepal.com
beautyniue.com
beautypanama.com
beautyportugal.com
beautyrwanda.com
beautysaintpierreandmiquelon.com
beautysaopaulo.com
beautyserbia.com
beautyshanghai.com
beautysintmaarten.com
beautysomalia.com
beautysouthkorea.com
beautysuriname.com
comfortspotmassage.com
cryptoisnotcryptocurrency.com
cryptologie.net
davidwong.fr
discocrypto.com
errant.me.uk
kgobisa.com
kinowcy.pl
maxfiles.pl
meczowe.pl
motoriruggenti.altervista.org
p1x3l.com
parkovka.co
starlincs.co.uk


Even some sites have this kind of insecure SSL on pages where users are meant to upload personal information such as credit card, ID/Passport/SSN/etc data. The use of this kind of MITM'd patch SSL (what about the connection between cloudflare and the backend?) usually used to protect against DDOS (you know, it is possible to prevent DDOS without actually seeing plaintext Cloudflare...), and the increased use of cloud/CDN servers (even if you use real SSL certs) for hosting/processing of such data is utterly inappropriate. After all CDNs historically were only meant for the mass download of less sensitive site content, not for the hosting of servers receiving and processing sensitive user-uploaded data.


Adi Shamir at RSA2010: "Once again, I have to rain on the parade, I'm deeply worried about [cloud computing]...Once most people move their IT operations, into the cloud it is going to be the wet dream of governments. Just have to remember the story of Crypto AG... turned out to be a front company for the NSA and its German equivalent. If we are going to see dozens and dozens of companies offering cloud services, please don't use Cloud AG services..."

Brian Snow's attitude at RSA2010 on the cloud: "I'm not a fan of the cloud either, frankly. You're renting an interface, and don't know what's cuddling up to you and going into your pockets. So, you have to write your contracts very carefully, at least - SLAs, etc, otherwise you are at great risk."

Anonymous

@Aaron Toponce

SHA-224 and SHA-384 are not completely immune to length extension attacks. It is slightly harder to perform, but too few bits of the hash are discarded. Only SHA-512/224 and SHA-512/256 provide computational security against LE attacks.