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

yeah... nonsense

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.

Quite simple to check file size also

I would have thought this not such a big issue for software developers who aren't incompetent.

Re:Quite simple to check file size also

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.

Re:Quite simple to check file size also

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.

Not like if it was AES

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.

Re:Not like if it was AES

I'm not an expert so don't take me seriously about it, but: I think hash algorithms are very important when signing things. For example, SHA-1 is the default hash algorithm used in GPG to sign messages. When the first attacks were mentioned I changed that to use RIPEMD-160. If you download something that has a SHA-1 sum to check both correctness and autenticity, it's a problem. Someone could modify the original tarball, for example, introducing a trojan horse, and append some other not useful data to it so the sum matches. I don't know if that's technically feasible as I say, but I imagine the possibilities are not so far. And, furthermore, for me this is another important warning that we should move out of SHA-1 ASAP. BTW, if I recall correctly BitTorrent uses SHA-1 to verify the 256KB chunks. There, having a fixed-size chunk is an advantage for this case, but, as I said, I wouldn't trust SHA-1 much longer. A further step and people could build evil BitTorrent clients that, at least, could corrupt your downloads introducing noise chunks.

Re:Not like if it was AES

The problem is that your old keys and the messages they encrypted are available for cracking now and forever. Most people only encrypt important messages, which are easy to look for in a mailbox, and at a later time could be easy to crack. There's probably even a good change the data in that mail could still be important.

Now, if all emails were encrypted, it would be harder to immediately see what messages in a mailbox deserve your attention. But then at a later date CPU speed may make that a negligible difference.

This is a big deal

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.

Re:This is NOT a big deal

Even if their test hardware could be accelerated from 33 MHz to 4 GHz, the process would still take 170,000 years. And even if a giant cluster of such machines were used, no collisions would be found within a realistic timeframe of a few years.

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

Re:This is NOT a big deal

1) No one will see what comes after that unless you like viewing the source of a webpage as opposed to an actual page.

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.

Re:This is a big deal

For anyone wanting to use Whirlpool in their apps, here are libraries that you can use:

• Whirlpool library for Ruby. [plan99.net] This is written by me, based on the sample C implementation by the inventors.
• The above library can also be used in C apps. Just copy whirlpool-*.[ch] to your project. See whirlpool-algorithm.h for API.
• The GNU Crypto [gnu.org] library for Java contains a Whirlpool implementation.

Re:This is a big deal

Whirlpool is a good choice these days. It's longer than most of the hashes out there, but I don't believe there have been any attacks yet demonstrated against it. For those pythoners out there I wrote a quick wrapper for it that should get you started. Excuse any site errors and just hit refresh

Seconded. Whirpool uses similiar mathematics to AES so an attack that breaks Whirpool is likely (although not certain by any stretch of the imagination) to also break AES.

I think much like it is harder to design a cipher that resists attack when you use an LFSR as your base primitive it is hard to design a hash that is secure that uses an Unbalanced Fiestel Network (UFN).

This is why I do not advocate moving to the higher SHAs. I believe that some weakness will be discovered and it will be found the UFN made it worse.

If you're going to use AES, you've already thrown all your eggs in the Wide-trail design basket. If you're going to do that for the cipher, you might aswell do the same for the hash too.

In fact, in most cases you will use the hash has part of an authentication primitive anyway. In this case, there's a good argument for dumping a new hash and using an encrypt-authenticate mode of operation instead of something like HMAC. That way, you reduce the number of assumptions which have to be true for the system to be secure, which can only be a good thing.

In short, if you need to authenticate use your favourite encrypt-authenticate mode. If you need a hash for some other purpose, use Whirlpool.

Simon

Re:This is a big deal

Whirlpool is also in mhash, which is now many versions on from the ones supplied by Fedora Core and Gentoo. Oh well. It's also in the Linux kernel's crypto library. Whirlpool is a damn good hash and uses the same principles as the Rijndael cipher, which means that the underlying concepts have been deeply analyzed twice - once in each form - showing the basic ideas are fairly solid. Being long should reduce the risk of collisions so is actually a strength in many cases - particularly as we're talking bytes, not megabytes.

Tiger is another good hash function - faster than Whirlpool, smaller for those embedded cases where even the bytes matter, and I believe it is not known to have any attacks against it. Tiger also appears in mhash, not certain if it's in the kernel but it should be.

I don't see that it is really of any consequence whether anyone has actually demonstrated an attack on SHA - the point of security is to not wait until AFTER the house has been plundered to upgrade. SHA is FIPS-180, but if there is even a theory on how it might become broken, I would urge people to use something stronger. Security that is only certain to be good against skript kiddies is really not very useful security.

A little information theory

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.

Original

So the original document that is trying to be forged/modified has to convienently have a "long nonsense part" after the tag. How real-world relevant is that?

