The following is her paper on the principle of cracking published in the International Cryptography Society.
Conflict of hash functions
Conflict of hash functions
MD4, MD5, HAVAL- 128 and RIPEMD
Wang Xiaoyun 1, Deng Guofeng 2, Lai 3, Yu Hongbo 1
School of Mathematics and System Science, Shandong University, Jinan 250 100, China 1
Institute of Software, Chinese Academy of Sciences, Beijing 100080
Department of Computer Science and Engineering, Shanghai Jiaotong University, China, Shanghai.
xywang@sdu.edu.cn 1
Revised on August 7, 2004/kloc-0.
1 MD5 conflict
MD5 is a hash function designed by Ron Rivest [9] and an enhanced version of MD4 [8]. At 1993 botden
Boer and Antoon Bosselaers [1] found the pseudo-conflict of MD5, which consists of two identical messages.
Initial values of different groups. H. Dobbertin[3] found a free start collision consisting of two different 5 12 bits.
Message with selected initial value of 0 v i.
ED BA x C B F x C B AC x A V I 763 4 0 D，97 62 5 0，34 1042 3 0x B，2375 12 0 : 0 0 0 0 0
Our attack can find many real conflicts between two 1024-bit messages and the original message.
Initial value of MD5 0 IV:
10325476 0，98 0，89 0 6745230 1 0 0:0 0 0 0 0 x D bad cfe x C xefcdab，B x A IV
) 0 , 2 ,..., 2 ,..., 2 , 0 , 0 , 0 , 0 ( , 3 1 15 3 1
1 1
) 0 , 2 ,..., 2 ,..., 2 , 0 , 0 , 0 , 0 ( , 3 1 15 3 1
2 2 C C N N i i
(Non-zero values at position 4, 1 1 and 14)
To such an extent
)，(5)，(5 i i N M MD N M MD。
On IBM P690, it takes about an hour to find such m and m, and then it only takes 15 seconds to 5.
Minutes to find i N and i N, so that (i N M and), (i N M will produce the same hash and the same value. Besides,
Our attack is valid for any given initial value.
The following are two pairs of conflicting 1024-bit messages. These two examples have the same1-st.
Half 5 12 position.
M
2dd 3 1d 1 C4 eee 6 c 5 69 a3d 69 5 cf 9 af 98 87 b5 ca 2f ab 7e 46 12 3e 580440 897 ffbb 8
634 ad 55 2b3f 409 8388 e 483 5a 4 17 125 e 8255 108 9 fc9 CDF 7 f2bd 1dd 9 5b3c 3780
X 1
N 1
d 1 1d0b 96 9c7b 4 1dc f 497 d8e 4d 555655 a c79a 7335 cf debf 0 66f 12930 8fb 109d 1
797 f 2775 eb5cd 530 baade 822 5c 15cc 79 ddcb 74 ed 6 DD 3c 55 f d 80 a9 bb 1 E3 a7 cc 35
M0
2dd 3 1d 1 C4 eee 6 c 5 69 a3d 69 5 cf 9 af 98 7 b5 ca 2f ab 7e 46 12 3e 580440 897 ffbb 8
634 ad 55 2b3f 409 8388 e 483 5a 4 1f 125 e 8255 108 9 fc9 CDF 7 72bd 1dd 9 5b3c 3780
X 1
N 1
d 1 1d0b 96 9c7b 4 1dc f 497 d8e 4d 555655 a 479 a 7335 cf debf 0 66f 12930 8fb 109d 1
797 f 2775 eb5cd 530 baade 822 5c 154 c 79 ddcb 74 ed 6 DD 3c 55 f 580 a9 bb 1 E3 a7 cc 35
h 9603 16 1f f 4 1 fc 7 ef 9 f 65 ffbc a 30 f 9 DBF
M
2dd 3 1d 1 C4 eee 6 c 5 69 a3d 69 5 cf 9 af 98 87 b5 ca 2f ab 7e 46 12 3e 580440 897 ffbb 8
634 ad 55 2b3f 409 8388 e 483 5a 4 17 125 e 8255 108 9 fc9 CDF 7 f2bd 1dd 9 5b3c 3780
X2
N2
3 13 e82d 8 5b8f 3456 d4ac 6 DAE c 6 19c 936 b4e 253 DD FD 03 da 87 6633902 A0 CD 48d 2
42339 Fe 9 e 87 e 570 f 70 b 654 ce 1 e0da 880 BC 2 198 c 6 9383 A8 b 6 2b 65 f 996 702 af 76f
M0
2dd 3 1d 1 C4 eee 6 c 5 69 a3d 69 5 cf 9 af 98 7 b5 ca 2f ab 7e 46 12 3e 580440 897 ffbb 8
634 ad 55 2b3f 409 8388 e 483 5a 4 1f 125 e 8255 108 9 fc9 CDF 7 72bd 1dd 9 5b3c 3780
3 13 e82d 8 5b8f 3456 d4ac 6 DAE c 6 19c 936 34e 253 DD FD 03 da 87 6633902 A0 CD 48d 2
42339 Fe 9 e87e 570 f 70 b 654 ce 1e0d 2880 BC 2 198 c 6 9383 A8 b 6 ab65f 996 702 af 76f
h8 d5e 70 19 6324 c 0 15 7 15 d6b 58 6 1804 e08
Two pairs of conflicts in table 1 MD5
Haval-128 two collisions
Harvard plans to be in [10]. HAVAL is a hashing algorithm that can compress 3,4.
And generate a fingerprint with the length of 128, 160, 192 or 224 bits.
P. R. Kasselman and W. T. penz horn[7] attacked the simplified version of Harvard.
It consists of the last rounds of Haval-128. We broke the Harvard-128 full, leaving only about 26 Harvard.
Calculate. Here we give two examples of Haval-128 collision, among which
) 0 ,..., 0 , 2 ,....2，0，0，0，2(，8 12 1
At position 0, 1 1, 18 and 3 1 have non-zero values, ... 2, 1, 0 i, so) () (m Haval m Haval.
M 1
6377448 b d 9 e 59 f 18 F2 aa 3c bb d6cb 92 ba ee 544 a 44 879 fa 576 1ca 34633 76 ca 5d 4 f
a 67 A8 a 42 8d 3 ADC 8 b b 6 e3d 8 14 5630998d 86 ea 5 DCD a 739 ae7b 54 fd8e 32 acbb2b 36
38 183 c9a b67a 9289 c 47299 b 2 27039 ee5 DD 555 e 14 8390 18d 8 aa bbd 9 c 9d 78fc 632
fff 4b 3a 7 400000096 7 f 466 AAC fffffbc 0 5f 40 16 D2 5f 40 16d 0 12 e2b 0 f 4307 f 87
M 1
6377488 b d 9 e 59 f 18 f 2 aa 3c bb d6cb 92 ba ee 544 a 44 879 fa 576 1ca 34633 76 ca 5d 4 f
a 67 A8 a 42 8d 3 ADC 8 b b 6 e3d 8 14d 630998d 86 ea 5 DCD a 739 ae7b 54 fd8e 32 acbb 2 b 36
38 183 c9a b67a 9289 c 47299 ba 27039 ee5 DD 555 e 14 8390 18d 8 aa bbd 9 c 9d 78fc 632
fff 4b 3a 7 400000096 7 f 466 AAC fffffbc 0 5f 40 16 D2 5f 40 16d 0 12 e2b 0 f 4307 f 87
h 95b 562 1c ca 628 17a a 48 dacd 8 6d2b 54 BF
The second part of money supply
6377448 b d 9 e 59 f 18 F2 aa 3c bb d6cb 92 ba ee 544 a 44 879 fa 576 1ca 34633 76 ca 5d 4 f
a 67 A8 a 42 8d 3 ADC 8 b b 6 e3d 8 14 5630998d 86 ea 5 DCD a 739 ae7b 54 fd8e 32 acbb2b 36
38 183 c9a b67a 9289 c 47299 b 2 27039 ee5 DD 555 e 14 8390 18d 8 aa bbd 9 c 9d 78fc 632
fff 4b 3a 7 400000096 7 f 466 AAC fffffbc 0 5f 40 16 D2 5f 40 16d 0 12 e2b 0 f5b 16963
6377488 b d 9 e 59 f 18 f 2 aa 3c bb d6cb 92 ba ee 544 a 44 879 fa 576 1ca 34633 76 ca 5d 4 f
a 67 A8 a 42 8d 3 ADC 8 b b 6 e3d 8 14d 630998d 86 ea 5 DCD a 739 ae7b 54 fd8e 32 acbb 2 b 36
38 183 c9a b67a 9289 c 47299 ba 27039 ee5 DD 555 e 14 8390 18d 8 aa bbd 9 c 9d 78fc 632
fff 4b 3a 7 400000096 7 f 466 AAC fffffbc 0 5f 40 16 D2 5f 40 16d 0 12 e2b 0 f5b 16963
h b0e 99492 d64eb 647 5 149 ef 30 4293733 c
Table 2 Two pairs of collisions, where i= 1 1, these two examples differ only in the last word.
Three conflicts of MD4
MD4 was designed by R. L. Rivest [8]. H. Dobbertin's attack in Eurocrypto'96[2] can be found with.
Probability 1/222. Our attack can be calculated by hand to find the collision, so that
)0，0，0，2，0，0，0，0，0，0，0，2 2，2，0(， 16 3 1 28 3 1 C C M M
And) (4) (4 mmmd mmmd.
M 1
4d 7 a9 c 83 56 CB 927 a b 9 d5a 578 57 a 7 a5 ee de 748 a3 c DCC 366 B3 b 683 a 020 3 B2 a5 d 9 f
c69d 7 1 B3 f9e 99 198 d79f 805 e a 63 bb 2e 8 45 dd8e 3 1 97e 3 1 Fe 5 2794 bf08 b 9 E8 c3e 9
M 1
4d 7 a9 c 83 d6cb 927 a 29 d5a 578 57 a7 a5 ee de 748 a3 c DCC 366 B3 b683a 020 3 B2 a5 d 9 f
c69d 7 1 B3 f9e 99 198 d79f 805 e a 63 bb 2e 8 45 dc8e 3 1 97e 3 1 Fe 5 2794 bf08 b 9 E8 c3e 9
h 5f5c 1a0d 7 1b 36046 1b 5435 da 9b0d 807 a
The second part of money supply
4d 7 a9 c 83 56 CB 927 a b 9 d5a 578 57 a 7 a5 ee de 748 a3 c DCC 366 B3 b 683 a 020 3 B2 a5 d 9 f
c69d 7 1 B3 f9e 99 198 d79f 805 e a 63 bb 2e 8 45 dd8e 3 1 97e 3 1 Fe 5 f 7 13c 240 a7b 8 cf 69
4d 7 a9 c 83 d6cb 927 a 29 d5a 578 57 a7 a5 ee de 748 a3 c DCC 366 B3 b683a 020 3 B2 a5 d 9 f
c69d 7 1 B3 f9e 99 198 d79f 805 e a 63 bb 2e 8 45 dc8e 3 1 97e 3 1 Fe 5 f 7 13c 240 a7b 8 cf 69
h e0f 76 122 c 429 c 56c ebb 5 e 256 b 809793
Two pairs of collisions in table MD4
Four conflicts in RIPEMD
RIPEMD was developed for the RIPE project (Race Integrity Primitives Evaluation, 1988- 1992). In ...
1995, H. Dobbertin proved that the reduced version of RIPEMD with two wheels is not collision-free [4]. We show
The complete RIPEMD is not conflict-free. The following are two pairs of conflicts in RIPEMD:
)2，0，0，0，0，2 2，0，0，0，0，0，0，2，0，0，0，0(，3 1 3 1 1 20 ' C C M M I
M 1
579 faf8e 9 ECF 579 574 a6 ABA 784 135 1 1 a2b 4 10 a4 ad 2 f 6 c 9 f b 56202 c 4d 7579 1 1
bde aae 7 78 BC 9 1 F2 47 BC 6d 7d 9 abdd 1 a45d 20 15 8 17 104 ff 264758 A8 6 1064 ea 5
M 1
579 faf8e 9 ECF 579 574 a6 ABA 785 135 1 1 a2b 4 10 a4 ad 2 f 6 c 9 f b 56202 c 4d 7579 1 1
bde aae 7 78 BC 9 1 F2 c 7c 06d 7d 9 abdd 1 a45d 20 15 8 17 104 ff 264758 A8 e 1064 ea 5
h 1 fab 152 1654 a 3 1b 7a 33776 a 9e 968 ba 7
The second part of money supply
579 faf8e 9 ECF 579 574 a6 ABA 784 135 1 1 a2b 4 10 a4 ad 2 f 6 c 9 f b 56202 c 4d 7579 1 1
bde aae 7 78 BC 9 1 F2 47 BC 6d 7d 9 abdd 1 a45d 20 15 a0a 504 ff b 18d 58 a 8 e 70 c 66 b 6
579 faf8e 9 ECF 579 574 a6 ABA 785 135 1 1 a2b 4 10 a4 ad 2 f 6 c 9 f b 56202 c 4d 7579 1 1
bde aae 7 78 BC 9 1 F2 c 7c 06d 7d 9 abdd 1 a45d 20 15 a0a 504 ff b 18d 58 a 8 670 c66b 6
h 1f2c 159 f 569 b 3 1 a6 dfcaa 5 1a 25665 d24
The collision of table RIPEMD
5 Remarks
In addition to the above hash functions we cracked, there are some other hash functions that do not have ideal security. for
For example, the conflict of SHA-0 [6] can be found by about 240 calculations of SHA-0 algorithm and one conflict.
For Haval-160, it can be found with the probability 1/232.
Note that the message and all other values in this article consist of 32-bit words, and each 32-bit word
The leftmost byte is the most significant byte.
1 B. den Boer, Antoon Bosselaers, collision of MD5 contractive functions, Eurocrypto, 93.
2 H. Dobbertin, Cryptanalysis of MD4, Fast Software Encryption, LNCS 1039, D., springer Publishing House, 1996.
3 H. Dobbertin, Cryptanalysis of MD5 Compression, presented at the rump Conference of EurocrZpt'96.
4 Hans Dobbertin, RIPEMD with two-wheel compression function is not collision-free, Journal of Cryptography 10( 1),
1997.
5 H. Dobbertin, A. Bosselaers, B. Preneel, "RIPPMEMD-160: Enhanced version of RIPPMMD", Fast.
Software encryption, LNCS 1039, edited by D.Gollmann. , springer Publishing House, 1996, page 7 1-82.
6 FIPS 180- 1, secure hash standard, NIST, U.S. Department of Commerce, Washington, D.C., zip code: 1995.
7 Wang Xiaoming, Wang Xiaoming, Li Xiaoming, Computer Cryptanalysis, 2000, 1 1(2)
Letters, 2000.
8 R.L. Riverst, MD4 Message Digest Algorithm, Draft for Comment (RFC) 1320, Internet Activities.
Committee of Internet Privacy Working Group, April 1992.
9 R. L Rivest, MD5 message digest algorithm, Exposure Draft (RFC) 132 1, Internet activities.
Council of Internet Privacy Working Group, April 1992.3
10 Y. Zheng, J. Pieprzyk, J. Seberry, HAVAL-A one-way hash algorithm with variable output length,
Auscrypto in' 92