Cryptanalysis Of The Hash Functions RIPEMD-128 And HMAC-MD4

We currently live in an information society. As information and communication technologies develop at an ever growing pace, the number of people who take these technologies as daily needs is also increasing. This development has brought substantial benefits but also introduced novel threats and vulnerabilities related to leakage of confidential information, the theft of identities and the unauthorized modification of data. These threats and vulnerabilities show the need for the development of a reliable and trustworthy information infrastructure. This requires trustworthy systems and an essential building block for such systems is the main topic of cryptography.Cryptography [1] is the study of mathematical techniques related to aspects of information security such as confidentiality, data integrity, entity authentication, and data origin authentication. It is a synthetical discipline and makes extensive use of mathematics such as number theory, probability, statistics and combinatorics as well as of information theory, computational complexity and coding theory. There exist various cryptographic algorithms that provide confidentiality, data integrity and entity authentication services.Hash Function plays a very important role in modern cryptography. It compresses an input of arbitrary length to a result with a fixed length, and we name the result of hash functions as hash value. Because of theirs definitions and properties, hash functions can be used to data integrity and be guarantee the security of many cryp-tosystems and protocols such as digital signature, message authentication code, etc. There are several advantages to using hash functions for digital schemes: breaking the mathematical structure of some digital schemes; improving the implement speed of digital schemes; ignoring the message corresponding to signature; separating the signature and encryption.Currently, the standard hash functions are consist of two families: MDx fam-ily(MD4 [11], MD5 [2], HAVAL [12], RIPEMD [13], RIPEMD-128 [6], RIPEMD-160 [6]) and SHA family( SHA-0 [14], SHA-1 [3], SHA-256, 384, 512 [15]). These hashing algorithms reveal the main deign methods and techniques of hash functions. MD4 is an early-appeared hash function which is designed using basic arithmetic and boolean operations in terms of the conception of " iterated " and Merkle-Damgard construction [30, 43]. After the publication of MD4, several hash functions have been designed, including MD5, HAVAL, RIPEMD, RIPEMD-128, RIPEMD-160, SHA-0 and SHA-1, etc., most of them are based on the design principles of MD4. RIPEMD was devised in the framework of the EU project RIPE [13]. RIPEMD-128 was proposed in 1996 by Hans Dobbertin, Antoon Bosselaers and Bart Preneel as a substitute for RIPEMD with a 128-bit result. RIPEMD-128 has two different and independent parallel lines that we named left line and right line respectively, the results of which are combined at the end of every application of the compression function. Each line has four rounds, and every round employs a round function which has different properties used in our attack.Generally speaking, hash functions have three security properties, including preim-age resistance, second-preimage resistance, collision resistance. So there are many different attacks on hash functions. In the past ten years, the cryptanalysis for hash functions has made much great progress. The most important generic attack on the collision resistance is the birthday attack, whose name comes from the so-called " birthday paradox ". It can be used to all kinds of hash functions and the complexity depends on the length of hash value. In 1996, H. Dobbertin [16] gave a collision attack on MD4 which finds a collision with probability 2^-22 . He also showed how to find collisions of meaningful messages. In 1998, H. Dobbertin [17] showed that the first two (out of the total three) rounds of MD4 is not one-way, and this means that there is an efficient attack for finding a preimage and a second-preimage. For RIPEMD, H. Dobbertin [18] gave an attack that finds a collision of RIPEMD reduced to two rounds with 2³¹ hash operations.Along with the development of the MDx-family of hash functions, there are security analysis on these functions. For example, B. den Boer and A. Bosselaers [19] found pseudo-collisions (same message with two different initial values) for MD5. In Eurocrypto ' 96, H. Dobbertin [20] presented a collisions of MD5, under another initial value. In Crypto ' 98. F. Chabaud and A. Joux [21] presented a differential attack on SHA-0 with probability 2^-61 . At Asiacrypt 2003. B.V. Rompay etc. [22] gave a collision attack on HAVAL-128 with probability 2^-29.Some powerful attacks on hash functions came out in 2004. Eli Biham and Rafi Chen [23] presented a near-collision attack on SHA-0. Then, A. Joux [25] presented a real collision of SHA-0 with four message blocks. Especially, in Crypto' 2004, Xi-aoyun Wang etc. [7, 8, 9, 10] announced real collisions of a series of hash functions including MD4, MD5, HAVAL-128 and RIPEMD, which can be found collisions on MD4 and RIPEMD with complexity less than 2⁸ MD4 operations and 2¹⁸ RIPEMD operations respectively. Simultaneously, Wang etc. also introduce a set of new analytical techniques that are applicable to all the hash functions in the MDx-family. More specifically, they show how to derive a set of the sufficient conditions on the chaining values to ensure the differential path to hold, and how to use message modification techniques to greatly improve the success probability of the attack. Subsequently, in 2005, Wang used these techniques to break MD5, SHA-0 and SHA-1. These techniques have proved to be very effective in cryptanalysis of dedicated hash functions. This attack also can be used to second-preimage attack on MD4 [26] and forgery and key recovery attack on HMAC and NMAC [28].Differential cryptanalysis [34] introduced by Biham and Shamir in 1990. is one of the most powerful chosen plaintext (or chosen ciphertext) attacks in symmetric- key cryptography (i.e., in block ciphers, stream ciphers, hash functions and MAC algorithms). The attack is a method which analyzes the effect of particular differences in plaintext pairs on the differences of the resultant ciphertext pairs. These differences can be used to assign probabilities to the possible keys and to locate the most probable key. Xiaoyun Wang uses the conception of differences that is different from the conventional differential analysis to attack MD4, RIPEMD, HAVAL, MD5, SHA-0, SHA-1[7, 8, 9, 10]. The differential definition in this attack is a kind of precise differential which uses the difference in term of integer modular subtraction, similarly as Dobbertin's method [16, 20, 18], also use modular characteristics, which describe for each round with both the differences in term of integer modular subtraction and the differences in term of XOR. The combination of both kinds of differences give attackers more information to find collisions.In this thesis, we detailedly introduce hash functions, including general definitions, properties, design principles, applications and several attacks on hash functions. The main contribution of this thesis include two parts. One is the study of collision attack on the last three rounds of RIPEMD-128 in Chapter 4. Another is the cryptanalysis for HMAC-MD4 in Chapter 5. The two parts use the techniques proposed by Xiaoyun Wang.In Chapter 4. we define integer modular substraction difference as:â–³X = X' - X for two parameters X and X'. In this attack, the difference is marked as a positive or a negative integer (modulo 2³²) and also with the XOR-difference. But then the XOR-difference is marked by the list of active bits with their relative sign, i.e., in the list of bits, the bits whose value in X is zero are marked without a sign, and the values whose value in X is 1 are marked with a negative sign. For example, the difference -2²³, [24, 25, 26, 27, 28, -29] marks the integer modular subtraction difference X'-X = -2²³, with many carries which start from bit 24 up to 29 bit . All bits of X from bit 24 to bit 28 are 0, and bit 29 is 1, while all bits of X' from bit 24 to bit 28 are 1, and bit 29 is 0. The XOR-difference has many difference due to carries.The attack includes three parts:Step 1 Select a collision differential for the last three rounds of RIPEMD-128Because RIPEMD-128 has two different and independent parallel line, it is difficult to choose differences that suffice to the differential path of two lines simultaneously. After analyzing the order of the message words and the properties of round functions seriously, and considering implementation of message modification, we select a difference between two messages for cur attack as follows, which is a two-bit difference.such thatThe output differences are:We can get the collision differential path of Left Line and Right Line, respectively. All the characteristics in the collision differential can be found in Table 4.1 and Table 4.2 in Chapter 4.Step 2. Deriving Conditions on Chaining ValueIn light of properties of round functions and differential characteristics, we derive sufficient conditions corresponding to Left line and Right line respectively which ensure the collision differential to hold. It is also an important process in our attack. If there are some conflicts among those conditions or can not satisfy differential characteristics, it shows that the differential path is error and we can not find a collision.We give two examples how to derive sufficient conditions as follows:1. The differential characteristic in step 19 in Left line is: (c₅[11, -12,13,32], d₅, a₅[31], b₄(-4,25,31]),For F₃{X, Y, Z) = (X∨(?)Y) (?) Z, according to Proposition 3-3(a) in Chapter 3. F₃(x,y,0) = 0 and F₃(x,y,1) = 1 if and only if x = 0 and y = 1, the conditions d_5,25 0,a_5,25= 1, and b_4,25= 0 result in F₃(d_5,25, a_5,25, b_4,25) = 0 and F₃(d_5,25,a_5,25 ,(?)b_4,25) = 1. Soâ–³f₁₉[25] = 2²⁴. Thenâ–³c₅[32] = ((â–³c₄[24] +â–³m₁₄ +â–³f₁₉[25]) mod 2³²) <<< 6 = ((2²³ + 2²³ + 2²⁴) mod 2³²) <<< 6 = 2³¹.2. The differential characteristic in step 18 in Right Line is:(a₅[5, -6], b₄[-5,16, -17, -24], c₄[-13, -26, -27, -28,29], d₄)→(d₅[13, 24, 25. -26, 31, -32], a₅[5, -6], b₄[-5,16, -17, -24], c₄[-13, -26, -27, -28, 29]),For F₂(X,Y,Z) = (X∧Y)∨((?)X∧Z) , according to Proposition 2-2(b), F₂(x,0,z) = 0 and F₂(x, 1,z) = 1 if and only if x = 1, the conditions a_5,17= 1 and b_4,17 = 1 result in F₂(a_5,17,b_4,17,c_4,17) = 1 and F₂(a_5,17,(?)b_4,17,c_4,17) = 0. Soâ–³d₅[24,25, -26] = -2²³. The conditions d_5,24= 0,d_5,25=0,d_5,26 = 1 ensure that d'₅=d₅[24,25,-26].Table 4.3 and 4.4 show how to derive a set of sufficient conditions using the approaches described above. At last, all sufficient conditions for two lines of the last three rounds of RIPEMD-128 are listed in Table 4.5 and 4.6.It is clear that the collision differential consists of two internal collisions respectively from 4-33 steps and 9-36 steps.Step 3. Message ModificationFor any random message M, we use single-step modification to decrease the conditions in the first round and use multi-step modification to decrease more conditions. These modifications must satisfy the differential path and can not produce contradictions. At last, we can derive the corresponding 19 and 36 conditions respectively, totaled 55 conditions.We can find a collision on the last three rounds of RIPEMD-128 with probability 2^-55, and it is lower than the birthday attack probability 2^-64. Because RIPEMD-128 has two different and independent parallel lines, and its round functions are different from others standards hash, functions, it is difficult to find efficient collision differential paths and sufficient conditions. The result of the attack in this thesis is the first cryptanalytic result for the last three rounds of RIPEMD-128 now.In Chapter 5. our cryptanalysis is based on the collision attack on MD4. Firstly, we show the differential path used in our attacks. Define two messages asThe difference between two messages isWe select the difference in our attack as follows:We can get a differential path in Table 5.1.Secondly, in light of the properties of round functions, we derive a set of sufficient conditions given in Table 5.2 that ensure differential characteristics to Isold. It is clear that we find a near collision with the probability 2^-54.Finally, we use the near collision for MD4 to attack the inner function of HMAC-MD4. Our attack is applied to distinguishing attack and partial key recovery attack on the inner function of HMAC-MD4. We can mount a distinguishing attack on the inner function of HMAC-MD4 that requires 2⁵⁴ message pairs and works with the probability of 0.63. From Table 5.2, (d₄[-7] , a₄, b₃[-28. -29., -30, -31. 32]. c₃) result in 22 conditions. This means we can recover the inner key that know 22-bit key and the others 106-bit with brute force attack.