How about this combination:

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.

to find one... how big will the html get

I mean this find is awesome... but to get a matching SHA-1, how big does the html get with the jibberish. I mean it just has to create the same hash, but i dont think it would be a couple of lines.... then again the first post about myspace content is prolly on to something, i guess there is a little truth in all jokes.

Already expected

Well, a variation of SHA-1, now called SHA-0 was broken similarily more that a year ago (before MD5 was broken). It was just a matter of time they figured out how to break full SHA-1. In the mean time, people who knew about this switched to SHA-256 which is still known to be good.

NO SHA-1 COLLISIONS HAVE EVER BEEN FOUND

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.

multiple hashes MD5 and SHA-1

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.

Add size of file

I can never quite figure out why the MD5 and SHA and all these other algorithms don't include the original message size as part of their hash. This would eliminate all attack vectors that stem from adding or deleting information from a file. But I guess that's too simple a solution for these mathematicians.

OK, what do we use now?

SHA-1 and MD5 are becomming non-safe to use. So, we go to SHA-256 or a completely different algorithm?

Insecure

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 [wikipedia.org]

Horray for validation

It looks like validation of document structure significantly complicates the problem of creating a hash collision (the technique mentioned relied on padding the document with junk at the end, which, IIRC, is not in line with modern XHTML specs). Of course it's best to use a secure hash to begin with, but this does add yet another layer of resistence.

Nothing to see here..

When messages are signed they are already compressed and the
file size is used as part of the final message digest.

If your application doesn't do this then you should use another
applications.

Using the above mentioned processes none of these attacks are
viable, both in the short and long terms. (supposedly)

When receiving the following message:

Jon D0e owe$ Jane Do3 $1000`000 d011ar5.

or

Jon Doe owes Jane Doe $1000000 do11ars.
$4#^$%^&*5#$^()^%ER$%^RT#$3

Would you not ask the sender to resend
their original message?

Arash Partow

If you can replace the file...

If you can manage to replace a hashed file from a web site with content of your choosing, couldn't you just as well change the hash it's checked against?

Even if the hash and the file came from seperate sources, odds are a user went to 'xyzzysoft.com' from which the link to both the hash and the file are provided; so if xyzzy's page were hacked, they are screwed anyway.

To use a car analogy, to steal a purse in a car, a theif dosn't pick the lock, he smashes the window.

Unless you have a seperate, secure channel for transmitting the hashes, end-to-end, and compare them manually. (such as faxing the hash, then downloading the file) it's silly to use the logic of: File Hash equals Website Hash therefore File is safe, File is the one I wanted, File is really from Xyzzy. Not that hashes are useless, far from it they are excellent to verify against transmission/storage corruption, viruses, and unsophisticated attacks.

There have been hacks such as replacing the system random number generator to cheat in an online game, which would wreak utter havok with any crypto depending on it; a complier virus that adds itself to compliers compiled with an infected compiler, which could silently modify the output of a hash comparing program if a particular sequence was detected. And here's an idea I just thought up, a hacked file decompression library that modifies executables as they are being extracted, after you carefully manually checked the hash of the compressed package you recieved. (if you used a user-priviledge extraction utility for something like an updated kernel mode driver)

Re:Why not include message size?

No, the MD5 attack produce the files with the same lenght.

Re:Why not include message size?

And what's to stop a would-be attacker from changing the included message size?

Re:Why not include message size?

Both SHA-1 and MD5 specify including the length of the message as part of padding to the next 512-bit block.

Re:Why not include message size?

t seems to me that all the attacks on both of these hash systems (SHA-1 and MD5) involve different message sizes which is easily fixed by using both hash and message size as a verification. I honestly don't come close to understanding the math involved in these hashes, but I get the idea that the complexity involved in creating a hash using the exact same amount of data is far higher.

No, usually the attacks produce 2 files with the same size.

Maybe factoring in message size as part of the hash is the solution? I don't know. Again, the math is way above me. But you could certainly do it by adding on some extra bits to the hash itself. A bit costly in size, but seems like maybe it might be worthwhile.

Yeah, SHA-256 adds some bits onto the hash itself, as do longer versions like SHA-384 and SHA-512. But it's unclear how much that helps; sometimes cryptographic attacks don't get much harder if you increase the size of the data.

Re:git

This is bad news for the git.

It is not a major problem. First of all to exploit it, you'd have to generate a collision and have one of the two versions accepted in mainstream. Second you'd have to get the wrong version onto some user's machine before the correct version. Linus explained this in a posting somewhere after the original SHA-1 weakness was published. And though Linus AFAIK does not have any education in cryptography, he has demonstrated, that he clearly knows how to apply cryptographic primitives in a sound way. I have a PhD in cryptography, and I have read about the design of git, and I did not spot any weakness.

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.