0xdeadbeef comes of age: making keysteak with GnuPG

[David Leon Gil <coruus () gmail com>]

Replying a little late to Thijs's message to oss-security. First:

"keysteak", a PoC keyserver-in-the-middle that generates fake V3
public keys with the same long keyid as V4 public keys requested from
a keyserver. It uses the classic 0xdeadbeef attack and a (novel?) V3
key/V4 signature  crossgrade.*) Available at:
https://github.com/coruus/cooperpair/tree/master/keysteak

As an example, a spoofed key for a Linux distro is attached. You can
confirm that the spoofed key is *not* the real key (which is available
at https://tails.boum.org/tails-signing.key) by doing either
       gpg2 --list-packets spoofed_tails.asc
or,
       mkdir test; chmod go-rwx test
       gpg2 --home ./test --import spoofed_tails.asc
       gpg2 --home ./test -k --fingerprint

* V3 signatures are not accepted without an explicit option in 2.1;
they produce a warning in 2.0 (and maybe recent 1.x as well).

(In summary: If you don't use the WoT, get OpenPGP keys via HTTPS.
E.g.: keybase.io or pgp.mit.edu (the latter thanks to Yan Zhu's
lobbying).)

Some details/comments:

Date: Mon, 1 Sep 2014 20:33:20 +0200
From: Thijs Kinkhorst <thijs ()    ian org>
Subject: gpg blindly imports keys from keyserver responses

> It is however argued that . . . specifying the full fingerprint is a safe way to retreive
> a key for a known-good fingerprint. But this argument is again somewhat countered
> by an attack on V3 [fingerprints] making such a request dubious again.

This isn't quite right.

- V3 fingerprints are 16 bytes (32 hex digits) long; they're an MD5
digest of the RSA modulus.
- V4 fingerprints are 20 bytes (40 hex digits) long; they're an SHA1
digest of the public key packet (kind of).

So: V3 and V4 fingerprints are easily distinguishable. Long keyids aren't:

- V3 long keyids are 8 bytes long. They're the low 8 bytes of the RSA modulus.
- V4 long keyids are 8 bytes long. They're the low 8 bytes of the V4
fingerprint.

As Greg Rose demonstrated (and Paul Leyland had earlier noted)[1],
this makes it trivial to forge long V3 keyids: You can control up to
about half the bits of an RSA modulus without affecting the strength
of the resulting key.

Note: Once you have a key with a given 64-bit keyid in your keychain,
GnuPG will not import any other key with the same 64-bit keyid.[2]
Even if you specify the new key by fingerprint.

It's been 18 years since the 0xdeadbeef attack. Maybe it's time to
deprecate V3 OpenPGP keys?

(There's a discussion on gnupg-devel on this presently; I am hopeful...)

[1] Raph Levien's excellent explanation of the history and math of the
0xdeadbeef attack:
https://groups.google.com/forum/#!topic/sci.crypt/JSSM6NbfweQ

[2] Thus the spoofed key and the real key are a "cooper pair".

Attachment: spoofed_tails.asc
Description: