<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: [EMAIL PROTECTED]> 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 [EMAIL PROTECTED]