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

Replacement Hash Functions

[Anonymous Coward]

Recommended replacements are SHA (preferably SHA-2), WHIRLPOOL and/or RIPEMD.

http://en.wikipedia.org/wiki/SHA-2
http://en.wikipedia.org/wiki/WHIRLPOOL
http://en.wikipedia.org/wiki/RIPEMD-160

Re:SHA1

[psykocrime]

So is SHA1 the recommended alternative?

No, see:

http://www.computerworld.com/securitytopics/securi ty/story/0,10801,99852,00.html

and

http://www.computerworld.com/softwaretopics/softwa re/story/0,10801,105875,00.html

I like this quote:

"SHA-1 is a wounded fish in shark-infested waters, but I'm more worried about MD5 because it's used everywhere," said Niels Ferguson, a cryptographer at Microsoft Corp. "Try to switch away from SHA-1 as quickly as you can, but switch away from MD5 first," he said when asked what recommendations he has regarding the algorithms during a panel discussion at the conference.

"broken" does not mean broken

[Edgewize]

This program is an efficient way to generate two source blocks with the same resulting MD5. This program does NOT allow you to match an arbitrary MD5 hash. That may come some day, but unless I've missed a very important paper somewhere, it has not happened yet.

This does not totally invalidate MD5 for verification. This attack still does not let you poison a torrent feed, etc, unless you are the author of the original source data and you engineered the data specifically to be vulnerable to this attack.

Re:So you found a collision, big deal

[Krischi]

See this: http://www.cits.rub.de/MD5Collisions/

It demonstrates the generation of two postscript files with the same MD5 hash that nevertheless display completely differently.

Re:SHA1

[Anonymous Coward]

No, MD5 and SHA1 were found to have better than brute-force attacks within a few months of each other.

Crypto people are recommending SHA-256 or SHA-512 which is only like SHA-1 in name.

Obviously check your the hash length beforehand and make sure your database column is wide enough.

When migrating existing hashes to the new hash be careful not to store the old hash anywhere -- that can be the weak link in the chain. For example, generating passwords and having the MD5 around lets attackers generate valid inputs and then try them against the more computationally complex hash. It gives them an approach to attacking your stronger hash.

Take a copy of your database and hash all the existing passwords into SHA-512 form, and you'll need some way of distinguishing the MD5-to-SHA512 hashes from the SHA512 hashes, so add a date column with todays date in it. Then write a function "hashString" as a wrapper that can identify when something was hashed, and go down a different branch of code based on that.

The first branch does MD5 then SHA512, the second branch does SHA512, and it does this based on the date column.

And, of course, re-salt both branches.

Re:SHA-1???

[poemofatic]

Huh? The SHA-2 family have been standardized, approved by NIST, and recommended by the NSA as part of their suite B for some time now. They are *much* more proven than Whirlpool and required for government use, whereas Whirlpool is not allowed for government use. Look at the SHA-512, SHA-384, SHA-256 CMVP instructions and validation lists before you say that NIST has not approved these hashes.

MOD ME DOWN

[swillden]

The parent comment, which I wrote, was based on a severe misunderstanding of the extent of the capability of the attack. In particular, I didn't realize that the attack could find collisions even with arbitrary, attacker-specified IVs. What that means is that it is indeed possible to generate x.509 certificates containing different keys but the same MD5 hash (and therefore the same signature). In fact, it's been done.