OpenPGP Short Key IDs are Weak
How did this happen?
OpenPGP short key IDs are much too small to provide a reasonable security against collision attacks. There are as few as 2^32 different short key IDs, which is less than 5 billion.
Generating such a large number of keys would require lots of time. But, the key ID is calculated from the OpenPGP public key (eg., the RSA public key) and the key generation time (as a unix timestamp, thus the number of seconds since 1970-01-01). This allows to reduce the number of keys to generate by orders of magnitude.
Using a rather simple computer program, one can easily generate key pairs, and then iterate over all reasonable key creation time values. Lets assume a reasonable period of the last five years, this means 150 million different key IDs. A probably somewhat under-estimate (dividing the number of possible short key IDs by the number of key IDs per generated key) which does not take into account that we also will have duplicate key IDs within the generated set assumes you only need to generate less than 30 "real" keys, which is a matter of seconds or minutes.
The OHM 2013 talk Trolling the Web of Trust by Micah Lee presented this flaw and some example implementation on how to exploit it. Richard Klafter and Eric Swanson used this technique to replicate the full strong set (the largest set of keys completely connected to each other, with other words most of the set of active OpenPGP users that did mutual key signing with others) including certifications and published it on a (non synchronizing) key server.
It is only a matter of time until somebody will copy the "faked" web of trust to the "real key servers", or simply generate his own "copy".
I provided a little bit longer explanation in What is an OpenPGP Key ID collision?, especially discussing the different OpenPGP key ID types and how they're related.
Don't use Short Key IDs
What can I do about this?
This attack does not only struck your key, but possibly every single one. Generating collisions does not require (much) special knowledge nor specific hardware, every "power user" will be able to generate collisions on commodity machines after reading up for a short time.
The only way out of this is to stop using short key IDs, especially when no subsequent fingerprint validation is performed. Thus:
- Whenever referring to your OpenPGP key - say on business cards or your mail signature - indicate your long key ID (64 bits, or 16 hex digits), or even better the full fingerprint.
- Never give trust to a short key ID. If you use one to fetch somebody's key, verify against the long key or fingerprint instead (if you're tired of typing the long key ID, but it's only eight digits more!).
- Tell about the problem. Refuse snippets/business cards/documents only containing the short key ID. Make people aware! This is a great point in time to educate over the web of trust in general, in my experience lots of OpenPGP users didn't completely get the basics of verifying validity of keys.
Do I have to revoke my key?
Revoking your OpenPGP key will not help you, an attacker will be able to recreate a new colliding OpenPGP key within seconds or minutes. Rather keep your reputation (certifications) in the web of trust, and make sure to extend it!
