Attacks on SHA-1 made even easier
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 252 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 269 instead of 280 attempts to find two different records with the same hash value. A few months later, the complexity was reduced to 263 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.
The US National Institute of Standards and Technology (NIST) therefore launched a competition to develop a new hash algorithm. Submissions for the competition closed on the 31st of October 2008 and 51 contenders from 50 developer teams have been entered. The winning entry will be called SHA-3 and become the official security standard in 2012.
- Differential Path for SHA-1 with complexity O(2[super52[/super])], a report from Cameron McDonald, Philip Hawkes and Josef Pieprzyk
- New hashes wanted, a report from The H.
- New successor to SHA-1 hash algorithm to be developed, a report from The H.
- European cryptologists attack hash functions, a report from The H.
- Hash cracked - The consequences of the successful attacks on SHA-1, a feature from The H.
- SHA-1 hash function under pressure, a report from The H.