SHA-1 has been broken

[xierox]

SHA-1 has been broken, according to Slashdot.org (http://it.slashdot.org/article.pl?sid=05/02/16/0146218&tid=93&tid=172&tid=218)

Nanolith (http://nanolith/) writes "From Bruce Schneier's weblog: (http://www.schneier.com/blog/archives/2005/02/sha1_broken.html) '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...'" Note, though, that Scheier also writes "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."

[zencoder]

Looks like it's time to make the full switch to MD5...

[xierox]

MD5 was also broken couple months ago. I believe it was by the same group.

- X

[Maestr0]

http://www.antionline.com/showthread.php?s=&threadid=264461

Interesting related materials from Dan Kaminsky:
http://www.doxpara.com/

-Maestr0

[sec_ware]

Hi

MD5 indeed was broken by the same group of Xiaoyun Wang[1]. However, they
have shown a collision attack rather than a preimage attack. But still ...

With SHA-1, the same group has shown a method to reduce the computational
effort to produce a collision by more than 10 orders of magnitude. Still, 2^69
operations seem to be necessary - which is far for being computationally feasible.

Future? I am wondering whether a collision for MD5 and SHA-1 with a preimage
attack can be created simultaneously. I assume it is perfectly safe at the moment
to rely on the combination of MD5 and SHA-1 hashes


Cheers.




[1] http://eprint.iacr.org/2004/199.pdf

[xierox]

More information posted on Slashdot this morning:
"Details are out about the Areported broken SHA-1 (http://www.schneier.com/blog/archives/2005/02/cryptanalysis_o.html) hash function. The findings are that SHA-1 is not collision free and can be broken in 2^69 attempts instead of 2^80. This is about 2000 times faster. With todays computing power and Moores Law, a SHA-1 hash does not last too long. Using a modified DES Cracker, for the small sum of up to $38M, SHA-1 can be broken in 56 hours, with current computing power. In 18 months, the cost should go down by half. Jon Callas, PGP's CTO, put it best: 'It's time to walk, but not run, to the fire exits. You don't see smoke, but the fire alarms have gone off.' As Schneier suggests, 'It's time for us all to migrate away from SHA-1.' Alternatives include SHA-256 and SHA-512."

Source: http://it.slashdot.org/it/05/02/19/1424201.shtml?tid=93&tid=172&tid=218

[RoadClosed]

Revisited:

Although alarming at first, I have revisited this issue a few times. Since almost everything I use is SHA-1 based. Can anyone say PGP and RSA? What has transpired here is the ability to duplicate the Hash far faster than anyone thought possible by generating and then detecting collisions. SHA-1 is a single component of a system using various techniques to protect data. Why do I bring up this old thread? I think the statement that it has been "broken" is a little over the top, but it IS a problem so what do we do?

The same methods can be used to detect hashes in MD4 by hand and MD5 in a few hours. These do NOT directly lead to a compromise, meaning someone can't just hang off the network and sniff your encryption but they are definitely items that should be addresses as software is upgraded because they could impersonate your applications, which would be a much deeper attack.

There is a new variant of SHA-1 that produces longer hash functions, (mentioned in AO as SHA-256 etc.) in fact the NSA says SHA-1 is fine, but should be phased out by 2010. But the NSA only uses SHA-1 for "unclassified" communications. To date, almost a year after the MD5 collisions were announced and then later the unpublished paper on SHA-1 (built off MD5) there has been very little accomplished. Why? Because it's a big concern but not an immediate threat. Meaning there are other glaring security issues taking up our time. Mostly poorly written application that are infinitely easier to compromise than creating a duplicate hash.

I think it’s safe to say that a personal computer would take a very long time to duplicate a hash so threats are limited to governments and rich corporations at the moment. But using the NSA as a gauge; 2010 isn't that far off considering a quick inventory of what could cause issues in the very near future as the paper is circulated: PGP, RSA, .Net, EVERYTHING MS uses (IIS,SQL,kitchen sink), and our beloved SSL. Using longer SHA-1 hashes only makes the "method" longer in its process. The application of compromise is the same.

Sensationalism aside; so we wait and deploy fixes as they become available through routine maintenance releases?


References:
http://www.answers.com/topic/sha-family
http://www.addict3d.org/index.php?page=viewarticle&type=security&ID=3103
http://www.cs.ucl.ac.uk/staff/I.Brown/nts.htm
http://nsa.gov
Http://nist.gov