Wednesday, October 3, 2012

SHA3 is over. Long live SHA3!

The Keccak 'sponge'
(Wikipedia/CC)
The news today is all about hash functions, and specifically, the new hash function we're all going to be calling SHA3. After six long years NIST has finally announced the winner of the SHA3 competition: it's Keccak.

This isn't a total shock: the scuttlebut is that Keccak got most of the 'hums' in NIST's informal 'hum if you like this hash function' poll at the SHA3 conference this year, followed closely by BLAKE. (Yes, seriously, this is how we do things.) Obviously hums aren't the only criteria NIST uses to pick a standard, but they do us an idea where the community stands on things. Moreover, Keccak sports a radically different design than SHA2 and its competitors -- something that appears to have given it a strong competitive advantage.

Now please let me stipulate (again!) that I'm no expert in hash function design. And sadly, many of the leading hash function experts had 'losing' submissions of their own, which means they're still in the first stages of the grieving process -- the one where they say nice things about the winner while secretly plotting its demise. (I'm only kidding. Sort of.)

So while I'm no expert in the deep internals of the design, I can sum up a few things that others -- both expert and non-expert -- are saying about the process and the decision.

To begin with, nobody really thinks that NIST blew it here. All of the finalists were strong designs, and each provides a substantial security margin over the previous state of the art. Each was evaluated under a base standard of 'indifferentiability from a random oracle', and each possesses a security proof to that effect (for more on what this means, see this post.) This is a great turn for NIST, which has been been iffy on provable security in the past. Concretely, this means no more length-extension attacks as in SHA1/2, though admittedly some SHA2 variants already satisfy this requirement.

Moreover, I hear nobody complaining about the security of Keccak. The major gripes appear to be centered around its performance in software, a concern that really does have some grounding. But more on that in a second.

So what do we know about Keccak/SHA3? This list is by no means comprehensive (nor does it represent my own thoughts alone), but it will hopefully provide a few insights:
  • The name 'Keccak' comes from 'Kecak', a Balinese dance. (h/t JP Aumasson)
  • Keccak differs from the other SHA3 finalists in that it uses a 'sponge' construction. Where other designs rely on a 'compression function' which is extended to larger domains, Keccak uses a non-compressing function to absorb and then 'squeeze out' a short digest. It's unclear whether this design is radically better or worse than the existing approaches. But it is different. NIST clearly felt that in this case, different is better.
  • Keccak doesn't blaze in software. In fact, Keccak/512 is estimated to be as much as half as fast in software as SHA-512. This fantastic table of tables sums up the results across all of the finalists. Needless to say they are highly processor dependent. I'm already seeing the first signs of pushback from security developers on mailing lists.
  • Keccak is quite speedy on hardware, something NIST cited in its decision. It also looks like it will be very GPU-friendly.
  • 'Attacks' on Keccak include a full distinguisher that applies to all 24 rounds of the hash function. But don't worry, the numbers in this attack are completely ridiculous, and this is in no way an actual attack.
  • Keccak includes relatively few non-linear bit operations per CPU instruction. The round function has algebraic degree 2, which facilitates some of the theoretical 'zero-sum' attacks on reduced-round Keccak (due to Aumasson and Meier).
  • No, it is not pronounced 'Ketchup', despite my best attempts to convince people of this. (Though there actually is a reduced-round variant called Keccup.)
My contribution to the SHA3 competition.
The full Keccak specification (including pseudocode and 'readable' C code) can be found here. A series of implementations exist for the SUPERCOP project. Unfortunately I know of no public or commercial implementations, at least not on major cryptographic libraries. I expect that to change quickly, and I also expect a whole bunch of further optimizations -- particularly on the GPU side.

It's not clear how the adoption of SHA3 will proceed. Right now there are no significant clouds on the horizon for the SHA2 series, and for the moment it seems like many people will continue to use those -- at least, those who aren't still using SHA1 or (god help us) MD5. I'm not sure what my recommendation is on switching, except that nobody's in a rush. If you absolutely must worry about long-term security, my recommendation is to consider using SHA2 and SHA3 in a secure composition. But I doubt anyone reading this blog needs to be that paranoid.

Even if you were rooting for another function, there is one major bright side to the selection of Keccak. Now that the SHA3 competition is behind us, cryptographers will have time to get back to the real task: putting holes in SHA1 and SHA2. I very much look forward to the results.

2 comments:

  1. From the attack paper, if I'm reading this correctly, they got the distinguisher attack down to 2^1579. If so, wow, so far, so good, hopefully time will keep it that way.

    ReplyDelete
  2. For any .net people out there, HashLib (http://hashlib.codeplex.com) contains all of the SHA-3 finalists including Keccak.

    ReplyDelete