Subject: [openpgp] "SHA-1 is a Shambles" and forging PGP WoT signatures

From: Marcus Brinkmann <[email-masked]>
Date: Wed, 22 Jan 2020 15:31:26 +0100

Hi,

I have now read the paper "SHA-1 is a Shambles"[1,2] by Gaëtan Leurent
and Thomas Peyrin, and want to bring to your attention the significance
of the included work for OpenPGP.

Key findings: The authors significantly improve the identical-prefix and
chosen-prefix collisions for SHA-1, demonstrating that chosen-prefix
collisions are possible at a cost of 45k USD.  They also demonstrate how
to use a chosen-prefix collision to transfer a signature that binds a
photo-ID to a key to a crafted other key with a chosen user ID.

Some more explanations:

The attack works as follows: The attacker prepares a public key packet
for a 8192 bit RSA key, and assigns an arbitrary user ID for which the
attacker wants to get a certificate from the victim.  The attacker also
prepares another public key packet for a 6114 bit RSA key, followed by a
user attribute packet with an innocent (honest) photo id. The JPEG
format allows arbitrary trailing data hiding the user ID under attack.

A signer that signs the photo id will inadvertently also sign the
contained user ID.  The signature can then be transfered to the
colliding 8192-bit key with that user ID, because the signed hash is
identical (the JPEG is hidden in the public exponent of the larger key).

The attack is not stealthy and can be detected before and after the
signature is made (for example by the user id in the jpeg or by the jpeg
in the public key).

Some observations and recommendations:

* Obvious: do not use SHA-1 in signatures. GnuPG 2.x now forbids them,
but GnuPG 1 users should be aware of that issue (among many other issues
in GnuPG 1).

* Large key sizes in RSA seem to make the attack simpler compared to
short key sizes in ECC (which does not offer enough rooms for a
collision block).

* Do not sign photo ids.  In fact, photo ids are problematic in many
other ways and should be deprecated and not be used anymore. Support for
user attribute packets should be dropped from the standard.

* The authors could have easily created colliding public keys with
identical (160 bit SHA-1) fingerprints, at the cost of 45k USD.
Although I don't know about any attack made possible by owning such a
pair of keys, the pure existence of a fingerprint collision could cause
problems in some appliations, triggering potential bugs in code that
assumes fingerprints can never be identical.

* The attack complexity is 2^63.4, while long key IDS are 64 bit.  Long
key ID collisions based on the birthday collision have been demonstrated
as early as 2013 [3, 4].  Just based on the bit complexity, a pre-image
collision for long key IDs seems within reach now (up to an unknown
constant factor).

Thanks,
Marcus

[1] https://sha-mbles.github.io/
[2] https://eprint.iacr.org/2020/014.pdf
[3] "OpenPGPv4 long keyid collision test cases?" (David Leon Gil)
https://mailarchive.ietf.org/arch/msg/openpgp/Al8DzxTH2KT7vtFAgZ1q17Nub_g
[4] "The Long Key ID Collider" (Chris Wellons)
https://nullprogram.com/blog/2019/07/22/

-- 
Dipl.-Math. Marcus Brinkmann

Lehrstuhl für Netz- und Datensicherheit
Ruhr Universität Bochum
Universitätsstr. 150, Geb. ID 2/461
D-44780 Bochum

Telefon: +49 (0) 234 / 32-25030
http://www.nds.rub.de/chair/people/mbrinkmann

---

From: Florian Weimer <[email-masked]>
Date: Wed, 22 Jan 2020 22:18:41 +0100

> user attribute packets should be dropped from the standard.

I expect that a similar attack would work involving non-critical
hashed subpackets in the private area.  They should provide enough
wiggle room.

> assumes fingerprints can never be identical.

It would definitely be nice to have such colliding keys for testing
purposes.

---

From: Marcus Brinkmann <[email-masked]>
Date: Thu, 23 Jan 2020 16:57:30 +0100

Hi,

> hashed subpackets in the private area.  They should provide enough

You certainly can use hashed subpackets to get a collision, although the
attacker would then need to control the content of such a subpacket
during signing (which is not required by the setup in the paper).

