Attacks on SHA-1 made even easier

June 11, 2009 – 6:48 AM

Australian researchers have described a new and faster way of provoking collisions of the SHA-1 hash algorithm. With their method, a collision can be found using only 2⁵² attempts. This makes practical attacks feasible and could have an impact on the medium-term use of the algorithm in digital signatures.

SHA-1 is used to verify data authenticity in many applications. To reduce the complexity of the collision process, the researchers combined a boomerang attack with the search for differential paths.

Towards the end of 2008, researchers demonstrated how to use 200 PlayStation 3 game consoles to forge SSL Certificate Authority certificates through finding MD5 hash collisions. SHA-1 could soon be in a similar position. However, successful exploits still require the attacker to have control of both hash messages. Pre-image attacks, in which attackers attempt to generate a new valid message using the hash of an already existing message, remain impossible.

The first method for speeding up the collision process was developed in early 2005, when Chinese researchers only needed 2⁶⁹ instead of 2⁸⁰ attempts to find two different records with the same hash value. A few months later, the complexity was reduced to 2⁶³ attempts.

The search for a successor to SHA-1 began in 2005. Algorithms of the SHA-2 family (SHA-224, SHA-256, SHA-384 and SHA-512) were among the suggestions, but they are essentially based on the same algorithm as SHA-1, only requiring longer hash values. As a result, they are probably vulnerable to the same types of attack.

Source:
http://www.h-online.com/security/Attacks-on-SHA-1-made-even-easier–/news/113510