Efficient collision generation for MD4 and MD5

Patrick Stach has announced a new implementation of an MD4/5 collision generation algorithm that can generate MD4 collisions instantaneously and MD5 collisions in under an hour on commodity hardware. MD4 hasn’t been considered to be secure in a while, but MD5 is a mainstay of digital signatures, IPSEC, and tons of other security applications.

The practical implications of this are easy enough: switch to SHA-1, now. Quit using MD5 for secure anything. Even if this attack turns out to be impractical (although it certainly looks reasonable), it’s still evidence that the aging hash is nearing its end. [Update: even if this code doesn’t work (still testing), the attack is very real.]

Patrick is a smart dude and he has been working on this problem for a while. Nice work, Pat!

UPDATE:: I have ported the code to windows; it builds with the .net DDK and is still running on a test box.

UPDATE 2: Matt Miller points out that SHA-1 has its own problems and should be regarded with great skepticism for its application in secure systems. Pat pointed out that there are possible attacks against SHA-256, 384, and 512, and that VSH is the only published algorithm he considers secure. Bruce Schneier doesn’t have much to say about it yet, and it’s too new to trust IMO, but it’s interesting to consider the reality check that it’s impossible to prove these algorithms secure.

If you’re using commercial hardware or software, or otherwise lack the ability to choose anything but md5 and sha-1, pick sha-1.

Update 3: Matt, Pat, and I continue to discuss the issue.

Pat says:

• There is no reason to switch to SHA-1, because it is next up to be cracked. He says he has an attack against it and just has to tune the loops.
• SHA-256, 384, and 512 are all [potentially] vulnerable – its the design of the cipher. I [Pat] have a differential that might work for SHA-512
• VSH is about the best generally published algorithm
• basically all you’re buying with sha-256 is about 3 years

My opinion is that SHA-1 is the best we’ve got at the moment unless you happen to have source code, and that excludes almost all commercial hardware (Cisco, Juniper, …). VSH looks neato, but don’t use it until it has had some more peer review. I have no idea how bad SHA-512 will hurt perf, but it might be worth looking into.

Schneier liveblogged the NIST hash workshop that recently took place; the first post says the following:

Xiaoyun Wang, the cryptographer who broke SHA-1, spoke about her latest results. They are the same results Adi Shamir presented in her name at Crypto this year: a time complexity of 2^63.

Wow! 2^63 is a huge break for a 160-bit hash. Birthday attack was only good for 2^80.

Update 4: Ken Johnson suggested an improvement to the ported Windows code; it has been updated (along with the link in update 1). Thanks, Ken.