Implications Of The Recent Hash Function Attacks

An anonymous reader writes "Cryptography Research has issued a Q&A that explains the security implications of the hash function collision attacks recently announced at CRYPTO 2004. Apparently the consequences can be catastrophic for certain kinds of code signing and digital signatures, but MD5 sums for checking binaries are (mostly) OK. While the speculation that SHA-1 is about to fail seems to be overblown, updating the many legacy systems and protocols that rely on MD5 is going to be a massive undertaking."

Comments

This is what I've been saying!

[Dthoma]

"While the speculation that SHA-1 is about to fail seems to be overblown, updating the many legacy systems and protocols that rely on MD5 is going to be a massive undertaking."

Any time I've tried to point this out, I've been shouted down by hysterical people (such as relex) squawking that because it may be possible to generate two messages with the same MD5 hash, SHA-1 is automatically broken. Um, no. They're two totally different algorithms. Use some common sense, people. I'm as cautious as the next person but screaming about how "all hash algos are insecure" is hyperbole at its worst.

Re:This is what I've been saying!

[AKAImBatman]

All hash algorithms have collisions. That's just the nature of the beast. The issue is that a way has been found to create and exploit MD5 collisions. SHA-1 will eventually be a target of something similar, just not today.

Re:This is what I've been saying!

[swillden]

finding a collission (or even several collissions) in MD5 does not invalidate its use.

No, but having an algorithm to generate collisions in a practical period of time *does* make it suspect.

What would invalidate its use is having some programatic way of changing the hash of some data by merely throwing in some junk to make it match a hash of choice

That would make it completely useless for all security-related applications, yes, but a weaker break (such as being able to generate collisions) can break its usage for some security applications. Read the Cryptography Research Q&A for some examples.

Re:This is what I've been saying!

[tyler_larson]

Have we forgotten what a hash function is?

Finding a few collisions, or even an algorithm to generate collisions doesn't change a damn thing. We've always known that there are collisions. A hash function maps in infinite input set to a finite output set. Of course there are collisions. There are an infinite number of collisions for ANY hash function. We already knew that--it's a mathematical certainty. Yet somehow we're shocked and horrified when we actually find some.

Tell me something I didn't already know. Then I'll be impressed.

Idiot Question

[OverlordQ]

Say I have program A that I distributed and I supply the md5/sha1 sum to insure it's 'validity'. From what I read you can get two bitstreams to produce the same sum, ok that was expected. But what I dont get is this still doesn't allow somebody to arbitrarily pick whatever sum they want for their code right? I mean still the chances of somebody writing some trojan'd program and magically somehow getting the sum's to match is extreemly small and/or really computationally expensive. If they were that smart, wouldn't they be working for one of the TLA's (Three letter Acronyms) already?

Re:Idiot Question

[Brandybuck]

Correct me if I'm wrong, but isn't it still just as difficult to create a collision with a *known* message, as it was before this "attack" was discovered? In other words, there's no feasible way for a crooked forensics technician to alter the data. And even if it were practical to create a collision with a known message, the result of this on a harddrive is not going to be data that looks like it came from a harddrive. Rather, it's going to look like data that came from a random number generator.

Hmmm, I guess that's one thing a crooked cop could do. He could make it look like the entire disk is encrypted. In France that's enough to convict your Grandmother with...

New methods needed?

[scumbucket]

In the wake of stories like this is this a message that we need more secure forms of encryption than we already have? RSA is great so far, but how long until 1024 is broken? Or any other schemes, like the MD5 hashing that's used for digital signatures?

Keeping ahead of the crackers is a big concern not only for security of transactions, but for personal privacy as well.

Re:New methods needed?

[merlin_jim]

The question isn't how long until its broken... the question is how long until its broken for cheap.

RSA-512 was already broken. It took a major portion of the world's computing resources for several years. You're not really in danger that your wife is going to find out about your girlfriend. Or that your state is gonna find out about your cocaine habit.

If you're using RSA-512 you just might be on the cusp of being in danger of the government, having caught you and trying you for terrorism, is able to decode your e-mail enough in the six months before your trial to convict you.

See its all about level of effort. How long till RSA-512 can be broken by anyone in a few minutes?