I have to add another point to the list of observations.  From the
paper: "We point out that the chosen-prefix collision is computed before
choosing the UserIDs and images that will be used in the attack.
Therefore, a single CPC can be reused to attack many different victims"

Recommendation: It would be prudent for implementers to blacklist public
keys starting with the same bits as the published colliding key for bob
under https://sha-mbles.github.io/bob.asc.

The author also describe an attack variant where the collision is made
within the jpg, but this requires computing a new collision for each
individual attack.  They suspect that more variants are possible.

Thanks,
Marcus

---

From: Kai Engert <[email-masked]>
Date: Thu, 23 Jan 2020 23:56:39 +0100

> assumes fingerprints can never be identical.

Does this mean, anyone can create a key pair that has the same 
fingerprint as I have on my business card, by spending that amount of money?

Does this mean, comparing a 20 bytes (40 hex digits) fingerprint, as 
printed by e.g. GnuPG 2.2.x, is no longer a reliable way to verify you 
have obtained the correct key?

Thanks
Kai

---

From: [email-masked]
Date: Thu, 23 Jan 2020 18:08:10 -0500

On 1/23/2020 at 5:57 PM, "Kai Engert"  wrote:On 22.01.20 15:31, Marcus

Does this mean, anyone can create a key pair that has the same 
fingerprint as I have on my business card, by spending that amount of
money?

=====
I have not checked the original paper, but I *think* they were talking
about making a key collision, 
with a given 160 bit SHA-1 fingerprint,
but *without* the same name, and e-mail address,
which would be much less of a practical threat.

Anybody, please correct, if I am wrong, and they did include the name
and e-mail in the proposal for a successful collision.

Thanks,

vedaal

---

From: Marcus Brinkmann <[email-masked]>
Date: Fri, 24 Jan 2020 00:48:43 +0100

Hi,

> fingerprint as I have on my business card, by spending that amount of

No. That is something that we would call a "second pre-image attack" on
your fingerprint.  The collision attacks described in the paper generate
two colliding files from scratch.  So, the attacker could come up with
two entirely new keys that have identical fingerprints.  As I said, I
don't know any attack that would be enabled by such two keys, but it is
concerning, because software might not be prepared for that to happen.

Pre-image attacks are much harder than collision attacks (which are
easier due to the "birthday paradox").  However, it is not good practice
to hold on to a cryptographic hash function for a long time just because
one narrow particular application of it has not been demonstrated
publicy to be broken in practice yet.  We pretty much know the
progression in which hash function attacks improve, and interest in
researching an obsolete hash function decreases pretty rapidly.  I'm
glad the authors spent the time and money to demonstrate their optimized
attacks on SHA-1, but such expenses will be increasingly hard to justify.

> have obtained the correct key?
The answer to this would formally be "yes", because after creating two
such keys, the attacker could first show you one key, and, later on show
you the other key and if the only thing you remember about the first key
is the fingerprint, you have no way to notice the swap.

The question if this is an actual problem (i.e.: violates a security
goal that the user is actually interested in) is more difficult to
answer and depends on many details.  Figuring this out would require a
careful review of OpenPGP implementations and applications using OpenPGP.

Thanks,
Marcus

---

From: Michael Richardson <[email-masked]>
Date: Thu, 23 Jan 2020 19:00:45 -0500

> Does this mean, anyone can create a key pair that has the same fingerprint as
    > I have on my business card, by spending that amount of money?

I did not read that.  It could be true, but I did not conclude that.
I read that they can forge a signature from you (or me), on a key, attesting
to your email address being attached to your key.

So, they can attach a different key, with a different fingerprint, to your
email address, with a signature that appears to come from either of us.

    > Does this mean, comparing a 20 bytes (40 hex digits) fingerprint, as printed
    > by e.g. GnuPG 2.2.x, is no longer a reliable way to verify you have obtained
    > the correct key?

I don't believe that this is the case.

I don't believe that there is anything in the bytes that goes into the
fingerprint that would permit a JPEG to be inserted to provide the mutable
bytes needed.

I also want to say that constructs that use HMAC-SHA1 (IPsec, TLS) are not affected.

