Paper 2017/190

The first collision for full SHA-1

Marc Stevens, Elie Bursztein, Pierre Karpman, Ange Albertini, and Yarik Markov

Abstract

SHA-1 is a widely used 1995 NIST cryptographic hash function standard that was officially deprecated by NIST in 2011 due to fundamental security weaknesses demonstrated in various analyses and theoretical attacks. Despite its deprecation, SHA-1 remains widely used in 2017 for document and TLS certificate signatures, and also in many software such as the GIT versioning system for integrity and backup purposes. A key reason behind the reluctance of many industry players to replace SHA-1 with a safer alternative is the fact that finding an actual collision has seemed to be impractical for the past eleven years due to the high complexity and computational cost of the attack. In this paper, we demonstrate that SHA-1 collision attacks have finally become practical by providing the first known instance of a collision. Furthermore, the prefix of the colliding messages was carefully chosen so that they allow an attacker to forge two distinct PDF documents with the same SHA-1 hash that display different arbitrarily-chosen visual contents. We were able to find this collision by combining many special cryptanalytic techniques in complex ways and improving upon previous work. In total the computational effort spent is equivalent to $2^{63.1}$ calls to SHA-1's compression function, and took approximately 6,500 CPU years and 100 GPU years. While the computational power spent on this collision is larger than other public cryptanalytic computations, it is still more than 100,000 times faster than a brute force search.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A minor revision of an IACR publication in CRYPTO 2017
Keywords
hash functioncryptanalysiscollision attackSHA-1collision exampledifferential path
Contact author(s)
info @ shattered io
History
2017-06-06: revised
2017-02-28: received
See all versions
Short URL
https://ia.cr/2017/190
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/190,
      author = {Marc Stevens and Elie Bursztein and Pierre Karpman and Ange Albertini and Yarik Markov},
      title = {The first collision for full SHA-1},
      howpublished = {Cryptology ePrint Archive, Paper 2017/190},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/190}},
      url = {https://eprint.iacr.org/2017/190}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.