Implications Of The Recent Hash Function Attacks

← Back to Stories (view on slashdot.org)

Implications Of The Recent Hash Function Attacks

Posted by timothy on Wednesday September 1, 2004 @05:40AM from the some-but-not-all dept.

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

19 of 262 comments (clear)

Min score:

Reason:

Sort:

browsers check for wildcard in domain names??????? by stonebeat.org · 2004-09-01 05:49 · Score: 3, Interesting

For example, a devastating attack would be one that enabled adversaries to obtain a legitimate server certificate with a collision to one containing a wildcard for the domain name and an expiration date far in the future.

quick questions:
1) Don't the browser check for wildcard domain names in the certificates???
2) If not, why not???

--

Consensus is good, but informed dictatorship is better
Re:Idiot Question by ponds · 2004-09-01 05:51 · Score: 5, Interesting

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.
How about this... by Millennium · 2004-09-01 05:58 · Score: 3, Interesting

Has a collision been found yet concerning data which has both the same MD5 sum and the same SHA-1 sum?

It would seem as though even if SHA-1 were to fail, the two algorithms used together could bolster each other security-wise. This slows things down, of course, but would it not suffice for the time being?
1. Re:How about this... by Anonymous Coward · 2004-09-01 06:52 · Score: 1, Interesting
  
  Remember, if you hash to a 32 byte value, there are 2^256 possible outcomes. That's the best you can do without collisions (2^256 inputs). With two different 32 byte values, you have what is basically a 64 byte value.
  
  What's the difference between 2 32 byte hashing algorithms and one 64 byte one? Well, if the algorithms do things in a similar way, the extra 32 bytes may be useless. The trivial case is if the algorithms are the same -- you have basically 32 bytes of lack-of-collision. The math to express how "similar" two algorithms are (and hence what "equivalent encryption strength" you have) is not really appropriate for a /. post, however.
Re:This is what I've been saying! by sk8king · 2004-09-01 05:59 · Score: 2, Interesting

Why not generate hashes that use both SHA-1 and MD5. The combined result would be that more unique. Finding two files that generate the same hash value in BOTH algorithms would be that much more improbable. Take the hash generated by SHA-1 and concatentate it [with a sensible delimiter if required] with the hash generated by MD5. Ta dah.
yes, it does invalidate its use by bani · 2004-09-01 06:01 · Score: 5, Interesting

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.
Re:This is what I've been saying! by Anonymous Coward · 2004-09-01 06:02 · Score: 2, Interesting

Wrong.
They cannot "create" collisions. They can only try and find them.
In fact the chances of finding a colision that could be used in a malicious manor are slim. Did you even look at the colision they found? It was two huge strings of random characters. Now if they find lots and lots more, and patters emerge, we're in trouble.
to protect binaries by Anonymous Coward · 2004-09-01 06:04 · Score: 2, Interesting

it would be better to post both the MD5 hash _and_ the SHA-1 sum. What's the chance of 2 different binaries having the same MD5 and the same SHA-1 at the same time??

Artaxerxes
Re:Idiot Question by ponds · 2004-09-01 06:04 · Score: 2, Interesting

Yes, if you mount a disk, it is completely useless as evidence. Any forensics practitioner who has been on the job for more than a day would never mount a disk. Thats why an image is made.
Re:Idiot Question by Grond_the_Hammer · 2004-09-01 06:20 · Score: 2, Interesting

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.
Neither of those statements are true. Hashing algorithms are useful for forensic verification but changing a single bit on a disk image will not cause it to be tossed from a case, as long as any changes can be explained as a result of something legitimate the forensic analyst did. Booting the original image (while risky) is sometimes necessary in forensics but it will not, contrary to popular opinion, invalidate the evidence. A slick defense attorney could, however, point to analyst incompetence as the reason and if successful could have the evidence tossed. Also, MD5 collision have been known about for years, and are an acceptable issue within forensics. DNA typing has collisions as well, but since collisions are in a statistical range that is nearly unassailable, a match still meets the "reasonable doubt" standard in criminal court.
Re:This is what I've been saying! by LnxAddct · 2004-09-01 06:28 · Score: 2, Interesting

