SHA-1 Broken

Schneier Weblog ^ | 02-16-2005 | Bruce Schneier

[ASA Vet]

There is No Such Agency

[Petronski]

Flux capacitance is so, like, last year, dude. It's all about ersatz tri-harmonics in plasma variances.

[Mad Dawgg]

'Who can tell me where this came from?
"Never go out in the rain with your socks on."'

Your mom?

[oyez]

Solid state rectifiers made all that hot cathode equipment obsolete years ago.

[July 4th]

Wow - interesting news. It was expected to come soon:



http://www.freedom-to-tinker.com/archives/000661.html

There's a rumor circulating at the Crypto conference, which is being held this week in Santa Barbara, that somebody is about to announce a partial break of the SHA-1 cryptographic hashfunction. If true, this will have a big impact, as I'll describe below. And if it's not true, it will have helped me trick you into learning a little bit about cryptography. So read on....

SHA-1 is the most popular cryptographic hashfunction (CHF). A CHF is a mathematical operation which, roughly speaking, takes a pile of data and computes a fixed size "digest" of that data. To be cryptographically sound, a CHF should have two main properties. (1) Given a digest, it must be essentially impossible to figure out what data generated that digest. (2) It must be essentially impossible to find find a "collision", that is, to find two different data values that have the same digest.

CHFs are used all over the place. They're used in most popular cryptographic protocols, including the ones used to secure email and secure web connections. They appear in digital signature protocols that are used in e-commerce applications. Since SHA-1 is the most popular CHF, and the other popular ones are weaker cousins of SHA-1, a break of SHA-1 would be pretty troublesome. For example, it would cast doubt on digital signatures, since it might allow an adversary to cut somebody's signature off one document and paste it (undetectably) onto another document.

At the Crypto conference, Biham and Chen have a paper showing how to find near-collisions in SHA-0, a slightly less secure variant of SHA-1. On Thursday, Antoine Joux announced an actual collision for SHA-0. And now the rumor is that somebody has extended Joux's method to find a collision in SHA-1. If true, this would mean that the SHA-1 function, which is widely used, does not have the cryptographic properties that it is supposed to have.

The finding of a single collision in SHA-1 would not, by itself, cause much trouble, since one arbitrary collision won't do an attacker much good in practice. But history tells us that such discoveries are usually followed by a series of bigger discoveries that widen the breach, to the point that the broken primitive becomes unusable. A collision in SHA-1 would cast doubt over the future viability of any system that relies on SHA-1; and as I've explained, that's a lot of systems. If SHA-1 is completely broken, the result would be significant confusion, reengineering of many systems, and incompatibility between new (patched) systems and old.

We'll probably know within a few days whether the rumor of the finding a collision in SHA-1 is correct.

[FactsMatter]

First, you should read the papers about this. It isn't completly broken it appears they have discovered a faster way to cause collisions.

Second, this team did the samething to md5 a few months ago :)

[zeugma]

It is possible the NSA knew about the weakness and got people (foreign govs) to use it so that they could read messages.

Not really. SHA is used for digital signatures mostly, not encryption, so it wouldn't be useful for decrypting intercepts. If they wanted to fake a digitally signed message from someone, then it would be useful. Personally, I don't think the NSA was aware of this attack. They don't have the monopoly on quality cryptographers like they used to.

[zeugma]

Does PKI use this?

Depends upon the implementation I would imagine. The term "PKI" encompasses quite a bit.

[Mannaggia l'America]

SHA-1 has been broken.

Bill Gates' fault! Macs and Linux unaffected! Only Windows and IE!

</sarcasm>

[July 4th]

PGP PKI uses SHA-1 or MD5 depending on the version.

[zeugma]

I figured it wouldn't be general interest, which is why I didn't put it in Breaking News. Some of the comments are pretty funny though. It's what makes FR fun!

I'm much more concerned with AES than SHA though. It has already been proven weak in low-round implementations. I was kind of disappointed that TwoFish didn't get selected as the AES algorithm.

On the bright side, from what I understand, RSA with sufficiently large keys is still safe, as is 3-DES.

[sarah_f]

What to they defer to?

[zeugma]

Thanks for the post. I recall hearing the rumors a few months ago, but hadn't thought about it. Excellent description of what a hash is btw.

[TrueKnightGalahad]

"The chicken is in the henhouse...repeat...the chicken is in the henhouse...14...2...83...7...Rene's mustache is waxed...repeat...Rene's mustache is waxed...switch to alternate frequency Zebra now...."

[Cicero]

Awful lot of silly posts on this one.

I hadn't heard of SHA-1 before reading this, but the meaning is obvious.

If a standard encryption protocol is broken, it means that every transaction on the net is vulnerable until it is replaced with something more secure.

At a guess, this results because computer power keeps rising exponentially, so what couldn't be cracked a few years ago is now far more vulnerable.

Changing a standard protocol that is buried in programs all over the net won't be done easily, I presume. Not like updating MSIE to 128-bit, which could be done by North American users just by filling out a few forms and doing a download.

[dfwgator]

I do agree, this is huge. Most Java-based apps use SHA-1 for their encryption algorithm, I know mine do.

[FoxPro]

First, you should read the papers about this.

Could you point me to these papers?

[BigDaddyTX]

"Your mom?" Shouldn't that be "Your Momma"?

The right answer is Fonzie's dad. The only thing he left him was a little safe. He had to run over it with his tricycle several times to open it only to find a note inside that had that message in it.

[FoxPro]

Some companies use SHA-1 to backup computers over the Internet. They use the hash to see if they already have a file, and therefore don't have to back it up again. Using this methodology to backup thousands of computers is very efficient (if the hash works) because most files on most computers are not unique. If the hash collides, it would call the whole methodology into question.

[FactsMatter]

This is all that is publicly available at this time. --NOT MY WORDS-- February 15, 2005 SHA-1 Broken SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing. The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper describing their results: * collisions in the the full SHA-1 in 2**69 hash operations, much less than the brute-force attack of 2**80 operations based on the hash length. * collisions in SHA-0 in 2**39 operations. * collisions in 58-round SHA-1 in 2**33 operations. This attack builds on previous attacks on SHA-0 and SHA-1, and is a major, major cryptanalytic result. It pretty much puts a bullet into SHA-1 as a hash function for digital signatures (although it doesn't affect applications such as HMAC where collisions aren't important). The paper isn't generally available yet. At this point I can't tell if the attack is real, but the paper looks good and this is a reputable research team. More details when I have them.