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

[Marcus Brinkmann <[e-mail]>]

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