The SHA-1
collision project

Results

The effectiveness and efficiency of the techniques described in the approach section have been demonstrated through the finding of real collisions on reduced round versions of SHA-1. In particular, in May 2010 we were able to spot a collision for a 71-round of SHA-1, which improves the best previous known result (obtained by C. De Cannière, F. Mendel, C. Rechberger in 2007).

This result, along with the techniques used to achieve it, are described in A. Cilardo, L. Esposito, A. Veniero, A. Mazzeo, V. Beltran, E. Ayugadé, A CellBE-based HPC application for the analysis of vulnerabilities in cryptographic hash functions, that will be presented during the High Performance Computing and Communication international conference 2010.

The result was furtherly improved in June 2010, when we were able to find a collision for a 72-round reduced version of SHA-1.

By applying all the optimizations and new techniques identified during this work, we estimate the time for a 71-round SHA-1 collision to be just about 500 machine hours (using the Cell B.E. processor over IBM QS22 Blade servers), while we estimate about 1500 hours per block for a 72-round version.