February 16, 2005
Shandong team attacks SHA-1
The draft note on the Chinese team's exploits of message digests has now alleged that SHA-1 suffers from the same cryptanalytic attack as that which broke the others. Note that this refers to collisions between two random hashes, finding a hash for your document is still unattacked, it seems. Early leaked reports may be exaggerated...
Over on Bruce Schneier's blog he reports presumably from the RSA conference. Collisions in 2^69 operations are indicated, which is to be compared to the brute force strength of 2^80; collisions in SHA-0 were found in 2^39. This would seem to suggest that SHA-256 and variants may be OK for now.
Steve Bellovin has this to say in response:
... a team has found collisions in full SHA-1. It's probably not a practical threat today, since it takes 2^69 operations to do it and we haven't
heard claims that NSA et al. have built massively parallel hash function collision finders, but it's an impressive achievement nevertheless -- especially since it comes just a week after NIST stated that there were no successful attacks on SHA-1.
That sounds more to my liking. Remember, 2^69 is well in excess of say the 56-bit key strength of DES, so I suspect the crunch is still out of reach of anyone without access to hardware that can dim the town lights. Also,as Eric points out the reduction in collision resistance has to be taken in context, most systems rely on it being hard to find a particular hash, not a collision between two random hashes.
All in all, this is shaping up to be the closing chapter on the current generation of hashes. The killer in the plot was as announced back last year at Crypto 2004.
Luckily, there are a few thinking blogs out there: Scott's stuff, and Rick's crypto blog is thinking on how to wrap the hash.
Postscript: Rumours had circulated (see comments below) that the 'break' was only applicable under some conditions related to including the padding. Those rumours have been debunked, the padding issue is irrelevant.
Addendum: this entry has changed many times to update new information!
Posted by iang at February 16, 2005 07:36 AM
Nice to be in contact again after all those years! Just read your blog entry on the reported SHA-I attack. While I have not yet had the time myself to read the paper and Bruce's report (so little time, so much work!), the following (e-mail) word just reached me from McGill five minutes ago: "it seems that Schneier forgot to mention that the paper has a footnote which says that the attack on full SHA-1 only works if some padding (which SHA-1 requires) is not done."
A work factor of 2^69 is still a serious amount of work. At a thousand million trials a second, that's still well over 17 years. I doubt you can get anything like that speed without _serious_ expenditure. For reference, a middling PC can do around 200k single block SHA-1's a second. So, multiply that by 5 million to get it down to 17 years, assuming all you have to do is hash.
Of course, we don't have the details yet, but this is not the sky falling on our heads (yet).
The NSA suggested message length is 2^64; so I think a collision in 2^69 was already expected. I don't think the sky is falling either. ;)
I think 2^69 is doable in a distributed environment.
www.distributed.net did 2^64 work factor when they broke RC5-64. It took them 5 years, with over 300,000 clients participating, but they did it. http://www1.distributed.net/pressroom/news-20020926.txt
So 2^69 is 2^5 (32) times that work. The distributed.net challenge finished in the summer of 2002, started in 1997 I think, so I believe it is safe to say that we passed at least 3 Moore's law cycles since then, meaning that computers at least 8 times faster in general. So, that means today it should only take about 4 times longer. Just put 4 times more computers to work and we are done. [They say over 300,000 clients participated, but many probably just did a little work (user installed the software to see how it works, let it do a little work and then uninstalled it shortly afterwards)].
Distributed.net's current project is RC5-72.
I think the SHA1 collision is doable in a distributed project. It depends as well if the attack is parallelizable, some problems are not. I don't know about that last point for the new SHA1 attacks.
But I agree that it's not the end of the cryptography world. Most applications don't need collision resistance (as usually defined, with random inputs), but rely more on pre-image resistance and second pre-image resistance with one fixed known pre-image (example a document and its hash).
Maybe we should just forget about collision resistance for random collisions if we canít achieve this property and if it is not used?
Ian Grigg writes:
>> Stefan Brands just posted on my blog (and I saw
>> reference to this in other blogs, posted anon)
>> saying that "it seems that Schneier forgot to
>> mention that the paper has a footnote which
>> says that the attack on full SHA-1 only works
>> if some padding (which SHA-1 requires) is not
First, that's not quite what it says. According to what I have seen
the language is, in reference to a pair of collisions exhibited for a
weakened SHA, "Note that padding rules were not applied to the messages."
But that is irrelevant. The padding for SHA, aka Merkle Damgard
strengthening, involves padding it up a a multiple of 512 bits, while
appending a 1 bit and a 64 bit length field. If you have two messages
M and M' which collide without this padding, they must by definition be
a multiple of the block length. So you add one extra block which is a 1
bit, all zeros, and then the length of M. Now you have a legally padded
pair of SHA messages which collide. In fact, you can add anything at
all after the blocks which collide (the same thing to both messages).
Once you have a collision it "stays collided" as long as the suffix
None of the hashes exhibited by Wang et al at
http://eprint.iacr.org/2004/199.pdf have the padding! That doesn't
matter. They are still valid collisions and can be extended or padded
any way we want while retaining the colliding property.
Presumably the text in the footnote was a reference to this fact.
Don't try to interpret it as meaning that the attack won't work against SHA.
Great discussion about SHA-1 and Shandong team. Do someone have some new informations about the "attacking"?