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

SHA1

[mysqlrocks]

So is SHA1 the recommended alternative?

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.

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:SHA1

[Anonymous Coward]

If you can find a collision in one, you can, for pretty much the same work, find a collision in the second hash. Cascading hash functions like this DOES NOT WORK.

Look up the Joux Multicollision paper from 2004 CRYPTO. This is a famous result.

This scheme you propose has been broken by Joux.

-Matt

Managed to get just the last few lines...

[Saint Aardvark]

...before even the Coral cache was Slashdotted, and it turns out they've written it in LISP:

))))))) ))))))))

(With sincere apologies to Bryce Jasmer.)

Re:Managed to get just the last few lines...

[Anonymous Coward]

I downloaded the source, but it doesn't seem to be working properly. Does anyone have an md5sum of the original so I can verify I got the right code?

-confused

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?

Re:So what the hell do I do now?

[DreadSpoon]

Do nothing.

MD5 has not been invalidated for those uses. Checking the MD5 sum of an ISO download is not done for security purposes, it's done so that you can make sure you didn't get a bad byte or two somewhere in that 650MB. I mean, if hackers could upload a malware-filled ISO to the FTP server, they could upload a new MD5SUMS file too, right?

Re:So what the hell do I do now?

[yamla]

That's not what MD5 sums are used for. TCP/IP already has packet integrity. MD5 sums are indeed used to make sure you don't have a malware-filled ISO. The trick is that you grab the MD5 sum from a trusted source, then you can grab the ISO image from any mirror site. Assuming MD5 is safe (obviously not the case), you know your downloaded ISO is exactly the same as the one distributed from the central repository.

Should I care?

[SlashAmpersand]

This is all really interesting theoretically, but who has the money to run a 1.6 GHz P4?

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

bittorrent?

[rayde]

doesn't bittorrent use md5 to verify the sections of files it has downloaded? will this facilitate poison seeds? or does BT use something more complex than md5?

Re:bittorrent?

[Wesley Felter]

BitTorrent uses SHA-1.

This is misleading - MD5 is still useful

[hoggoth]

This new algorithm does not ruin the usefulness of MD5 hashes. The algorithm can generate two documents that have the same MD5 hash, an MD5 collision. But it can NOT generate an MD5 collision starting with an existing document. In practical terms, this means a file that has been signed with an MD5 hash is STILL secure. Nobody can replace the file with a different file that will have the same MD5 hash. However someone can prepare in advance two documents with the same MD5 hash and trick someone into believing one document is really the other. So if you trust the original source (a Linux distro for example) you can be confident you are downloading the original document.

Collisions do not mean the end of MD5

[afaik_ianal]

This more than anything should be the final stake in the heart of MD5, now that anyone can generate collisions whenever they want.

No, no, no. This does not allow an attacker to generate any collision they like. They cannot find data that collides with a piece of data I provide them with. All they can do is provide me with 2 pieces of data that happen to collide.

This means that an attacker can theoretically provide 2 different documents to people with the same hash, but they cannot easily produce a document that has the same hash as a document I have written.

