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

Authors

  • E.A. Grechnikov
  • A.V. Adinets

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.

New computational technologies

Downloads

Published

2012-09-10

Issue

Vol. 13 (2012): Issue 3.

Section

Section 2. Programming

Author Biographies

E.A. Grechnikov

Lomonosov Moscow State University,
Faculty of Mechanics and Mathematics
• PhD Student

A.V. Adinets

Lomonosov Moscow State University,
Research Computing Center
• Researcher

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.