Analysis of modern cryptographic hash functions II

The strength of the security of electronic applications and systems relies on the security of the smallest building blocks. Cryptographic hash functions are one example of a ubiquitously deployed building block, with applications ranging from digital signatures, authentication protocols, random number generation and many more. Since the discovery of weaknesses in the most frequently used hash functions in 2005, an extensive amount of work has been invested in hash functions. The SHA-3 competition initiated by NIST in order to find the new standard in hash functions strongly motivates a growing need for fundamental and applied research to support the choice of the new worldwide hash standard. The proposed project wants to investigate in detail the security and foundations of modern hash functions. The first goal of the project is to analyze already established hash functions (e.g. the SHA-2 family, Whirlpool). An important point will be to further generalize the attack methods developed for SHA-1. The second target of the project is to extend the research to recently proposed hash functions within the SHA-3 competition. A third goal is to work towards foundations of hash functions security. It is of utmost importance to advance the state-of-the-art in hash function cryptanalysis and to attain a level of understanding that is comparable to the theory of block cipher cryptanalysis. The Krypto group at IAIK under the lead of Prof. Rijmen has established itself as one of the world`s most active institutions in hash function research. The contributions lie in the range of hash function cryptanalysis as well as hash function design and resulted in numerous publications in conference proceedings and journals. Furthermore, our staff is in charge of the working group on hash functions within the European Network of Excellence ECRYPT II.

Cryptographic hash functions are one security-critical building block for this digital economy. For example, when a document is signed by means of a digital signature (advanced electronic signature), a hash function is first used to compress the document resulting in a so-called fingerprint. For performance reasons, the raw signature using asymmetric techniques like RSA, DSA or ECDSA, is made on the fingerprint of the document only. For a digital signature scheme that uses a hash function for which collisions can be generated, forgeries can be generated from real signatures. For example, one could argue that with the current state of the art, it makes little sense to use the RSA signing primitive with key lengths of more than 2048 bits, since the security level of the hash functions used, is not as good anyway. In order to obtain the full picture on the security of digital signature applications, it is hence as important to do continuous evaluations of the security of cryptographic hash functions, as to stay up to date with the state of the art in e.g. factoring methods.Currently, almost all applications use as hash function RIPEMD-160, SHA-1, MD5 or SHA-2. Since the breakthrough results of Wang et al. hash functions have been the target in many cryptanalytic attacks. These attacks have especially shown that commonly used algorithms as MD5 and SHA-1 can no longer be considered as secure. For this reason, NIST has proposed the transition from SHA-1 to the SHA-2 family as a first solution. As a consequence, more and more companies and organizations are migrating to SHA-2. Furthermore, NIST has initiated an open competition for a new hash function standard, called SHA-3. Hence, there was a growing need for fundamental and applied research to support the choice of the new world wide hash standard and to evaluate the current standards.In this project, we have investigated the security of the SHA-2 family and several proposed alternatives. Furthermore, we contributed significantly to the international SHA-3 competition by providing analysis for several designs, including our own. Due to the increasing complexity in the design of hash functions, especially noticeable in the SHA-3 competition, the necessity of new and automated tools were apparent. We developed a new set of tools which is used to search automated for differential characteristics that hold with high probability. Our methods are based on recent developments in the cryptanalysis of hash functions. Besides the SHA-2 family, we also analyzed the security of many other hash functions against our methods. By linking the security of hash functions to more fundamental problems (coding theory and solving of nonlinear equations over finite fields), we were able to obtain better bounds on their security level. All our results significantly improved on previous ones and led to new insights in the analysis and design of cryptographic hash functions.