The Situation Of The Hash Function Structures And A New Design

The cryptographic hash function is a class of foundational cryptographic algorithms, and it is widely used in the modern communications, financial works, secure computing and many other fields. It can provide many secure properties such as message detection code MDC, message authentication code MAC, non-repudiation, digital signature, password authentication, and so on. It becomes the key technology in the protection of the security of the electronic signatures, identity authentications, and other cryptographic systems.There are two methods to construct a cryptographic hash function. One is using the sophisticated block ciphers to construct a hash function with the serial and parallel Davies-Meyer structures, such as MDC-2 and MDC-4 and so on. Such hash functions are based on the maturity of the block cipher algorithms, but their efficiency is very low. These functions is not able to meet the application requirements when they are used for the massive data. The security analysis of such hash functions mainly focuses on the structure analysis. The other method is the dedicated safe and efficient hash function. At Crypto 1989[7,19], Merkle and Damgard respectively presented a method by iterating a fixed input length of compression function to construct the hash function, and their purposes are that making the collision resistance of the hash function be equivalent to that of the compression function and so that the design of hash function can be focused on that of the fixed length compression function. Their designs are known as the MD structure. The most representative hash function is the MDx family functions. It includes MD4, MD5, HAVAL, SHA-0, SHA-1, SHA-2, RIPEMD-160[26,27,22,23,24.37] and so on. These hash functions use the design ideas of MD4 and add some new design concept to improve the security. Until 2004, MD5 and SHA-1 have been widely used as the two standard hash functions in the computer networks.The security analysis on the dedicated hash functions began in 1992. At Eurocrypt 1993[2], Boer and Bosselaers found a path of a pseudo collision on MD5. At Eurocrypt 1996[9], Dobbertin gave a collision attack on MD5 with the non-standard initial values. Dobbertin made an effective collision attack on MD4 at FSE 1996[10]. This was the first theoretical attack on the MDx hash functions and it was also an effective practical attack.In 1997, Professor Xiaoyun Wang first used a novel method named bit tracing to show how SHA-0 could be broken in theory[30]. In the next year, Wang improved this result in conjunction with the message modification technique[31]. In 1998, Chahaud and Joux[5] also published the theoretical analysis result of SHA-0 that used the ordinary differential analysis method. At Crypto 2004[32,34], Wang presented the collision attacks on MD4, MD5, HAVAL and RIPEMD. The bit tracing method was public at Eurocrypto 2005[33] and it laid the theoretical foundation for the breaking of most MDx family hash functions, including MD5 and SHA-1 [35]. This illustrated that the current usage of the MDx family hash functions was insecure.In this article, we review a variety of attacks on the hash function structures, especially the MD structure. In recent years, there are some new structures mainly include the Wide-Pipe construction[18], the HAIFA structure[1], the sponge function[3] etc.. In this paper, we discuss the new hash function structures and generally summarize their characteristics. On this basis, we present an improved version of the Double-Pipe construction, named the Enstrengthed Double Pipe (EDP).Due to the iterative nature, the earlier MD structure is vulnerable to the length extension attack and the second collision attack. Merkle improved the MD structure by padding the message with its length. The modified MD was called enhanced MD. However, if computing the underlying compression function collision is somehow feasible, the MD-based hash function may fail worse than expected. Since 2004, there are many recent advances in collision finding of the MD hash functions. At Crypto 2004[14], Joux presented the multicollisions attack on the MD hash functions. By this method, constructing multicollisions in iterated hash function can be done quite efficiently. More precisely, constructing 2t-collisions costs t times as much as building ordinary 2-collisions. The complexity of this method is t·2n/2. Kelsey and Schneier proposed a method for a second preimage attack against long messages at Eurocrypt 2005[16]. This method is achieved using both Dean's fixed point method[8] and Joux's multicollisions method[14] to construct an expandable message respectively. At Eurocrypt 2006[15], Kelsey and Kohno presented a chosen target preimage attack for relatively short messages. The total time complexity of the chosen target forced prefix preimage attack is much below the expected O(2n). In this attack, the attacker publishes in advance a digest value. Then, given a previously unknown message, the attacker finds a preimage to the digest value that contains the unknown message.The original hash function design is vulnerable to the length extension attack. If a hash function isn't the length extension resistance, the corresponding message authentication code is easy to be forged. Therefore, the length extension resistance security attribute is suggested by NIST to the SHA-3 standard hash algorithm competition.There are a number of new hash function structures in recent years, and these new structures are trying to avoid these attacks on the MD structures. At Asiacrypt 2005[18], the Wide-Pipe hash and the Double-Pipe hash were proposed by Lucks. These two constructions show that increasing the chaining values of the compression function improves the security against certain attacks, even if the compression function fails to be collision resistant. In 2005, Rivest presented a novel way of "dithering" the operation of an iterated hash function[28], based on the notion of square-free sequences and on their generalization to abelian square-free sequences, as a means of defeating some "message expansion"attacks. But when the labels repeat, this method fails to resist the second preimage attacks. In 2007, Biham and Dunkelman proposed the HAsh Iterative FrAmework[1] to solve many of the pitfalls of the MD construction. The main ideas behind HAIFA are the introduction of number of bits that were hashed so far and a salt value into the compression functions. The inclusion of the number of bits hashed so fare is suggested in order to prevent the easy exploitation of Dean's fixed point. The salt parameter is considered in order that using the off-line precomputation is unavailable, and increasing the security of digital signatures is avialable, as the signer chooses the salt value, and thus, any attack aiming at finding two messages with the same hash value has to take the salt into consideration. In 2007, Bertoni et al proposed a sponge function[3], and proved that the sponge construction is indifferentiable from a random oracle when being used with a random transformation or a random permutation the first time[4]. But in fact, most hash algorithms of the sponge structure use a simplified block cipher algorithm or a simple transformation so that they can not achieve the desired security claim.Finally, we learn the feature that the great internal states of Wide-Pipe construction can prevent an adversary from finding the internal collisions. We propose an improved version of the Double-Pipe construction, named the Enstrengthed Double Pipe (EDP). Our new construction is multicollisions resistant and (second) preimage resistant. The efficiency of this new construction is as the same as the Double-Pipe construction.