The cost of SHA-1 collisions reduced to 2^{52}

Australian researchers Cameron McDonald, Philip Hawkes and Josef Pieprzyk have announced a new attack to find collisions in SHA-1 requiring only 2^{52} operations. This new result decreases the cost of a collision attack by a factor of over 2000 as compared to previous methods. The researchers note that “practical collisions are within resources of a well funded organisation”.

SHA-1 produces a 160-bit output, which according to the birthday paradox, implies that a collision attack should require approximately 2^{80} operations to succeed. However in early 2005, three Chinese researchers announced a collision attack on SHA-1 that required only 2^{69} operations. Since then a series of cryptanalytic results has weakened confidence in the strength of SHA-1 and other hash functions in the SHA family. The new attack builds on these previous results.

The 2^{52} announcement came at the informal session of the Eurocrypt 2009 conference, where works-in-progress and results completed too late for submission are discussed. The full details of the attack will be published in due course on the eprint service of the IACR.

On a personal note, Phil Hawkes was my first (and perhaps only) PhD student. He is a gifted mathematician and I am very glad to see him producing world class research results. My thanks to Eric Rescorla for posting this result on his blog.

Related Posts

• Weapons of Math Instruction: The Birthday Paradox