Verifying the results of:
Collisions for Hash Functions MD4, MD5, HAVAL-128 and Ripemd
By xiaoyun Wang, Dengguo Feng, Xuejia Lai, Hongbo Yu
(Available from
http://eprint.iacr.org/2004/199/)
Earlier Version of the Paper by Wang et All (AUG 16) Contained A Flaw
Which led to qustions WHETER OR NOT The Attack Is Real. The Bug HAS
Now (Aug 17, 2004) Been Fixed.
Note That The Paper Contains No Information About The Methods and
Algorithmics Used in the attack. my modely educated guess is there
Both Joux and the Chinese Group HAS Used The "neutral bit" and other
Techniques of Biham and Chen ("Near-Collisions of Sha-0", Crypto 2004)
To Improve Older Attacks. Thase Are Exciting Times in Hash Function
Cryptanalysis!
The New Paper Provides At Least One Real Collision for the MD5 Function
- Which I Have Extracted from the it. You can now Easily Check it TOO.
Consider these 128-byte Files, Which Only Difer in Six Bytes (in Fact)
THEIR Hamming Distance Is Only Six Bits, TOO:
File1.dat:
00000000 D1 31 DD 02 C5 E6 EE C4 69 3D 9A 06 98 AF F9 5C
00000010 2F CA B5 87 12 46 7e AB 40 04 58 3E B8 FB 7F 89
00000020 55 AD 34 06 09 F4 B3 02 83 E4 88 83 25 71 41 5A
00000030 08 51 25 E8 F7 CD C9 9F D9 1D BD F2 80 37 3C 5B
00000040 96 0B 1D D1 DC 41 7b 9c E4 D8 97 F4 5A 65 55 D5
00000050 35 73 9A C7 F0 EB FD 0C 30 29 F1 66 D1 09 B1 8F
00000060 75 277F 79 30 D5 5C EB 22 E8 AD BA 79 CC 15 5C
00000070 ED 74 CB DD 5F C5 D3 6D B1 9B 0A D8 35 CC A7 E3
MD5 (file1.dat) = A4C0D35C95A63A805915367DCFE6B751
File2.dat:
00000000 D1 31 DD 02 C5 E6 EE C4 69 3D 9A 06 98 AF F9 5C
00000010 2F CA B5 07 12 46 7e AB 40 04 58 3E B8 FB 7F 89
00000020 55 AD 34 06 09 F4 B3 02 83 E4 88 83 25 F1 41 5A00000030 08 51 25 E8 F7 CD C9 9F D9 1D BD 72 80 37 3C 5B
00000040 96 0B 1D D1 DC 41 7b 9c E4 D8 97 F4 5A 65 55 D5
00000050 35 73 9A 47 F0 EB FD 0C 30 29 F1 66 D1 09 B1 8F
00000060 75 27 7F 79 30 D5 5C EB 22 E8 AD BA 79 4C 15 5C
00000070 ED 74 CB DD 5F C5 D3 6D B1 9B 0A 58 35 CC A7 E3
MD5 (file2.dat) = a4c0d35c95a63a805915367dcfe6b751
ONCE You Have Downloaded Thase Files You CAN Easily Verify (in unix shell)
That this is indeed a collision for md5:
$ CMP file1.dat file2.dat
File1.dat file2.dat Differ: Char 20, Line 1
$ md5sum file1.dat
A4C0D35C95A63A805915367DCFE6B751 File1.dat
$ md5sum file2.dat
A4C0D35C95A63A805915367DCFE6B751 File2.dat
This Clearly Shows That The Resistance of MD5 Against Collision Attacks
IS Significantly Lower Than 2 ^ 64 Idicated by ITS 128-bit Digest. Since The
Attack Allows Free Selection of IV, THESE Attacks Mean That MD5 SHOULD
Not be used for any serious cryptographic purpose, NOTBRYPTOGRAPHIC PURPOSE.
Note for That Because MD5 is a chained hash function, you can generate an
Infinity of New Collisions from these by Simple Process of ConcateNation:
$ Echo 'Hello, World!'> Hello.txt
$ cat file1.dat Hello.txt | MD5SUM
158701224AEF36986648D9F0DFB0CA3C -
$ cat file2.dat hello.txt | MD5SUM
158701224AEF36986648D9F0DFB0CA3C -
Here the text "Hello, World!" HAS SIMPLY BEEN ATDED AT THE End of The
Previous Collisions.
Chem,
-MJOS
This File Was Written by Markku-juhani O. Saarinen <
Mjos@iki.fi> on Aug 17, 2004.
