CHES invited talk: The future of SHA-3

The second Thursday morning session comprised of a very illuminative invited talk by John Kelsey from NIST, on the SHA-3 selection and (anticipated) standardisation process.

Thanks to the widely-acknowledged success of the AES contest, open competitions have begun to play an increasingly important role in arriving at new, rigorously tested primitives. When -- at and after Crypto 2004 -- several new and powerful attack techniques against Merkle-Damgaard based constructions were introduced (Joux, Biham/Chen, Wang), confidence in existing hashes was substantially shaken. At the same time, NIST was pushing to move from 80-bit to 112-bit security, which required switching from SHA-1 to SHA-2. Even though SHA-2 was not (and still is not) known to be insecure, the ongoing flurry of cryptanalytic progress produced a sense of skepticism about the value of a costly transition to a new construction liable (it then seemed) to be broken at any minute.

What was needed was a new hash standard -- one sufficiently different to SHA-2 to offer useful performance/implementation trade-offs as well as to (hopefully) remain immune to any future attack against its predecessor.

Following vibrant discussion at hash workshops in Gaithersburg 2005 and UCSB 2006, the competition was announced in 2007 with an anticipated 5-year schedule. Response from the research community was admirable: 64 initial submissions (compared with 15 for AES). A first quick cut (excluding those not fitting the guidelines) brought it down to a list of 51, published in December 2008. The high number and huge diversity of designs made the selection rounds very difficult. But in another year or so many had been broken or seriously dented and a list of 14 was announced. It took another year and a half to reduce the list to 5, and then, in the words of Joyce…

"What clashes here of wills gen wonts, oystrygods gaggin fishy-gods! Brékkek Kékkek Kékkek Kékkek!" (Finnegans Wake, Ch 1) [1]

...another two years of rigorous cryptanalytic scrutiny and performance evaluation and Keccak was announced as the winner in October 2012.

Decisions were made based on security, performance, and how well the construction complemented SHA-2. None of the final candidates were knocked out by cryptanalysis, though some (domain extenders) have the benefit of security proofs, and Keccak and Blake have the best security margins. All 5 have acceptable performance, though Keccak performs particularly well in dedicated hardware. But a big point in Keccak's favour seems to have been its fundamental difference from SHA-2, rendering shared vulnerabilities unlikely and offering scope for flexible deployment.

In particular, Keccak is a sponge function, taking an input stream of any given length and producing an output stream of any desired length. Variable length output is needed by many protocols (OAEP, most KDFs, the fix for Bleichenbacher's DSA attack). Whilst it is desirable to have this as a part of a hash definition, Kelsey pointed out that it may be tricky to use it correctly (i.e., without introducing vulnerabilities) as different output lengths on the same input produce related hashes, for example:

SHAKE256(X,224) = ABCDEFG
SHAKE256(X,256) = ABCDEFGH

(SHAKE = SHA + Keccak).

The security of sponges relates to a parameter C called the capacity. Unlike Merkle-Damgaard constructions which aim at n/2-bit collision resistance and n-bit preimage resistance (where n is the number of output bits), collisions and preimages for a sponge function are equally hard to find. A good construction aims at a resistance of C/2 bits. The nice thing about this is that the security level is determined by function internals, not output size. But, of course, the larger C is, the slower the hashing.

Kelsey then spoke about the planned changes to Keccak in preparation for standardisation. The original proposal had four versions, each with different capacity (224, 256, 384, 512). They guaranteed n-bit preimage resistance by making capacity huge, but suffered a big performance hit to achieve this. In NIST's view, this trade-off produces higher claimed security than what is actually needed and therefore is not worth it. They therefore propose that SHA3 will have only 2 capacities:

1) SHA3-224, SHA3-256, SHAKE256: 128 bits of security against everything (C = 256)
2) SHA3-334 SHA3-512, SHAKE512: 256 bits of security against everything (C = 512)

Other anticipated changes to the original proposal include a different padding scheme.

The next step for NIST is to get the FIPS out. They plan to have a draft for public comment around the end of October 2013. Kelsey warned that the FIPS process can be slow, and is mostly outside of NIST control (the final document goes to Secretary of Commerce for approval) so NIST are unable to make guarantees about dates.

Eventually, they would also like to standardise other nice features of Keccak: a duplex mode for authenticated encryption, a dedicated PRF which can be used in place of HMAC, support for tree hashing (incorporating Keccak team's Sakura padding scheme where possible), and possibly (in the further future) random number generation using the duplex mode. They are also interested in analysis of Keccak with smaller permutation sizes, as this could be nice for constrained devices.

Throughout the talk, and in concluding, Kelsey was keen to emphasise how highly NIST value the input of the academic community and how open they are to further comment and critique -- with regard to both the planned modifications to the main functionality and to the avenues for further standardisation and applications of sponge functions and the Keccak duplex mode. In the question time concerns were raised by one delegate that the fairly dramatic capacity reductions proposed amount to standardising an untested cipher (thus somewhat defeating the point of the competition); another delegate put forward that such parameter changes do not invalidate the analysed security of the underlying algorithm. Clearly there is much yet to be discussed -- and NIST appear extremely keen to engage fully with this discussion. To this end there will be a NIST hash workshop co-located with next year's Crypto, at which they hope to hear research community insights on all things SHA-2 and SHA-3: Keccak with smaller permutations, cryptanalysis and differential/linear trail bounds, tree hashing, generic hash-based authenticated encryption, clever applications for sponges or duplex mode and so on. Plenty to work towards in the meantime!


[1] I concede that Joyce may not in fact have been referring to the SHA-3 competition. But it seems as good a guess as any...