Slashdot Mirror
SHA-1 Collisions for Meaningful Messages
mrogers writes "Following on the heels of last year's collision search attack against SHA-1, researchers at the Crypto 2006 conference have announced a new attack that allows the attacker to choose part of the colliding messages. "Using the new method, it is possible, for example, to produce two HTML documents with a long nonsense part after the closing </html> tag, which, despite slight differences in the HTML part, thanks to the adapted appendage have the same hash value." A similar attack against MD5 was announced last year."
Using the new method, it is possible, for example, to produce two HTML documents with a long nonsense part
To achieve this, the method uses material pulled from myspace.com.
Push Button, Receive Bacon
It's a hash algorithm... no big deal ? Just like it was proven possible to break MD5 for binary executables and others them (both) won't be dropped for, say, storing passwords on a database.
Where's the "Correct filesize" kept? If it's stored in the document, it's still possible (Though more difficult) to change it and make a collision.
One thing is that cryptographic hash functions should be easier to make secure than ciphers. At leaste that is what many cryptogtaphers thought. The other is that up to now you could rely on SHA-1 to be collision resistant, no matter what. The argument that you have a large part of the message being "garbage" does not give any real security. Many, many applications can still be attacked, and they need not even be broken for that.
While expected since last year, selecting and using crypto-hashes just got a lot more difficult and error prone.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
It's quite relevant for those using it as a way to verify executables are the way developer had intended. Like the attack last year they're saying it would be possible for someone craft an exe without a virus, generated a checksum for it, get it linked to from major websites (after passing a virus scan of course), and then drop a virus in the end of the file and not have the checksum change. That's the real-world relevance.
Moderation is not supposed to be used as an indicator of agreement.
The second reason to keep cool is just as important, if not even more so: hackers will have to execute a pre-image attack to manipulate, for instance, a contract that has been digitally signed. In other words, hackers will have to find a second, manipulated contract with the same hash value as the real contract. In principle, the number of operations needed is thus far greater (2160). Indeed, as far as we know all attacks to date have only concerned collisions, and Wang et al. does not change that. There are no known methods to reduce significantly the number of operations needed for pre-image attacks.
Don't you think you're flying off the meter here a bit... Just because a collision was found means truly little. So a garbage laced HTML page was created after the actual HTML closing tag... 1) No one will see what comes after that unless you like viewing the source of a webpage as opposed to an actual page. 2) You should read up on birthday paradoxes. If someone created two similar messages, it would take years for them to figure out how to compute a hash to match. Now in the field of sending out something so so so secure, what makes you think that even if a someone did re-computate a hash to match, that message would be worth anything years down the line. Someone would have to be able to accomplish a collision, re-computate the hash in their new message and send it all within minutes for it to truly be a threat.
Let's look at this scenario... A massive kernel update is made to say Linux... The information is hashed, posted, and everyone is now going to update their Linux boxes... Unless someone is so quick fast to intercept along this path, most are safe unless they choose to verify the hash years down the line (which by then would be worthless). So unless someone can exploit this within minutes (no more than I would guesstimate 36 hours), I see little reason to get all bent out of shape over this...
Infiltrated dot Net
I have to say, trusting SHA-1 to do what it says on the tin, is not incompetent. Naive, sure, but not incompetent.
Common web browsers (I just tried Opera, FF, and Lynx) will happily display everything after the closing tag. You would have to put it inside <!-- --> comment delimiters, but then it doesn't matter whether it is before or after the closing tag. Unless the attack doesn't work if the --> has to come at the end, but then you can just omit the closing tag. Only an XHTML-compliant browser would complain. From cursory scanning TFA it is not clear to me what the reason is for mentioning the closing </html.
Avantslash: low-bandwidth mobile slashdot.
Provide the following 3 pieces of data:
1) Message/file length
2) SHA1 hash
3) MD5 checksum or some other hash/checksum that's calculated way differently from SHA1.
Providing the length means that the person trying to change the data needs to keep it the same length which makes it more difficult.
Using 2 different hashing/checksumming methods means they have to be able to match both of them in order to be able to switch the data.
The more restrictrictsion we toss on the data, the harder it is to manipulate. I do think that using more than 2 or 3 hashing/checksumming methods would be overkill however.
I'm not quite sure what your comment means.
As the heise.de article points out; the twins are of equal length - the file size would be the same.
Finding hash twins whereby the chosen one is, oh, let's say 160 bits longer is a degree less sophisticated.
SCO employee? Check out the bounty
I would have thought this not such a big issue for software developers who aren't incompetent.
I don't know the details of this particular attack, but usually attacks on hashes like this produce two documents with the same file size. Certainly the MD5 collisions a couple years ago had the same file size.
I hereby place the above post in the public domain.
That would work for typical everyday use (like a checksum next to a link to a downloadable file). Of course, this is assuming that the birthday attack wasn't keeping a uniform file size.
It would also take a bit more (though maybe not much) to apply it to digital signatures.
(IANAL)
NO SHA-1 COLLISIONS HAVE EVER BEEN FOUND!
Ahem.
Sorry, my caps lock key got stuck there.
No SHA-1 collisions have ever been found. The first person or group to find one will achieve considerable fame. I say this as an attendee of both last week's Crypto conference and the immediately following hash function workshop.
The work factor estimated for a SHA-1 collision is something over 2^60 cycles. That would put it on par with the biggest calculations that have ever been done (publicly anyway). So far nobody has put together a sufficient effort to achieve a collision.
At the hash function workshop, cryptographer Antoine Joux published a set of recommendations for how such a hash collision effort should be mounted, in order to minimize the damaged from a published collision. The main goal is to make it difficult to take a published collision and use it to create harmful effects in various ways. Hopefully Joux's guidelines will be followed if and when a SHA-1 collision finding project gets started.
From the article:
Using the new method, it is possible, for example, to produce two HTML documents with a long nonsense part after the closing </html>tag, which, despite slight differences in the HTML part, thanks to the adapted appendage have the same hash value.
So it appears that both the original and the new messages need that appendage. This isn't just about adding an appendage to a known, appendage-less document.More data, damnit!
If the MD5 of the two different strings that had the same SHA-1 value are different then there's no real reason to panic. For an added level of security you could also calculate the byte length of the data.
Software will just need to be updated to calculate two hashes. Good luck finding two sets of data that are different yet have the same length, the same SHA-1 hash and the same MD5 hash.
Work Safe Porn
SHA-1 was proved to have insecurities years ago. Because of that SHA-2 ("SHA-256", "SHA-384", and "SHA-512") was released back in 2001 as a better version of SHA-1. SHA-2 was tested and no insecurities were found (yet). What's more, SHA-2 is now the official US standard.
Complaining that SHA-1 is insecure is like complaining that Windows 98 is insecure.
Oblig Wikipedia link: http://en.wikipedia.org/wiki/SHA_hash_functions
MD5, SHA, and every other hash function I've ever read the spec for appends some zeros followed by the original message size (the zeros are so it comes to an integer number of blocks) as the first thing it does. For exactly this reason.
At a guess, this attack requires that the two files be the same size. (But I haven't actually read TFA.) And attacks that delete or add data but can't manage to correct the file size are the minority anyway.
I really do think the mathematicians are doing exactly what you guys think they should be.
For now though from a theoretical viewpoint this is a major weakness, it still requires way too much processing power to be realistic. And the way git is designed, I don't think it is going to be any major problem switching to a new hash once cryptographers starts to agree which one should be considered secure in the future. Once they start using a new hash, you can actually still safely use old repositories based on SHA-1. Because once there is no longer being added new data based on SHA-1, a collision is no longer enough to perform an attack, rather you need a second preimage, something which there has not yet been demonstrated an efficient way to produce.
Do you care about the security of your wireless mouse?
Not true -- XHTML-compliant browsers will only treat it as XHTML if it's sent with a "Content-Type: application/xhtml+xml" header. This is very nice for keeping your page clean -- view it in Firefox with that header, and it'll parse it as XML, and complain whenever you have a problem with your XML, saving you a trip to the even more pedantic W3C validator. Unfortunately, sending that header will have browsers that don't understand XHTML attempt to download the page, rather than displaying it as HTML. Even worse, browsers aren't consistent in the "Accept:" header they send, which is supposed to help with this -- Firefox prefers XHTML and says so, for instance, but while Safari is perfectly capable of receiving XHTML, it just says "Accept: */*", which says it doesn't prefer any type of document -- I may as well send it a PDF (which it would try to download). Even browsers which indicate a preference have to have "*/*" somewhere in there if they want to be able to download files.
So, there's really no good, standard way of detecting whether to send XHTML as XHTML or HTML. I've tried implementing something on my website, but I doubt that it will really work properly until I break down and attempt to detect specific versions of browsers.
Don't thank God, thank a doctor!
Actually, hashes are difficult to secure for general communications purposes without putting a cap on the size of the transmission. In information-content terms, a collision proof hash is equivalent to a lossless compression algorithm.
A hash will either contain all of the non-redundant information in the original content, or some of the information gets lost during the hash. Non-redundant information being defined in an information-theory sense that a given bit is completely random/unpredictable based on the content of preceding bits.
In order for a hash to be completely collision proof, it has to contain all of the non-redundant information contained in the original file. Otherwise information in the orignal message is lost in the hash. And if information is lost from the original message, that creates a possibility of constructing a message that differs only in the information that is removed by the hash. Only if the original message is reconstructible from the hash (plus possible information contained in the hash algorithm itself) will it be collision-proof. You've either got the information-content, or you don't. And if you don't have the content, you can't validate it.
We are the 198 proof..
I think the key point is this:
No SHA1 collisions have ever been published
whether or not they have been found is a different matter entirely.
That's fine, except where the interpreted data can be created from more than one set of actual data. An example might be when creating a hash of a zip archive. If I take the original zip archive, and recompress it using a more efficient algorithm I can reduce the actual data size. I could even go so far as to manipulate the compression algorithm for every byte encoded until I found an encoding that enabled me to produce a hash collision and still match the original file size.
For other document types, I could, for example, take a marked-up UTF-16 document and change the character encoding to UTF-8, saving roughly half the space for a document whose characters were mostly English glyphs, then execute the same attack. For rich documents, space could be saved by minimally degrading image quality. For binaries, by running packers on them.
Adding the filesize to the hash string doesn't offer as much protection as you might first think when at the end of the day you can still find ways to create a collision.
Let's not forget this attack is against a reduced 64 round version of SHA-1.
SHA-1 still does what it says on the tin: the best attack known against the 80-round version is 2^63, which is still not practical.