--
]               Never tell me the odds!                 | ipv6 mesh networks [
]   Michael Richardson, Sandelman Software Works        |    IoT architect   [
]     [email-masked]  http://www.sandelman.ca/        |   ruby on rails    [

---

From: Damien Goutte-Gattat <[email-masked]>
Date: Fri, 24 Jan 2020 00:22:28 +0000

>fingerprint as I have on my business card, by spending that amount of 

No.

What they have done is generate two keys in such a way that a SHA-1 
certification on one key is also a valid certification for the other 
key.

It means that someone can:

1) create a key A with *your* user ID;

2) create a key *B* with a different user ID;

3) have someone certify the key B with a SHA-1-based signature;

4) attach that signature to key *A* and your user ID.

At the end, that someone gets a key with your name and a 
cryptographically valid signature (or even several signatures, if the 
attacker repeats steps 3 and 4). She can thus impersonate you to anyone 
trusting the signer(s) involved at step 3.

What Marcus says the author *could* have done is to generate the two 
keys A and B in such a way that they also have the same fingerprint. 
They have not done so, as one can easily verify e.g. by running `gpg 
--list-packets` on the provided keys (they don’t even have the same 
short key ID). In the scenario outlined above, I am not sure the 
attacker would have anything to gain in having the two keys A and B 
sharing the same fingerprint anyway, which may explain why the authors 
did not try. They don’t even discuss that possibility.

In any case, the attack does *not* allow to generate a key with the same 
fingerprint as a pre-existing, un-related key.

Cheers,

- Damien

---

From: Michael Richardson <[email-masked]>
Date: Fri, 24 Jan 2020 11:57:09 -0500

Damien Goutte-Gattat <[email-masked]> wrote:
    > What Marcus says the author *could* have done is to generate the two keys A
    > and B in such a way that they also have the same fingerprint. They have
    > not

I'm not convinced that there are enough under-determined bytes that can be
mutated in the content that goes into making the fingerprint.
AFAIK, it's just the key.

I guess, maybe if the key is big enough (rsa 8K, bigger), that the bytes
could be in the prime itself.  Are you saying that?  If so, I wonder what the
smallest key for which this is true is.

---

From: Michael Richardson <[email-masked]>
Date: Fri, 24 Jan 2020 12:00:51 -0500

> is the fingerprint, you have no way to notice the swap.

Would the attacker have to control the private keys of both generated keys to
accomplish this?  I don't entirely see why.

Clearly the signatures generated by the two keys (with identical
fingerprints) would also be different (assume that the signatures were
calculated on a SHA256 hash, to remove an attack from that side).

---

From: Damien Goutte-Gattat <[email-masked]>
Date: Fri, 24 Jan 2020 21:21:28 +0000

On Fri, Jan 24, 2020 at 11:57:09AM -0500, Michael Richardson wrote:
>I guess, maybe if the key is big enough (rsa 8K, bigger), that the 
>bytes could be in the prime itself.  Are you saying that?

Yes.

> If so, I wonder what the smallest key for which this is true is.

The collision found by the authors used 9 near-collision blocks (4608 
bits). They believe it would have been possible to find a collision with 
7 near-collision blocks (3584 bits), which could fit into a 4096-bit RSA 
key.

- Damien

---

From: Marcus Brinkmann <[email-masked]>
Date: Sat, 25 Jan 2020 02:15:51 +0100

Hi,

> smallest key for which this is true is.

The authors demonstrate a collision block within a RSA 6144 bit public
key.  The collision happens at the first 6056 bits of the modulus, and
the remaining 88 bits are used to make a valid modulus for the public
exponent, which is fixed at 2^16+1.

Thanks,
Marcus

---

From: Marcus Brinkmann <[email-masked]>
Date: Sat, 25 Jan 2020 02:21:14 +0100

Hi,

> accomplish this?  I don't entirely see why.

As the collision I am thinking of happens in the modulus MPI, the
attacker would control the modulus and thus the private exponent (public
exponent fixed at 2^16+1).

> calculated on a SHA256 hash, to remove an attack from that side).

Yes. Any signatures made by these keys would be different.

Thanks,
Marcus