Fixing a hole in security

How three researchers rocked the world of cryptography last month by breaking a widely used method for digital signatures.
Written by Robert Lemos, Contributor on
Last year was a bad year for the Secure Hash Algorithm. This year has been worse.

A key technology used in digitally signing documents and programs, the Secure Hash Algorithm, or SHA, is used by U.S. federal agencies and by corporations. It's used to reduce long documents to a smaller unique digital fingerprint, or hash, which is then signed using public-key encryption.

Last year, researchers found holes in various techniques used to create the numerical fingerprints. Among the results was a successful attack against the first version of the SHA algorithm, SHA-0.

This year, two of the researchers responsible for finding that attack--Xiaoyun Wang and Hongbo Yu of China's Shandong University--teamed up with Yiqun Lisa Yin, an independent security consultant in the United States. Together, they broke the more popular version of the algorithm, SHA-1. The paper describing that break will likely be published in May.

Though the complexity of the technique for attacking SHA-1 means it is not practical with today's computers, the research will have far-reaching consequences. CNET News.com recently spoke with Yin to learn about the ramifications of the team's research and whether security can be more than fleeting.

Q: When did you start analyzing SHA-1 for weaknesses?
A: Last October, I went back to Beijing to visit Tsinghua University and met with Professor Wang, who was also visiting there. We decided to do the research together.

What gave you the idea to try and break the algorithm?
Professor Wang and her students have been doing research in hash functions since 1996. Over the years, they have developed a set of powerful techniques that led to their breaks of several hash functions.

In addition, there were two other major results reported last year on hash functions at the Crypto 2004 conference. One team found a way to produce collisions in SHA-0. (A collision is when two different files result in the same fingerprint, or hash, and is considered a failure in the system. --RL) Another team found that reduced versions of SHA-1 can been broken.

We thought that there was the possibility of combining these existing techniques and some new techniques to create a new method for breaking the full version of SHA-1.

It was estimated that the existing techniques cannot be used to attack SHA-1 greater than 50 rounds.

What is a round--a measure of complexity?
SHA-1 consists of 80 steps of operation. Each step is also called a "round." Usually, more rounds imply more security, and hence harder to break.

What is the difference between SHA-0 and SHA-1? Is SHA-0 used anymore?
SHA-0 was issued by the (National Institute of Standards and Technology) in 1993 as the secure hashing standard. Then in 1995, NIST issued SHA-1 as a more secure version of SHA-0. The only difference between the two is an extra operation in the file preprocessing step, before the execution of the 80 rounds.

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 preprocessing step is not complicated enough; another is that certain math 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 to the 69th operations (about 590 million billion operations). Finding the collision in SHA-0 last summer took about 2 to the 50th 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 to the 19th 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 a RC5 key three years ago. (That effort took almost 6 years. --RL) 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 (fingerprints) 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.

Editorial standards