tl;dr Fake PGP keys cannot be removed from public key servers, but they can be uploaded by anyone. In a business context this may lead to technical problems and awkward first business contacts. Why not write a postcard instead?
Problem PGP key servers serve as directories for PGP keys. Unfortunately it is hard to remove keys once they are uploaded. And anyone can upload any key, even their own fake version of keys associated with arbitrary email addresses. Wikipedia puts it this way: "This leads to an accumulation of old fossil public keys that never go away, a form of "keyserver plaque"." So, there is no way for the legitimate user of an email address to revoke or remove keys not actually generated by that user. There is no server side email validation. There is no enforced expiration on keys. And there is no usable web of trust. The original idea was that keys signed by other keys will eventually lead to a trust chain, but that turned out to be a privacy nightmare.
The real problem Suppose someone uploaded a fake key with your company's contact email address 'contact@your-company.foo'. Unfortunately some potential customers don't check the validity of such a key. As long as the key server finds a matching key, that key is just used to encrypt emails to your company. And of course in the eyes of a customer it is supposedly your fault that such a key exists in the first place and was not revoked properly. Having a business relationship start with a technical problem is not a good start. You have to reply asking for another copy of the email encrypted with a proper key. The customer has to delete the invalid key and import the new key, which can be time consuming for non-technically versed people. Finally the initial email is sent again with the 'friendly' reminder that some key server is 'still' serving an old key. So, in my opinion the problem is a social problem, but I try to find technical solutions anyway.
Not working solutions
- WKD - Web Key Directory. This is the new and fancy way to download keys directly from a web server associated with the email address. But customers and their standard email client won't use it unless it is supported and switched on by default.
- Put the real key on your company website. Customers don't care. They will just assume, that the key file is identical to the fake key served by the key server.
- Sign the fake key with a 'do not use' warning message attached, as suggested here. Of course anyone could do that and potentially invalidate all keys using this method.
- Switch to S/MIME. This solution won't solve the problem with PGP key servers.
- Communicate unencrypted. This may actually be a working solution for "the real problem", that starting a business relationship with technical difficulties appears to be suboptimal. You could also use the telephone or a postcard or a bicycle courier instead of email.
Working technical solutions (practical and impractical)
- Set up an auto-responder for encrypted emails without known encryption keys. Let the customer deal with the fast response that they chose the wrong key and point them to the real key or alternative methods of contacting the office.
- Extend all key servers to validate email addresses. This is what the PGP Global Directory has been doing.
- Let key servers reject keys without reasonable expiration date, e.g. 2 or 4 years in the future. This will not solve a targeted attack, but at least gets rid of unmaintained old keys without expiration date.
- Require keys to be uploaded again after a while. Same as above.
- Extend client software to prefer keys in order, first manually imported keys, then keys downloaded via WKD, then keys with expiration date, then other keys.
- Disable the use of legacy key servers by default in your client configuration.
Conclusion In my opinion the legacy PGP key server infrastructure does more harm than good by not providing email verification or any kind of removal option. The optimal scenario would be for a first time contact to retrieve the PGP key in person from a trusted source. The next best thing is implemented with Web-Key-Directory (WKD). Why anyone is still 'trusting' (to some degree) arbitrary keys from public key servers is a conundrum to me. But people doing that are exactly the customers in need for professional IT consulting, so it is counterproductive to put the blame on them.
