Category: Blog

In response to the GPG.Fail attacks, a Hacker News user made this claim about the 64-bit “Long Key IDs” used by OpenPGP and GnuPG, while responding to an answer I gave to someone else’s question:

OK, to be clear, I am specifically contending that a key fingerprint does not include collisions. My proof is empirical, that no one has come up with an attack on 64 bit PGP key fingerprints.

Hacker News Thread

This was a stupid thing to say to me, of all people.

CMYKat

And thus:

Proof of Concept

Save this file as pubkey1.asc:

-----BEGIN PGP PUBLIC KEY BLOCK-----

xjQEZVQvDBYKCSsGAQQB2kcPAQEHQPlChumZ771BEWmLgtsrm2QUf3YE4xSbpiRr
wGelIDITzShDb2xsaXNpb24gS2V5IDEgPGtleTFAY29sbGlzaW9uLmV4YW1wbGU+
=8+QC
-----END PGP PUBLIC KEY BLOCK-----

Save this file as pubkey2.asc:

-----BEGIN PGP PUBLIC KEY BLOCK-----

xjQEZVRJOxYKCSsGAQQB2kcPAQEHQE5YOa8jzfZ1IAUmqaxKvrGdq3RJWQ1QBfh4
9ffaD/S3zShDb2xsaXNpb24gS2V5IDIgPGtleTJAY29sbGlzaW9uLmV4YW1wbGU+
=Ah4C
-----END PGP PUBLIC KEY BLOCK-----

Run the following commands, and despair:

gpg --list-packets pubkey1.asc | grep keyid
gpg --list-packets pubkey2.asc | grep keyid

You will observe the following:

$ gpg --list-packets pubkey1.asc | grep keyid
        keyid: 948F9326DD647C78
$ gpg --list-packets pubkey2.asc | grep keyid
        keyid: 948F9326DD647C78

However, the public keys and full fingerprints are different for each public key.

CMYKat

What Is Actually Happening?

This was the result of a Birthday attack against the 64-bit size of the “Long Key ID” feature of OpenPGP.

I’ve written about the Birthday Bound before. But generally:

• If you have possible outputs from a function…
• And the input domain is larger than the output domain…
• And you want to generate two distinct inputs that produce the same output (a collision attack)…

…then you only need about or inputs before your collision probability approaches 50%.

Since the output space of a Long Key ID is 64 bits, there are possible Long Key IDs. However, you expect a collision with about 50% probability after only Long Key IDs are generated.

This is a widely known fact about cryptography, and the crux of the attack.

EDIT: Apparently it was also done before. In 2019.

CMYKat

Methodology

The full attack took about 3 days on a laptop, running in the background while I was doing other work.

This is within an order of magnitude of the same runtime needed to break Rainbow, for comparison.

Because it was a memory-constrained device, the strategy looked roughly like this:

1. Generate keypairs. (~2 seconds)
2. For each keypair, iterate over a range of UNIX timestamps.
3. Compute the Key ID for each (public key, timestamp).
4. Write the Key IDs, index pointing to which keypair, and timestamps to a file (~15 hours).
5. Use the sort command on this enormous file (~57 hours).
   • This probably took so long because my laptop goes into sleep mode when I’m not using it, so at least 20 hours of that can be written off as “nap time for my computer”.
6. Read through this file from start to until a colliding key ID was found (~30 minutes).

I could have done it faster if I felt like using a cloud provider, but I didn’t want to put too much work into this.

Virtually no cryptography expert worth listening to will be surprised by this.

“What impact does colliding Key IDs give an attacker?”

To head off any questions like this, we need to be clear that a successful collision is, in and of itself, a successful attack. This is cryptography. None of us can weasel-word our way out of that fact.

But it’s still worth entertaining: what can you do with such a colliding keypair in practice?

Let’s say I was the maintainer of a popular open source package and got a bunch of Linux kernel devs to sign pubkey1.asc instead of publishing it here.

If I decided to go rogue in the future, I could replace the public key that other people will download with pubkey2.asc. Especially if I secretly control the PGP key server they’re using.

Users following instructions that mean to verify the Long Key ID instead of the full fingerprint will see that pubkey2.asc checks out, and then install backdoored software. All their apes, gone!

If I’m ever confronted about it (especially by the folks that signed my actual public key), I could point out that my private key was never compromised, and claim the attacker clearly did a “preimage” attack on my Long Key ID. Thus, there’s plausible deniability in the absence of other forensics.

Especially since PGP users advise each other to check the Long Key ID. (Alternative archive.)

This kind of attack has to be setup in advance. Collision attacks aren’t preimage attacks. But it’s a realistic exploit scenario.

Bonus: The Private Keys

private1.asc

-----BEGIN PGP PRIVATE KEY BLOCK-----
xVkEZVQvDBYKCSsGAQQB2kcPAQEHQPlChumZ771BEWmLgtsrm2QUf3YE4xSbpiRr
wGelIDITAAEAX7B7GVQBGE9VxroU6ilaSYp7D0QrZFRgbLDBM+uVTxEMis0dVGVz
dCBLZXkgMSA8a2V5MUBleGFtcGxlLmNvbT4=
=hStH
-----END PGP PRIVATE KEY BLOCK-----

private2.asc

-----BEGIN PGP PRIVATE KEY BLOCK-----
xVkEZVRJOxYKCSsGAQQB2kcPAQEHQE5YOa8jzfZ1IAUmqaxKvrGdq3RJWQ1QBfh4
9ffaD/S3AAEAA6ztnLShhUmlWLdG8TLgtyT6SsW+EibmRMuMOzUK5iMQN80dVGVz
dCBLZXkgMiA8a2V5MkBleGFtcGxlLmNvbT4=
=Tdrc
-----END PGP PRIVATE KEY BLOCK-----

TL;DR

Do not make stupid “empirical” claims about the security of cryptosystems, especially when the cost to disprove you is so low.

Header art by Kyume.

Original post written by Soatok