Grant: Discovery Grants Program - Individual

Cryptographic hash functions can be considered as the workhorse of cryptography and they are sprinkled all over security protocols. In spite of this, hash functions are arguably the least well-understood cryptographic primitives, and hashing techniques are much less developed than encryption techniques. Cryptanalysis during the early 2000s has shown that widely used hash functions offered only a very limited security margin. A completely new chapter in the history of analysis of Merkle-Damg¶rd (MD)-like designs was opened when Chinese cryptanalysts managed to enhance multi-block differential cryptanalysis to a point that finding collisions for MD5 became very easy and a substantial reduction of the security margin was obtained for SHA-1. Soon after the first collisions for MD5 have been found, it was shown how such collisions can be used to mislead integrity checking software and to produce documents with popular formats that collide under MD5. Furthermore, MD5 collisions were also used to create a rogue certification authority. In response to these dramatic cryptanalytic attacks, the National Institute for Standards and Technology (NIST) has decided to develop one or more additional hash functions. Consequently, in November 2007, the NIST has announced the launch of the SHA-3 competition to select a new hash function family. The objective of this research is to investigate the design and analysis of efficient families of provably secure hash functions. In particular, we aim to (i) Formalize both the design and the practice of cryptanalysis of hash functions by introducing more sound concepts from mathematics (ii) Produce a theory to quantify the resistance of iterated hash functions to a large set of cryptanalytic attacks, and (iii) Develop a new alternative to the current MD-like iterative structures which can be used to bring practical hash functions closer to the random oracle model. The cryptographic primitives that will be investigated in this project are the main focus of the cryptographic and security communities from both academia and industry. Consequently, the findings of this project are expected to be of high significance because of its impact on a very wide range of security products and applications.