Generate Your Own MD5 Collisions In Under a Minute

[LLXX]

Let me begin this post by quoting myself:

Quote:

Posted by LLXX @ 09-27-2005, 03:32 AM And a few years ago we all thought it was impossible to generate MD5 collisions within a short amount of time. I predict that within the next few years MD5 will be as secure as CRC32 is today, with the speed of computer hardware increasing at its present rate. What would really be interesting would be arbitary binary data that MD5'd to some 16-byte long ASCII message. However at the moment it is still nearly impossible to reverse MD5. All we can do is generate collisions quickly.

My prediction seems to be correct

Frodevitoyem: http://eprint.iacr.org/2006/104.pdf
Poter omgpet: http://eprint.iacr.org/2006/105.pdf

The method of generating the collisions is by "bit tunneling", and looks obscure at first but after a few days of pondering the ephiphany is reached and you'll probably be thinking "why didn't I think of that?" like I am right now... the technique is simply to adjust various bits in the data so that the changes cancel each other, resulting in the same hash. Finding those critical bits is where "tunneling" process is used.

*nix source: http://web.mit.edu/AFS/sipb/project/fastcoll/
win32 source: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5_source.zip
win32 binary: http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip

Attached is an example of two little files with the same MD5 (hash them yourself if you don't believe )

[dELTA]

Nice, thanks for the info.

[mylo]

Quote:

[Originally Posted by LLXX;65694]Let me begin this post by quoting myself: My prediction seems to be correct

While interesting, I think that implying that MD5 is as "broken" as CRC32 is a bit premature. It's possible - under some limited conditions to generate two files with the same MD5 hash.

However it's still not practical to, for any given file, generate another file that hashes to the same MD5 value.

i.e. you may not find it any easier to generate a file with the MD5 value "5ccd8b8c6e6ae27dd2ceb62a3d99343e" than you did before discovering this attack.

[0xf001]

hi,

i follow the md5 attacks, too, over the years. i remember the demonstrations with the signatures of pdf files. the collisions are "just collisions", so the impact is only in some cases valuable/"useable"

i don't think md5 can be cracked "within the next years", but things like the collision attacks show that the effort is going somewhere and enable us things we didnt think they are possible, so ... i watch for further surprises ...

the links are _very_ good, thank you LLXX!

cheers, 0xf001

[0xf001]

hi,

i just looked the link up for completeness, as they are so nice documents :

How to Break MD5 and Other Hash Functions
Xiaoyun Wang and Hongbo Yu
http://www.infosec.sdu.edu.cn/paper/md5-attack.pdf

and
Colliding X.509 Certificates
Arjen Lenstra1,2 , Xiaoyun Wang3 , and Benne de Weger2
http://www.win.tue.nl/~bdeweger/CollidingCertificates/CollidingCertificates.pdf

from http://www.woodmann.com/forum/showpost.php?p=47633&postcount=4

regards, 0xf001

[gera]

If you are interested, here's a nice post about some colliding .EXEs with same crc32, and more than just 2 colliding files (8 files with same MD5).

http://hexale.blogspot.com/2005/12/taking-advantage-of-md5-for-real.html

If anybody is interested in details of this constructs, let me know

[Shub-nigurrath]

well, interested for sure. Post it or PM ..

[LLXX]

Of course you can have more than 2 files with the same MD5, just generate multiple copies of the second collision block (which is generated randomly within certain constraints -- to satisfy the hash of the first).

[gera]

yes, that's one way. What I'm doing is different.

As the method allows for generating collisions on an arbitrary IV, what I do is take the MD5 of the first block and use that as IV to generate a collision. This way, generating 2 collisions give me 4 colliding files. In general, this can be chained, and the method gives 2^n colliding files generating n collisions.

At one point I had generated 128 chained collisions, what would gave me 2^128 colliding files. Of course I did not generate the 2^128 files, because I son't have enough storage

This scheme could be used to encode 128 bits of information, and all the different possibilities would have the same MD5. (for example, to leave messages somewhere where the integrity is checked using MD5)

[gera]

Quote:

[Originally Posted by Shub-nigurrath;66253]well, interested for sure. Post it or PM ..

specifically what do you want more info on?
if it's a general question, I may be able to give you some links to follow,
but I could try to answer a more specific question inline