Finding a collision for the 75-round SHA-1 hash function using clusters of GPUs

Authors

  • E.A. Grechnikov Lomonosov Moscow State University
  • A.V. Adinets Lomonosov Moscow State University

Keywords:

cryptoanalysis, cryptographic hash functions, building collisions, SHA-1, GPU, clusters, high-performance computing

Abstract

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.

Author Biographies

E.A. Grechnikov

A.V. Adinets

References

  1. Teat C., Peltsverger S. The security of cryptographic hashes // Proc. of the 49th Annual Southeast Regional Conference. New York: ACM, 2011. 103-108.
  2. National Institute of Standards and Technology (NIST). FIPS-180-2: Secure Hash Standard, August 2002. Available online at http://www.itl.nist.gov/fipspubs/.
  3. Grechnikov E.A., Adinetz A.V. Collision for 75-step SHA-1: intensive parallelization with GPU // Cryptology ePrint Archive: Report 2011/641. Available online at http://eprint.iacr.org/2011/641.
  4. Dobbertin H. Cryptanalysis of MD4 // Fast Software Encryption. LNCS 1039. D. Gollmann, Ed. Berlin: Springer, 1996. 53-69.
  5. Wang X., Yu H. How to break MD5 and other hash functions // Proc. of Eurocrypt. Berlin: Springer, 2005. 19-35.
  6. Wang X., Yin Y.L., Yu H. Finding collisions in the full SHA-1 // Proc. of CRYPTO. LNCS 3621. Berlin: Springer, 2005. 17-36.
  7. Chabaud F., Joux A. Differential collisions in SHA-0 // Proc. of CRYPTO. Berlin: Springer, 1998. 56-71.
  8. Biham E., Chem R., Joux A., Carribault P., Lemuet C., Jalby W. Collisions of SHA-0 and Reduced SHA-1 // Proc. of Eurocrypt. Berlin: Springer, 2005. 36-57.
  9. de Canniére C., Rechberger C. Finding SHA-1 characteristics: general results and applications // Proc. of ASIACRYPT. LNCS 4284. Berlin: Springer, 2006. 1-20.
  10. de Canniére C., Mendel F., Rechberger C. Collisions for 70-step SHA-1: on the full cost of collision search // Proc. of Conf. on Selected Areas in Cryptography. LNCS 4876. Berlin: Springer, 2007. 56-73.
  11. Adinetz A.V. NUDA programmer’s guide (http://nuda.sf.net).
  12. Satish N., Kim C., Chhugani J., Nguyen A.D., Lee V.W., Kim D., Dubey P. Fast sort on CPUs and GPUs: a case for bandwidth oblivious SIMD sort // Proc. of the 2010 Int. Conf. on Management of Data (SIGMOD’10). New York: ACM, 2010. 351-362.
  13. Grechnikov E.A. Collisions for 72-step and 73-step SHA-1: improvements in the method of characteristics. Cryptology ePrint Archive: Report 2010/413. Available at http://eprint.iacr.org/2010/413.

Published

10-09-2012

How to Cite

Гречников Е.А., Адинец А.В. Finding a Collision for the 75-Round SHA-1 Hash Function Using Clusters of GPUs // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2012. 13. 82-89

Issue

Section

Section 2. Programming