SHA-1 Broken

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

[zeugma]

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.

[zeugma]

This is big news. SHA-1 is used for digital certificates and cryptographic hashes. Part of the security you get with these types of hashes is the difficulty that you would have in generating a "collision", which is where two separate messages generate the same "hash". A reduction to 2^69 operations to generate a collision is significant. Like Mr. Schneier said, SHA-1 is dead for cryptographic use.

[Dallas59]

That's what I thought.

[ericthecurdog]

I like potato chips.

[traderrob6]

I was just chatting with the wife about this at breakfast

[Constantine XIII]

My cat's breath smells like cat food. :P

[oyez]

I thought SHA-0 and SHA-1 were kaput even back to their inception. The tripole phase cross delta inverters were proved impractical years ago.

[sure_fine]

I was just telling my grandkids about this, this morning

[ladtx]

Same here. I was just thinking about this yesterday.

[ricer1]

All your SHA-1 belong to us....

[ZinGirl]

[George Smiley]

Thanks for the info.

Lots of uneasy IT folk will be running 'round after hearing this news.

[Cyber Liberty]

I believe your green sweater might be over here....

[minus_273]

worth noting is that SHA short for US Secure Hash Algorithm made by the NSA and heavily used for about 9 years now. It is possible the NSA knew about the weakness and got people (foreign govs) to use it so that they could read messages. Amusingly enough, no one know exaclty how the much much older DES works :)

[ricer1]

Does this mean that Walmart will be selling the SHA-1 at discount prices now?

[Dallas59]

It's either bullets, particles or underwear.

[NonValueAdded]

The tripole phase cross delta inverters were proved impractical years ago.

Yeah, whatever you do, don't cross the streams.

[balrog666]

Amusingly enough, no one know exaclty how the much much older DES works :)

Only the Shadow knows!

[blanknoone]

I'll reply to your other post later today.

[FoxPro]

Can MD5 be far behind? This would cause general chaos.