Theory and practice for hash functions

This week many members of the group have been in Cambridge for the Newton Institute workshop titled 'Is Cryptographic Theory Practically Relevant?' The workshop was my first encounter with the wider cryptographic community and I thoroughly enjoyed the talks and the atmosphere during my time at the Newton Institute. I particularly enjoyed Bart Preneel's discussion of hash functions [video], with particular focus on the SHA-3 competition. Hash functions are crucial to many cryptographic applications, so naturally the competition is being closely followed by many in the cryptographic community, but it was noted that the amount of active researchers in the field is surprisingly low, particularly when compared to the AES competition.

There are many requirements of a good hash function, but there is still a discussion on exactly what properties the winning entry should satisfy. It is vital that the security definitions are formulated correctly and that they accurately reflect practical needs, particularly when the hash function is iterated. In 2004 Maurer et al. [pdf] introduced indifferentiability as a way of using random oracles as a proof method, however in 2011 Ristenpart et al. [pdf] showed that this is not always enough when composition is concerned, and in keeping with the theme of the workshop the the gap between the theory and the practical applications was in fact considerable.

In 2008 60 submissions were made to the SHA-3 competition, and the winner from the final 5 entrants will be picked at some point in 2012. There are many attacks on Merkle-Damgard constructions [pdf] [pdf], so designing a new construction method has been a major feature of the competition so far. Bart Preneel noted that his student Bart Mennink has made some considerable progress in understanding the various constructions including the sponge [details], and more work in this area will help the community provide more precise and effective security definitions and create tight security reductions from which meaningful conclusions can be drawn. The point was made that industry was advised to stop using MD5 in the mid-1990s but this advice was largely ignored until 2009. Many papers attacking SHA-1 have been withdrawn, and in the community it is not an acceptable suggestion that this surprising lack of progress is due to the strength of the hash function and in fact more work needs to be done. These points were very effectively portrayed with images of the Golden Gate bridge shrouded in varying levels of fog.

Work analysing the SHA-3 candidates was highlighted ([pdf] , [pdf] , [pdf] ) and the concluding remarks of the talk noted the open questions such as:

• Are standard model security proofs possible, and if so how will the new proof approaches help the rest of the cryptographic literature?
• Are improvements to the current indifferentiability bounds possible?