[Translation] Wang Xiaoyun Paper: Collision in Hatt Functions
Hatches (Hash) Functions MD4, MD5, HAVAL-128 and RIPEMD
Original: wang xiaoyun feng dengguo lai xuejia yu hongbo [because of the specific names, inconvenience in Chinese] (China University of Ji Shandong University 250100, China, Beijing China Science Research Institute Software Software Association 100080, Shanghai Shanghai Jiaotong University Computer Science and Mechanical Ministry) XYWANG@sdu.edu.cn Original: Favorites Translation: Lover_P
1 MD5 collision
MD5 is designed by Ron Rivest [9], which is the enhancement version of MD4 [8]. In 1993, Bert Den Boer and Antoon Bosselaers [1] found a pseudo collision of the MD5 algorithm, which has the same message from two sets of initial worths. H. Dobbertin [3] found a collision of a single state, which consists of two different 512-bit messages obtained by a given initial value IV0 '.
IV0 ': A0' = 0x12AC2375, B0 '= 0x3b341042, C0' = 0x5f62b97c, d0 '= 0xba763ed
Our attack can find a lot of two 1024-bit MD5 messages with the same original initial value IV0:
IV0: A0 = 0x67452301, b0 = 0xefcdab89, c0 = 098badefd, d0 = 0x10325476
M '= m ΔC1, ΔC1 = (0, 0, 0, 0, 231, ..., 215, ..., 231, 0)
Ni '= Ni ΔC2, ΔC2 = (0, 0, 0, 0 231, ..., -215, ..., 231, 0)
(Location 4, 11 and 14 non-zero)
at this time,
MD5 (M, Ni) = MD5 (M ', Ni')
On IBM P690, you can find such M and M 'for nearly an hour, and then Ni and Ni' can be found in 15 seconds to 5 minutes, at this time (M, Ni) and ( M ', ni') will produce the same hash value. In addition, our attacks can work in any given initial value.
Below is a two-pair of 1024-bit messages that generate collisions, which have the same first half 512 bits.
X1M2dd31d1 c4eee6c5 69a3d69 5cf9af98 87b5ca2f ab7e4612 3e580440 897ffbb8634ad55 2b3f409 8388e483 5a417125 e8255108 9fc9cdf7 f2bd1dd9 5b3c3780N1d11d0b96 9c7b41dc f497d8e4 d555655a c79a7335 cfdebf0 66f12930 8fb109d1797f2775 eb5cd530 baade822 5c15cc79 ddcb74ed 6dd3c55f d80a9bb1 e3a7cc35X1'M'2dd31d1 c4eee6c5 69a3d69 5cf9af98 7b5ca2f ab7e4612 3e580440 897ffbb8634ad55 2b3f409 8388e483 5a41f125 e8255108 9fc9cdf7 72bd1dd9 5b3c3780N1d11d0b96 9c7b41dc f497d8e4 d555655a 479a7335 cfdebf0 66f12930 8fb109d1797f2775 eb5cd530 baade822 5c154c79 ddcb74ed 6dd3c55f 580a9bb1 e3a7cc35H9603161f f41fc7ef 9f65ffbc a30f9dbfX2M2dd31d1 c4eee6c5 69a3d69 5cf9af98 87b5ca2f ab7e4612 3e580440 897ffbb8634ad55 2b3f409 8388e483 5a417125 e8255108 9fc9cdf7 f2bd1dd9 5b3c3780N2313e82d8 5b8f3456 d4ac6dae c619c936 b4e253dd fd03da87 6633902 a0cd48d242339fe9 e87e570f 70b654ce 1e0da880 bc2198c6 9383a8b6 2b65f996 702af76fX2'M'2dd31d1 c4eee6c5 69a3d69 5cf9af98 7b5ca2f AB7E4612 3E580440 897FFBB8634AD55 2B3F409 8388E483 5A41F125 E825 5108 9fc9cdf7 72bd1dd9 5b3c3780N2313e82d8 5b8f3456 d4ac6dae c619c936 34e253dd fd03da87 6633902 a0cd48d242339fe9 e87e570f 70b654ce 1e0d2880 bc2198c6 9383a8b6 ab65f996 702af76fH8d5e7019 6324c015 715d6b58 61804e08 Table 1 MD5 collision of two pairs
2 collisions in HAVAL-128
Haval is also within the proposal [10]. Haval is also a hash algorithm that produces a length of 128, 160, 192 or 224-bit lengths through 3, 4 or 5 overhead, through a message of any length.
A simplified version of Haval is given by P. R. Kasselman and W. T. Penzhorn [7], which consists of the last round of HAVAL-128 (abstract). And we only destroy the entire HAVAL-128 algorithm by approximately 26 HAVAL calculations. Here we give two examples of HAVAL-128 collision, including
M '= m ΔC, ΔC = (2i-1, 0, 0, 0, 2i-12, ..., 2i-8, 0, ..., 0)
Since the position 0, 11, 18 is non-zero, and I = 0, 1, 2, ..., 31, Haval (m) = HAVAL (M ').
M16377448b d9e59f18 f2aa3cbb d6cb92ba ee544a44 879fa576 1ca34633 76ca5d4fa67a8a42 8d3adc8b b6e3d814 5630998d 86ea5dcd a739ae7b 54fd8e32 acbb2b3638183c9a b67a9289 c47299b2 27039ee5 dd555e14 839018d8 aabbd9c9 d78fc632fff4b3a7 40000096 7f466aac fffffbc0 5f4016d2 5f4016d0 12e2b0 f4307f87M1'6377488b d9e59f18 f2aa3cbb d6cb92ba ee544a44 879fa576 1ca34633 76ca5d4fa67a8a42 8d3adc8b b6e3d814 d630998d 86ea5dcd a739ae7b 54fd8e32 acbb2b3638183c9a b67a9289 c47299ba 27039ee5 dd555e14 839018d8 aabbd9c9 d78fc632fff4b3a7 40000096 7f466aac fffffbc0 5f4016d2 5f4016d0 12e2b0 f4307f87H95b5621c ca62817a a48dacd8 6d2b54bfM26377448b d9e59f18 f2aa3cbb d6cb92ba ee544a44 879fa576 1ca34633 76ca5d4fa67a8a42 8d3adc8b b6e3d814 5630998d 86ea5dcd a739ae7b 54fd8e32 acbb2b3638183c9a b67a9289 c47299b2 27039ee5 dd555e14 839018d8 aabbd9c9 d78fc632fff4b3a7 40000096 7f466aac fffffbc0 5f4016d2 5f4016d0 12e2b0 f5b16963M2'6377488b d9e59f18 f2aa3cbb d6cb92ba ee544a44 879fa576 1ca34633 76ca5d4fa67a8a42 8d3adc8b B6E3D814 D630998D 8 6ea5dcd a739ae7b 54fd8e32 acbb2b3638183c9a b67a9289 c47299ba 27039ee5 dd555e14 839018d8 aabbd9c9 d78fc632fff4b3a7 40000096 7f466aac fffffbc0 5f4016d2 5f4016d0 12e2b0 f5b16963Hb0e99492 d64eb647 5149ef30 4293733c Table 2 two collision, where i = 11 different and only the last two examples a word
3 md4 collision
MD4 is designed by R. L. Rivest [8]. H. Dobbertin Attack [2] can find a collision of 1/222 probability. Our attack can find a collision through its hand, such as:
M '= m ΔC, ΔC = (0, 231, -228 231, 0, 0, 0, 0, 0, 0, 0, 0, 0, -216, 0, 0, 0)
And MD4 (M) = MD4 (M ').
M14d7a9c83 56cb927a b9d5a578 57a7a5ee de748a3c dcc366b3 b683a020 3b2a5d9fc69d71b3 f9e99198 d79f805e a63bb2e8 45dd8e31 97e31fe5 2794bf08 b9e8c3e9M1'4d7a9c83 d6cb927a 29d5a578 57a7a5ee de748a3c dcc366b3 b683a020 3b2a5d9fc69d71b3 f9e99198 d79f805e a63bb2e8 45dc8e31 97e31fe5 2794bf08 b9e8c3e9H5f5c1a0d 71b36046 1b5435da 9b0d807aM24d7a9c83 56cb927a b9d5a578 57a7a5ee de748a3c dcc366b3 b683a020 3b2a5d9fc69d71b3 f9e99198 d79f805e a63bb2e8 45dd8e31 97e31fe5 f713c240 a7b8cf69M2'4d7a9c83 d6cb927a 29d5a578 57a7a5ee de748a3c dcc366b3 b683a020 3b2a5d9fc69d71b3 f9e99198 d79f805e a63bb2e8 45dc8e31 97e31fe5 f713c240 a7b8cf69He0f76122 c429c56c ebb5e256 b809793 table 3 MD4 collision of two pairs
4 collisions in ripemd
RIPEMD was developed by RIPE project (RACE INTEGRITY Primitives Evalustion, 1988-1992). In 1995, the H. Dobbertin provided only two rounds (abstract) RIPEMD simplified version [4] did not collide. And we found that the complete RIPEMD is not collisted. Below is the two pairs of collisions of RIPEMD:
Mi '= mi ΔC, ΔC = (0, 0, 0, 220, 0, 0, 0, 0, 0, 0, 218 231, 0, 0, 0, 0, 231)
M1579faf8e 9ecf579 574a6aba 78413511 a2b410a4 ad2f6c9f b56202c 4d757911bdeaae7 78bc91f2 47bc6d7d 9abdd1b1 a45d2015 817104ff 264758a8 61064ea5M1'579faf8e 9ecf579 574a6aba 78513511 a2b410a4 ad2f6c9f b56202c 4d757911bdeaae7 78bc91f2 c7c06d7d 9abdd1b1 a45d2015 817104ff 264758a8 e1064ea5H1fab152 1654a31b 7a33776a 9e968ba7M2579faf8e 9ecf579 574a6aba 78413511 a2b410a4 ad2f6c9f b56202c 4d757911bdeaae7 78bc91f2 47bc6d7d 9abdd1b1 a45d2015 a0a504ff b18d58a8 e70c66b6M2'579faf8e 9ecf579 574a6aba 78513511 A2B410A4 AD2F6C9F B56202C 4D757911BDEAAE7 78BC91F2 C7C06D7D 9ABDD1B1 A45D2015 A0A504FF B18D58A8 670C66B6H1F2C159F 569B31A6 DFCAA51A 25665D 24
Table 4 Collision in RIPEMD
5 note
In addition to several hash functions we destroyed above, some other hash functions do not have ideal security. For example, the collision of SHA-0 [6] can be found by approximately 240 SHA-0, and a collision of a probability of HAVAL-160 is also a 50232. Note that all messages and other values in this report are in 32-bit, and the leftmost byte of each 32-bit word is a key byte (the translation: the big tail method representation).
1 B. den Boer, Antoon Bosselaers, Collisions for the Compression Function of MD5, Eurocrypto, 93.2 H. Dobbertin, Cryptanalysis of MD4, Fast Software Encryption, LNCS 1039, D., Springer-Verlag, 1996.3 H. Dobbertin, Cryptanalysis of MD5 compress, presented at the rump session of EurocrZpt'96.4 Hans Dobbertin, RIPEMD with Two-round Compress Function is Not Collision-Free, J. Cryptology 10 (1), 1997.5 H. Dobbertin, A. Bosselaers, B. Preneel, "RIPMEMD -160: a StrengThened Version of Ripmmd, "Fast Software Encrzption, LNCS 1039, D. Gollmann, Ed., Springer-Verlag, 1996, PP. 71-82.6 FIPS 180-1, Secure Hash Standard, Nist, US Department of Commerce , Washington DC, April 1995.7 PR Kasselman, WT Penzhorn, Cryptananlysis od reduced version of HAVAL, Vol. 36, No. 1, Electronic Letters, 2000.8 RL Rivest, The MD4 Message Digest Algorithm, Request for Comments (RFC) 1320, Internet Activities Board, Internet Privacy Task Force, April 1992.9 R. L Rivest, The MD5 Message Digest Algorithm, Request for Comments (RFC) 1321, Internet Activities Board, Internet PrivacZ Task Force, April 1992.3RIPEMD-128110 Y. Zheng, J. Pieprzyk, J. Seberry, HAVAL - A One-way Hashing Algorithm with Variable Length of Output, Auscrypto '92.
