[cryptography] New result on MD5 collisions

Francois Grieu fgrieu at gmail.com
Thu Dec 30 04:12:49 EST 2010


There is a new result on MD5 collisions: it is feasible
for 512 bit messages (instead of 1024 previously [*])

http://eprint.iacr.org/2010/643
Construct MD5 Collisions Using Just A Single Block Of Message
Tao Xie and Dengguo Feng


The example given is for the two distinct 64-byte messages

0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c87
40cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef

0e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c87
40cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef

which both hash to   cee9a457e790cf20d4bdaa6d69f01e41
and differ in 2 bits only.

The method is withheld for untold "security reasons", and a
cash prize of $10000 is announced for another example.

The differential used was previously published in a paper by the
same authors, but exploiting it was then an open problem.
http://eprint.iacr.org/2009/223


  Francois Grieu


[*] the first collision published was in
http://eprint.iacr.org/2004/199
Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD
Xiaoyun Wang and Dengguo Feng and Xuejia Lai and Hongbo Yu

exhibiting the two distinct 128-byte messages

d131dd02c5e6eec4693d9a0698aff95c2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a085125e8f7cdc99fd91dbdf280373c5b
960b1dd1dc417b9ce4d897f45a6555d535739ac7f0ebfd0c3029f166d109b18f
75277f7930d55ceb22e8adba79cc155ced74cbdd5fc5d36db19b0ad835cca7e3

d131dd02c5e6eec4693d9a0698aff95c2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a085125e8f7cdc99fd91dbd7280373c5b
960b1dd1dc417b9ce4d897f45a6555d535739a47f0ebfd0c3029f166d109b18f
75277f7930d55ceb22e8adba794c155ced74cbdd5fc5d36db19b0a5835cca7e3

which both hash to   a4c0d35c95a63a805915367dcfe6b751
and differ in 6 bits, 3 per 512-bit block, with the same
locations/differential in each block.




More information about the cryptography mailing list