iSGTW - International Science Grid This Week
iSGTW - International Science Grid This Week

Home > iSGTW 24 October 2007 > iSGTW Feature - Secure enough? Re-assessment of the world's most-used hash function


Feature - Secure enough? Re-assessment of the world’s most-used hash function

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 269 unit operations.

Although this is still an infeasible number of computations, it is 2000 times less than 280, 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


 iSGTW 22 December 2010

Feature – Army of Women allies with CaBIG for online longitudinal studies

Special Announcement - iSGTW on Holiday

Video of the Week - Learn about LiDAR


NeHC launches social media

PRACE announces third Tier-0 machine

iRODS 2011 User Group Meeting

Jobs in distributed computing


Enter your email address to subscribe to iSGTW.


 iSGTW Blog Watch

Keep up with the grid’s blogosphere

 Mark your calendar

December 2010

13-18, AGU Fall Meeting

14-16, UCC 2010

17, ICETI 2011 and ICSIT 2011

24, Abstract Submission deadline, EGI User Forum


January 2011

11, HPCS 2011 Submission Deadline

11, SPCloud 2011

22, ALENEX11

30 Jan – 3 Feb, ESCC/Internet2


February 2011

1 - 4, GlobusWorld '11

2, Lift 11

15 - 16, Cloudscape III

More calendar items . . .


FooterINFSOMEuropean CommissionDepartment of EnergyNational¬†Science¬†Foundation RSSHeadlines | Site Map