Paper 2015/530

Practical Free-Start Collision Attacks on 76-step SHA-1

Pierre Karpman, Thomas Peyrin, and Marc Stevens

Abstract

In this paper we analyze the security of the compression function of SHA-1 against collision attacks, or equivalently free-start collisions on the hash function. While a lot of work has been dedicated to the analysis of SHA-1 in the past decade, this is the first time that free-start collisions have been considered for this function. We exploit the additional freedom provided by this model by using a new start-from-the-middle approach in combination with improvements on the cryptanalysis tools that have been developed for SHA-1 in the recent years. This results in particular in better differential paths than the ones used for hash function collisions so far. Overall, our attack requires about $2^{50}$ evaluations of the compression function in order to compute a one-block free-start collision for a 76-step reduced version, which is so far the highest number of steps reached for a collision on the SHA-1 compression function. We have developed an efficient GPU framework for the highly branching code typical of a cryptanalytic collision attack and used it in an optimized implementation of our attack on recent GTX-970 GPUs. We report that a single cheap US$350 GTX-970 is sufficient to find the collision in less than 5 days. This showcases how recent mainstream GPUs seem to be a good platform for expensive and even highly-branching cryptanalysis computations. Finally, our work should be taken as a reminder that cryptanalysis on SHA-1 continues to improve. This is yet another proof that the industry should quickly move away from using this function.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2015
Keywords
SHA-1hash functioncryptanalysisfree-start collisionGPU implementation
Contact author(s)
pierre karpman @ gmail com
History
2015-06-05: received
Short URL
https://ia.cr/2015/530
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/530,
      author = {Pierre Karpman and Thomas Peyrin and Marc Stevens},
      title = {Practical Free-Start Collision Attacks on 76-step {SHA}-1},
      howpublished = {Cryptology {ePrint} Archive, Paper 2015/530},
      year = {2015},
      url = {https://eprint.iacr.org/2015/530}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.