(Disclaimer: I haven't actually been able to RTFA (it's /.'d), but unless they have made an enormous breakthrough since this was last reported, this attack has very little implications for those of us who use MD5).

"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.

MD5 and verification

[n0dalus]

Just because collisions can be generated doesn't mean that MD5 is dead.
It might only take minutes to calculate two random strings with the same hash, but it would still take a very long time to calculate a second string that collides with a pre-existing string. So even though it is now cryptographically weak, it can still be used effectively to check the integrity of files.

Re:Why?

[einhverfr]

Even if SHA1 and MD5 have attackable collisions the chances are very low that you can find a meaningful collision that affects both algorithms.

Coral cache?

[Viper Daimao]

(Coral cache links provided to prevent slashdotting)

Im sorry, you must be new here.

Re:The end of edonkey

[n0dalus]

No. This only helps you find collisions in two randomly generated strings.
It is still very difficult to produce a colliding file given a pre-existing file on the network.
It should also be noted that edonkey splits a file into 9500KB chunks, and then into smaller chunks again, and hashes each one. It would be far more difficult to produce a chunk that causes collisions on all three levels.
Anyway, I expect an eMule extension will come out soon to allow for sharing of SHA1 hashes between clients (if it doesn't already exist).

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.

Weak code.

[kg_o.O]

This code is weak. I fired it up like 20 minutes ago and still haven't r00ted my box.

Re:So you found a collision, big deal

[andyh1978]

Maybe someone could explain why collisions are a serious problem for MD5. Or at least in what instances they are. I can see that in some cases, such as password hashing this could be a problem.

It's not a problem in password hashing. There is still no feasible way to compute one of the infinite plaintexts that would generate a given MD5 from just the MD5. Rainbow Tables are the main threat there, but they're defeated by salting (e.g. HMAC-MD5) as you have to regenerate the tables all over again (and find the salt in the first place). It doesn't hurt to go to a larger, more complex hash, but for this purpose, there's no additional worries. It's still "preimage resistant".

Re:MD5 is not an encryption algo

[swillden]

t's also the default algorithm to hash passwords (i.e. if you type in your password, it gets hashed into an MD5 sum which is then compared to what the MD5-ed password should be, thereby avoiding plaintext password storage).

Doesn't matter. This attack has no significant effect on password hashing, with or without salt.

This attack allows you to find a pair of plaintexts that hash to the same value; you don't get to pick either the plaintexts or the hash value. It does not help you find a plaintext that hashes to a given value. To use this to attack an unsalted password hashing system you would need to first generate a collision, then convince the target of your attack to set one of those plaintexts to be his/her password, then you could log in using the other plaintext. But if you can convince the target to use a particular password, why not just use that to log in?

This is not an insignificant cryptologic result, and people should move away from MD-5 as fast as practically possible (actually, people have been moving away from it for years due to some results against MD-4, which MD-5 is very similar to) but it doesn't really have any practical implications right now.

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.

Q and A

[Sheepdot]

For those of you who store passwords as hashes in your web apps, I've developed a little "Q & A" post here that explains this as best as possible.

Question: Does this mean all my MD5 passwords for all my users can be cracked?
Answer: The short answer is yes, they can be cracked. The long answer is no, not if you used a salt, and the attacker has to get those md5 hashes first. You are not safe you are storing your user's password field input directly to the database ala the php/sql method of:

INSERT INTO users VALUES ('user','" . md5($password) . "');

Question: How should I remedy this?
Answer: Always use a salt or salts. For example in the case above you could use this php/sql method instead:

INSERT INTO users VALUES ('user','" . sha1(md5($password . '¥1i9k') . 'a-thirty-five-ch4racter-l0ng-str1ng' . md5($password)) . "');

Question: How/Why is this safer?
Answer: Collisions are only direct input for the md5 function to get the same md5 hash. So in the above case, $password was directly taken from the user and made into a hash. Assuming an attacker got an SQL injection in and grabbed the database, they could run this collision creator on a hash and produce an input that gave that exact hash.

But, this would be much more difficult with any code that introduced a salt. That is why the second code is better, it includes two salts that the attacker (through his SQL injection) is unable to account for.

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.

breaking torrents?

[OrangeTide]

Ah! That's a very good point.

now if you you were a software company you could put torrents out (I assume they use blocks of MD5sum), and then after the torrent becomes popular start randomly seeding people with blocks that hash correctly but are complete garbage (since you can't pick what exactly you hash). if you do it right you would have games out there that would still mostly run. but would crash, or have garbled game data, etc.

I'm not sure if this is really all that useful. but this exploit certainly seems to make it easy to do.

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:MD5 is not an encryption algo

[Haeleth]

You don't seem to understand... Having the MD5 hash of a piece of software and the ability to generate a collision for that hash will--

Stop right there, because it's quite clear that the one who doesn't understand is you. Nobody has the ability to generate a collision for a given MD5 hash. All we have is the ability to generate two bits of random junk that share the same hash. This makes some attacks possible, but it does not make it possible for you to distribute a malicious version of someone else's software that has the same MD5 hash as their version.

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.