Hacks: Smashing SHA-1 to Shambles for less than 1BTC

[grarpamp]

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
261.2 rather than 264.7, and chosen-prefix collisions with a
complexity of 263.4 rather than 267.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).