Schneier on Security: SHA-1 Broken

R.A. Hettinga rah at shipwright.com
Tue Feb 15 23:08:09 EST 2005


<http://www.schneier.com/blog/archives/2005/02/sha1_broken.html>

 

Bruce Schneier
 

Schneier on Security

A weblog covering security and security technology.

« RSA Conference |  Main

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

 Posted on February 15, 2005 at 07:15 PM

Trackback Pings

TrackBack URL for this entry:
 http://www.schneier.com/cgi-bin/mt/mt-tb.cgi/130

Listed below are links to weblogs that reference SHA-1 Broken:

» SHA-1 Broken from *scottstuff*
 Bruce Schneier: 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 pa... [Read More]

Tracked on February 15, 2005 07:45 PM

» SHA-1 broken from James Seng's Blog


>From Bruce Schneier:

SHA-1 has been broken. Not a reduced-round version. Not a simplified
version. The real thing.

The research team of Xiaoyun Wan
[Read More]

Tracked on February 15, 2005 09:00 PM

» Running out of hash functions from Descriptive Epistemology
 Bruce says, 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... [Read More]

Tracked on February 15, 2005 09:51 PM

» SHA-1 broken. from The Chicken Coop
[Read More]

Tracked on February 15, 2005 09:52 PM

» sha-1 has been broken from Party of Five
 From Bruce Schneier's weblog: The research team of Xiaoyun Wang, Yiqun
Lisa Yin, and Hongbo Yu (mostly from Shandong University... [Read More]

Tracked on February 15, 2005 09:55 PM

Comments

Time for NIST to have another competition?

Posted by: David Magda at February 15, 2005 07:36 PM

So what hash functions are available that don't have a substantially
similar construction? AFAIK, RIPEMD160 and the SHA256-384-512 series are of
the same sort, and the attack could in principle work for them as well.
There's Tiger, which appears quite different, and Whirlpool. Any other
suggestions?

This is, it would appear, a collision attack, not a preimage attack, so I
guess we have some time to phase out the old hash functions.

Posted by: Rafael Sevilla at February 15, 2005 08:25 PM

Feb. 7, 2005 Hashing out encryption:


 http://www.fcw.com/fcw/articles/2005/0207/web-hash-02-07-05.asp

Federal agencies have been put on notice that National Institute of
Standards and Technology officials plan to phase out a widely used
cryptographic hash function known as SHA-1 in favor of larger and stronger
hash functions such as SHA-256 and SHA-512.

Posted by: David Mohring at February 15, 2005 08:56 PM

2**69 operations is still an awful lot of operations. What is it that lets
us say that 2**69 is "broken" but 2**80 is "not broken"?

Posted by: Jordan at February 15, 2005 09:03 PM

> (although it doesn't affect applications such as HMAC)

Bruce,

Pardon my ignorance but can you elaborate why this doesn't affect HMAC?

Posted by: Yakov Shafranovich at February 15, 2005 09:16 PM

That's 2**11 less operations. Let's say breaking this (2**69 ops) takes the
NSA a week. If it had been 2**80, it would have taken 2048 weeks, or 39
years. If it would have taken the NSA (or whomever) a year to break SHA-1
before, it could be broken in 4 hours.

My guess would be it would still take a lot longer than a week - but would
now be in the realm of possibility, whereas before it would have been in
the lifetime(s) range. However, this is totally a wild-assed-guess, based
on the assumption that it was expected to take 100+ years before this to
crack.

Posted by: Randell Jesup at February 15, 2005 09:19 PM

"...whereas before it would have been in the lifetime(s) range."

Either way, it's well within the statute of limitations for whatever crime
you've committed. ;-)

Posted by: Anthony Martin at February 15, 2005 09:25 PM

He said 69!!!!!!!!

COOOOOOOOLLLLLL!!!!!!!!!!!!!!

Posted by: Mr Anon at February 15, 2005 09:32 PM

I don't think any public calculation has successfully solved a problem
which required as much as 2^69 work. It will be interesting to see if this
motivates people to search for an actual SHA-1 collision. Exhibiting a
collision always has more impact than a theoretical break.

Of course, these researchers have yet to publish their techniques. Isn't it
kind of contradictory to the spirit of academic research to keep your
methodology secret for so long? It's been six months now since their MD5
results.

Posted by: Hal at February 15, 2005 09:46 PM

Regarding how long it should take to break... Let's assume that a single
CPU can tackle 2**32 ops/sec. (About 4 billion, so assuming each op is one
cycle, about 4 GHz... Gross oversimplification, but it makes the math
pretty easy.) So, how long would it take to do 2**69 ops?

2**37 seconds of CPU time. About 4000 years.

So, if you have a 4000 node cluster, it ought to take about a year, which
would be well within the statute of limitations, for most crimes and
jurisdictions... :)

Brute forcing, using the same hypothetical cluster, would have taken over
2000 years. So, I guess today's lesson is that it isn't completely broken,
but it certainly ain't secure.

Posted by: Will at February 15, 2005 09:53 PM



Schneier.com is a personal website. Opinions expressed are not necessarily
those of Counterpane Internet Security, Inc.
 

-- 
-----------------
R. A. Hettinga <mailto: rah at ibuc.com>
The Internet Bearer Underwriting Corporation <http://www.ibuc.com/>
44 Farquhar Street, Boston, MA 02131 USA
"... however it may deserve respect for its usefulness and antiquity,
[predicting the end of the world] has not been found agreeable to
experience." -- Edward Gibbon, 'Decline and Fall of the Roman Empire'

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list