SHA1 collisions down to 2^52 [pdf]

http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf

by durin42 • 17 years ago

40 23 17 years ago

eurocrypt2009rump.cr.yp.to

ars3• 17 years ago

What is it about hashes? Every single one gets broken eventually.

Encryption doesn't seem to suffer from this - the keyspace might be small enough to search, but they don't get broken.

2^52 isn't small, but it's a lot less than the expected 2^80.

cperciva7• 17 years ago

Encryption doesn't seem to suffer from this - the keyspace might be small enough to search, but they don't get broken.

DES is vulnerable to linear cryptanalysis (2^43 plaintexts). RC2 is vulnerable to a related-key attack (2^34 chosen plaintexts). RC4 is broken in too many ways to list. Khufu and Khafre are subject to differential cryptanalysis.

tptacek3• 17 years ago

DES, RC2, RC4, Khufu, Khafre. Now can we get an analysis for something that isn't in the "don't ever use" list in Practical Cryptography?

Because it is the case that hashes are less well studied (and thus possibly less "hardened") than our workhorse block ciphers.

You're the expert here, can we wheedle you into giving us the real answer?

Barnabas• 17 years ago

2 ^ 52 = 4,503,599,627,370,500

If that equals a number of seconds, then it is equal to 142,808,207 years. If kilometers, it is equal to 476.03 light years.

So 2 ^ 52 is still a big number anyway.

cperciva7• 17 years ago

If that equals a number of seconds, then it is equal to 142,808,207 years.

Yes, but it isn't a number of seconds. It's a number of cryptographic operations. My laptop can perform 2^23 SHA1s per second. SHA1 collision-finding is getting into the "idle resources from a university computing lab for a few months" range.

jmatt• 17 years ago

"idle resources from a university computing lab for a few months" range.

Out of curiosity, what sort of time frame does that translate to for a government agency such as the NSA?

dfranke• 17 years ago

For the Storm botnet it'd be on the order of one hour.

Eliezer• 17 years ago

And if you do a billion operations per second, it's equal to .142808207 years.

tptacek3• 17 years ago

Quick context:

A reasonable attack against SHA1 is cause for alarm. The "next step up" is SHA256, which is a function that designers actively avoid because it's expensive. Virtually everything that used MD5 had a trivial upgrade path to SHA1.

Most SSL certificates are signed with SHA1.

Interestingly, the SSL protocol itself uses both MD5 and SHA1, but is not vulnerable to these attacks, because Paul Kocher got them to use both MD5 and SHA1 (on interleaved portions of the handshake).

ars3• 17 years ago

Using both MD5 and SHA1 helps very little. If you can find a collision in one, you can find a simultaneous collision for the other as well. (Since both are semi-broken.)

Basically if you use two you are as strong as the strongest one - but NOT stronger.

So it was a gamble of sorts on which one (MD5 or SHA1) would break first. But if both break (as has semi-happened) it doesn't help at all.

Daniel_Newby• 17 years ago

That assumes that the attack can find a collision for a chosen hash value, not merely two inputs that collide to some random value. Are the attacks that strong?

I am amused that the URL for a hash-is-broken paper is based on the file's MD5 hash.

SHA1 collisions down to 2^52 [pdf]

Related Stories