1512
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View 1512 as PDF for free.
More details
- Words: 8,906
- Pages: 17
How to Break MD5 and Other Hash Functions Xiaoyun Wang and Hongbo Yu Shandong University, Jinan 250100, China, [email protected], [email protected]
Abstract. MD5 is one of the most widely used cryptographic hash functions nowadays. It was designed in 1992 as an improvement of MD4, and its security was widely studied since then by several authors. The best known result so far was a semi free-start collision, in which the initial value of the hash function is replaced by a non-standard value, which is the result of the attack. In this paper we present a new powerful attack on MD5 which allows us to find collisions efficiently. We used this attack to find collisions of MD5 in about 15 minutes up to an hour computation time. The attack is a differential attack, which unlike most differential attacks, does not use the exclusive-or as a measure of difference, but instead uses modular integer subtraction as the measure. We call this kind of differential a modular differential. An application of this attack to MD4 can find a collision in less than a fraction of a second. This attack is also applicable to other hash functions, such as RIPEMD and HAVAL.
1
Introduction
People know that digital signatures are very important in information security. The security of digital signatures depends on the cryptographic strength of the underlying hash functions. Hash functions also have many other applications in cryptography such as data integrity, group signature, e-cash and many other cryptographic protocols. The use of hash functions in these applications not only ensure the security, but also greatly improve the efficiency. Nowadays, there are two widely used hash functions – MD5 [18] and SHA-1 [12]. MD5 is a hash function designed by Ron Rivest as a strengthened version of MD4 [17]. Since its publication, some weaknesses has been found. In 1993, B. den Boer and A. Bosselaers [3] found a kind of pseudo-collision for MD5 which consists of the same message with two different sets of initial values. This attack discloses the weak avalanche in the most significant bit for all the chaining variables in MD5. In the rump session of Eurocrypt’96, H. Dobbertin [8] presented a semi free-start collision which consists of two different 512-bit messages with a chosen initial value IV0 . a0 = 0x12ac2375, b0 = 0x3b341042, c0 = 0x5f62b97c, d0 = 0x4ba763ed A general description of this attack was published in [9]. Although H. Dobbertin cannot provide a real collision of MD5, his attack reveals the weak avalanche for the full MD5. This provides a possibility to find a special differential with one iteration.
In this paper we present a new powerful attack that can efficiently find a collision of MD5. From H. Dobbertin’s attack, we were motivated to study whether it is possible to find a pair of messages, each consists of two blocks, that produce collisions after the second block. More specifically, we want to find a pair (M0 , M1 ) and (M0 , M1 ) such that (a, b, c, d) = MD5(a0 , b0 , c0 , d0 , M0 ), (a , b , c , d ) = MD5(a0 , b0 , c0 , d0 , M0 ), MD5(a, b, c, d, M1 ) = MD5(a , b , c , d , M1 ), where a0 , b0 , c0 , d0 are the initial values for MD5. We show that such collisions of MD5 can be found efficiently, where finding the first blocks (M0 , M0 ) takes about 239 MD5 operations, and finding the second blocks (M1 , M1 ) takes about 232 MD5 operations. The application of this attack on IBM P690 takes about an hour to find M0 and M0 , where in the fastest cases it takes only 15 minutes. Then, it takes only between 15 seconds to 5 minutes to find the second blocks M1 and M1 . Two such collisions of MD5 were made public in the Crypto’04 rump session [19]. This attack is applicable to many other hash functions as well, including MD4, HAVAL-128 and RIPEMD ([17], [20], [15]). In the case of MD4, the attack can find a collision within less than a second, and can also find second pre-images for many messages. In Crypto’04 Eli Biham and Rafi Chen presented a near-collision attack on SHA-0 [2], which follows the lines of the technique of [4]. In the rump session they described their new (and improved) results on SHA-0 and SHA-1 (including a ˜ multi-block technique and collisions of reduced SHA-1). Then, A.Joux presented a 4-block full collision of SHA-0 [14], which is a further improvement of these results. Both these works were made independently of this paper. This paper is organized as follows: In Section 2 we briefly describe MD5. Then in Section 3 we give the main ideas of our attack, and in Section 4 we give a detailed description of the attack. Finally, in Section 5 we summarize the paper, and discuss the applicability of this attack to other hash functions.
2
Description of MD5
In order to conveniently describe the general structure of MD5, we first recall the iteration process for hash functions. Generally a hash function is iterated by a compression function X = f (Z) which compresses l-bit message block Z to s-bit hash value X where l > s. For MD5, l = 512, and s = 128. The iterating method is usually called the MerkleDamgard meta-method (see [6], [16]). For a padded message M with multiples of l-bit length, the iterating process is as follows: Hi+1 = f (Hi , Mi ), 0 ≤ i ≤ t − 1. Here M = (M0 , M2 , · · · , Mt−1 ), and H0 = IV0 is the initial value for the hash function.
In the above iterating process, we omit the padding method because it has no influence on our attack. The following is to describe the compression function for MD5. For each 512-bit block Mi of the padded message M , divide Mi into 32-bit words, Mi = (m0 , m1 , ...., m15 ). The compression algorithm for Mi has four rounds, and each round has 16 operations. Four successive step operations are as follows: a = b + ((a + φi (b, c, d) + wi + ti ) ≪ si ), d = a + ((d + φi+1 (a, b, c) + wi+1 + ti+1 ) ≪ si+1 ), c = d + ((c + φi+2 (d, a, b) + wi+2 + ti+2 ) ≪ si+2 ), b = c + ((b + φi+3 (c, d, a) + wi+3 + ti+3 ) ≪ si+3 ), where the operation + means ADD modulo 232 . ti+j and si+j (j = 0, 1, 2, 3) are step-dependent constants. wi+j is a message word. ≪ si+j is circularly leftshift by si+j bit positions. The details of the message order and shift positions can be seen in Table 3. Each round employs one nonlinear round function, which is given below. Φi (X, Y, Z) = (X ∧ Y ) ∨ (¬X ∧ Z), Φi (X, Y, Z) = (X ∧ Z) ∨ (Y ∧ ¬Z), Φi (X, Y, Z) = X ⊕ Y ⊕ Z, Φi (X, Y, Z) = Y ⊕ (X ∨ ¬Z),
0 ≤ i ≤ 15, 16 ≤ i ≤ 31, 32 ≤ i ≤ 47, 48 ≤ i ≤ 63,
where X, Y , Z are 32-bit words. The chaining variables are initialized as: a = 0x67452301, b = 0xefcdab89, c = 0x98badcfe, d = 0x10325476. We select a collision differential with two iterations as follows: Let Hi−1 = (aa, bb, cc, dd) be the chaining values for the previous message block. After four rounds, the compression value Hi is obtained by wordwise addition of the chaining variables to Hi−1 .
3
Differential Attack for Hash Functions
3.1
The Modular Differential and the XOR Differential
The most important analysis method for hash functions is differential attack which is also one of most important methods for analyzing block ciphers. In general, the differential attack especially in block ciphers is a kind of XOR differential attack which uses exclusive-or as the difference. The differential attack was introduced by E. Biham and A. Shamir to analyze the security of DES-like cryptosystems. E. Biham and A. Shamir [1], described that differential cryptanalysis is a method which analyzes the effect of particular differences in plain text pairs on the differences of the resultant cipher text pairs. The differential definition in this paper is a kind of precise differential which uses the difference in term of integer modular subtraction. A similar definition
about the differential with the integer subtraction as the measure of difference were described in [5] for differential analysis of RC6. We 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 us more information than each of them keep by itself. For example, when the modular integer subtraction difference is X − X = 26 for some value X, the XOR difference X ⊕ X can have many possibilities, which are 1. One-bit difference in bit 7, i.e., 0x00000040. In this case X − X = 26 which means that bit 7 in X is 1 and bit 7 in X is 0. 2. Two-bit difference, in which a different carry is transferred from bit 7 to bit 8, i.e., 0x000000C0. In this case X − X = 26 , but the carry to bit 8 is different in X and X , so X7 is now 0, and X7 = 1, while X8 = 1, and X8 = 0. (i.e., bits 7 and 8 together in X are 10 in binary, and in X there are 01 in binary). 3. Three-bit difference, in which a different carry is transferred from bit 7 to bit 8 and then to bit 9, i.e., 0x000001C0. In this case bits 7, 8, and 9 in X are 0, 0, and 1, respectively, and in X they are the complement of these values. 4. Similarly, there can be more carries to further bits, and the binary form of X is 1000. . . , and of X is 0111. . . . 5. In case the former difference is negative, the XOR differences still look the same, but the values of X and X are exchanged (i.e., X is of the form 1000. . . , and X of the form 0111. . . ). In order to explain our attack clearly, we refer to the modular differences in the differential path (see Table 3) with both kinds of differences together, i.e., the difference is marked as a positive or a negative integer (modulo 232 ) 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 −26 , [7, 8, 9, . . . , 22, −23] marks the integer modular subtraction difference X − X = −26 (with X < X), with many carries which start from bit 7 up to bit 23. All bits of X from bit 7 to bit 22 are 0, and bit 23 is 1, while all bits of X from bit 7 to bit 22 are 1, and bit 23 is 0. A more complicated example is −1 − 26 + 223 − 227 , [1, 2, 3, 4, 5, −6, 7, 8, 9, 10, 11, −12, −24, −25, −26, 27, 28, 29, 30, 31, −32], where the integer modular subtraction difference is composed of several (positive and negative) exponents of 2, and the XOR difference has many difference due to carries. Note that when the carry arrives to bit 32, a further (dropped) carry may happen, and then there is no negative sign in bit 32. It should be noted that the modular differential has been used earlier to analyze some hash functions ([4], [7], [10]). Compared with these attacks, our attack has the following advantages: 1. Our attack is to find collisions with two iterations, i. e., each message in the collision includes two message blocks (1024-bit).
2. Our attack is a precise differential attack in which the characteristics are more restrictive than used, and that they gives values of bits in addition to the differences. 3. Our attack gives a set of sufficient conditions which ensure the differential to occur. 4. Our attack use a message modification technique to greatly improve the collision probability. 3.2
Differential Attacks on Hash Functions
The difference for two parameters X and X is defined as ∆X = X − X. For any two messages M and M with l-bit multiples, M = (M0 , M1 , · · · , Mk−1 ), M = (M0 , M1 , · · · , Mk−1 ), a full differential for a hash function is defined as follows: ∆H0
(M0 ,M0 )
−→
∆H1
(M1 ,M1 )
−→
∆H2
(M2 ,M2 )
−→
· · · · · · ∆Hk−1
) (Mk−1 ,Mk−1
−→
∆H,
where ∆H0 is the initial value difference which equals to zero. ∆H is the output difference for the two messages. ∆Hi = ∆IVi is the output difference for the i-th iteration, and also is the initial difference for the next iteration. It is clear that if ∆H = 0, there is a collision for M and M . We call the differential that produces a collision a collision differential. Provided that the hash function has 4 rounds, and each round has 16 step operations. For more details, we can represent the i-th iteration differential ∆Hi
(Mi ,Mi )
−→ ∆Hi+1 as follows: P
P
P
P
1 2 3 4 ∆Hi −→ ∆Ri+1,1 −→ ∆Ri+1,2 −→ ∆Ri+1,3 −→ ∆Ri+1,4 = ∆Hi+1 .
The round differential ∆Rj−1 −→ ∆Rj (j = 1, 2, 3, 4) with the probability Pj is expanded to the following differential characteristics. Pj1
Pj2
Pj16
∆Rj−1 −→ ∆X1 −→ · · · · · · −→ ∆X16 = ∆Rj , Pjt
where ∆Xt−1 −→ ∆Xt , t = 1, 2, · · · · · · , 16 is the differential characteristic in the t-th step of j-th round. (Mi ,M )
The probability P of the differential ∆Hi −→ i ∆Hi+1 satisfies 4 16 P ≥ i=1 Pj and Pj ≥ t=1 Pjt . 3.3
Optimized Collision Differentials for Hash Functions
In Section 3.1, we mentioned that our attack uses a message modification technique to improve the collision probability. According to the modification technique, we can get a rough method to search for optimized differentials (including collision differentials) of a hash function. There are two kinds of message modifications:
1. For any two message blocks (Mi , Mi ) and a 1-st round non-zero differential ∆Hi
(Mi ,Mi )
−→ ∆Ri+1,1 .
Our attack can easily modify Mi to guarantee the 1-st round differential to hold with probability P1 = 1. 2. Using multi-message modification techniques, we can not only guarantee the first-round differential to hold with the probability 1, but also improve the second-round differential probability greatly. To find an optimized differential for a hash function, it is better to select a message block difference which results in a last two-round differential with a high probability.
4
Differential Attack on MD5
4.1
Notation
Before presenting our attack, we first introduce some notation to simplify the discussion. 1. M = (m0 , m1 , ..., m15 ) and M = (m0 , m1 , ..., m15 ) represent two 512-bit messages. ∆M = (∆m0 , ∆m1 , ..., ∆m15 ) denotes the difference of two message blocks. That is, ∆mi = mi − mi is the i − th word difference. 2. ai , di , ci , bi respectively denote the outputs of the (4i − 3)-th, (4i − 2)-th (4i − 1)-th and 4i-th steps for compressing M , where 1 ≤ i ≤ 16. ai , bi , ci , di are defined similarly. 3. ai,j , bi,j , ci,j , di,j represent respectively the j − th bit of ai , bi , ci , di , where the least significant bit is the 1-st bit, and the most significant bit is 32-th bit. 4. φi,j is the j-th bit of the output for the nonlinear function φi in the i-th step operation. 5. ∆xi,j = xi,j − xi,j = ±1 is the bit difference that is produced by changing the j-bit of xi . xi [j], xi [−j] (x can be a, b, c, d, φ) is the resulting values by only changing the j − th bit of the word xi . xi [j] is obtained by changing the j-th bit of xi from 0 to 1, and xi [−j] is obtained by changing the j-th bit of xi from 1 to 0. 6. ∆xi [j1 , j2 , ..., jl ] = xi [j1 , j2 , ..., jl ]−xi denotes the difference that is produced by the changes of j1 − th, j2 − th, ..., jl − th bits of xi . xi [±j1 , ±j2 , ..., ±jl ] is the value by change j1 − th, j2 − th, ..., jl − th bits of xi . The “+” sign (usually is omitted) means that the bit is changed from 0 to 1, and the “–” sign means that the bit is changed from 1 to 0. 4.2
Collision Differentials for MD5
Our attack can find many real collisions which are composed of two 1024-bit messages (M0 , M1 ) and (M0 , M1 ) ) with the original initial value IV0 of MD5: IV0 : a0 = 0x67452301, b0 = 0xefcdab89, c0 = 0x98badcfe, d0 = 0x10325476.
We select a collision differential with two iterations as follows: ∆H0
(M0 ,M0 )
−→
∆H1
(M1 ,M1 )
−→
∆H = 0
where ∆M0 = M0 − M0 = (0, 0, 0, 0, 231 , 0, 0, 0, 0, 0, 0, 215 , 0, 0, 231 , 0) ∆M1 = M1 − M1 = (0, 0, 0, 0, 231 , 0, 0, 0, 0, 0, 0, −215 , 0, 0, 231 , 0) ∆H1 = (231 , 231 + 225 , 231 + 225 , 231 + 225 ). Non-zero entries of ∆M0 and ∆M1 are located at positions 5, 12 and 15. ∆H1 = (∆a, ∆b, ∆c, ∆d) is the difference of the four chaining values (a, d, c, b) after the first iteration. We select ∆M0 to ensure that both 3-4 round differential happens with a high probability. ∆M1 is selected not only to ensure both 3-4 round differential happens with a high probability, but also to produce an output difference that can be cancelled with the output difference ∆H1 . The collision differential with all the characteristics can be referred to Table 3 and Table 5. The columns of both tables have the same meanings. We just give the explanation for Table 3. The first column denotes the step, the second column is the chaining variable in each step for M0 , the third is the message word for M0 in each step, the fourth is shift rotation, the fifth and the sixth are respectively the message word difference and chaining variable difference for M0 and M0 , and the seventh is the chaining variable for M0 . Especially, the empty items both in sixth and fifth columns denote zero differences, and steps those aren’t listed in the table have zero differences both for message words and chaining variables. 4.3
Sufficient Conditions for the Characteristics to Hold
In what follows, we describe how to derive a set of sufficient conditions that guarantee the differential characteristic in Step 8 of MD5 (Table 3) to hold. Other conditions can be derived similarly. The differential characteristic in Step 8 of MD5 is: (∆c2 , ∆d2 , ∆a2 , ∆b1 ) −→ ∆b2 . Each chaining variable satisfies one of the following equations. b1 = b1
a2 = a2 [7, ..., 22, −23] d2 = d2 [−7, 24, 32]
c2 = c2 [7, 8, 9, 10, 11, −12, −24, −25, −26, 27, 28, 29, 30, 31, 32, 1, 2, 3, 4, 5, −6] b2 = b2 [1, 16, −17, 18, 19, 20, −21, −24]
According to the operations in the 8-th step, we have b2 = c2 + ((b1 + F (c2 , d2 , a2 ) + m7 + t7 ) ≪ 22
b2 = c2 + ((b1 + F (c2 , d2 , a2 ) + m7 + t7 ) ≪ 22 φ7 = F (c2 , d2 , a2 ) = (c2 ∧ d2 ) ∨ (¬c2 ∧ a2 ) In the above operations, c2 occurs twice in the right hand side of the equation. NF denote In order to distinguish the two, let cF 2 denote the c2 inside F , and c2 the c2 outside F . The derivation is based on the following two facts: F 1. Since ∆b1 = 0 and ∆m7 = 0, we know that ∆b2 = ∆cN + (∆φ7 ≪ 22). 2 2. Fix one or two of the variables in F so that F is reduced to a single variable.
We get a set of sufficient conditions that ensure the differential characteristic holds. 1. The conditions for each of the non-zero bits in ∆b2 . (a) The conditions d2,11 = 1 and b2,1 = 0 ensure the change of 1-st bit of b2 . i. If d2,11 = a2,11 = 1, we know that ∆φ7,11 = 1. ii. After ≪ 22, ∆φ7,11 is in the position 1. F NF iii. Since ∆cN 2,1 = 0, so, ∆b2,1 = ∆c2,1 + ∆φ7,11 = 1. (b) The conditions d2,26 = a2,26 = 1, b2,16 = 0 and b2,17 = 1 ensure the changes of 16-th bit and 17-th bit of b2 . (c) The conditions d2,28 = a2,28 = 0, b2,i = 0, i = 18, 19, 20 and b2,21 = 1 ensure the changes of 18-th, 19-th, 20-th, 21-th bits of b2 . (d) The conditions d2,3 = a2,3 = 0 and b2,24 = 1 ensure the change of 24-th bit of b2 . This can be proven by the equation: F 23 ∆cN − 224 = −223 . 2 [−24, −25, −26, 27] + (∆φ7 [3] ≪ 22) = 2
2. The conditions for each of the zero bits in ∆b2 . (a) The condition c2,17 = 0 ensures the changed bits from 7-th bit to 12-th NF bit in c2 and 17-th bit of a2 result in no bit change in b2 . It is easily proven by the following equation: F 6 6 ∆cN 2 [7, . . . 11, −12] + (∆φ7 [17] ≪ 22) = −2 + 2 = 0.
(b) The conditions d2,i = a2,i ensure that the changed i-th bit in cF 2 result in no change in b2 , where i ∈ {1, 2, 4, 5, 25, 27, 29, 30, 31}. (c) The conditions c2,i = 1 ensure that the changed i-th bit in a2 result in no change in b2 , where i ∈ {13, 14, 15, 16, 18, 19, 20, 21, 22, 23}. (d) The condition d2,6 = a2,6 = 0 ensures that the 6-th bit in cF 2 result in no change in b2 . (e) The condition a2,32 = 1 ensures that the changed 32-th bit in cF 2 and the 32-th bit in d2 result in no change in b2 . (f) The condition d2,i = 0 ensures that the changed i-th bit in a2 and the i-th bit in cF 2 result in no change in b2 , where i ∈ {8, 9, 10}. (g) The condition d2,12 = 1 ensures that the changed 12-th bit in a2 and the 12-th bit in cF 2 result in no change in b2 .
(h) The condition a2,24 = 0 ensures that the changed 24-th bit in cF 2 and the 24-th bit in d2 result in no change in b2 . (i) The changed 7-th bits in cF 2 , d2 and a2 result in no change in b2 . By the similar method, we can derive a set of sufficient conditions (see Table 4 and Table 6) which guarantee all the differential characteristics in the collision differential to hold. 4.4
Message Modification
Single-message Modification In order to make the attack efficient, it is very attractive to improve over the probabilistic method that we describe, by fixing some of the message words to a prior fulfilling some of the conditions. We observe that it is very easy to generate messages that fulfill all the conditions of the first 16 steps of MD5. We call it single-message modification. For each message block M0 (or similarly M1 ) and intermediate values (H0 , or for the second block H1 and H1 ), we apply the following procedures to modify M0 (or M1 , respectively), so that all the conditions of round 1 (the first 16 steps) in Table 4 and Table 6 hold. It is easy to modify M0 such that the conditions of round 1 in Table 4 hold with probability 1. For example, to ensure that 3 conditions for c1 in Table 4 hold, we modify m2 as follows: old 6 old 11 19 ← cold − cold cnew 1 1 − c1,7 · 2 − c1,12 · 2 1,20 · 2 old mnew ← ((cnew − cold 2 1 1 ) ≫ 17) + m2 .
By modifying each message word of message M0 , all the conditions in round 1 of Table 4 hold. The first iteration differential hold with probability 2−43 . The same modification is applied to M1 . After modification, the second iteration differential hold with probability 2−37 . Multi-message Modification We further observe that it is even possible to fulfill a part of the conditions of the first 32 steps by an multi-message modification. For example, if a5,32 = 1, we correct it into a5,32 = 0 by modifying m1 , m2 ,m3 , m4 ,m5 such that the modification generates a partial collision from 2-6 steps, and remains that all the conditions in round 1 hold. See Table 1. Some other conditions can be corrected by the similar modification technique or other more precise modification techniques. By our modification, 37 conditions in round 2-4 are undetermined in the table 4, and 30 conditions in round 2-4 are undetermined in the table 6. So, the 1-st iteration differential holds with probability 2−37 , and the second iteration differential holds with probability 2−30 .
Table 1. The Message Modification for Correcting a5,32
2 3 4 5 6
m1 m2 m3 m4 m5
4.5
Modify mi anew , bnew , cnew , dnew 12 m1 ←− m1 + 226 dnew , a1 , b0 , c0 1 new new 17 m2 ←− ((c1 − d1 ) ≫ 17) − c0 − φ2 (d1 , a1 , b0 ) − t2 c1 , dnew , a1 , b0 1 22 m3 ←− (b1 − c1 ) ≫ 22) − b0 − φ3 (c1 , dnew , a1 ) − t3 b1 , c1 , dnew , a1 1 1 7 m4 ←− ((a2 − b1 ) ≫ 7) − a1 − φ4 (b1 , c1 , dnew − t4 a2 , b1 , c1 , dnew 1 1 12 m5 ←− ((d2 − a2 ) ≫ 12) − dnew − φ5 (a2 , b1 , c1 ) − t5 d2 , a2 , b1 , c1 1
The Differential Attack on MD5
From the above description, it is very easy to show our attack on MD5. The following is to describe how to find a two-block collision, of the following form H0
(M0 ,M0 ),2−37
−→
∆H1
(M1 ,M1 ),2−30
−→
∆H = 0.
1. Repeat the following steps until a first block is found (a) Select a random message M0 . (b) Modify M0 by the message modification techniques described in the previous subsection. (c) Then, M0 and M0 = M0 + ∆M0 produce the first iteration differential ∆M0 −→ (∆H1 , ∆M1 ) with the probability 2−37 . (d) Test if all the characteristics really hold by applying the compression function on M0 and M0 . 2. Repeat the following steps until a collision is found (a) Select a random message M1 . (b) Modify M1 by the message modification techniques described in the previous subsection. (c) Then, M1 and M1 + ∆M1 generate the second iteration differential (∆H1 , ∆M1 ) −→ ∆H = 0 with the probability 2−30 . (d) Test if this pair of messages lead to a collision. The complexity of finding (M0 , M0 ) doesn’t exceed the time of running 239 MD5 operations. To select another message M0 is only to change the last two words from the previous selected message M0 . So, finding (M0 , M0 ) only needs about one-time single-message modification for the first 14 words. This time can be neglected. For each selected message M0 , it is only needs two-time single-message modifications for the last two words and 7-time multi-message modifications for correcting 7 conditions in the second round, and each multi-message modification
only needs about a few step operations, so the total time for both kinds of modifications is not exceeds about two MD5 operations for each selected message. According to the probability of the first iteration differential, it is easy to know that the complexity of finding (M0 , M0 ) is not exceeds 239 MD5 operations. Similarly, we can show that the complexity of finding (M1 , M1 ) is not exceeds 32 2 MD5 operations. Two collisions of MD5 are given in Table 2. It is noted that the two collisions Table 2. Two pairs of collision for MD5. H is the hash value with little-endian and no message padding, and H ∗ is the hash value with big-endian and message padding. M0 M1 M0 M1 H H∗ M0 M1 M0 M1 H H∗
2dd31d1 634ad55 d11d0b96 797f2775 2dd31d1 634ad55 d11d0b96 797f2775 9603161f a4c0d35c 2dd31d1 634ad55 313e82d8 42339fe9 2dd31d1 634ad55 313e82d8 42339fe9 8d5e7019 79054025
c4eee6c5 2b3f409 9c7b41dc eb5cd530 c4eee6c5 2b3f409 9c7b41dc eb5cd530 a30f9dbf 95a63a80 c4eee6c5 2b3f409 5b8f3456 e87e570f c4eee6c5 2b3f409 5b8f3456 e87e570f 61804e08 255fb1a2
69a3d69 8388e483 f497d8e4 baade822 69a3d69 8388e483 f497d8e4 baade822 9f65ffbc 5915367d 69a3d69 8388e483 d4ac6dae 70b654ce 69a3d69 8388e483 d4ac6dae 70b654ce 715d6b58 6e4bc422
5cf9af98 5a417125 d555655a 5c15cc79 5cf9af98 5a41f125 d555655a 5c154c79 f41fc7ef cfe6b751 5cf9af98 5a417125 c619c936 1e0da880 5cf9af98 5a41f125 c619c936 1e0d2880 6324c015 aef54eb4
87b5ca2f e8255108 c79a7335 ddcb74ed 7b5ca2f e8255108 479a7335 ddcb74ed
ab7e4612 9fc9cdf7 cfdebf0 6dd3c55f ab7e4612 9fc9cdf7 cfdebf0 6dd3c55f
3e580440 f2bd1dd9 66f12930 d80a9bb1 3e580440 72bd1dd9 66f12930 580a9bb1
897ffbb8 5b3c3780 8fb109d1 e3a7cc35 897ffbb8 5b3c3780 8fb109d1 e3a7cc35
87b5ca2f e8255108 b4e253dd bc2198c6 7b5ca2f e8255108 34e253dd bc2198c6
ab7e4612 9fc9cdf7 fd03da87 9383a8b6 ab7e4612 9fc9cdf7 fd03da87 9383a8b6
3e580440 f2bd1dd9 6633902 2b65f996 3e580440 72bd1dd9 6633902 ab65f996
897ffbb8 5b3c3780 a0cd48d2 702af76f 897ffbb8 5b3c3780 a0cd48d2 702af76f
start with the same 1-st 512-bit block, and that given a first block that satisfies all the required criteria, it is easy to find many second blocks M1 , M1 which lead to collisions.
5
Summary
In this paper we described a powerful attack against hash functions, and in particular showed that finding a collision of MD5 is easily feasible. Our attack is also able to break efficiently other hash functions, such as HAVAL-128, MD4, RIPEMD, and SHA-0. The analysis results for these hash functions are as follows:
1. The time complexity for finding a collision for MD4 is about 223 MD4 operations without the multi-message modification, and is about 28 MD4 operations with the multi-message modification. 2. The time complexity for finding a collision for HAVAL-128 is about 213 MD4 operations without the multi-message modification, and is 27 HAVAL-128 operations with the multi-message modification. 3. The time complexity for finding a collision for RIPEMD is about 230 RIPEMD operations without the multi-message modification, and is 218 RIPEMD operations with the multi-message modification. 4. The time complexity for finding a collision for SHA-0 is about 261 SHA-0 operations without the multi-message modification, and is 245 SHA-0 operations with the multi-message modification.
Acknowledgements It is a pleasure to acknowledge Dengguo Feng for the conversations that led to this research on MD5. We would like to thank Eli Biham, Andrew C. Yao, and Yiqun Lisa Yin for their important advice, corrections, and suggestions, and for spending their precious time on our research. We would also like to thank Xuejia Lai, Hans Dobbertin, Magnus Daum for various discussions on this paper. The research is supported by the National Natural Science Foundation of China (Grant No. 90304009).
References 1. E. Biham, A. Shamir. Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1993. 2. E. Biham, R. Chen, Near collision for SHA-0, Advances in Cryptology, Crypto’04, 2004, LNCS 3152, pp. 290-305. 3. B. den. Boer, A. Bosselaers. Collisions for the compression function of MD5, Advances in Cryptology, Eurocrypt’93 Proceedings, Springer-Verlag, 1994. 4. F. Chabaud, A. Joux. Differential collisions in SHA-0, Advances in Cryptology, Crypto’98 Proceedings, Springer-Verlag, 1998. 5. S. Cotini, R.L. Rivest, M.J.B. Robshaw, Y. Lisa Yin. Security of the RC6T M Block Cipher, http://www.rsasecurity.com/rsalabs/rc6/. 6. I. B. Damgard. A design principle for hash functions, Advances in Cryptology, Crypto’89 Proceedings, Springer-Verlag, 1990. 7. H. Dobbertin. Cryptanalysis of MD4, Fast Software Encryption, LNCS 1039, Springer-Verlag, 1996, 53-69. 8. H. Dobbertin. Cryptanalysis of MD5 compress, presented at the rump session of Eurocrypt’96. 9. H. Dobbertin. The status of MD5 after a recent attack, CryptoBytes 2 (2), 1996, ftp://ftp.rsasecurity.com/pub/cryptobytes/crypto2n2.pdf. 10. H. Dobbertin. RIPEMD with two round compress function is not collision-free, Journal of Cryptology, 10:51-69, 1997. 11. H. Dobbertin, A. Bosselaers, B. Preneel. RIPEMD-160: A strengthened version of RIPEMD, Fast Software Encryption, LNCS 1039, Springer-Verlag, 1996.
12. FIPS 180-1. Secure hash standard, NIST, US Department of Commerce, Washington D.C., Springer-Verlag, 1996. 13. FIPS 180-2. Secure Hash Standard, http://csrc.nist.gov/publications/, 2002. 14. A. Joux. Collisions for SHA-0, rump session of Crypto’04, 2004. 15. RIPE. Integrity Primitives for Secure Information Systems. Final Report of RACE Integrity Primitives Evaluation (RIPE-RACE 1040), LNCS 1007, Springer-Verlag, 1995. 16. R.C. Merkle. One way hash function and DES, Advances in Cryptology, Crypto’89 Proceedings, Springer-Verlag, 1990. 17. R.L. Rivest. The MD4 message digest algorithm, Advances in Cryptology, Crypto’90, Springer-Verlag, 1991, 303-311. 18. R.L. Rivest. The MD5 message-digest algorithm, Request for Comments (RFC 1320), Internet Activities Board, Internet Privacy Task Force, 1992. 19. X.Y. Wang, F.D. Guo, X.J. Lai, H.B. Yu, Collisions for hash functions MD4, MD5, HAVAL-128 and RIPEMD, rump session of Crypto’04, E-print, 2004. 20. Y.L. Zheng, J. Pieprzyk, J. Seberry. HAVAL–A one-way hashing algorithm with variable length of output, Advances in Cryptology, Auscrypt’92 Proceedings, Springer-Verlag.
Table 3. The Differential Characteristics in the First Iteration Differential Step
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ... 34 35 36 37 38 39 ... 45 46 47 48 49 50 51 52 ... 58 59 60 61 62 63 64
The output in i-th step for M0 b1 a2 d2 c2
aa0 dd0 cc0 bb0
b2 a3 d3 c3 b3 a4 d4 c4 b4 a5 d5 c5 b5 a6 d6 c6 b6 a7 d7 c7 ... d9 c9 b9 a10 d10 c10 ... a12 d12 c12 b12 a13 d13 c13 b13 ... d15 c15 b15 = a16 + a0 = d16 + d0 = c16 + c0 = b16 + b0
wi si ∆wi The output difference The output in i-th step for M0 in i-th step m3 m4 m5 m6
22 7 231 −26 12 −26 + 223 + 231 17 −1 − 26 + 223 − 227
m7 m8 m9 m10 m11 m12 m13 m14 m15 m1 m6 m11 m0 m5 m10 m15 m4 m9 m14 m3 ... m8 m11 m14 m1 m4 m7 ... m9 m12 m15 m2 m0 m7 m14 m5 ... m15 m6 m13 m4 m11 m2 m9
22 7 12 17 22 7 12 17 22 5 9 14 20 5 9 14 20 5 9 14 ... 11 16 23 4 11 16 ... 4 11 16 23 6 10 15 21 ... 10 15 21 6 10 15 21
215
231
215
1 − 215 − 217 − 223 1 − 26 + 231 212 + 231 230 + 231 −27 − 213 + 231 224 + 231 231 23 − 215 + 231 −229 + 231 231 231 217 + 231 231 231 231
231 231 ... ... 215 231 231 231 231 31 2 231 231 ... ... 231 231 231 231 231 231 231 231 231 ... ... 231 231 231 31 2 231 215 231 231 231
a2 [7, . . . , 22, −23] d2 [−7, 24, 32] c2 [7, 8, 9, 10, 11, −12, −24, −25, −26, 27, 28, 29, 30, 31, 32, 1, 2, 3, 4, 5, −6] b2 [1, 16, −17, 18, 19, 20, −21, −24], a3 [−1, 2, 7, 8, −9, −32] d3 [−13, 14, 32] c3 [31, 32] b3 [8, −9, 14, . . . , 19, −20, 32] a4 [−25, 26, 32] d4 [32] c4 [4, −16, 32] b4 [−30, 32] a5 [32] d5 [32] c5 [18, 32] b5 [32] a6 [32] d6 [32] c6 b6 a7 d7 c7 ... d9 c9 [∗32] b9 [∗32] a10 [∗32] d10 [∗32] c10 [∗32] ... a12 [∗32] d12 [32] c12 [32] b12 [32] a13 [32] d13 [−32] c13 [32] b13 [−32] ... d15 [−32] c15 [32] b15 [32] aa0 = aa0 [32] dd0 = dd0 [26, 32] cc0 = cc0 [−26, 27, 32] bb0 = bb0 [26, −32]
Table 4. A Set of Sufficient Conditions for the First Iteration Differential c1 b1
a2
d2
c2
b2
a3
d3 c3 b3 a4 d4 c4 b4 a5 d5 c5 b5 a6 − b 6 c9 , b12 a13 − b13 a14 − b14 a15 d15 c15 b15 aa0 = a16 + a0 dd0 = d16 + d0 cc0 = c16 + c0 bb0 = b16 + b0
c1,7 = 0, c1,12 = 0, c1,20 = 0 b1,7 = 0, b1,8 = c1,8 , b1,9 = c1,9 , b1,10 = c1,10 , b1,11 = c1,11 , b1,12 = 1, b1,13 = c1,13 , b1,14 = c1,14 , b1,15 = c1,15 , b1,16 = c1,16 , b1,17 = c1,17 , b1,18 = c1,18 ,b1,19 = c1,19 , b1,20 = 1, b1,21 = c1,21 , b1,22 = c1,22 , b1,23 = c1,23 , b1,24 = 0, b1,32 = 1 a2,1 = 1, a2,3 = 1, a2,6 = 1, a2,7 = 0, a2,8 = 0, a2,9 = 0, a2,10 = 0, a2,11 = 0, a2,12 = 0, a2,13 = 0, a2,14 = 0, a2,15 = 0, a2,16 = 0, a2,17 = 0, a2,18 = 0, a2,19 = 0, a2,20 = 0, a2,21 = 0, a2,22 = 0, a2,23 = 1, a2,24 = 0, a2,26 = 0, a2,28 = 1, a2,32 = 1 d2,1 = 1, d2,2 = a2,2 , d2,3 = 0, d2,4 = a2,4 , d2,5 = a2,5 , d2,6 = 0, d2,7 = 1, d2,8 = 0, d2,9 = 0, d2,10 = 0, d2,11 = 1, d2,12 = 1, d2,13 = 1, d2,14 = 1, d2,15 = 0, d2,16 = 1, d2,17 = 1, d2,18 = 1, d2,19 = 1, d2,20 = 1, d2,21 = 1, d2,22 = 1, d2,23 = 1, d2,24 = 0, d2,25 = a2,25 , d2,26 = 1, d2,27 = a2,27 , d2,28 = 0, d2,29 = a2,29 , d2,30 = a2,30 , d2,31 = a2,31 , d2,32 = 0 c2,1 = 0, c2,2 = 0, c2,3 = 0, c2,4 = 0, c2,5 = 0, c2,6 = 1, c2,7 = 0, c2,8 = 0, c2,9 = 0, c2,10 = 0, c2,11 = 0, c2,12 = 1, c2,13 = 1, c2,14 = 1, c2,15 = 1, c2,16 = 1, c2,17 = 0, c2,18 = 1, c2,19 = 1, c2,20 = 1, c2,21 = 1, c2,22 = 1, c2,23 = 1, c2,24 = 1, c2,25 = 1, c2,26 = 1, c2,27 = 0, c2,28 = 0, c2,29 = 0, c2,30 = 0, c2,31 = 0, c2,32 = 0 b2,1 = 0, b2,2 = 0, b2,3 = 0, b2,4 = 0, b2,5 = 0, b2,6 = 0, b2,7 = 1, b2,8 = 0, b2,9 = 1, b2,10 = 0, b2,11 = 1, b2,12 = 0, b2,14 = 0, b2,16 = 0, b2,17 = 1, b2,18 = 0, b2,19 = 0, b2,20 = 0, b2,21 = 1, b2,24 = 1, b2,25 = 1, b2,26 = 0, b2,27 = 0, b2,28 = 0, b2,29 = 0, b2,30 = 0, b2,31 = 0, b2,32 = 0 a3,1 = 1, a3,2 = 0, a3,3 = 1, a3,4 = 1, a3,5 = 1, a3,6 = 1, a3,7 = 0, a3,8 = 0, a3,9 = 1, a3,10 = 1, a3,11 = 1, a3,12 = 1, a3,13 = b2,13 , a3,14 = 1, a3,16 = 0, a3,17 = 0, a3,18 = 0, a3,19 = 0, a3,20 = 0, a3,21 = 1, a3,25 = 1, a3,26 = 1, a3,27 = 0, a3,28 = 1, a3,29 = 1, a3,30 = 1, a3,31 = 1, a3,32 = 1 d3,1 = 0, d3,2 = 0, d3,7 = 1, d3,8 = 0, d3,9 = 0, d3,13 = 1, d3,14 = 0, d3,16 = 1, d3,17 = 1, d3,18 = 1, d3,19 = 1, d3,20 = 1, d3,21 = 1, d3,24 = 0, d3,31 = 1, d3,32 = 0 c3,1 = 0, c3,2 = 1, c3,7 = 1, c3,8 = 1, c3,9 = 0, c3,13 = 0, c3,14 = 0, c3,15 = d3,15 , c3,17 = 1, c3,18 = 0, c3,19 = 0, c3,20 = 0, c3,16 = 1, c3,31 = 0, c3,32 = 0 b3,8 = 0, b3,9 = 1, b3,13 = 1, b3,14 = 0, b3,15 = 0, b3,16 = 0, b3,17 = 0, b3,18 = 0, b3,20 = 1, b3,25 = c3,25 , b3,26 = c3,26 , b3,19 = 0, b3,31 = 0, b3,32 = 0 a4,4 = 1, a4,8 = 0, a4,9 = 0, a4,14 = 1, a4,15 = 1, a4,16 = 1, a4,17 = 1, a4,18 = 1, a4,20 = 1, a4,25 = 1, a4,26 = 0, a4,31 = 1, a4,19 = 1, a4,32 = 0 d4,4 = 1, d4,8 = 1, d4,9 = 1, d4,14 = 1, d4,15 = 1, d4,16 = 1, d4,17 = 1, d4,18 = 1, d4,19 = 0, d4,20 = 1, d4,25 = 0, d4,26 = 0, d4,30 = 0, d4,32 = 0 c4,4 = 0, c4,16 = 1, c4,25 = 1, c4,26 = 0, c4,30 = 1, c4,32 = 0 b4,30 = 1, b4,32 = 0 a5,4 = b4,4 , a5,16 = b4,16 , a5,18 = 0, a5,32 = 0 d5,18 = 1, d5,30 = a5,30 , d5,32 = 0 c5,18 = 0, c5,32 = 0 b5,32 = 0 a6,18 = b5,18 , a6,32 = 0, d6,32 = 0, c6,32 = 0, b6,32 = c6,32 + 1 φ34,32 = 0, b12,32 = d12,32 a13,32 = c12,32 , d13,32 = b12,32 + 1, c13,32 = a13,32 , b13,32 = d13,32 a14,32 = c13,32 , d14,32 = b13,32 , c14,32 = a14,32 , b14,32 = d14,32 a15,32 = c14,32 d15,32 = b14,32 c15,32 = a15,32 b15,26 = 0, b15,32 = d15,32 + 1 a16,26 = 1, a16,27 = 0, a16,32 = c15,32 dd0,26 = 0, d16,32 = b15,32 cc0,26 = 1, cc0,27 = 0, cc0,32 = dd0,32 , c16,32 = d16,32 bb0,26 = 0, bb0,27 = 0, bb0,6 = 0, bb0,32 = cc0,32
Table 5. All the Differential Characteristics in the Second Iteration Differential Step The output in i-th step for M1 IV aa0 , dd0 cc0 , bb0 1 a1 2 d1 3 c1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ... 34 35 36 37 38 39 ... 49 50 51 52 ... 59 60 61 62 63 64
b1 a2 d2 c2 b2 a3 d3 c3 b3 a4 d4 c4 b4 a5 d5 c5 b5 a6 d6 c6 b6 a7 d7 c7 ... d9 c9 b9 a10 d10 c10 ... a13 d13 c13 b13 ... c15 b15 a16 + aa0 d16 + dd0 c16 + cc0 b16 + bb0
wi si ∆wi The output Difference The output in i-th step for M1 in i-th step
m0 7 m1 12 m2 17 m3 m4 m5 m6 m7 m8 m9 m10 m11 m12 m13 m14 m15 m1 m6 m11 m0 m5 m10 m15 m4 m9 m14 m3 ... m8 m11 m14 m1 m4 m7 ... m0 m7 m14 m5 ... m6 m13 m4 m11 m2 m9
22 7 12 17 22 7 12 17 22 7 12 17 22 5 9 14 20 5 9 14 20 5 9 14 ... 11 16 23 4 11 16 ... 6 10 15 21 ... 15 21 6 10 15 21
231
−215 231
−215
225 + 231 25 + 225 + 231 25 + 211 + 216 +225 + 231 −2 + 25 + 225 + 231 1 + 26 + 28 + 29 + 231 −216 − 220 + 231 −26 − 227 + 231 215 − 217 − 223 + 231 1 + 26 + 231 212 + 231 231 −27 − 213 + 231 224 + 231 231 23 + 215 + 231 −229 + 231 231 231 217 + 231 231 231 231
231 231 ... ... −215 231 231 231 231 31 2 231 231 ... ... 231 231 31 2 231 231 ... ... 231 231 231 −215
aa0 [32], dd0 [26, 32] cc0 [−26, 27, 32], bb0 [26, −32] a1 [26, −32] d1 [6, 26, −32] c1 [−6, −7, 8, −12, 13, -17,. . . ,-21,22,-26,. . . ,-30,31,-32] b1 [2, 3, 4, −5, 6, −26, 27, −32] a2 [1, −7, 8, 9, −10, −11, −12, 13, 32] d2 [17, −18, 21, −22, 32] c2 [7, 8, 9, −10, 28, −29, −32] b2 [−16, 17, −18, 24, 25, 26, −27, −32] a3 [−1, 2, −7, −8, −9, 10, −32] d3 [13, −32] c3 [−32] b3 [−8, 14, 15, 16, 17, 18, 19, −20, −32] a4 [−25, . . . , −30, 31, 32] d4 [32] c4 [4, 16, 32] b4 [−30, 32] a5 [32] d5 [32] c5 [18, 32] b5 [32] a6 [32] d6 [32] c6 [32] b6 [32] a7 d7 c7 ... d9 c9 [∗32] d9 [∗32] a10 [∗32] d10 [∗32] c10 [∗32] ... a13 [32] d13 [−32] c13 [32] b13 [−32] ... c15 [32] b15 [32] a16 + aa0 = a16 + aa0 d16 + dd0 = d16 + dd0 c16 + cc0 = c16 + cc0 b16 + bb0 = b16 + bb0
Table 6. A Set of Sufficient Conditions for the Second Iteration Differential a1 d1
c1
b1
a2
d2
c2 b2 a3
d3 c3
b3 a4 d4 c4 b4 a5 d5 c5 b5 a6 − b 6 c9 , b12 a13 − b13 a14 − b14 a15 − b15 a16 d16 c16 b16
a1,6 = 0, a1,12 = 0, a1,22 = 1, a1,26 = 0, a1,27 = 1, a1,28 = 0, a1,32 = 1 d1,2 = 0, d1,3 = 0, d1,6 = 0, d1,7 = a1,7 , d1,8 = a1,8 , d1,12 = 1, d1,13 = a1,13 , d1,16 = 0, d1,17 = a1,17 , d1,18 = a1,18 , d1,19 = a1,19 , d1,20 = a1,20 , d1,21 = a1,21 , d1,22 = 0, d1,26 = 0, d1,27 = 1, d1,28 = 1, d1,29 = a1,29 , d1,30 = a1,30 , d1,31 = a1,31 , d1,32 = 1 c1,2 = 1, c1,3 = 1, c1,4 = d1,4 , c1,5 = d1,5 , c1,6 = 1, c1,7 = 1, c1,8 = 0, c1,9 = 1, c1,12 = 1, c1,13 = 0, c1,17 = 1, c1,18 = 1, c1,19 = 1, c1,20 = 1, c1,21 = 1, c1,22 = 0, c1,26 = 1, c1,27 = 1, c1,28 = 1, c1,29 = 1, c1,30 = 1, c1,31 = 0, c1,32 = 1 b1,1 = c1,1 , b1,2 = 0, b1,3 = 0, b1,4 = 0, b1,5 = 1, b1,6 = 0, b1,7 = 0, b1,8 = 0, b1,9 = 0, b1,10 = c1,10 , b1,11 = c1,11 , b1,12 = 0, b1,13 = 0, b1,17 = 0, b1,18 = 0, b1,19 = 1, b1,20 = 0, b1,21 = 0, b1,22 = 0, b1,26 = 1, b1,27 = 0, b1,28 = 1, b1,29 = 1, b1,30 = 1, b1,31 = 0, b1,32 = 1 a2,1 = 0, a2,2 = 0, a2,3 = 0, a2,4 = 0, a2,5 = 1, a2,6 = 0, a2,7 = 1, a2,8 = 0, a2,9 = 0, a2,10 = 1, a2,11 = 1, a2,12 = 1, a2,13 = 0, a2,17 = 1, a2,18 = 1, a2,19 = 1, a2,20 = 1, a2,27 = 0, a2,28 = 1, a2,29 = 0, a2,30 = 0, a2,21 = 0, a2,22 = 1, a2,31 = 1, a2,32 = 0 d2,1 = 0, d2,2 = 1, d2,3 = 1, d2,4 = 0, d2,5 = 1, d2,6 = 0, d2,7 = 1, d2,8 = 0, d2,9 = 0, d2,10 = 0, d2,11 = 1, d2,12 = 1, d2,13 = 0, d2,17 = 0, d2,18 = 1, d2,21 = 0, d2,22 = 1, d2,26 = 0, d2,27 = 1, d2,28 = 0, d2,29 = 0, d2,32 = 0 c2,1 = 1, c2,7 = 0, c2,8 = 0, c2,9 = 0, c2,10 = 1, c2,11 = 1, c2,12 = 1, c2,13 = 1, c2,16 = d2,16 , c2,17 = 1, c2,18 = 0, c2,21 = 0, c2,22 = 0, c2,24 = d2,24 , c2,25 = d2,25 , c2,26 = 1, c2,27 = 1, c2,28 = 0, c2,29 = 1, c2,32 = 1 b2,1 = 0, b2,2 = c2,2 , b2,7 = 1, b2,8 = 1, b2,9 = 1, b2,10 = 1, b2,16 = 1, b2,17 = 0, b2,18 = 1, b2,21 = 1, b2,22 = 1, b2,24 = 0, b2,25 = 0, b2,26 = 0, b2,27 = 1, b2,28 = 0, b2,29 = 0, b2,32 = 1 a3,1 = 1, a3,2 = 0, a3,7 = 1, a3,8 = 1, a3,9 = 1, a3,10 = 0, a3,13 = b2,13 , a3,16 = 0, a3,17 = 1, a3,18 = 0, a3,24 = 0, a3,25 = 0, a3,26 = 0, a3,27 = 1, a3,28 = 1, a3,29 = 1, a3,32 = 1 d3,1 = 0, d3,2 = 0, d3,7 = 1, d3,8 = 1, d3,9 = 1, d3,10 = 1, d3,13 = 0, d3,16 = 1, d3,17 = 1, d3,18 = 1, d3,19 = 0, d3,24 = 1, d3,25 = 1, d3,26 = 1, d3,27 = 1, d3,32 = 1 c3,1 = 1, c3,2 = 1, c3,7 = 1, c3,8 = 1, c3,9 = 1, c3,10 = 1, c3,13 = 0, c3,14 = d3,14 , c3,15 = d3,15 , c3,16 = 1, c3,17 = 1, c3,18 = 0, c3,19 = 1, c3,20 = d3,20 , c3,32 = 1 b3,8 = 1, b3,13 = 1, b3,14 = 0, b3,15 = 0, b3,16 = 0, b3,17 = 0, b3,18 = 0, b3,19 = 0, b3,20 = 1, b3,25 = c3,25 , b3,26 = c3,26 , b3,27 = c3,27 , b3,28 = c3,28 , b3,29 = c3,29 , b3,30 = c3,30 , b3,31 = c3,31 , b3,32 = 1 a4,4 = 1, a4,8 = 0, a4,14 = 1, a4,15 = 1, a4,16 = 1, a4,17 = 1, a4,18 = 1, a4,19 = 1, a4,20 = 1 a4,25 = 1, a4,26 = 1, a4,27 = 1, a4,28 = 1, a4,29 = 1, a4,30 = 1, a4,31 = 0, a4,32 = 0 d4,4 = 1, d4,8 = 1, d4,14 = 1, d4,15 = 1, d4,16 = 1, d4,17 = 1, d4,18 = 1, d4,19 = 0, d4,20 = 1 d4,25 = 0, d4,26 = 0, d4,27 = 0, d4,28 = 0, d4,29 = 0, d4,30 = 0, d4,31 = 1, d4,32 = 0 c4,4 = 0, c4,16 = 0, c4,25 = 1, c4,26 = 0, c4,27 = 1, c4,28 = 1, c4,29 = 1, c4,30 = 1 c4,31 = 1, c4,32 = 0 b4,30 = 1, b4,32 = 0 a5,4 = b4,4 , a5,16 = b4,16 , a5,18 = 0, a5,32 = 0 d5,18 = 1, d5,30 = a5,30 , d5,32 = 0 c5,18 = 0, c5,32 = 0 b5,32 = 0, a6,18 = b5,18 , a6,32 = 0, d6,32 = 0, c6,32 = 0, b6,32 = c6,32 + 1 φ34,32 = 1, b12,32 = d12,32 , a13,32 = c12,32 , d13,32 = b12,32 + 1, c13,32 = a13,32 , b13,32 = d13,32 a14,32 = c13,32 , d14,32 = b13,32 , c14,32 = a14,32 , b14,32 = d14,32 a15,32 = c14,32 , d15,32 = b14,32 , c15,32 = a15,32 , b15,32 = d15,32 + 1 a16,26 = 1, a16,32 = c15,32 d16,26 = 1,d16,32 = b15,32 c16,26 = 1,c16,32 = a16,32 b16,26 = 1
Abstract. MD5 is one of the most widely used cryptographic hash functions nowadays. It was designed in 1992 as an improvement of MD4, and its security was widely studied since then by several authors. The best known result so far was a semi free-start collision, in which the initial value of the hash function is replaced by a non-standard value, which is the result of the attack. In this paper we present a new powerful attack on MD5 which allows us to find collisions efficiently. We used this attack to find collisions of MD5 in about 15 minutes up to an hour computation time. The attack is a differential attack, which unlike most differential attacks, does not use the exclusive-or as a measure of difference, but instead uses modular integer subtraction as the measure. We call this kind of differential a modular differential. An application of this attack to MD4 can find a collision in less than a fraction of a second. This attack is also applicable to other hash functions, such as RIPEMD and HAVAL.
1
Introduction
People know that digital signatures are very important in information security. The security of digital signatures depends on the cryptographic strength of the underlying hash functions. Hash functions also have many other applications in cryptography such as data integrity, group signature, e-cash and many other cryptographic protocols. The use of hash functions in these applications not only ensure the security, but also greatly improve the efficiency. Nowadays, there are two widely used hash functions – MD5 [18] and SHA-1 [12]. MD5 is a hash function designed by Ron Rivest as a strengthened version of MD4 [17]. Since its publication, some weaknesses has been found. In 1993, B. den Boer and A. Bosselaers [3] found a kind of pseudo-collision for MD5 which consists of the same message with two different sets of initial values. This attack discloses the weak avalanche in the most significant bit for all the chaining variables in MD5. In the rump session of Eurocrypt’96, H. Dobbertin [8] presented a semi free-start collision which consists of two different 512-bit messages with a chosen initial value IV0 . a0 = 0x12ac2375, b0 = 0x3b341042, c0 = 0x5f62b97c, d0 = 0x4ba763ed A general description of this attack was published in [9]. Although H. Dobbertin cannot provide a real collision of MD5, his attack reveals the weak avalanche for the full MD5. This provides a possibility to find a special differential with one iteration.
In this paper we present a new powerful attack that can efficiently find a collision of MD5. From H. Dobbertin’s attack, we were motivated to study whether it is possible to find a pair of messages, each consists of two blocks, that produce collisions after the second block. More specifically, we want to find a pair (M0 , M1 ) and (M0 , M1 ) such that (a, b, c, d) = MD5(a0 , b0 , c0 , d0 , M0 ), (a , b , c , d ) = MD5(a0 , b0 , c0 , d0 , M0 ), MD5(a, b, c, d, M1 ) = MD5(a , b , c , d , M1 ), where a0 , b0 , c0 , d0 are the initial values for MD5. We show that such collisions of MD5 can be found efficiently, where finding the first blocks (M0 , M0 ) takes about 239 MD5 operations, and finding the second blocks (M1 , M1 ) takes about 232 MD5 operations. The application of this attack on IBM P690 takes about an hour to find M0 and M0 , where in the fastest cases it takes only 15 minutes. Then, it takes only between 15 seconds to 5 minutes to find the second blocks M1 and M1 . Two such collisions of MD5 were made public in the Crypto’04 rump session [19]. This attack is applicable to many other hash functions as well, including MD4, HAVAL-128 and RIPEMD ([17], [20], [15]). In the case of MD4, the attack can find a collision within less than a second, and can also find second pre-images for many messages. In Crypto’04 Eli Biham and Rafi Chen presented a near-collision attack on SHA-0 [2], which follows the lines of the technique of [4]. In the rump session they described their new (and improved) results on SHA-0 and SHA-1 (including a ˜ multi-block technique and collisions of reduced SHA-1). Then, A.Joux presented a 4-block full collision of SHA-0 [14], which is a further improvement of these results. Both these works were made independently of this paper. This paper is organized as follows: In Section 2 we briefly describe MD5. Then in Section 3 we give the main ideas of our attack, and in Section 4 we give a detailed description of the attack. Finally, in Section 5 we summarize the paper, and discuss the applicability of this attack to other hash functions.
2
Description of MD5
In order to conveniently describe the general structure of MD5, we first recall the iteration process for hash functions. Generally a hash function is iterated by a compression function X = f (Z) which compresses l-bit message block Z to s-bit hash value X where l > s. For MD5, l = 512, and s = 128. The iterating method is usually called the MerkleDamgard meta-method (see [6], [16]). For a padded message M with multiples of l-bit length, the iterating process is as follows: Hi+1 = f (Hi , Mi ), 0 ≤ i ≤ t − 1. Here M = (M0 , M2 , · · · , Mt−1 ), and H0 = IV0 is the initial value for the hash function.
In the above iterating process, we omit the padding method because it has no influence on our attack. The following is to describe the compression function for MD5. For each 512-bit block Mi of the padded message M , divide Mi into 32-bit words, Mi = (m0 , m1 , ...., m15 ). The compression algorithm for Mi has four rounds, and each round has 16 operations. Four successive step operations are as follows: a = b + ((a + φi (b, c, d) + wi + ti ) ≪ si ), d = a + ((d + φi+1 (a, b, c) + wi+1 + ti+1 ) ≪ si+1 ), c = d + ((c + φi+2 (d, a, b) + wi+2 + ti+2 ) ≪ si+2 ), b = c + ((b + φi+3 (c, d, a) + wi+3 + ti+3 ) ≪ si+3 ), where the operation + means ADD modulo 232 . ti+j and si+j (j = 0, 1, 2, 3) are step-dependent constants. wi+j is a message word. ≪ si+j is circularly leftshift by si+j bit positions. The details of the message order and shift positions can be seen in Table 3. Each round employs one nonlinear round function, which is given below. Φi (X, Y, Z) = (X ∧ Y ) ∨ (¬X ∧ Z), Φi (X, Y, Z) = (X ∧ Z) ∨ (Y ∧ ¬Z), Φi (X, Y, Z) = X ⊕ Y ⊕ Z, Φi (X, Y, Z) = Y ⊕ (X ∨ ¬Z),
0 ≤ i ≤ 15, 16 ≤ i ≤ 31, 32 ≤ i ≤ 47, 48 ≤ i ≤ 63,
where X, Y , Z are 32-bit words. The chaining variables are initialized as: a = 0x67452301, b = 0xefcdab89, c = 0x98badcfe, d = 0x10325476. We select a collision differential with two iterations as follows: Let Hi−1 = (aa, bb, cc, dd) be the chaining values for the previous message block. After four rounds, the compression value Hi is obtained by wordwise addition of the chaining variables to Hi−1 .
3
Differential Attack for Hash Functions
3.1
The Modular Differential and the XOR Differential
The most important analysis method for hash functions is differential attack which is also one of most important methods for analyzing block ciphers. In general, the differential attack especially in block ciphers is a kind of XOR differential attack which uses exclusive-or as the difference. The differential attack was introduced by E. Biham and A. Shamir to analyze the security of DES-like cryptosystems. E. Biham and A. Shamir [1], described that differential cryptanalysis is a method which analyzes the effect of particular differences in plain text pairs on the differences of the resultant cipher text pairs. The differential definition in this paper is a kind of precise differential which uses the difference in term of integer modular subtraction. A similar definition
about the differential with the integer subtraction as the measure of difference were described in [5] for differential analysis of RC6. We 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 us more information than each of them keep by itself. For example, when the modular integer subtraction difference is X − X = 26 for some value X, the XOR difference X ⊕ X can have many possibilities, which are 1. One-bit difference in bit 7, i.e., 0x00000040. In this case X − X = 26 which means that bit 7 in X is 1 and bit 7 in X is 0. 2. Two-bit difference, in which a different carry is transferred from bit 7 to bit 8, i.e., 0x000000C0. In this case X − X = 26 , but the carry to bit 8 is different in X and X , so X7 is now 0, and X7 = 1, while X8 = 1, and X8 = 0. (i.e., bits 7 and 8 together in X are 10 in binary, and in X there are 01 in binary). 3. Three-bit difference, in which a different carry is transferred from bit 7 to bit 8 and then to bit 9, i.e., 0x000001C0. In this case bits 7, 8, and 9 in X are 0, 0, and 1, respectively, and in X they are the complement of these values. 4. Similarly, there can be more carries to further bits, and the binary form of X is 1000. . . , and of X is 0111. . . . 5. In case the former difference is negative, the XOR differences still look the same, but the values of X and X are exchanged (i.e., X is of the form 1000. . . , and X of the form 0111. . . ). In order to explain our attack clearly, we refer to the modular differences in the differential path (see Table 3) with both kinds of differences together, i.e., the difference is marked as a positive or a negative integer (modulo 232 ) 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 −26 , [7, 8, 9, . . . , 22, −23] marks the integer modular subtraction difference X − X = −26 (with X < X), with many carries which start from bit 7 up to bit 23. All bits of X from bit 7 to bit 22 are 0, and bit 23 is 1, while all bits of X from bit 7 to bit 22 are 1, and bit 23 is 0. A more complicated example is −1 − 26 + 223 − 227 , [1, 2, 3, 4, 5, −6, 7, 8, 9, 10, 11, −12, −24, −25, −26, 27, 28, 29, 30, 31, −32], where the integer modular subtraction difference is composed of several (positive and negative) exponents of 2, and the XOR difference has many difference due to carries. Note that when the carry arrives to bit 32, a further (dropped) carry may happen, and then there is no negative sign in bit 32. It should be noted that the modular differential has been used earlier to analyze some hash functions ([4], [7], [10]). Compared with these attacks, our attack has the following advantages: 1. Our attack is to find collisions with two iterations, i. e., each message in the collision includes two message blocks (1024-bit).
2. Our attack is a precise differential attack in which the characteristics are more restrictive than used, and that they gives values of bits in addition to the differences. 3. Our attack gives a set of sufficient conditions which ensure the differential to occur. 4. Our attack use a message modification technique to greatly improve the collision probability. 3.2
Differential Attacks on Hash Functions
The difference for two parameters X and X is defined as ∆X = X − X. For any two messages M and M with l-bit multiples, M = (M0 , M1 , · · · , Mk−1 ), M = (M0 , M1 , · · · , Mk−1 ), a full differential for a hash function is defined as follows: ∆H0
(M0 ,M0 )
−→
∆H1
(M1 ,M1 )
−→
∆H2
(M2 ,M2 )
−→
· · · · · · ∆Hk−1
) (Mk−1 ,Mk−1
−→
∆H,
where ∆H0 is the initial value difference which equals to zero. ∆H is the output difference for the two messages. ∆Hi = ∆IVi is the output difference for the i-th iteration, and also is the initial difference for the next iteration. It is clear that if ∆H = 0, there is a collision for M and M . We call the differential that produces a collision a collision differential. Provided that the hash function has 4 rounds, and each round has 16 step operations. For more details, we can represent the i-th iteration differential ∆Hi
(Mi ,Mi )
−→ ∆Hi+1 as follows: P
P
P
P
1 2 3 4 ∆Hi −→ ∆Ri+1,1 −→ ∆Ri+1,2 −→ ∆Ri+1,3 −→ ∆Ri+1,4 = ∆Hi+1 .
The round differential ∆Rj−1 −→ ∆Rj (j = 1, 2, 3, 4) with the probability Pj is expanded to the following differential characteristics. Pj1
Pj2
Pj16
∆Rj−1 −→ ∆X1 −→ · · · · · · −→ ∆X16 = ∆Rj , Pjt
where ∆Xt−1 −→ ∆Xt , t = 1, 2, · · · · · · , 16 is the differential characteristic in the t-th step of j-th round. (Mi ,M )
The probability P of the differential ∆Hi −→ i ∆Hi+1 satisfies 4 16 P ≥ i=1 Pj and Pj ≥ t=1 Pjt . 3.3
Optimized Collision Differentials for Hash Functions
In Section 3.1, we mentioned that our attack uses a message modification technique to improve the collision probability. According to the modification technique, we can get a rough method to search for optimized differentials (including collision differentials) of a hash function. There are two kinds of message modifications:
1. For any two message blocks (Mi , Mi ) and a 1-st round non-zero differential ∆Hi
(Mi ,Mi )
−→ ∆Ri+1,1 .
Our attack can easily modify Mi to guarantee the 1-st round differential to hold with probability P1 = 1. 2. Using multi-message modification techniques, we can not only guarantee the first-round differential to hold with the probability 1, but also improve the second-round differential probability greatly. To find an optimized differential for a hash function, it is better to select a message block difference which results in a last two-round differential with a high probability.
4
Differential Attack on MD5
4.1
Notation
Before presenting our attack, we first introduce some notation to simplify the discussion. 1. M = (m0 , m1 , ..., m15 ) and M = (m0 , m1 , ..., m15 ) represent two 512-bit messages. ∆M = (∆m0 , ∆m1 , ..., ∆m15 ) denotes the difference of two message blocks. That is, ∆mi = mi − mi is the i − th word difference. 2. ai , di , ci , bi respectively denote the outputs of the (4i − 3)-th, (4i − 2)-th (4i − 1)-th and 4i-th steps for compressing M , where 1 ≤ i ≤ 16. ai , bi , ci , di are defined similarly. 3. ai,j , bi,j , ci,j , di,j represent respectively the j − th bit of ai , bi , ci , di , where the least significant bit is the 1-st bit, and the most significant bit is 32-th bit. 4. φi,j is the j-th bit of the output for the nonlinear function φi in the i-th step operation. 5. ∆xi,j = xi,j − xi,j = ±1 is the bit difference that is produced by changing the j-bit of xi . xi [j], xi [−j] (x can be a, b, c, d, φ) is the resulting values by only changing the j − th bit of the word xi . xi [j] is obtained by changing the j-th bit of xi from 0 to 1, and xi [−j] is obtained by changing the j-th bit of xi from 1 to 0. 6. ∆xi [j1 , j2 , ..., jl ] = xi [j1 , j2 , ..., jl ]−xi denotes the difference that is produced by the changes of j1 − th, j2 − th, ..., jl − th bits of xi . xi [±j1 , ±j2 , ..., ±jl ] is the value by change j1 − th, j2 − th, ..., jl − th bits of xi . The “+” sign (usually is omitted) means that the bit is changed from 0 to 1, and the “–” sign means that the bit is changed from 1 to 0. 4.2
Collision Differentials for MD5
Our attack can find many real collisions which are composed of two 1024-bit messages (M0 , M1 ) and (M0 , M1 ) ) with the original initial value IV0 of MD5: IV0 : a0 = 0x67452301, b0 = 0xefcdab89, c0 = 0x98badcfe, d0 = 0x10325476.
We select a collision differential with two iterations as follows: ∆H0
(M0 ,M0 )
−→
∆H1
(M1 ,M1 )
−→
∆H = 0
where ∆M0 = M0 − M0 = (0, 0, 0, 0, 231 , 0, 0, 0, 0, 0, 0, 215 , 0, 0, 231 , 0) ∆M1 = M1 − M1 = (0, 0, 0, 0, 231 , 0, 0, 0, 0, 0, 0, −215 , 0, 0, 231 , 0) ∆H1 = (231 , 231 + 225 , 231 + 225 , 231 + 225 ). Non-zero entries of ∆M0 and ∆M1 are located at positions 5, 12 and 15. ∆H1 = (∆a, ∆b, ∆c, ∆d) is the difference of the four chaining values (a, d, c, b) after the first iteration. We select ∆M0 to ensure that both 3-4 round differential happens with a high probability. ∆M1 is selected not only to ensure both 3-4 round differential happens with a high probability, but also to produce an output difference that can be cancelled with the output difference ∆H1 . The collision differential with all the characteristics can be referred to Table 3 and Table 5. The columns of both tables have the same meanings. We just give the explanation for Table 3. The first column denotes the step, the second column is the chaining variable in each step for M0 , the third is the message word for M0 in each step, the fourth is shift rotation, the fifth and the sixth are respectively the message word difference and chaining variable difference for M0 and M0 , and the seventh is the chaining variable for M0 . Especially, the empty items both in sixth and fifth columns denote zero differences, and steps those aren’t listed in the table have zero differences both for message words and chaining variables. 4.3
Sufficient Conditions for the Characteristics to Hold
In what follows, we describe how to derive a set of sufficient conditions that guarantee the differential characteristic in Step 8 of MD5 (Table 3) to hold. Other conditions can be derived similarly. The differential characteristic in Step 8 of MD5 is: (∆c2 , ∆d2 , ∆a2 , ∆b1 ) −→ ∆b2 . Each chaining variable satisfies one of the following equations. b1 = b1
a2 = a2 [7, ..., 22, −23] d2 = d2 [−7, 24, 32]
c2 = c2 [7, 8, 9, 10, 11, −12, −24, −25, −26, 27, 28, 29, 30, 31, 32, 1, 2, 3, 4, 5, −6] b2 = b2 [1, 16, −17, 18, 19, 20, −21, −24]
According to the operations in the 8-th step, we have b2 = c2 + ((b1 + F (c2 , d2 , a2 ) + m7 + t7 ) ≪ 22
b2 = c2 + ((b1 + F (c2 , d2 , a2 ) + m7 + t7 ) ≪ 22 φ7 = F (c2 , d2 , a2 ) = (c2 ∧ d2 ) ∨ (¬c2 ∧ a2 ) In the above operations, c2 occurs twice in the right hand side of the equation. NF denote In order to distinguish the two, let cF 2 denote the c2 inside F , and c2 the c2 outside F . The derivation is based on the following two facts: F 1. Since ∆b1 = 0 and ∆m7 = 0, we know that ∆b2 = ∆cN + (∆φ7 ≪ 22). 2 2. Fix one or two of the variables in F so that F is reduced to a single variable.
We get a set of sufficient conditions that ensure the differential characteristic holds. 1. The conditions for each of the non-zero bits in ∆b2 . (a) The conditions d2,11 = 1 and b2,1 = 0 ensure the change of 1-st bit of b2 . i. If d2,11 = a2,11 = 1, we know that ∆φ7,11 = 1. ii. After ≪ 22, ∆φ7,11 is in the position 1. F NF iii. Since ∆cN 2,1 = 0, so, ∆b2,1 = ∆c2,1 + ∆φ7,11 = 1. (b) The conditions d2,26 = a2,26 = 1, b2,16 = 0 and b2,17 = 1 ensure the changes of 16-th bit and 17-th bit of b2 . (c) The conditions d2,28 = a2,28 = 0, b2,i = 0, i = 18, 19, 20 and b2,21 = 1 ensure the changes of 18-th, 19-th, 20-th, 21-th bits of b2 . (d) The conditions d2,3 = a2,3 = 0 and b2,24 = 1 ensure the change of 24-th bit of b2 . This can be proven by the equation: F 23 ∆cN − 224 = −223 . 2 [−24, −25, −26, 27] + (∆φ7 [3] ≪ 22) = 2
2. The conditions for each of the zero bits in ∆b2 . (a) The condition c2,17 = 0 ensures the changed bits from 7-th bit to 12-th NF bit in c2 and 17-th bit of a2 result in no bit change in b2 . It is easily proven by the following equation: F 6 6 ∆cN 2 [7, . . . 11, −12] + (∆φ7 [17] ≪ 22) = −2 + 2 = 0.
(b) The conditions d2,i = a2,i ensure that the changed i-th bit in cF 2 result in no change in b2 , where i ∈ {1, 2, 4, 5, 25, 27, 29, 30, 31}. (c) The conditions c2,i = 1 ensure that the changed i-th bit in a2 result in no change in b2 , where i ∈ {13, 14, 15, 16, 18, 19, 20, 21, 22, 23}. (d) The condition d2,6 = a2,6 = 0 ensures that the 6-th bit in cF 2 result in no change in b2 . (e) The condition a2,32 = 1 ensures that the changed 32-th bit in cF 2 and the 32-th bit in d2 result in no change in b2 . (f) The condition d2,i = 0 ensures that the changed i-th bit in a2 and the i-th bit in cF 2 result in no change in b2 , where i ∈ {8, 9, 10}. (g) The condition d2,12 = 1 ensures that the changed 12-th bit in a2 and the 12-th bit in cF 2 result in no change in b2 .
(h) The condition a2,24 = 0 ensures that the changed 24-th bit in cF 2 and the 24-th bit in d2 result in no change in b2 . (i) The changed 7-th bits in cF 2 , d2 and a2 result in no change in b2 . By the similar method, we can derive a set of sufficient conditions (see Table 4 and Table 6) which guarantee all the differential characteristics in the collision differential to hold. 4.4
Message Modification
Single-message Modification In order to make the attack efficient, it is very attractive to improve over the probabilistic method that we describe, by fixing some of the message words to a prior fulfilling some of the conditions. We observe that it is very easy to generate messages that fulfill all the conditions of the first 16 steps of MD5. We call it single-message modification. For each message block M0 (or similarly M1 ) and intermediate values (H0 , or for the second block H1 and H1 ), we apply the following procedures to modify M0 (or M1 , respectively), so that all the conditions of round 1 (the first 16 steps) in Table 4 and Table 6 hold. It is easy to modify M0 such that the conditions of round 1 in Table 4 hold with probability 1. For example, to ensure that 3 conditions for c1 in Table 4 hold, we modify m2 as follows: old 6 old 11 19 ← cold − cold cnew 1 1 − c1,7 · 2 − c1,12 · 2 1,20 · 2 old mnew ← ((cnew − cold 2 1 1 ) ≫ 17) + m2 .
By modifying each message word of message M0 , all the conditions in round 1 of Table 4 hold. The first iteration differential hold with probability 2−43 . The same modification is applied to M1 . After modification, the second iteration differential hold with probability 2−37 . Multi-message Modification We further observe that it is even possible to fulfill a part of the conditions of the first 32 steps by an multi-message modification. For example, if a5,32 = 1, we correct it into a5,32 = 0 by modifying m1 , m2 ,m3 , m4 ,m5 such that the modification generates a partial collision from 2-6 steps, and remains that all the conditions in round 1 hold. See Table 1. Some other conditions can be corrected by the similar modification technique or other more precise modification techniques. By our modification, 37 conditions in round 2-4 are undetermined in the table 4, and 30 conditions in round 2-4 are undetermined in the table 6. So, the 1-st iteration differential holds with probability 2−37 , and the second iteration differential holds with probability 2−30 .
Table 1. The Message Modification for Correcting a5,32
2 3 4 5 6
m1 m2 m3 m4 m5
4.5
Modify mi anew , bnew , cnew , dnew 12 m1 ←− m1 + 226 dnew , a1 , b0 , c0 1 new new 17 m2 ←− ((c1 − d1 ) ≫ 17) − c0 − φ2 (d1 , a1 , b0 ) − t2 c1 , dnew , a1 , b0 1 22 m3 ←− (b1 − c1 ) ≫ 22) − b0 − φ3 (c1 , dnew , a1 ) − t3 b1 , c1 , dnew , a1 1 1 7 m4 ←− ((a2 − b1 ) ≫ 7) − a1 − φ4 (b1 , c1 , dnew − t4 a2 , b1 , c1 , dnew 1 1 12 m5 ←− ((d2 − a2 ) ≫ 12) − dnew − φ5 (a2 , b1 , c1 ) − t5 d2 , a2 , b1 , c1 1
The Differential Attack on MD5
From the above description, it is very easy to show our attack on MD5. The following is to describe how to find a two-block collision, of the following form H0
(M0 ,M0 ),2−37
−→
∆H1
(M1 ,M1 ),2−30
−→
∆H = 0.
1. Repeat the following steps until a first block is found (a) Select a random message M0 . (b) Modify M0 by the message modification techniques described in the previous subsection. (c) Then, M0 and M0 = M0 + ∆M0 produce the first iteration differential ∆M0 −→ (∆H1 , ∆M1 ) with the probability 2−37 . (d) Test if all the characteristics really hold by applying the compression function on M0 and M0 . 2. Repeat the following steps until a collision is found (a) Select a random message M1 . (b) Modify M1 by the message modification techniques described in the previous subsection. (c) Then, M1 and M1 + ∆M1 generate the second iteration differential (∆H1 , ∆M1 ) −→ ∆H = 0 with the probability 2−30 . (d) Test if this pair of messages lead to a collision. The complexity of finding (M0 , M0 ) doesn’t exceed the time of running 239 MD5 operations. To select another message M0 is only to change the last two words from the previous selected message M0 . So, finding (M0 , M0 ) only needs about one-time single-message modification for the first 14 words. This time can be neglected. For each selected message M0 , it is only needs two-time single-message modifications for the last two words and 7-time multi-message modifications for correcting 7 conditions in the second round, and each multi-message modification
only needs about a few step operations, so the total time for both kinds of modifications is not exceeds about two MD5 operations for each selected message. According to the probability of the first iteration differential, it is easy to know that the complexity of finding (M0 , M0 ) is not exceeds 239 MD5 operations. Similarly, we can show that the complexity of finding (M1 , M1 ) is not exceeds 32 2 MD5 operations. Two collisions of MD5 are given in Table 2. It is noted that the two collisions Table 2. Two pairs of collision for MD5. H is the hash value with little-endian and no message padding, and H ∗ is the hash value with big-endian and message padding. M0 M1 M0 M1 H H∗ M0 M1 M0 M1 H H∗
2dd31d1 634ad55 d11d0b96 797f2775 2dd31d1 634ad55 d11d0b96 797f2775 9603161f a4c0d35c 2dd31d1 634ad55 313e82d8 42339fe9 2dd31d1 634ad55 313e82d8 42339fe9 8d5e7019 79054025
c4eee6c5 2b3f409 9c7b41dc eb5cd530 c4eee6c5 2b3f409 9c7b41dc eb5cd530 a30f9dbf 95a63a80 c4eee6c5 2b3f409 5b8f3456 e87e570f c4eee6c5 2b3f409 5b8f3456 e87e570f 61804e08 255fb1a2
69a3d69 8388e483 f497d8e4 baade822 69a3d69 8388e483 f497d8e4 baade822 9f65ffbc 5915367d 69a3d69 8388e483 d4ac6dae 70b654ce 69a3d69 8388e483 d4ac6dae 70b654ce 715d6b58 6e4bc422
5cf9af98 5a417125 d555655a 5c15cc79 5cf9af98 5a41f125 d555655a 5c154c79 f41fc7ef cfe6b751 5cf9af98 5a417125 c619c936 1e0da880 5cf9af98 5a41f125 c619c936 1e0d2880 6324c015 aef54eb4
87b5ca2f e8255108 c79a7335 ddcb74ed 7b5ca2f e8255108 479a7335 ddcb74ed
ab7e4612 9fc9cdf7 cfdebf0 6dd3c55f ab7e4612 9fc9cdf7 cfdebf0 6dd3c55f
3e580440 f2bd1dd9 66f12930 d80a9bb1 3e580440 72bd1dd9 66f12930 580a9bb1
897ffbb8 5b3c3780 8fb109d1 e3a7cc35 897ffbb8 5b3c3780 8fb109d1 e3a7cc35
87b5ca2f e8255108 b4e253dd bc2198c6 7b5ca2f e8255108 34e253dd bc2198c6
ab7e4612 9fc9cdf7 fd03da87 9383a8b6 ab7e4612 9fc9cdf7 fd03da87 9383a8b6
3e580440 f2bd1dd9 6633902 2b65f996 3e580440 72bd1dd9 6633902 ab65f996
897ffbb8 5b3c3780 a0cd48d2 702af76f 897ffbb8 5b3c3780 a0cd48d2 702af76f
start with the same 1-st 512-bit block, and that given a first block that satisfies all the required criteria, it is easy to find many second blocks M1 , M1 which lead to collisions.
5
Summary
In this paper we described a powerful attack against hash functions, and in particular showed that finding a collision of MD5 is easily feasible. Our attack is also able to break efficiently other hash functions, such as HAVAL-128, MD4, RIPEMD, and SHA-0. The analysis results for these hash functions are as follows:
1. The time complexity for finding a collision for MD4 is about 223 MD4 operations without the multi-message modification, and is about 28 MD4 operations with the multi-message modification. 2. The time complexity for finding a collision for HAVAL-128 is about 213 MD4 operations without the multi-message modification, and is 27 HAVAL-128 operations with the multi-message modification. 3. The time complexity for finding a collision for RIPEMD is about 230 RIPEMD operations without the multi-message modification, and is 218 RIPEMD operations with the multi-message modification. 4. The time complexity for finding a collision for SHA-0 is about 261 SHA-0 operations without the multi-message modification, and is 245 SHA-0 operations with the multi-message modification.
Acknowledgements It is a pleasure to acknowledge Dengguo Feng for the conversations that led to this research on MD5. We would like to thank Eli Biham, Andrew C. Yao, and Yiqun Lisa Yin for their important advice, corrections, and suggestions, and for spending their precious time on our research. We would also like to thank Xuejia Lai, Hans Dobbertin, Magnus Daum for various discussions on this paper. The research is supported by the National Natural Science Foundation of China (Grant No. 90304009).
References 1. E. Biham, A. Shamir. Differential Cryptanalysis of the Data Encryption Standard, Springer-Verlag, 1993. 2. E. Biham, R. Chen, Near collision for SHA-0, Advances in Cryptology, Crypto’04, 2004, LNCS 3152, pp. 290-305. 3. B. den. Boer, A. Bosselaers. Collisions for the compression function of MD5, Advances in Cryptology, Eurocrypt’93 Proceedings, Springer-Verlag, 1994. 4. F. Chabaud, A. Joux. Differential collisions in SHA-0, Advances in Cryptology, Crypto’98 Proceedings, Springer-Verlag, 1998. 5. S. Cotini, R.L. Rivest, M.J.B. Robshaw, Y. Lisa Yin. Security of the RC6T M Block Cipher, http://www.rsasecurity.com/rsalabs/rc6/. 6. I. B. Damgard. A design principle for hash functions, Advances in Cryptology, Crypto’89 Proceedings, Springer-Verlag, 1990. 7. H. Dobbertin. Cryptanalysis of MD4, Fast Software Encryption, LNCS 1039, Springer-Verlag, 1996, 53-69. 8. H. Dobbertin. Cryptanalysis of MD5 compress, presented at the rump session of Eurocrypt’96. 9. H. Dobbertin. The status of MD5 after a recent attack, CryptoBytes 2 (2), 1996, ftp://ftp.rsasecurity.com/pub/cryptobytes/crypto2n2.pdf. 10. H. Dobbertin. RIPEMD with two round compress function is not collision-free, Journal of Cryptology, 10:51-69, 1997. 11. H. Dobbertin, A. Bosselaers, B. Preneel. RIPEMD-160: A strengthened version of RIPEMD, Fast Software Encryption, LNCS 1039, Springer-Verlag, 1996.
12. FIPS 180-1. Secure hash standard, NIST, US Department of Commerce, Washington D.C., Springer-Verlag, 1996. 13. FIPS 180-2. Secure Hash Standard, http://csrc.nist.gov/publications/, 2002. 14. A. Joux. Collisions for SHA-0, rump session of Crypto’04, 2004. 15. RIPE. Integrity Primitives for Secure Information Systems. Final Report of RACE Integrity Primitives Evaluation (RIPE-RACE 1040), LNCS 1007, Springer-Verlag, 1995. 16. R.C. Merkle. One way hash function and DES, Advances in Cryptology, Crypto’89 Proceedings, Springer-Verlag, 1990. 17. R.L. Rivest. The MD4 message digest algorithm, Advances in Cryptology, Crypto’90, Springer-Verlag, 1991, 303-311. 18. R.L. Rivest. The MD5 message-digest algorithm, Request for Comments (RFC 1320), Internet Activities Board, Internet Privacy Task Force, 1992. 19. X.Y. Wang, F.D. Guo, X.J. Lai, H.B. Yu, Collisions for hash functions MD4, MD5, HAVAL-128 and RIPEMD, rump session of Crypto’04, E-print, 2004. 20. Y.L. Zheng, J. Pieprzyk, J. Seberry. HAVAL–A one-way hashing algorithm with variable length of output, Advances in Cryptology, Auscrypt’92 Proceedings, Springer-Verlag.
Table 3. The Differential Characteristics in the First Iteration Differential Step
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ... 34 35 36 37 38 39 ... 45 46 47 48 49 50 51 52 ... 58 59 60 61 62 63 64
The output in i-th step for M0 b1 a2 d2 c2
aa0 dd0 cc0 bb0
b2 a3 d3 c3 b3 a4 d4 c4 b4 a5 d5 c5 b5 a6 d6 c6 b6 a7 d7 c7 ... d9 c9 b9 a10 d10 c10 ... a12 d12 c12 b12 a13 d13 c13 b13 ... d15 c15 b15 = a16 + a0 = d16 + d0 = c16 + c0 = b16 + b0
wi si ∆wi The output difference The output in i-th step for M0 in i-th step m3 m4 m5 m6
22 7 231 −26 12 −26 + 223 + 231 17 −1 − 26 + 223 − 227
m7 m8 m9 m10 m11 m12 m13 m14 m15 m1 m6 m11 m0 m5 m10 m15 m4 m9 m14 m3 ... m8 m11 m14 m1 m4 m7 ... m9 m12 m15 m2 m0 m7 m14 m5 ... m15 m6 m13 m4 m11 m2 m9
22 7 12 17 22 7 12 17 22 5 9 14 20 5 9 14 20 5 9 14 ... 11 16 23 4 11 16 ... 4 11 16 23 6 10 15 21 ... 10 15 21 6 10 15 21
215
231
215
1 − 215 − 217 − 223 1 − 26 + 231 212 + 231 230 + 231 −27 − 213 + 231 224 + 231 231 23 − 215 + 231 −229 + 231 231 231 217 + 231 231 231 231
231 231 ... ... 215 231 231 231 231 31 2 231 231 ... ... 231 231 231 231 231 231 231 231 231 ... ... 231 231 231 31 2 231 215 231 231 231
a2 [7, . . . , 22, −23] d2 [−7, 24, 32] c2 [7, 8, 9, 10, 11, −12, −24, −25, −26, 27, 28, 29, 30, 31, 32, 1, 2, 3, 4, 5, −6] b2 [1, 16, −17, 18, 19, 20, −21, −24], a3 [−1, 2, 7, 8, −9, −32] d3 [−13, 14, 32] c3 [31, 32] b3 [8, −9, 14, . . . , 19, −20, 32] a4 [−25, 26, 32] d4 [32] c4 [4, −16, 32] b4 [−30, 32] a5 [32] d5 [32] c5 [18, 32] b5 [32] a6 [32] d6 [32] c6 b6 a7 d7 c7 ... d9 c9 [∗32] b9 [∗32] a10 [∗32] d10 [∗32] c10 [∗32] ... a12 [∗32] d12 [32] c12 [32] b12 [32] a13 [32] d13 [−32] c13 [32] b13 [−32] ... d15 [−32] c15 [32] b15 [32] aa0 = aa0 [32] dd0 = dd0 [26, 32] cc0 = cc0 [−26, 27, 32] bb0 = bb0 [26, −32]
Table 4. A Set of Sufficient Conditions for the First Iteration Differential c1 b1
a2
d2
c2
b2
a3
d3 c3 b3 a4 d4 c4 b4 a5 d5 c5 b5 a6 − b 6 c9 , b12 a13 − b13 a14 − b14 a15 d15 c15 b15 aa0 = a16 + a0 dd0 = d16 + d0 cc0 = c16 + c0 bb0 = b16 + b0
c1,7 = 0, c1,12 = 0, c1,20 = 0 b1,7 = 0, b1,8 = c1,8 , b1,9 = c1,9 , b1,10 = c1,10 , b1,11 = c1,11 , b1,12 = 1, b1,13 = c1,13 , b1,14 = c1,14 , b1,15 = c1,15 , b1,16 = c1,16 , b1,17 = c1,17 , b1,18 = c1,18 ,b1,19 = c1,19 , b1,20 = 1, b1,21 = c1,21 , b1,22 = c1,22 , b1,23 = c1,23 , b1,24 = 0, b1,32 = 1 a2,1 = 1, a2,3 = 1, a2,6 = 1, a2,7 = 0, a2,8 = 0, a2,9 = 0, a2,10 = 0, a2,11 = 0, a2,12 = 0, a2,13 = 0, a2,14 = 0, a2,15 = 0, a2,16 = 0, a2,17 = 0, a2,18 = 0, a2,19 = 0, a2,20 = 0, a2,21 = 0, a2,22 = 0, a2,23 = 1, a2,24 = 0, a2,26 = 0, a2,28 = 1, a2,32 = 1 d2,1 = 1, d2,2 = a2,2 , d2,3 = 0, d2,4 = a2,4 , d2,5 = a2,5 , d2,6 = 0, d2,7 = 1, d2,8 = 0, d2,9 = 0, d2,10 = 0, d2,11 = 1, d2,12 = 1, d2,13 = 1, d2,14 = 1, d2,15 = 0, d2,16 = 1, d2,17 = 1, d2,18 = 1, d2,19 = 1, d2,20 = 1, d2,21 = 1, d2,22 = 1, d2,23 = 1, d2,24 = 0, d2,25 = a2,25 , d2,26 = 1, d2,27 = a2,27 , d2,28 = 0, d2,29 = a2,29 , d2,30 = a2,30 , d2,31 = a2,31 , d2,32 = 0 c2,1 = 0, c2,2 = 0, c2,3 = 0, c2,4 = 0, c2,5 = 0, c2,6 = 1, c2,7 = 0, c2,8 = 0, c2,9 = 0, c2,10 = 0, c2,11 = 0, c2,12 = 1, c2,13 = 1, c2,14 = 1, c2,15 = 1, c2,16 = 1, c2,17 = 0, c2,18 = 1, c2,19 = 1, c2,20 = 1, c2,21 = 1, c2,22 = 1, c2,23 = 1, c2,24 = 1, c2,25 = 1, c2,26 = 1, c2,27 = 0, c2,28 = 0, c2,29 = 0, c2,30 = 0, c2,31 = 0, c2,32 = 0 b2,1 = 0, b2,2 = 0, b2,3 = 0, b2,4 = 0, b2,5 = 0, b2,6 = 0, b2,7 = 1, b2,8 = 0, b2,9 = 1, b2,10 = 0, b2,11 = 1, b2,12 = 0, b2,14 = 0, b2,16 = 0, b2,17 = 1, b2,18 = 0, b2,19 = 0, b2,20 = 0, b2,21 = 1, b2,24 = 1, b2,25 = 1, b2,26 = 0, b2,27 = 0, b2,28 = 0, b2,29 = 0, b2,30 = 0, b2,31 = 0, b2,32 = 0 a3,1 = 1, a3,2 = 0, a3,3 = 1, a3,4 = 1, a3,5 = 1, a3,6 = 1, a3,7 = 0, a3,8 = 0, a3,9 = 1, a3,10 = 1, a3,11 = 1, a3,12 = 1, a3,13 = b2,13 , a3,14 = 1, a3,16 = 0, a3,17 = 0, a3,18 = 0, a3,19 = 0, a3,20 = 0, a3,21 = 1, a3,25 = 1, a3,26 = 1, a3,27 = 0, a3,28 = 1, a3,29 = 1, a3,30 = 1, a3,31 = 1, a3,32 = 1 d3,1 = 0, d3,2 = 0, d3,7 = 1, d3,8 = 0, d3,9 = 0, d3,13 = 1, d3,14 = 0, d3,16 = 1, d3,17 = 1, d3,18 = 1, d3,19 = 1, d3,20 = 1, d3,21 = 1, d3,24 = 0, d3,31 = 1, d3,32 = 0 c3,1 = 0, c3,2 = 1, c3,7 = 1, c3,8 = 1, c3,9 = 0, c3,13 = 0, c3,14 = 0, c3,15 = d3,15 , c3,17 = 1, c3,18 = 0, c3,19 = 0, c3,20 = 0, c3,16 = 1, c3,31 = 0, c3,32 = 0 b3,8 = 0, b3,9 = 1, b3,13 = 1, b3,14 = 0, b3,15 = 0, b3,16 = 0, b3,17 = 0, b3,18 = 0, b3,20 = 1, b3,25 = c3,25 , b3,26 = c3,26 , b3,19 = 0, b3,31 = 0, b3,32 = 0 a4,4 = 1, a4,8 = 0, a4,9 = 0, a4,14 = 1, a4,15 = 1, a4,16 = 1, a4,17 = 1, a4,18 = 1, a4,20 = 1, a4,25 = 1, a4,26 = 0, a4,31 = 1, a4,19 = 1, a4,32 = 0 d4,4 = 1, d4,8 = 1, d4,9 = 1, d4,14 = 1, d4,15 = 1, d4,16 = 1, d4,17 = 1, d4,18 = 1, d4,19 = 0, d4,20 = 1, d4,25 = 0, d4,26 = 0, d4,30 = 0, d4,32 = 0 c4,4 = 0, c4,16 = 1, c4,25 = 1, c4,26 = 0, c4,30 = 1, c4,32 = 0 b4,30 = 1, b4,32 = 0 a5,4 = b4,4 , a5,16 = b4,16 , a5,18 = 0, a5,32 = 0 d5,18 = 1, d5,30 = a5,30 , d5,32 = 0 c5,18 = 0, c5,32 = 0 b5,32 = 0 a6,18 = b5,18 , a6,32 = 0, d6,32 = 0, c6,32 = 0, b6,32 = c6,32 + 1 φ34,32 = 0, b12,32 = d12,32 a13,32 = c12,32 , d13,32 = b12,32 + 1, c13,32 = a13,32 , b13,32 = d13,32 a14,32 = c13,32 , d14,32 = b13,32 , c14,32 = a14,32 , b14,32 = d14,32 a15,32 = c14,32 d15,32 = b14,32 c15,32 = a15,32 b15,26 = 0, b15,32 = d15,32 + 1 a16,26 = 1, a16,27 = 0, a16,32 = c15,32 dd0,26 = 0, d16,32 = b15,32 cc0,26 = 1, cc0,27 = 0, cc0,32 = dd0,32 , c16,32 = d16,32 bb0,26 = 0, bb0,27 = 0, bb0,6 = 0, bb0,32 = cc0,32
Table 5. All the Differential Characteristics in the Second Iteration Differential Step The output in i-th step for M1 IV aa0 , dd0 cc0 , bb0 1 a1 2 d1 3 c1 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 ... 34 35 36 37 38 39 ... 49 50 51 52 ... 59 60 61 62 63 64
b1 a2 d2 c2 b2 a3 d3 c3 b3 a4 d4 c4 b4 a5 d5 c5 b5 a6 d6 c6 b6 a7 d7 c7 ... d9 c9 b9 a10 d10 c10 ... a13 d13 c13 b13 ... c15 b15 a16 + aa0 d16 + dd0 c16 + cc0 b16 + bb0
wi si ∆wi The output Difference The output in i-th step for M1 in i-th step
m0 7 m1 12 m2 17 m3 m4 m5 m6 m7 m8 m9 m10 m11 m12 m13 m14 m15 m1 m6 m11 m0 m5 m10 m15 m4 m9 m14 m3 ... m8 m11 m14 m1 m4 m7 ... m0 m7 m14 m5 ... m6 m13 m4 m11 m2 m9
22 7 12 17 22 7 12 17 22 7 12 17 22 5 9 14 20 5 9 14 20 5 9 14 ... 11 16 23 4 11 16 ... 6 10 15 21 ... 15 21 6 10 15 21
231
−215 231
−215
225 + 231 25 + 225 + 231 25 + 211 + 216 +225 + 231 −2 + 25 + 225 + 231 1 + 26 + 28 + 29 + 231 −216 − 220 + 231 −26 − 227 + 231 215 − 217 − 223 + 231 1 + 26 + 231 212 + 231 231 −27 − 213 + 231 224 + 231 231 23 + 215 + 231 −229 + 231 231 231 217 + 231 231 231 231
231 231 ... ... −215 231 231 231 231 31 2 231 231 ... ... 231 231 31 2 231 231 ... ... 231 231 231 −215
aa0 [32], dd0 [26, 32] cc0 [−26, 27, 32], bb0 [26, −32] a1 [26, −32] d1 [6, 26, −32] c1 [−6, −7, 8, −12, 13, -17,. . . ,-21,22,-26,. . . ,-30,31,-32] b1 [2, 3, 4, −5, 6, −26, 27, −32] a2 [1, −7, 8, 9, −10, −11, −12, 13, 32] d2 [17, −18, 21, −22, 32] c2 [7, 8, 9, −10, 28, −29, −32] b2 [−16, 17, −18, 24, 25, 26, −27, −32] a3 [−1, 2, −7, −8, −9, 10, −32] d3 [13, −32] c3 [−32] b3 [−8, 14, 15, 16, 17, 18, 19, −20, −32] a4 [−25, . . . , −30, 31, 32] d4 [32] c4 [4, 16, 32] b4 [−30, 32] a5 [32] d5 [32] c5 [18, 32] b5 [32] a6 [32] d6 [32] c6 [32] b6 [32] a7 d7 c7 ... d9 c9 [∗32] d9 [∗32] a10 [∗32] d10 [∗32] c10 [∗32] ... a13 [32] d13 [−32] c13 [32] b13 [−32] ... c15 [32] b15 [32] a16 + aa0 = a16 + aa0 d16 + dd0 = d16 + dd0 c16 + cc0 = c16 + cc0 b16 + bb0 = b16 + bb0
Table 6. A Set of Sufficient Conditions for the Second Iteration Differential a1 d1
c1
b1
a2
d2
c2 b2 a3
d3 c3
b3 a4 d4 c4 b4 a5 d5 c5 b5 a6 − b 6 c9 , b12 a13 − b13 a14 − b14 a15 − b15 a16 d16 c16 b16
a1,6 = 0, a1,12 = 0, a1,22 = 1, a1,26 = 0, a1,27 = 1, a1,28 = 0, a1,32 = 1 d1,2 = 0, d1,3 = 0, d1,6 = 0, d1,7 = a1,7 , d1,8 = a1,8 , d1,12 = 1, d1,13 = a1,13 , d1,16 = 0, d1,17 = a1,17 , d1,18 = a1,18 , d1,19 = a1,19 , d1,20 = a1,20 , d1,21 = a1,21 , d1,22 = 0, d1,26 = 0, d1,27 = 1, d1,28 = 1, d1,29 = a1,29 , d1,30 = a1,30 , d1,31 = a1,31 , d1,32 = 1 c1,2 = 1, c1,3 = 1, c1,4 = d1,4 , c1,5 = d1,5 , c1,6 = 1, c1,7 = 1, c1,8 = 0, c1,9 = 1, c1,12 = 1, c1,13 = 0, c1,17 = 1, c1,18 = 1, c1,19 = 1, c1,20 = 1, c1,21 = 1, c1,22 = 0, c1,26 = 1, c1,27 = 1, c1,28 = 1, c1,29 = 1, c1,30 = 1, c1,31 = 0, c1,32 = 1 b1,1 = c1,1 , b1,2 = 0, b1,3 = 0, b1,4 = 0, b1,5 = 1, b1,6 = 0, b1,7 = 0, b1,8 = 0, b1,9 = 0, b1,10 = c1,10 , b1,11 = c1,11 , b1,12 = 0, b1,13 = 0, b1,17 = 0, b1,18 = 0, b1,19 = 1, b1,20 = 0, b1,21 = 0, b1,22 = 0, b1,26 = 1, b1,27 = 0, b1,28 = 1, b1,29 = 1, b1,30 = 1, b1,31 = 0, b1,32 = 1 a2,1 = 0, a2,2 = 0, a2,3 = 0, a2,4 = 0, a2,5 = 1, a2,6 = 0, a2,7 = 1, a2,8 = 0, a2,9 = 0, a2,10 = 1, a2,11 = 1, a2,12 = 1, a2,13 = 0, a2,17 = 1, a2,18 = 1, a2,19 = 1, a2,20 = 1, a2,27 = 0, a2,28 = 1, a2,29 = 0, a2,30 = 0, a2,21 = 0, a2,22 = 1, a2,31 = 1, a2,32 = 0 d2,1 = 0, d2,2 = 1, d2,3 = 1, d2,4 = 0, d2,5 = 1, d2,6 = 0, d2,7 = 1, d2,8 = 0, d2,9 = 0, d2,10 = 0, d2,11 = 1, d2,12 = 1, d2,13 = 0, d2,17 = 0, d2,18 = 1, d2,21 = 0, d2,22 = 1, d2,26 = 0, d2,27 = 1, d2,28 = 0, d2,29 = 0, d2,32 = 0 c2,1 = 1, c2,7 = 0, c2,8 = 0, c2,9 = 0, c2,10 = 1, c2,11 = 1, c2,12 = 1, c2,13 = 1, c2,16 = d2,16 , c2,17 = 1, c2,18 = 0, c2,21 = 0, c2,22 = 0, c2,24 = d2,24 , c2,25 = d2,25 , c2,26 = 1, c2,27 = 1, c2,28 = 0, c2,29 = 1, c2,32 = 1 b2,1 = 0, b2,2 = c2,2 , b2,7 = 1, b2,8 = 1, b2,9 = 1, b2,10 = 1, b2,16 = 1, b2,17 = 0, b2,18 = 1, b2,21 = 1, b2,22 = 1, b2,24 = 0, b2,25 = 0, b2,26 = 0, b2,27 = 1, b2,28 = 0, b2,29 = 0, b2,32 = 1 a3,1 = 1, a3,2 = 0, a3,7 = 1, a3,8 = 1, a3,9 = 1, a3,10 = 0, a3,13 = b2,13 , a3,16 = 0, a3,17 = 1, a3,18 = 0, a3,24 = 0, a3,25 = 0, a3,26 = 0, a3,27 = 1, a3,28 = 1, a3,29 = 1, a3,32 = 1 d3,1 = 0, d3,2 = 0, d3,7 = 1, d3,8 = 1, d3,9 = 1, d3,10 = 1, d3,13 = 0, d3,16 = 1, d3,17 = 1, d3,18 = 1, d3,19 = 0, d3,24 = 1, d3,25 = 1, d3,26 = 1, d3,27 = 1, d3,32 = 1 c3,1 = 1, c3,2 = 1, c3,7 = 1, c3,8 = 1, c3,9 = 1, c3,10 = 1, c3,13 = 0, c3,14 = d3,14 , c3,15 = d3,15 , c3,16 = 1, c3,17 = 1, c3,18 = 0, c3,19 = 1, c3,20 = d3,20 , c3,32 = 1 b3,8 = 1, b3,13 = 1, b3,14 = 0, b3,15 = 0, b3,16 = 0, b3,17 = 0, b3,18 = 0, b3,19 = 0, b3,20 = 1, b3,25 = c3,25 , b3,26 = c3,26 , b3,27 = c3,27 , b3,28 = c3,28 , b3,29 = c3,29 , b3,30 = c3,30 , b3,31 = c3,31 , b3,32 = 1 a4,4 = 1, a4,8 = 0, a4,14 = 1, a4,15 = 1, a4,16 = 1, a4,17 = 1, a4,18 = 1, a4,19 = 1, a4,20 = 1 a4,25 = 1, a4,26 = 1, a4,27 = 1, a4,28 = 1, a4,29 = 1, a4,30 = 1, a4,31 = 0, a4,32 = 0 d4,4 = 1, d4,8 = 1, d4,14 = 1, d4,15 = 1, d4,16 = 1, d4,17 = 1, d4,18 = 1, d4,19 = 0, d4,20 = 1 d4,25 = 0, d4,26 = 0, d4,27 = 0, d4,28 = 0, d4,29 = 0, d4,30 = 0, d4,31 = 1, d4,32 = 0 c4,4 = 0, c4,16 = 0, c4,25 = 1, c4,26 = 0, c4,27 = 1, c4,28 = 1, c4,29 = 1, c4,30 = 1 c4,31 = 1, c4,32 = 0 b4,30 = 1, b4,32 = 0 a5,4 = b4,4 , a5,16 = b4,16 , a5,18 = 0, a5,32 = 0 d5,18 = 1, d5,30 = a5,30 , d5,32 = 0 c5,18 = 0, c5,32 = 0 b5,32 = 0, a6,18 = b5,18 , a6,32 = 0, d6,32 = 0, c6,32 = 0, b6,32 = c6,32 + 1 φ34,32 = 1, b12,32 = d12,32 , a13,32 = c12,32 , d13,32 = b12,32 + 1, c13,32 = a13,32 , b13,32 = d13,32 a14,32 = c13,32 , d14,32 = b13,32 , c14,32 = a14,32 , b14,32 = d14,32 a15,32 = c14,32 , d15,32 = b14,32 , c15,32 = a15,32 , b15,32 = d15,32 + 1 a16,26 = 1, a16,32 = c15,32 d16,26 = 1,d16,32 = b15,32 c16,26 = 1,c16,32 = a16,32 b16,26 = 1
Related Documents
1512
December 2019 30
1512
December 2019 10
Vinod 1512
May 2020 7
1512-002
December 2019 15
1512-s
April 2020 5