Even if you could quickly be given a message and generate a separate message which has the same hash but is the same size of the original message, it still won't really matter simply because you have no control over what the second message is. For example, in the article they use "I, Bob, agree to pay Charlie $ 5000.00 on 4/12/2005.", well a 2nd message that has the same hash and is the same length as the first message would probably look like this "bhedjfgd70gdgr6rhg2rkjhgvrek342rgkhverghvgkhkfgrr e2wd". What I'm getting at is that since you have no control over the new message, and because it is decided by an algorithm, it will probably be a bunch of random characters, even if a word or two were formed, it would be a non-sensical statement. The article is making appear like you can take any two messages and modify the second one to have the same hash. Its bullshit. The best you could do is add a bunch of random characters at the end of your 2nd message until it has the same hash as the real message, but then its easy to point out, "Hey I didn't sign a paper with a bunch of random shit all over it." Oh yea, and it would also take many millenia.
Regards,
Steve
The next hash by augustz · 2004-09-01 06:34 · Score: 2, Interesting

The work that went into putting together AES was really fantastic.

I'm just looking forward to a similar effort around an advanced hashing standard.

Where would an effort like this form?
Re:Summary for those too lazy to read it by Isao · 2004-09-01 06:35 · Score: 3, Interesting

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.
You never could. It merely said that it was unlikely for you to be getting something else. The difficulty of arranging such a situation just got easier. Not easy. Not trivial. Just easier. Probably by the same factor it got easier over the past four years due to Moore's law increases. Eventually this will become a real issue, and we should be prepared for that, much the same way we don't use plain DES any more.
Real scoop by Anonymous Coward · 2004-09-01 06:38 · Score: 4, Interesting

I wasn't there this year. A friend told me that the embarrassing thing was that the Chinese paper was REJECTED from the conference. They presented their results at the rump session. Other non-Asian researchers with hash collisions got papers in the conference. This doesn't help one's faith in academia, does it, when one of the most important developments at a conference is rejected by the program committee. There is a growing rift between Asian research and Western research. The Asian side has much lower standards, but also has some good results. Sometimes good Asian papers end up being rejected by association with so many mediocre Asian papers.
Posted anonymously to avoid offending any of my colleagues.
Re:Ok... by YoJ · 2004-09-01 06:53 · Score: 2, Interesting

You have to be really careful when you combine things. A lot of times you can end up with something that is less secure than either part separately. That said, I think this form of chaining is good. Being able to find MD5 or SHA1 collisions/preimages alone is not enough to break this hash. The hash is also at least as secure as SHA1 to any type of attack, since the SHA1 hash is included verbatim. The remaining item is to show why this chaining is better than simply using SHA1 with a longer signature length (i.e. the length of HASH1 + HASH2). I would guess that against known attacks, the longer single hash is better than two half-size hashes. The added safety of a chaining scheme such as this is the safety against unknown attacks that might completely break SHA1 or MD5 somehow.
Re:This is what I've been saying! by jwdb · 2004-09-01 06:59 · Score: 2, Interesting

Why it's a big deal is explained in the article:

Let's say someone uses this attack to generate two ssl certificates with the same hash, one benign, one malignant (ie * for host, 2200 AD for expiry). This person then sends the benign one in to Verisign and gets it signed as a trusted certificate. He then applies the malignant certificate, with a valid Verisign signature, to his little scam website - people log on, check the certificate, see that it's signed, trust the website...

Jw
Weird results by Lisper · 2004-09-01 08:31 · Score: 2, Interesting

On a lark I decided to run the purported collisions in the paper through MD5 to verify the claim, and I got a weird result. The two examples given are indeed collisions, but the hash is not what the paper says it is. The paper says that the hashes for the two examples are supposed to be:

9603161f f41fc7ef 9f65ffbc a30f9dbf

and

8d5e7019 6324c015 715d6b58 61804e08

but the hashes I get are:

74BE7342 8C5BDB65 9BE40E00 CF6AE31C

and

BC5E1391 D31E52F3 D41CBE8C 05D7DBC1

I'm using the MD5 library built in to Darwin (OS X) and I've verified that it passes the standard MD5 test suite in RFC 1321.
Re:MOD UP INFORMATIVE by ComputerizedYoga · 2004-09-01 08:59 · Score: 2, Interesting

parent's trying to say more along the lines of "it'll be a lot less easy to find a collision dataset that's simultaneously a collision for md5 and sha1"

A lot of stuff I've seen floating around carries multiple verification methods (apache uses md5 and pgp sigs for example).

Even if one verification technique is rendered "broken" -- together, the two hash algorithms are still that much more complex to break (though your point is also valid: wasting 32 bits on crc32 isn't going to make it more secure than adding those 32 bits to your new nonbroken cryptographic hashing algorithm).
Re:Idiot Question by ahdeoz · 2004-09-01 11:03 · Score: 2, Interesting

For most Financial Transactions, you're probably safe enough throwing a `wc -c` on to your message to make MD5 impregnable, if you're really paranoid.