Slashdot Mirror
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."
"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.
Note to M1-ers: a curt but otherwise insightful message is not "Flamebait" or "Troll".
In many situations any data inconsistancy can cause catastrophe. When distributing binaries it isn't that big of a deal, however there are other applications of hashing algorithms.
Think about forensics: Someone gets arrested, computer confiscated. The first thing that happens is a hash checksum is ran of the disk, then a disk image is made, then the image checksum is verified to make sure that it is the same as the original disk. If the checksum of the original disk ever changes, the evidence is useless. When there are collisions in the algorithm, the checksum cannot prove, beyond a reasonable doubt, that the data has not been tampered with. Especially when the hashing algorithm is ran on 20 or more gigabytes of data, which is the typical case in forensics.
you don't have to generate specific malicious code in order to exploit md5.
merely creating pure trash would be sufficient, think of the case of BIOS or other firmware. create random garbage with the same md5 hash and voila, you've turned your victim's PC/laptop/celphone/pda/etc into a doorstop.
there are many other ways that md5 can be exploited, this is only one.
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.)
"SHA1 is a totally different algorithm, so it's still perfectly safe."
Yes and no. MD5 collisions are not SHA1 collisions, and the attack that generated the MD5 collisions doesn't seem to be applicable to SHA1, or its authors would have published collisions on SHA1. The published collisions on several other algorithms: HAVAL-128, MD4, and RIPEMD. They also say that their method will work against SHA0. All these hash functions share similar design principles. It seems highly probable that the MD5 attack will have at least some applicability to SHA1 even though it isn't directly an attack against SHA1. Also, other researchers have published results against SHA1. In particular, Biham and Chen con produce collisions on reduced versions of SHA1 with up to about 40 rounds (the full hash function has 80). That isn't a break of the full hash function, and there's no guaranteed it can be extended to more rounds, but it looks worrisome.
"This attack produces two messages with the same hash, no guarantee what that hash would be, instead of one message with a chosen desired hash, so it isn't a threat to real systems."
That's just stupid. "No practically-findable collisions" is one of the design requirements for a secure hash function. Protocols using secure hash functions are based on the assumption that the functions used are secure hash functions. If your hash function doesn't guarantee collision resistence, then your protocols must be assumed to be broken unless you can go back and prove, for every protocol, "This one is still secure even if we use something that is not a real secure hash function."
One way a hash collision could be useful, for instance, would be against some signature schemes where the secret key is revealed if you ever sign an identical message more than once. People who use those schemes are careful to avoid signing the same message twice... but if you had two different messages and they had the same hash, it's quite possible to imagine that you could be tricked into signing the same hash more than once (because people sign hashes, not actual messages) and making trouble for yourself. Similarly, if you use hash output for initialization vectors in cipher modes that use those, the result could be encrypting two messages with the same keystream, which means an attacker can probably recover both messages (and then use them as stepping-stones to breaking the rest of your system).
Also, a fast way of finding collisions may well be extensible to a somewhat-slower, but still faster-than-brute-force, way of finding the preimages that you think an attacker really wants.
"This attack depends on the messages having a special form; they don't look like real plaintext, so it isn't a threat to real systems."
One of the conditions for a secure cryptographic system is that you don't depend on the plaintext having (or NOT having) a specific form. If your system doesn't work regardless of the content of the data I put through it, then I will punt on your system, and recommend to my clients some other system that will actually work. It's also not clear that the attack on MD5 really does require a specific form... those strings look randomly-generated to me, even though the XOR difference of them clearly is not. Maybe with just a little more work they can produce collisions of two meaningful and interesting strings with opposite meanings.
"All hash functions have collisions, so it was bound to happen and isn't a threat."
The important question is whether people can actually find collisions. With a good hash function, collisions should be rare enough that nobody has any reasonable chance of finding them on purpose any time soon. Wang, Feng, Lai, and Yu can find collisions on MD5 deliberately, with practical amounts of computer power. They have done this more than once, and have at least outlined a plausible theoretical explanation of how they can do it. That means MD5 does not provide the guarantees that a secure hash function must
Slight correction: AFAIK RSA-512 was not broken, it was brute-forced. There is a huge difference between the two.
Breaking a combination lock is figuring out that you can hear the tumblers go *click* when you hit the right number. It will take you twenty seconds and five tries to get the right combination.
Brute-Forcing a combination lock is trying every combination from 00-00-00 through 99-99-99 until you get the right one. You will get the right combination, it will just take you long enough that someone will notice you.
Just to give you back a little bit of a warm-fuzzy feeling about RSA strength, realize that every bit added doubles the brute-force keyspace. So if you can brute-force 40-bit SSL in 10 seconds, you can do 41-bit SSL in 20 seconds, but it'll take 98 billion-billion years for the same computer to do 128-bit SSL.
For the combo lock analogy, it would be adding on another number to guess, a 4 number lock instead of 3, which would give you 100x as much work (original amount of work to get numbers A-B-C with D=00, then lather, rinse, repeat until D=99). If the combo lock were truly broken instead, it would take you about a minute and seven tries, instead of 100x as long.
Using two hashes in conjunction does not work as well as you would expect it to work. There are at least half a dozen posters here proposing this idea, so I will try to explain in some detail why it does not work.
In general an n-bit hash can be collided in 2^(n/2) time using the birthday paradox attack. When you concactenate two hashes of lengths n and m bits, you get a hash of length n+m bits. However, this (n+m)-bit hash can in fact be collided in m*2^(n/2) + 2^(m/2) time (assuming n is greater than or equal to m). This is only slightly more effort than it takes to collide both hashes separately. In the case of SHA-1 and MD5, n is 160 and m is 128, so colliding both hashes would take 128*2^80 + 2^64 = 2^87.00000017 effort versus 2^80 effort for SHA-1 alone.
It must be especially stressed that m*2^(n/2) + 2^(m/2) is considerably smaller than the attack time of 2^((n+m)/2) which you would normally expect from a well designed hash having n+m output bits.
So how does the attack on two hashes work, you ask? It exploits a curious property of the birthday attack which says that generating a multicollision (three or more messages all with the same hash) by brute force takes only marginally more effort than generating a single collision. Specifically, generating a 2^(m/2) way multicollision takes only m/2 times as much effort as generating a single collision. So what you do to collide two hash functions is: you generate a huge multicollision in the first hash function, and then from that set you look randomly for a pair that collides the second function. It seems very counterintuitive, but the point is you can break the hash functions one by one instead of having to break both of them at once. Strength in numbers doesn't apply here.
If one of the hash functions (say MD5) has a better than brute force attack, then that can be used to speed up the attack against both hash functions by the same factor. The only uncertainty is if both of the hash functions have better than brute force attacks; in this case it would depend on the particulars of the attacks as to whether one can make them interact in such a way as to break both. However, no matter what, the idea of concactenating two hash functions has such low security compared to designing a good hash function of the same length from scratch that it is unlikely that this concept will ever be useful from a pure cryptography standpoint.
For more information on multicollisions and attacking concactenated hash functions, see A. Joux "Multicollisions in Iterated Hash Functions", Proceedings of Crypto 2004, LNCS 3152.