Fingerprints and Key IDs
OpenPGPv4 fingerprints are made from an SHA-1 digest over the key's public key material, creation date, and some boilerplate. SHA-1 digests are 160 bits in length. The "long key ID" of a key is the last 64 bits of the key's fingerprint. The "short key ID" of a key is the last 32 bits of the key's fingerprint. You can see both of the key IDs as a hash in and of themselves, as "32-bit truncated SHA-1" is a sort of hash (albeit not a cryptographically secure one).
I'm arguing here that short Key IDs and long Key IDs are actually useless, and we should stop using them entirely where we can do so. We certainly should not be exposing normal human users to them.
(Note that I am not arguing that OpenPGP v4 fingerprints themselves are cryptographically insecure. I do not believe that there are any serious cryptographic risks currently associated with OpenPGP v4 fingerprints. This post is about Key IDs specifically, not fingerprints.)
Key IDs have serious problems
Asheesh pointed out two years ago that OpenPGP short key IDs are bad because they are trivial to replicate. This is called a preimage attack against the short key ID (which is just a truncated fingerprint).
Today, David Leon Gil demonstrated that a collision attack against the long key ID is also trivial. A collision attack differs from a preimage attack in that the attacker gets to generate two different things that both have the same digest. Collision attacks are easier than preimage attacks because of the birthday paradox. dlg's colliding keys are not a surprise, but hopefully the explicit demonstration can serve as a wakeup call to help us improve our infrastructure.
So this is not a way to spoof a specific target's long key ID on its
own. But it indicates that it's more of a worry than most people tend to
think about or plan for. And remember that for a search space as small
as 64-bits (the long key ID), if you want to find a pre-image against
any one of 2k keys, your search is actually only in a (64-k)-bit
space to find a single pre-image.
The particularly bad news: gpg doesn't cope well with the two keys that have the same long key ID:
0 dkg@alice:~$ gpg --import xgpg: key B8EBE1AF: public key "9E669861368BCA0BE42DAF7DDDA252EBB8EBE1AF" importedgpg: Total number processed: 1gpg: imported: 1 (RSA: 1)0 dkg@alice:~$ gpg --import ygpg: key B8EBE1AF: doesn't match our copygpg: Total number processed: 12 dkg@alice:~$
This probably also means that caff (from the signing-party
package) will also choke
when trying to deal with these two keys.
I'm sure there are other OpenPGP-related tools that will fail in the face of two keys with matching 64-bit key IDs.
We should not use Key IDs
I am more convinced than ever that key IDs (both short and long) are actively problematic to real-world use of OpenPGP. We want two things from a key management framework: unforgability, and human-intelligible handles. Key IDs fail at both.
- Fingerprints are unforgable (as much as SHA-1's preimage resistance, anyway -- that's a separate discussion), but they aren't human-intelligible.
- User IDs are human-intelligible, and they are unforgable if we can rely on a robust keysigning network.
- Key IDs (both short and long) are neither human-intelligible nor unforgable (regardless of existence of a keysigning network), so they are the worst of all possible worlds.
So reasonable tools should not expose either short or long key IDs to users, or use them internally if they can avoid them. They do not have any properties we want, and in the worst case, they actively mislead people or lead them into harm. What reasonable tool should do that?
How to replace Key IDs
If we're not going to use Key IDs, what should we do instead?
For anything human-facing, we should be using human-intelligible things like user IDs and creation dates. These are trivial to forge, but people can relate to them. This is better than offering the user something that is also trivial to forge, but that people cannot relate to. The job of any key management UI should be to interpret the cryptographic assurances provided by the certifications and present that to the user in a comprehensible way.
For anything not human-facing (e.g. key management data storage, etc), we should be using the full key itself. We'll also want to store the full fingerprint as an index, since that is used for communication and key exchange (e.g. on calling cards).
There remain parts of the spec (e.g. PK-ESK, Issuer subpackets) that make some use of the long key ID in ways that provide some measure of convenience but no real cryptographic security. We should fix the spec to stop using those, and either remove them entirely, or replace them with the full fingerprints. These fixes are not as urgent as the user-facing changes or the critical internal indexing fixes, though.
Key IDs are not useful. We should stop using them.