CRYPTO: Day 4

On the last day of the conference I paid a visit to the friendly workshop next door – CHES (Cryptographic Hardware and Embedded Systems). It was all foreign to me – a different mix of people, posters outside the lecture hall. After this year’s CRYPTO compressed talks, 25 minutes felt like an eternity. Actual food during coffee breaks. Some things never change, though: Adi Shamir was sitting in the front row and asking pointed questions.

My main interest was in the invited talk by John Kelsey on SHA-3. A quick recap of the last few years in hash functions may be necessary here. On January 1, 2004 two hash functions were used in virtually all cryptographic applications – MD5 and SHA-1, both dating back to the 90s. The more recent SHA-2, which was substantially slower and more complex, was thought as somewhat of overkill. In less than two years MD5 was badly broken and SHA-1 seriously compromised in a series of papers by Chinese cryptanalysts led by Xiaoyun Wang. Although no attacks on SHA-2 had been announced, its structure was deemed uncomfortably close to those of the broken functions. To address these concerns, NIST launched a competition for the new hash function design to be eventually standardized as SHA-3. The competition ran from 2007 to 2012 and became the focal point of cryptanalytic community with a lot of interest and support from theoreticians.

The competition progressed through several rounds, and concluded in September 2012 with selection of Keccak. The winning design was proposed by a team of European cryptographers and based on innovative “sponge” construction. The hash function competition was explicitly modeled on the AES selection process that has given us the DES successor. Differences between the cipher standardized by NIST and the winner of the competition were basically editorial – the standard omitted some of the modes of the winning submission, and its name was changed from distinctly Dutch Rijndael to an abbreviation that only bureaucrats can love – AES.

The speaker today was John Kelsey of NIST, who introduces himself using the nine most terrifying words in English – “I’m from the government, and I’m here to help”. After going through the history of the SHA-3 competition and explaining some rationale behind the NIST decision (all last year news), he dropped a bombshell, announcing that the design chosen for standardization differs from the winning entry in a significant structural change. Although the change appears to be within parameters endorsed by the Keccak designers, it was not part of the “official” entry. NIST is considering narrowing the internal state of the hash function to improve its performance without seriously compromising its security (whether it is actually the case is open for debate).

More concretely, the call for submissions required the candidates to offer at least security against collision-finding attacks, and second-preimage resistance (with some allowance for long messages). Since the minimum output length is at least 224 bits, the second-preimage resistance appears to be excessive security margin. Narrowing the internal state has the effect of collapsing security of the hash function against many attacks to “just” . Whether this is a legitimate compromise (the construction becomes 30% faster) will be subject of lively discussions over the next few months.

With this, I conclude my series of posts from the CRYPTO 2013 conference. Let me know if you think it was an experiment worth repeating.