More MD5 Attacks Devised

rbarreira writes "Bruce Schneier's blog is reporting on a new paper by Vlastimil Klýma, which summarizes a new method for finding collisions on the MD5 hash algorithm. Furthermore, the first pair of colliding X.509 Certificates has been published by a different team."

Comments

Misspelled surname.

[Yenya]

Actually the author's surname is Klíma, not Klýma (Klima in ASCII).

But I use MD5...

[Anonymous Coward]

...for copy protection of my copyrighted works. This man is doing illegal and immoral things under the DMCA, and should be stopped at once. I am willing to testify in court.

Re:But I use MD5...

[meiao]

well it is not imoral nor illegal.
He just showed that MD5 has become weak for today's computation power (or his brain power).

Too bad you use MD5 for your work. But at least he showed that MD5 is weak before anyone do something which could damage your work.
And thus give you time to select another encryption/hashing method to secure your work.

Or would you rather learn that MD5 is weak the painful way?

I told you so

[Omnifarious]

I was moderated down heavily for stating that MD5 was broken for any and all purposes before. Now I think I feel at least somewhat vindicated.

There are two problems here... Yes, the break in MD5 (and SHA-1) involved two chosen pre-images, and it was still not computationally easy. But there are two problems with hiding behind those justifications.

The first is that once an analytical wedge has been driven into a crack in the algorithm, it often doesn't take long for that wedge to be wiggled back and forth to make the crack even wider. This demonstrates that the attack is computationally feasible enough for anybody to generate two keys that have matching MD5 signatures. I don't think anybody would've agreed that this would happen this quickly a few months ago.

Secondly, deciding when a certain kind of attack is relevant in a particular situation is not trivial. So, if you can generate two different keys that appear identical, what kinds of interesting attacks can you perform? What assumptions to browsers and other software make about keys that are now broken? Can those assumptions be exploited? This shouldn't make phishing any easier, but what if a phisher manages to be the person who generated the bank's key in the first place?

Having an algorithm that is weaker in some significant way than what everybody expects makes everything very tricky. MD5 (and SHA1) are no longer secure hash algorithms, and should not be treated as such for any purpose at all, regardless of whether or not you think you have the gigantic cranium that can think through all the implications of a particular weakness. You are most likely wrong.

Re:I told you so

[melandy]

I was moderated down heavily for stating that MD5 was broken for any and all purposes before. Now I think I feel at least somewhat vindicated.

Your statement that MD5 was broken for "any and all" purposes is pretty broad. The bottom line in security is that circumventing a security measure should be more expensive (in terms of money, time, etc.) than the value of what it is trying to protect. If you are trying to protect something that is particularly valuable, then yes, you should go to lengths to ensure that it is adequately protected. On the other hand, if you are trying to protect something that holds no real value, why go to the time and effort?

So you were modded down for it. On this point, I will agree with you. You are entitled to your opinion, and I don't think that you should be squelched for it if your opinion differs from those that have mod points. Others, however, are entitled to post a dissenting opinion, much in the way that I am doing now.

Re:I told you so

[pla]

MD5 was broken for any and all purposes before

For long-term cryptographic purposes where no other form of authentication exists, yes.

As a general hashing algorithm, it works just fine.

As a short-lived authentication (probably still good for a period of several days, but for a few minutes, such as a secure website transaction, it still works perfectly well) - No need to rush out and change a few thousand storefronts just because, with luck, massive CPU power, and a week or two of CPU time, a determined cracker can fake a message. And note that I refer to signing the transaction itself, not to certs guaranteeing a site as authentic.

As an adjunct to another semi-private means of authentication (such as a password), no problem.

For checking the integrity of a file transfer - In-transit changes such as a man-in-the-middle attack, no problem. Checking an executable against the known-good hash when you have reason to suspect someone might want to change it, probably not so safe.


Now, that said, if a coder sat down today to implement a secure cryptographic hash in a new project, should they use something better, like SHA-512? Sure! But should everyone scramble to purge all references to MD5 from their existing codebases? For 99% of code out there, I'd say no.

Re:WTF?

[rbarreira]

I think the same as you about that matter, but the chinese researchers have already released the paper containing the full details (I think) of their method:

http://www.infosec.sdu.edu.cn/paper/md5-attack.pdf

I saw this link at the page linked in this /.'s article: http://cryptography.hyperlink.cz/MD5_collisions.ht ml

MD5 attacks

[Idlechat]

I totally agree with you!
Those attacks on MD5 must be stopped! How can people be so heartless?

Wait for the dust to settle

[Paul Crowley]

If you can't wait for the dust to settle, use SHA-256.

But if you can, you're best off waiting a few years. This and other recent results will spark a period of frenetic research into new ways of building fast hash functions that don't have these vulnerabilities. I'm sure some great stuff will come out of it. A front-runner may not really emerge for a good few years.

I'm in some ways even more struck by Kelsey and Schneier's recent second-preimage finding attack, which works against pretty much all modern hash functions, and suggests that the fundamental Merkle-Damgard paradigm by which we build them needs to be revisited. Our hash functions may end up looking more like Panama than like MD4.