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

From: Russ Housley <[email-masked]>
Date: Tue, 7 Jan 2020 10:23:08 -0500

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).

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 7 Jan 2020 13:53:37 -0500

I was just about to post. As it happens, I was in the middle of making an
intro video on digest functions for my free course on crypto. So I guess I
will tape it today rather than waiting till Friday (if the heavy equipment
laying new gas pipes in the street is quiet enough).

The need to move on from SHA-1 was one of the reasons I originally started
looking at an improved fingerprint presentation using Base32 encoding that
allowed for safe truncation etc. SHA-1 has more than enough bits for many
applications, the problem is the algorithm. I would like to move to
SHA-2-512/ SHA-3-512 and only 512 bits regardless of the precision required.

https://mathmesh.com/Documents/draft-hallambaker-mesh-udf.html

On Tue, Jan 7, 2020 at 10:23 AM Russ Housley <[email-masked]> wrote:

> _______________________________________________
> saag mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/saag
>

---

From: Peter Gutmann <[email-masked]>
Date: Wed, 8 Jan 2020 00:05:57 +0000

> Application to the PGP Web of Trust

I'd commented on this on the cryptography list, my thoughts were:

-- Snip --

An interesting paper has just appeared on the IACR e-print archive:

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

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

tl;dr: Attacks sped up by a factor of ~16 over previous work, chosen-prefix
collision for ~$75k and 2 months effort.

It's a long (32 pages) but interesting read.  The only thing I have a bit of
an issue with is the conclusion:

  SHA-1 signatures now offers virtually no security in practice

It should really be "SHA-1 signatures where the attacker has two months time
and tens of thousands of dollars (there are some cheaper options than $75k) to
prepare a forgery offer no security in practice".

Even then, the demonstrated attack relies on the ability to stuff arbitrary
garbage data into the signed message (in this case into a JPEG image after the
End-of-Image marker), so add:

  "... and the ability to stuff arbitrary attacker-chosen data into the signed
  message..."

to that.

Not trying to downplay the findings in the paper, but more to provide some
perspective on where the major risks lie for people who need to think about
the use of SHA-1 in legacy products and systems.

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 7 Jan 2020 19:29:20 -0500

> prepare a forgery offer no security in practice".

I think we can be fairly clear what the real risk is going to be and I am
working on this in the podcast (could not record it today because there
were roadworks outside the studio).

What will happen is

* Short term panic and lots of people explaining there is nothing to worry
about.
* Five to ten years of complacency.
* A successful attack on a significant target that did not transition but
proved profitable.

$75K will be $5K before long and don't discount the possibility that $75K
could be a profitable attack. I am sure that organized crime has noted the
Lehman etc insider trading frauds and started planting moles in the banks.
$75K would be nothing when they are looking to cash out $100 million. We
have observed very significant amounts being paid for zero day attacks.

Most likely attack targets will be Git repos and similar applications using
SHA-1 hashes internally. The Git project did raise itself from the usual
security negligence Torvalds projects suffer from. The IPv6 buffer overrun
guards he stripped out of the kernel because he didn't understand them in
his 'compiler masturbation' rant is a more likely source of security
breach. It speaks of a hostile work environment.

---

From: Christian Huitema <[email-masked]>
Date: Tue, 7 Jan 2020 15:35:56 -1000

On 1/7/2020 2:29 PM, Phillip Hallam-Baker wrote:
> $75K will be $5K before long and don't discount the possibility that
> $75K could be a profitable attack. I am sure that organized crime has
> noted the Lehman etc insider trading frauds and started planting moles
> in the banks. $75K would be nothing when they are looking to cash out
> $100 million. We have observed very significant amounts being paid for
> zero day attacks.

The paper explains that the actual cost of the attack is $11K, and that
the $75K was spent because of trials and errors tuning the attack. Also,
they apparently bought the capacity at retail price. So, yes, probably
close to $5K already for a capable adversary. Not to mention a botnet
with access to a bunch of GPUs.

-- Christian Huitema

---

From: Jeffrey Walton <[email-masked]>
Date: Tue, 7 Jan 2020 20:46:01 -0500

