Security threats Toolkit

SHA-1: Your questions answered

Tags:
Cryptography,
Cyryptanalysis,
SHA-1,
Hashing

Published: 03 Mar 2005 09:50 GMT

Last year was a bad year for the Secure Hashing 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 goverment 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 is likely to 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. ZDNet UK sister site 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] 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 pre-processing step, before the execution of the 80 rounds.