Recently an Evil32 project group announced that they have found collisions for all OpenPGP keys from public keyservers (https://evil32.com/).
What does the term collision refer to?
Information Security Stack Exchange is a question and answer site for information security professionals. It only takes a minute to sign up.Sign up to join this community
They're referring to short key IDs, which are considered vulnerable to collision attacks for quite some time now. The problem is already referenced in RFC 4880, OpenPGP, 3.3. Key IDs:
A Key ID is an eight-octet scalar that identifies a key. Implementations SHOULD NOT assume that Key IDs are unique.
Each OpenPGP key has a fingerprint attached, calculated mainly from its public key packet which also contains the creation time. The calculation is defined in RFC 4880, OpenPGP, 12.2. Key IDs and Fingerprints.
There are short and long key IDs, which resemble the lower 32 respective 64 bits of the fingerprint. For example, looking at the IDs of my OpenPGP key:
fingerprint: 0D69 E11F 12BD BA07 7B37 26AB 4E1F 799A A4FF 2279 long id: 4E1F 799A A4FF 2279 short id: A4FF 2279
Fingerprints and key IDs are used, as sharing and comparing a whole key with usually 1024 to 8096 bits (adding some more for headers like the creation date) is very impractical.
While shorter IDs are easier to share and compare, they also increase the chance of collisions. This is growing exponentially with the lenght, in numbers. This is the number of possible key IDs for each length:
2^32 = 4294967296 2^64 = 18446744073709551616 2^160 = 1461501637330902918203684832716283019655932542976
The collision probability is the inverse of the numbers, being the chance of generating two different keys having the same ID.
Finding collisions for all publicly available OpenPGP key data requires finding collisions for barely 4 million keys. The project actually limited itself to the strong set (which contains the largest set of keys, that are all linked together, possibly with transient edges), and this currently contains about 55.000 keys.
Key collisions are still possible for long key IDs and fingerprints, but unlikely to very unlikely. The number of possible fingerprints is even larger than the number of possible UUIDs and these are usually expected to be unique. The same number of IPv6-adresses is available, techtarget.com has some examples to get an impression of numbers that large.
Generating keys with reasonable security takes some time, making it impractical to enumerate enough keys to find those four million collisions. But that's why I already mentioned the key generation time above: with a single key, you can create lots of different OpenPGP keys from a single (lets say, RSA) key without the expensive key generation, you simply iterate over the time. This was already proposed by Micah Lee in his Talk on "Trolling the Web of Trust".
Regarding the UNIX timestamp to be stored as a 32 bit number, and assuming SHA-1 as a good hash function has nearly equal distribution of result values, iterating of a single RSA key with different timestamps should suffice to generate all possible short key IDs (in reality, you will have to repeat this for a number of keys). If you want to only generate reasonable keys created within some reasonable time span (say, the last few years, definitely not before PGP was released and not in the future) you will have to use some more keys, but generating some more keys is still doable in a rather short time.
Openpgp uses key ids to identify keys. A "key ID" is a portion of the hash of the public key. There are two types, "short" (32-bit) and "long" (64-bit).
For short key IDs it's fairly easy to construct a new key that has the same short key ID, and same user visible details as an existing key. It's common (bad but common) practice to identify keys by their short key ids.
If you are building a system around openpgp you need to carefully check that short key IDs are NEVER used as a means of indicating which keys are trusted.
Even gpg itself messed this up, when requesting a key from a keyserver it would request by short key ID (even if the user specified a long one). If you use a "keyring" file as a list of keys trusted for a given purpose this makes it really easy to end up trusting a key generated by an attacker.
Even if you have an updated gpg it's almost certainly a good idea to only do "recv" and "refresh" operations on a keyring where the presense of untrusted keys is not a problem, then carefully inspect them before copying them to a "trusted keys only" keyring.