MD5 Collision Source Code Released

SiliconEntity writes "The crypto world was shaken to its roots last year with the announcement of a new algorithm to find collisions in the still widely-used MD5 hash algorithm. Despite considerable work and commentary since then, no source code for finding such collisions has been published. Until today! Patrick Stach has announced the availability of his source code for finding MD5 collisions and MD4 collisions (Coral cache links provided to prevent slashdotting). MD4 collisions can be found in a few seconds (but nobody uses that any more), while MD5 collisions (still being used!) take 45 minutes on a 1.6 GHz P4. At last we will be able to implement various attacks which have been purely hypothetical until now. This more than anything should be the final stake in the heart of MD5, now that anyone can generate collisions whenever they want."

Comments

So what the hell do I do now?

[jeblucas]

I'm essentially crypto ignorant. About all I've known to do was verify MD5 hashes on downloads. Now that this is by-and-large pointless, how to check the veracity of things like Linux ISO's, video drivers, etc, ad inifintum?

You can spoof (almost) arbitrary documents!

[ChaosDiscord]

Maybe I misunderstand but as I understand it MD5s are normally used in a checksum manner to sign or provide a fingerprint of a document. If you have an original document and compute it's MD5 then it can match some certified MD5 check sum. If someone were to generate a fake document they coul dnot design it to match the MD5 fingerprint. They could create some bit of gibberish that did match it but not a document that was useful as a forgery.

Most document formats have lots of "dead space", parts you can pretty much modify at will without changing what the user actually sees. Comments in HTML or PostScript. Old junk data in Word documents. Executables can have just about anything you like added if you know your stuff. The MD5 attacks currently available only 128 "dead space" bytes to generate a collision. So far from being a gibberish document, one can generate almost any document you want. This page has a simple example with PostScript files. Both files have the same MD5 hash, but one is a relatively harmless letter of recommendation while the other is a grant of security clearance. Get your boss to sign your letter of recommendation digitally, swap in the security clearance file, and pass it on. This is a Big Deal and a Major Problem.

Re:Q and A

[CodeRx]

sha1(md5($password . '¥1i9k') . 'a-thirty-five-ch4racter-l0ng-str1ng' . md5($password))

This is a very bad password salting scheme and vulnerable to a dictionary attack. Once I have your database and salts, I can run a dictionary of common passwords through your scheme and crack any weak passwords.

You can make things much harder by having your salt change for each password - include the username for example. Now I have to run my entire dictionary through the sha/md5 function for each user. By doing this, you make the attack O(m*n) instead of O(m) (where m = the number of words in my dictionary and n = the number of users).

And as you mentioned in a follow up post, this code only generates documents with identical md5 sums, it does not generate a document with a given sum. So MD5 is broken for document signing and the like, but secure for password hashing for the time being.