Well 40-bit SSL was supposedly bulletproof when it was introduced. My P4 1.8 can decode SSL messages in about 10 seconds. So RSA-512 should be good for another 3-5 years.

Honestly; always use the maximum number of bits. If your data is important enough to encrypt, its important enough to encrypt right.

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:The cycle repeats

[rewt66]

This isn't "a faster computer". This is "a better technique" or "a deeper understanding" - much more dangerous.

Summary for those too lazy to read it

[rewt66]

The world is going to end! Giant asteroids will destroy all life on earth!

Oops, wrong article. Um... The world is going to end! Global warming... um, well... the Patriot Act... umm...

Well, it's not that bad. Somebody might be able to flip four very carefully selected bits in a file, and still produce the same MD5 hash. This could let me, for example, create an executable that had a normal, benign behaviour, and an evil trojan behaviour, and have one of the bits that I flip change a conditional so that the trojan behaviour was activated. (Note that open source tends to be immune to this kind of nonsense, since in the source code, the actual trojan part - not the conditional that activates it, but the actual evil payload - tends to stick out like a sore thumb.)

Note well that this does not let me create an evil version of somebody else's file. It only lets me create two closely related files, one of which differs by four bits from the other. I have to be able to construct the benign file in such a way that I can turn it into an evil file by changing four bits. And it can't be just any four bits, either; it's a very specific four bits.

So this isn't the end of the world. What it means is that you can't quite trust MD5 to guarantee that you got exactly, bit-for-bit, what you think you got.

But really, this new situation isn't much worse than what we had before. I mean, I could simply have the evil behaviour activated by the date, or by the IP address of the installed machine, or whatever, and get somebody else (who never saw the evil part run) to state that the program did what it was supposed to. Having an MD5 hash doesn't guarantee that the program isn't evil. Bottom line: don't run code written by bad people, whether it has a valid MD5 or not. (I know, I know. How do you tell who the bad people are? That's a hard question, but my point is that a valid MD5 has never told you whether the authors were bad people or not.)

Re:The cycle repeats

[Zocalo]

Exactly. With crypto, it's often that little bit of extra insight or improved technique which can bring the entire thing crashing down. As an example, take Charles Babbage's (yes, that one) breaking of what up until then had been the presumed unbreakable Vigenere cipher. The observation Babbage made was that certain sequences of letters might recur in the ciphered text, and the insight was that these might be the same plaintext letters encrypted against the same cipher sequence. From this small foothold, Babbage was able to ascertain the length of the keyword used to drive the encryption and from there break the complexity down into a limited number of substitution ciphers which are much easier to tackle.

While it's still not certain whether a similar jump might be made in the case of the MD5 and SHA-1 hashing algorithms, you can bet that a lot of crypto people are looking. What's that OSS saying about many eyes making flaws shallow again? Even if there is a fatal flaw though, I doubt it's not going to be the show stopper for hashes some people seem to think; you just use more of them. RPM supports DSA, SHA1, MD5 *and* GPG checksums for example, even if all four algorithms were broken, I doubt there is a method for generating an equivalent file that matches all four checksums at the same time.

Re:yes, it does invalidate its use

[JSBiff]

But, it still is worth pointing out to people that the uses of this collision finding technique is still *very* limited. Someone can't take a digitally signed contract, make arbitrary changes to it, and still have the signature valid. In most cases, the change would be non beneficial (to the attacker that is), like maybe changing 3 characters in the document (this statement is made based upon the fact that, in the collision examples given by the author of the paper, the two messages differed only by like 4 bits or something like that), and the odds are slim that the 3 characters would end up being in the right place in the text, and have an appropriate value, to make it useful. For example, what *would* be useful, but unlikely, would be to change the string '$1995' to '$2995', but as likely as not, to get it to hash right, you'd end up with like '$#g95' or some other rubbish, even if you managed to get the changed bits to line up with the critical bit of data (in this case a dollar amount). It's more likely that you'd end up changing some word like 'benefactor' to '2knefactor'.

However, for the example you gave, of firmware code, where you want it to be exactly right, or else it will cause problems (even 4 bits of difference in bios code can make a computer inoperable), you are right that the hash collision can be a much bigger, much harder to detect, problem.