SHA-1: Your questions answered

• Tags:
• Cryptography,
• Cyryptanalysis,
• SHA-1,
• Hashing

Published: 03 Mar 2005 09:50 GMT

• 
• 
• 
• 
• 

In general terms, what weaknesses of SHA are being exploited by your analysis techniques?
This is quite difficult to explain in general terms. Roughly, we exploit the following two weaknesses: One is that the file pre-processing step is not complicated enough; another is that certain mathematical operations in the first 20 rounds have unexpected security problems.

Should companies worry that their data might be at risk because of this?
There is no immediate threat. It just shows that SHA-1 should be phased out faster than people originally anticipated.

The estimate that we made is that a collision could be found in about 2⁶⁹ operations (about 590 million billion operations). Finding the collision in SHA-0 last summer took about 2⁵⁰ operations, requiring more than 80,000 hours of supercomputer time.

That means that finding a collision of SHA-1 using our method will take 2¹⁹ times longer (about 5 million years). That is certainly out of the reach of our computing resources.

So finding one of these collisions is still nearly impossible?
No, that's not true. A distributed computing effort cracked an RC5 key three years ago. [That effort took almost 6 years]. That was 64 bits, so the 69 bits of security for SHA-1 is not that far away.

And doing those years of calculations would break a digital signature?
No, it only allows you to find a pair of collisions.

Let's imagine we can find a pair of collisions every minute. That doesn't give you an immediate threat, because the pair of collisions is generally garbage messages. You would have to find meaningful messages. However, it is possible that with all these new techniques we will be able to improve this in the near future and find meaningful messages.

Are there unbroken hashing functions that can be used instead of SHA? What makes them stronger?
NIST issued several new hash functions (SHA-2) in 2002. They are, generally speaking, more secure than SHA-1, since the size of the hashes are much larger, and so the expected security level is much higher.

Would your techniques help find problems in those other algorithms?
It's still too early to tell. Historically, though, major advances in cryptanalysis tend to have broad applications. The new techniques can give cryptographers more tools to tackle other hash functions.

• 
• 
• 
• 

• Share this article:
• Digg
• Slashdot
• Del.ici.ous
• Stumble
• Reddit

• Most Recent
• Most Popular
• Most Discussed