Geodesic
Finding a collision for the 75-round SHA-1 hash function using clusters of GPUs
Numerical methods and programming, Tome 13 (2012) no. 3, pp. 82-89.

Voir la notice de l'article provenant de la source Math-Net.Ru

SHA-1 is one of the most widely used cryptographic hash functions. An important property of all cryptographic hash functions is the collision resistance, i.e., the infeasibility of finding two different input messages such that they have the same hash values. A further development of the differential attack method for SHA-1 and its reduced versions are proposed. The porting collision search based on the method of characteristics is described for GPU clusters. The method of characteristics employs the backtracking search, which leads to a low GPU performance due to branch divergence if implemented naively. Using a number of optimizations, we reduce the branch divergence and achieve a GPU usage efficiency of 50%, which gives an acceleration of 39 times over a single CPU core. With the aid of our application running on a 512-GPU cluster, we were able to find a collision for a version of SHA-1 reduced to 75 rounds, which is currently (February 2012) the world's best result in terms of number of rounds for SHA-1.
Keywords: cryptoanalysis; cryptographic hash functions; building collisions; GPU; clusters; high-performance computing. 
@article{VMP_2012_13_3_a15,
     author = {E. A. Grechnikov and A. V. Adinetz},
     title = {Finding a collision for the 75-round {SHA-1} hash function using clusters of {GPUs}},
     journal = {Numerical methods and programming},
     pages = {82--89},
     publisher = {mathdoc},
     volume = {13},
     number = {3},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMP_2012_13_3_a15/}
}
TY  - JOUR
AU  - E. A. Grechnikov
AU  - A. V. Adinetz
TI  - Finding a collision for the 75-round SHA-1 hash function using clusters of GPUs
JO  - Numerical methods and programming
PY  - 2012
SP  - 82
EP  - 89
VL  - 13
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VMP_2012_13_3_a15/
LA  - ru
ID  - VMP_2012_13_3_a15
ER  - 
%0 Journal Article
%A E. A. Grechnikov
%A A. V. Adinetz
%T Finding a collision for the 75-round SHA-1 hash function using clusters of GPUs
%J Numerical methods and programming
%D 2012
%P 82-89
%V 13
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VMP_2012_13_3_a15/
%G ru
%F VMP_2012_13_3_a15
E. A. Grechnikov; A. V. Adinetz. Finding a collision for the 75-round SHA-1 hash function using clusters of GPUs. Numerical methods and programming, Tome 13 (2012) no. 3, pp. 82-89. http://geodesic.mathdoc.fr/item/VMP_2012_13_3_a15/