SHA-1 (Secure Hashing Algorithm 1) is the most used cryptographic hash function in the world. But is the 80-fold iteration of this transformation enough for its security? Images courtesy of SHA-1 Collision Search Graz

Cryptographic hash functions are essential to the security of e-government and other applications requiring electronic signatures.

Such hash functions can be seen as a kind of redundancy code with some special properties. The most important of these is that it should be computationally infeasible to construct collisions—sets of two different inputs for the hash function that result in the same output value.

SHA-1 (Secure Hashing Algorithm 1) is the most used cryptographic hash function in the world. It was designed by the American National Security Agency and standardized by the National Institute of Standards and Technology.

Under attack

In 2005, a team of researchers led by Xiaoyun Wang of Shangdong University, China, announced they had discovered a method of constructing collisions for SHA-1 with an estimated complexity of 2⁶⁹ unit operations.

Although this is still an infeasible number of computations, it is 2000 times less than 2⁸⁰, which is the commonly accepted boundary for secure applications.

Recently, as part of a team from the Institute for Applied Information Processing and Communication at the Graz University of Technology, Austria, we developed a new method for constructing collisions that is considerably faster.

We wrote a tool that automatically tracks flipping bits in the internal state of SHA-1 during computations. Using this tool, we can determine sets of messages that are more likely to contain a collision. In the end, however, there remains a large space that needs to be searched.

Researchers have developed a new method for constructing collisions, supposedly computationally infeasible. The new method is designed to aim for sequences of flipping bits (green) similar to the above during execution of the hash function SHA-1. Each column represents a step in the computation. Images courtesy of SHA-1 Collision Search Graz

Real SHA-1 collisions within reach

Our tool brings a real SHA-1 collision within reach for the first time and we have demonstrated its validity on reduced variants of SHA-1. For the real SHA-1, computing a collision remains a challenge too large for the computational resources of one university.

To tackle this problem we created SHA-1 Collision Search Graz—a distributed computing environment that uses the publicly available BOINC software to allow any computer connected to the Internet to contribute to the project by processing a small part of the search space. The BOINC server keeps track of who is searching what part of the space, and also facilitates automatic update of the client software.

The National Institute of Standards and Technology has already decided to replace SHA-1 with another hash function. To come up with a new encryption standard the NIST are planning to run a competition similar to that run from 1998 to 2000 to design the Advanced Encryption Standard. Designers Joan Daemen and Vincent Rijmen won this competition for their algorithm Rijndael.

Through the SHA-1 Collision Search Graz project we want to validate our methods on a real-life hash function to enable more accurate estimates of the security of replacement candidates that will participate in the upcoming competition.

- Florian Mendel, Christian Rechberger and Vincent Rijmen, SHA-1 Collision Search Graz