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

My bad

[rbarreira]

Oops, and I was so careful not to forget the accent...

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

[Anonymous Coward]

I'm hopping you'll get modded +5 Funny...

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

[Anonymous Coward]

MD5 can be used where it is one part of a two part session id/token where the variables used to generate the md5 token are not visible or predictable by the attacker, even if the attacker knows how they are derived.

Yes they can find different values to generate the same key, but if they can not see or manipulate the application variables used in the algorithm which checks it, and the session they are trying to crack is invalidated and destroyed on the first attempt to crack it, the id and token are no longer relevant so can't provide any information to the attacker.

Without being able to control or see the values by which the token is generated, especially if the only visible value is the session id, which is not used in any way to generate the token, I am having trouble seeing how this token could be guessed, especially given the short life of the session (artificially limited to 20 minutes), the fact that the only visible factor is the session id and the fact it is destroyed on the very first failed attempt to crack it.

The window is very, very small.

I do, however agree that MD5, if used by itself, to encrypt data, or make a hard to guess session ID, is a joke when used as your hashing algorithm. It can be used as part of a larger security scheme where there are other contributing factors.

if x and y are weak, but you still need to figure out z, which is strong, easily cracking x and y won't help you crack z.

Despite all of this, I'd still use something else simply because better algorithms are readily available.

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:I told you so

[Omnifarious]

If you read the article, it was a few hours of CPU time, not a week.

And I hope you get to live with the consequences of your decision. I still say that people are too dumb to think of all the ways in which something can be exploited. It was hard enough to design the protocols with algorithms that had particular desirable properties. Trying to figure out if they work in some situation when some important property no longer holds true isn't a puzzle I think is worth trying to solve. Best to chuck the hold algorithm and use a new one, even in old code.

Re:I told you so

[Anonymous Coward]

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.

What have you said that couldn't of been said by someone that was introduced to the subject 5 minutes ago? Not very informative.

WTF?

[Anonymous Coward]

This paper doesn't seem to offer any better explanation of the attack than the Wang et. al. paper. Why are these people not explaining their results?

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

Thank you kind sir!

[Anonymous Coward]

Thank you very much. I hadn't seen that paper, and from a quick scan it does indeed appear to be a full explanation of the technique used by Wang.

MD5 attacks

[Idlechat]

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

What should we use now?

[tweedlebait]

IINACryptoExpert-

So there is enough buzz to stop using MD5 in several situations at least.

It's a shame because there are so many great tools that many people have made that are now a few shades away from dust but that's how the security game goes.

I run into situations where I've used MD5 to uniquely ID/fingerprint/tamperproof document images used in legal cases, so although the chances seem very slim that the md5 problems would be exploited in this instance- it's no longer something i can ever use again.

So what can now fill MD5's shoes?

What's also likely to be the most popular replacement?

Thanks!

Re:What should we use now?

[aphor]

One of the weakest uses of MD5 in light of these discoveries is using the trusted digest of a file to validate files downloaded from untrusted sources/mirrors. FWIW, try using MD5 hash for the whole file, and then a second one for the first 512 bytes of a file. Then compare the trusted pair of hashes and file size against what you downloaded.

Until we get good data on the performance of this MD5 collision generator, we cannot know how much more difficult it would be to break the authentication scheme I suggested, but it will be significantly more difficult. What if you used both SHA-1 and MD5? How difficult would it be to produce a colliding message that has the same MD5 *and* SHA-1 digest as any given message?

My point is that there are small things we can (and should) do to make a great difference overcoming the recently discovered weaknesses. Also, for certificates, one could just include another ASN.1 value in the cert to include the MD5 collisions. Certs would get bigger, and fewer, and computationally more expensive to use, but MD5 is not necessarily dead in the water!

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.

Re:Wait for the dust to settle

[dr.badass]

Our hash functions may end up looking more like Panama than like MD4.

But Panama already has a big hole that goes right through it!

Re:Wait for the dust to settle

[Paul Crowley]

*grin* nice one!

Actually Panama hashing is broken, but the underlying idea is nevertheless worthwhile and will hopefully see more attention.

MD5, SHA1

[Anonymous Coward]

So MD5 and SHA1 have had vulnerabilities revealed...would a hybrid of them produce a slightly more secure hash? For instance, XOR the MD5 and SHA1 hashes together for a given piece of data (yes, I know the hash lengths are different).

Re:MD5, SHA1

[impaque]

And what is the reason for doing two hash operations that take double the time when you already have better, stronger hash functions?

Addendum

[Anonymous Coward]

After reading more carefully I realize that this is *still* not a complete exposition of the research done by the Chinese group. They still do not offer a complete description of the attack.

Re:Addendum

[rbarreira]

I haven't yet read it very attentively. What do you think is missing, specifically?

MOD PARENT DOWN

[Anonymous Coward]

How come this +1, Funny became Interesting or Insightful?