> > branch now rejects SHA-1 signatures (the issue is tracked as

And if interested, Mozilla's cacert.pem
(https://curl.haxx.se/docs/caextract.html) has 52 certificates at
risk:

$ ./test.exe
Load certificates from cacert.pem
Certificates total: 138

ecdsa-with-SHA256: 5
ecdsa-with-SHA384: 16
id_sha1WithRSASignature: 52
id_sha256WithRSAEncryption: 56
id_sha256WithRSAEncryption: 8
id_sha512WithRSAEncryption: 1

Jeff

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Tue, 7 Jan 2020 20:49:20 -0500

Those certificates are not actually at risk because they were originally
signed when SHA-1 was still trusted. It is the intermediate and EE certs
that are the concern.

On the cost of attack thing. $11K is well within the amount of computer
time that can be stolen...

---

From: Andrey Jivsov <[email-masked]>
Date: Tue, 7 Jan 2020 19:18:22 -0800

Even more precise, the hash algorithm in X.509 certificate trust anchors
doesn't matter for security. Self-signed X.509 certs are the most common
trust anchors.

If a self-signed cert is a part of a certificate chain, it must be a trust
anchor. Therefore, the hash algorithm in a self-signed X.509 certificate
never matters for security. This should include compliance reasons of "no
SHA-1" because the signature field on self-signed cert should never be
verified (we can, but it just wastes compute cycles).

Remarkably, the above straightforward facts are for some reason not
well-understood and companies make an effort to remove X.509 trust anchors
with SHA-1 in signatures over them.

---

From: Alan DeKok <[email-masked]>
Date: Tue, 7 Jan 2020 22:22:12 -0500

> On Jan 7, 2020, at 10:18 PM, Andrey Jivsov <[email-masked]> wrote:
> 
> Even more precise, the hash algorithm in X.509 certificate trust anchors doesn't matter for security. Self-signed X.509 certs are the most common trust anchors. 
> 
> If a self-signed cert is a part of a certificate chain, it must be a trust anchor. Therefore, the hash algorithm in a self-signed X.509 certificate never matters for security. This should include compliance reasons of "no SHA-1" because the signature field on self-signed cert should never be verified (we can, but it just wastes compute cycles).
> 
> Remarkably, the above straightforward facts are for some reason not well-understood and companies make an effort to remove X.509 trust anchors with SHA-1 in signatures over them.

  My $0.02 is it's because it's easier to say "get rid of SHA1" than to explain to people where / when it can be used, and why.  I'm not sure that they're wrong.

  Alan DeKok.

---

From: Peter Gutmann <[email-masked]>
Date: Thu, 9 Jan 2020 07:16:55 +0000

Phillip Hallam-Baker <[email-masked]> writes:

>signed when SHA-1 was still trusted. It is the intermediate and EE certs that
>are the concern.

In terms of the web PKI, they're also not at risk because they're not
defending against anything that non-nation-state attackers care about.  And
I'm not being snarky there, I mean that literally, there's no point in
attackers investing anything more than the minimum necessary in trying to
forge certs for web sites because they can do just as well without them (Refs:
Too many to list here, but start with the APWG data if you need something to
go from).

However, let's look at the actual threat a bit more closely, and in particular
from the point of view of someone who has legacy infrastructure they need to
work with and wants to know where and what needs shoring up.  The attack
requires that someone be able to stuff arbitrary binary data that the victim
won't check into a signed message, as well as causing the victim to
reinterpret the message in an entirely different manner than originally
intended.

This happens to work quite well for OpenPGP/GPG, but is more tricky for certs
both because there's no attackerControlledData extension (yet [0]) and because
of the amount of decoration that ASN.1 adds to anything that's being encoded.
So what the attacker would have to do is define a new extension
attackerControlledData and create a cert where it's present in there, to
mirror the (mis-)use of JPEG images with attached binary garbage in OpenPGP/
GPG (this is from reading the paper on-screen, I still need to get a printed
version to study properly, in particular to try and understand whether the
process described in section 6.1 can even be applied to an X.509 cert), and
also to figure out how to get the victim to reinterpret what's being signed as
was done for the OpenPGP data.

A simple countermeasure there for long-lived signatures where this type of
attack is a threat (assuming the ASN.1-reinterpretation is achievable), e.g.
X.509 certs in legacy deployments, is that if SHA-1 is being used, reject
certs with an unknown extension, or one with type-and-value fields of unknown
type.

Peter.

[0] Watch out for an April 1 RFC "The attackerControlledData extension for
    X.509" :-).

---

From: "Black, David" <[email-masked]>
Date: Thu, 9 Jan 2020 14:59:56 +0000

> [0] Watch out for an April 1 RFC "The attackerControlledData extension for

Be careful what you wish for ... after all, RFC 1149 was implemented :-) !!

https://en.wikipedia.org/wiki/IP_over_Avian_Carriers

Thanks, --David

> -----Original Message-----
> From: saag <[email-masked]> On Behalf Of Peter Gutmann
> Sent: Thursday, January 9, 2020 2:17 AM
> To: Phillip Hallam-Baker; [email-masked]
> Cc: IETF SAAG
> Subject: Re: [saag] SHA-1 is a Shambles: First Chosen-Prefix Collision on SHA-
> 1
> 
> 
> [EXTERNAL EMAIL]
>

---

From: Watson Ladd <[email-masked]>
Date: Thu, 9 Jan 2020 11:45:47 -0500

On Thu, Jan 9, 2020 Peter Gutman wrote

> certs with an unknown extension, or one with type-and-value fields of

Let's look at actual exploitation of a chosen prefix attack in the CA
ecosystem. This happened twice, once as a talk demo and another time as
part of a cyberattack.

http://deweger.xs4all.nl/papers/[41]StSoApLeMoOsdW-RogueCA-Crypto[2009].pdf

Did the attackers succeed? Yes
Did they need a custom extension? No
Does the countermeasure work? No

Why is this less work then disabling SHA-1 verification 14 years after
Wang's attacks, 3 years after the Web PKI disabled SHA-1 etc?

There are some other countermeasures like injecting randomized large serial
numbers, but these aren't followed uniformly by CAs outside the Web PKI.

Beyond cryptography there are all manner of other attacks that require
updating. It's clear that slow update cycles and backwards compatibility
have had substantial negative impacts on security.

---

From: Peter Gutmann <[email-masked]>
Date: Fri, 10 Jan 2020 01:28:41 +0000

>Does the countermeasure work? No
Was the hash function and its weakness practically identical to MD5? No
Did the CA that was attacked randomise serial numbers? No

Again, this is just to understand how to mitigate problems for legacy stuff,
not to try and prolong SHA-1 use indefinitely, but it would be good to
understand where the exact risks for SHA-1 use lie.

Peter.

---

From: Viktor Dukhovni <[email-masked]>
Date: Thu, 9 Jan 2020 20:44:41 -0500

> understand where the exact risks for SHA-1 use lie.

In the DNSSEC space, it now seems a good time to emphasize the
deprecation (RFC8642) of algorithms 5 and 7 which sign with RSA-SHA1.

    https://tools.ietf.org/html/rfc8624#section-3.1 

the potential avenues for abuse are expored at:

    https://www.dns.cam.ac.uk/news/2020-01-09-sha-mbles.html

the attack is still comparatively expensive, and the attacks are
contigent on some additional operational practices, but it seems there's
enough exposure that is likely to only get worse, that it is much easier
to tell users to move along to stronger algorithms than try to explain
which use-cases remain safe, and which not.

-- 
    Viktor.

---

From: Robert Moskowitz <[email-masked]>
Date: Fri, 24 Jan 2020 10:19:47 -0500

I got to be at the conference.  A lot of very good material.  And note 
the attack on OCB2.  Thank you Russ for CCM to dodge the patent fight 
and thus NOT do OCB for 802.11i!   Of course we were looking at OCB1 at 
the time, but who knows what may have been in the final standard.  The 
timing was right for it to have been OCB2...

Anyway on to the SHA1 presentation and the Levchin award for it.

Quite interesting.  Unfortunately the video for it is not being provided at

https://totalwebcasting.com/view/?func=VOFF&id=columbia&date=2020-01-08&seq=1

But check out the Enterprise Cryptography talk from ABN AMRO and their 
moving away from SHA1 certs.

The CRLite talk was also interesting (and talk available).

As to the cost, we are in an exploded bubble right now due to the 
collapse of crypto coin mining. Too much available GPU farms idle 
looking for revenue.  But if this is the cost from public GPU farms 
looking for revenue (and 1 month leases), what is out there dark to our 
reseachers with a little bit of grant money to spend?

The 15 years from theory to practice is something to take away. Don't 
just ignore a theoretical attack, but don't immediately panic and then 
become complacent when nothing seems to come from it (the theory) in a 
year or two.