# SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust

Abstract : The SHA-1 hash function was designed in 1995 and has been widely used during two decades. A theoretical collision attack was first proposed in 2004 [29], but due to its high complexity it was only implemented in practice in 2017, using a large GPU cluster [23]. More recently, an almost practical chosen-prefix collision attack against SHA-1 has been proposed [12]. This more powerful attack allows to build colliding messages with two arbitrary prefixes, which is much more threatening for real protocols. In this paper, we report the first practical implementation of this attack, and its impact on real-world security with a PGP/GnuPG impersonation attack. We managed to significantly reduce the complexity of collision attacks against SHA-1: on an Nvidia GTX 970, identical-prefix collisions can now be computed with a complexity (expressed in terms of SHA-1 equivalents on this GPU) of 2 61.2 rather than 2 64.7 , and chosen-prefix collisions with a complexity of 2 63.4 rather than 2 67.1. When renting cheap GPUs, this translates to a cost of US$11k for a collision, and US$ 45k for a chosen-prefix collision, within the means of academic researchers. Our actual attack required two months of computations using 900 Nvidia GTX 1060 GPUs (we paid US\$ 75k because GPU prices were higher, and we wasted some time preparing the attack). Therefore, the same attacks that have been practical on MD5 since 2009 are now practical on SHA-1. In particular, chosen-prefix collisions can break signature schemes and handshake security in secure channel protocols (TLS, SSH), if generated extremely quickly. We strongly advise to remove SHA-1 from those type of applications as soon as possible. We exemplify our cryptanalysis by creating a pair of PGP/GnuPG keys with different identities, but colliding SHA-1 certificates. A SHA-1 certification of the first key can therefore be transferred to the second key, leading to an impersonation attack. This proves that SHA-1 signatures now offer virtually no security in practice. The legacy branch of GnuPG still uses SHA-1 by default for identity certifications, but after notifying the authors, the modern branch now rejects SHA-1 signatures (the issue is tracked as CVE-2019-14855).
Keywords :
Document type :
Conference papers

https://hal.inria.fr/hal-03136301
Contributor : Gaëtan Leurent Connect in order to contact the contributor
Submitted on : Tuesday, February 9, 2021 - 3:54:35 PM
Last modification on : Friday, January 21, 2022 - 3:18:53 AM
Long-term archiving on: : Monday, May 10, 2021 - 6:56:54 PM

### File

sec20-leurent.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : hal-03136301, version 1

### Citation

Gaëtan Leurent, Thomas Peyrin. SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1 and Application to the PGP Web of Trust. USENIX 2020 - 29th USENIX Security Symposium, Aug 2020, Boston / Virtual, United States. pp.1839--1856. ⟨hal-03136301⟩

### Metrics

Les métriques sont temporairement indisponibles