Design and analysis of hash functions \ud

A function that compresses an arbitrarily large message into a fixed small size ‘message digest’ is known as a hash function. For the last two decades, many types of hash functions have been defined but, the most widely used in many of the cryptographic applications currently are hash functions based on block ciphers and the dedicated hash functions. Almost all the dedicated hash functions are generated using the Merkle-Damgård construction which is developed independently by Merkle and Damgård in 1989 [6, 7]. A hash function is said to be broken if an attacker is able to show that the design of the hash function violates at least one of its claimed security property. There are various types of attacking strategies found on hash functions, such as attacks based on the block ciphers, attacks depending on the algorithm, attacks independent of the algorithm, attacks based on signature schemes, and high level attacks. Besides this, in recent years, many structural weaknesses have been found in the Merkle-Damgård construction [51-54], which indirectly effects the hash functions developed based on this construction. MD5, SHA-0 and SHA-1 are currently the most widely deployed hash functions. However, they were all broken by Wang using a differential collision attack in 2004 [55-60], which increased the urgency of replacement for these widely used hash functions. Since then, many replacements and modifications have been proposed for the existing hash functions. The first alternative proposed is the replacement of the effected hash function with the SHA-2 group of hash functions. This thesis presents a survey on different types of the hash functions, different types of attacks on the hash functions and structural weaknesses of the hash functions. Besides that, a new type of classification based on the number of inputs to the hash function and based on the streamability and non-streamability of the design is presented. This classification consists of explanation of the working process of the already existing hash functions and their security analysis. Also, compression of the Merkle-Damgård construction with its related constructions is presented. Moreover, three major methods of strengthening hash functions so as to avoid the recent threats on hash functions are presented. The three methods dealt are: 1) Generating a collision resistant hash function using a new message preprocessing method called reverse interleaving. 2) Enhancement of hash functions such as MD-5 and SHA-1 using a different message expansion coding, and 3) Proposal of a new hash function called 3-branch. The first two methods can be considered as modifications and the third method can be seen as a replacement to the already existing hash functions which are effected by recent differential collision attacks. The security analysis of each proposal is also presented against the known generic attacks, along with some of the applications of the dedicated hash function. \u