[saag] SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-1

[Russ Housley <[e-mail]>]

https://eprint.iacr.org/2020/014

> SHA-1 is a Shambles - First Chosen-Prefix Collision on SHA-1 and
> Application to the PGP Web of Trust
> 
> Gaëtan Leurent and Thomas Peyrin
> 
> 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 [WYY05], but due to its high complexity it was only
> implemented in practice in 2017, using a large GPU cluster [SBK+17].
> More recently, an almost practical chosen-prefix collision attack
> against SHA-1 has been proposed [LP19]. 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 collisions attack against SHA-1: on an Nvidia GTX 970,
> identical-prefix collisions can now be computed with a complexity 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 11k US$ for a collision, and 45k US$ 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 75k US$ 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). 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 a forgery. This
> proves that SHA-1 signatures now offers 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).