Hi Ian,

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

Stefan
www.idcorner.org

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

Cheers,

Ben.

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?

--Anton

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
>> done."
>>
>> http://www.financialcryptography.com/mt/archives/000355.html

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
is identical.

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.

Hal Finney

http://drger.com

ergergte

Great discussion about SHA-1 and Shandong team. Do someone have some new informations about the "attacking"?