Cryptology ePrint Archive: Report 2017/190

The first collision for full SHA-1

Marc Stevens and Elie Bursztein and Pierre Karpman and 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.

Category / Keywords: public-key cryptography / hash function, cryptanalysis, collision attack, SHA-1, collision example, differential path

Original Publication (with minor differences): IACR-CRYPTO-2017

Date: received 24 Feb 2017, last revised 6 Jun 2017

Contact author: info at shattered io

Available format(s): PDF | BibTeX Citation

Version: 20170606:072928 (All versions of this report)

Short URL: ia.cr/2017/190

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]