How do key servers resolve conflicts?

Question

According to the PGP network FAQ

While a number of key servers exist, it is only necessary to send your key to one of them. The key server will take care of the job of sending your key to all other known servers.

Quite convenient. Let's say Bob, despite the advice above, decides to upload his public key to two servers at the same time - one of which is compromised. The user has confidence in both servers and doesn't check if the key hasn't been changed. He signs off for the day.

At some point the servers will propagate the keys and a collision will occur. One of the following will happen:

1. The server will accept both keys (most likely)
2. The newest key will be rejected
3. The servers will "vote" on what they believe is the valid key (least likely)

Bob can now revoke the key he uploaded whenever he wants, however assuming (1) above, the false key will stay with the server indefinitely.

My question: Is there a way for a user to validate the correct key to the other (honest) servers? Perhaps sending a signed email with the correct key? Or is there another conflict resolution system?

---

Correction: When I say "conflict" I mean two public keys corresponding to the same email address.

Answer 1

Generally, PGP key servers resolve conflicts by not resolving them. Key servers store public keys. If they get several public keys which somehow "collide" for some notion of collision (say, both keys relate to the same email address), then they just keep all of them. And that's by design. In particular, fake keys cannot be deleted. The whole concept of the PGP Web of Trust is that trust comes from the signatures, not from the key servers, who are just storage areas (or, more often, garbage dump areas).

See for instance the MIT PGP key server FAQ:

1. Can you delete my key from the key server?

No, we cannot remove your key from the key server. When you submit a key to our key server the key is also forwarded to other key servers around the world, and they in turn forward the key to still other servers. Deleting the key from our server would not cause it to be deleted from any of the other servers in the world and so this is not an effective way to ensure the discontinued use of your key.

2. So, you can't delete my key, is there anything I can do?

If you still have the private key, you can use your PGP software to generate a revocation certificate, and upload that to the keyserver. The exact procedure for generating a revocation certificate varies depending on what PGP software you are using, please consult the documentation for more information. This will not delete your key from the key server, but it will tell people who download it that the key has been revoked, and should not be used.

3. But the reason I want to delete my key from the keyserver is that I lost the private key (so I can't generate a revocation certificate), can you please delete my key for me?

No.

I quite like the definitiveness of the answer to the third question.

Answer 2

OpenPGP data for a key is built from multiple, independent subpackets for each key. Key servers do not validate keys in any fashion (Symantec's servers do e-mail address validation and thus are kind of special), all trust comes from signatures between users.

OpenPGP identifies keys by a rather large fingerprint which should prevent collisions, so there should not be any conflicts regarding keys. These fingerprints used as identifiers are large enough to be sufficiently sure it represents exactly one key, not different ones.

For all other packets like signatures and UIDs, there are no conflicts by design. If another received packet is exactly the same like another one already stored on a keyserver, no need for resolving any conflicts -- just ignore it. If a keyserver doesn't know a received packet, he will keep and redistribute it. There is no way to delete a packet, it can be revoked by sending another one. Again, no packet will be deleted, but the revocation certificate gets stored and redistributed.

These subpackets only get added and are not ordered, thus no conflicts can occur. All merging is done by storing all new data from all sources, no conflict resolution is required.