Practical Collision Attack Against Long Key IDs in PGP

Practical Collision Attack Against Long Key IDs in PGP
文章描述了一项针对OpenPGP和GnuPG 64位“长密钥ID”的碰撞攻击。通过生日攻击方法，在三天内生成了两个不同的公钥（pubkey1.asc和pubkey2.asc），它们具有相同的密钥ID（948F9326DD647C78），但指纹不同。这表明64位长密钥ID存在碰撞风险，验证了其不安全性。 2026-1-7 19:12:6 Author: soatok.blog(查看原文) 阅读量:6 收藏

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.

And thus:

Proof of Concept

Save this file as pubkey1.asc:

Save this file as pubkey2.asc:

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.

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 $2^{n}$ 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 $\sqrt{2^{n}}$ or $2^{n/2}$ inputs before your collision probability approaches 50%.

Since the output space of a Long Key ID is 64 bits, there are $2^{64}$ possible Long Key IDs. However, you expect a collision with about 50% probability after only $2^{32}$ 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.

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:

Generate $2^{16}$ keypairs. (~2 seconds)
For each keypair, iterate over a range of $2^{17}$ UNIX timestamps.
Compute the Key ID for each (public key, timestamp).
Write the Key IDs, index pointing to which keypair, and timestamps to a file (~15 hours).
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”.
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.

Bonus: The Private Keys

private1.asc

private2.asc

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.

文章来源: https://soatok.blog/2026/01/07/practical-collision-attack-against-long-key-ids-in-pgp/
如有侵权请联系:admin#unsafe.sh