Welcome to the new Woodmann RCE Messageboards Regroupment
Please be patient while the rest of the site is restored.

To all Members of the old RCE Forums:
In order to log in, it will be necessary to reset your forum login password ("I forgot my password") using the original email address you registered with. You will be sent an email with a link to reset your password for that member account.

The old vBulletin forum was converted to phpBB format, requiring the passwords to be reset. If this is a problem for some because of a forgotten email address, please feel free to re-register with a new username. We are happy to welcome old and new members back to the forums! Thanks.

All new accounts are manually activated before you can post. Any questions can be PM'ed to Kayaker.

Generate Your Own MD5 Collisions In Under a Minute

To discuss DES MD5 El-Gamal RSA PGP and others....
Locked
LLXX
Senior Member
Posts: 981
Joined: Wed Aug 17, 2005 8:37 pm

Generate Your Own MD5 Collisions In Under a Minute

Post by LLXX »

Let me begin this post by quoting myself:
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/fastcol ... source.zip
win32 binary: http://www.win.tue.nl/hashclash/fastcol ... .5.exe.zip

Attached is an example of two little files with the same MD5 (hash them yourself if you don't believe ;) )
Attachments
ex1.zip
(434 Bytes) Downloaded 581 times
[ ~Litana L.X. Xahanien~ ]
User avatar
dELTA
Posts: 4209
Joined: Mon Oct 30, 2000 7:00 am
Location: Ring -1

Post by dELTA »

Nice, thanks for the info. :yay:
"Give a man a quote from the FAQ, and he'll ignore it. Print the FAQ, shove it up his ass, kick him in the balls, DDoS his ass and kick/ban him, and the point usually gets through eventually."
mylo

Post by mylo »

LLXX wrote: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
Posts: 601
Joined: Thu Jul 29, 2004 11:00 am
Contact:

Post by 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" :devil:

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! :yay:

cheers, 0xf001
0xf001
Posts: 601
Joined: Thu Jul 29, 2004 11:00 am
Contact:

Post by 0xf001 »

hi,

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

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/Collidi ... icates.pdf

from showpost.php?p=47633&postcount=4

regards, 0xf001
gera
Junior Member
Posts: 14
Joined: Sat May 19, 2007 7:57 am

Post by 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/taki ... -real.html

If anybody is interested in details of this constructs, let me know
User avatar
Shub-nigurrath
Senior Member
Posts: 431
Joined: Mon May 10, 2004 2:00 pm
Location: Obscure Kadath

Post by Shub-nigurrath »

well, interested for sure. Post it or PM ..
(¯`·._.·[¯¨´*·~-.¸¸,.-~*´¨ Ŝħůβ¬Ňïĝµŕřāŧħ ₪¯¨´*·~-.¸¸,.-~*´¨]·._.·´¯)
There are only 10 types of people in the world: Those who understand binary, and those who don't
http://www.accessroot.com
LLXX
Senior Member
Posts: 981
Joined: Wed Aug 17, 2005 8:37 pm

Post by 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).
[ ~Litana L.X. Xahanien~ ]
gera
Junior Member
Posts: 14
Joined: Sat May 19, 2007 7:57 am

Post by 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
Junior Member
Posts: 14
Joined: Sat May 19, 2007 7:57 am

Post by gera »

Shub-nigurrath wrote: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
LaBBa
Senior Member
Posts: 177
Joined: Thu May 02, 2002 6:00 am

Post by LaBBa »

is there a tool that on a given hash (md5) it can create a data that will result same hash ?
reverser
Senior Member
Posts: 104
Joined: Tue May 23, 2006 11:36 am

Post by reverser »

dongs

Post by dongs »

LaBBa wrote:is there a tool that on a given hash (md5) it can create a data that will result same hash ?
That is known as a pre-image attack --- no attack is known for MD5 that would be faster than exhaustive search, i.e. about 2^127 tries.

However, in most cases there is extra information about how the hash was generated, e.g. derived from a password. Rainbow tables are useful in that case, or smart password bruteforcing (trying the most likely words/character combinations).
Locked