SKS Keyserver Network Under Attack

keyservers.md

SKS Keyserver Network Under Attack

This work is released under a Creative Commons Attribution-NoDerivatives 4.0 International License.

Terminological Note

"OpenPGP" refers to the OpenPGP protocol, in much the same way that HTML refers to the protocol that specifies how to write a web page. "GnuPG", "SequoiaPGP", "OpenPGP.js", and others are implementations of the OpenPGP protocol in the same way that Mozilla Firefox, Google Chromium, and Microsoft Edge refer to software packages that process HTML data.

Who am I?

Robert J. Hansen <rjh@sixdemonbag.org>. I maintain the GnuPG FAQ and unofficially hold the position of crisis communicator. This is not an official statement of the GnuPG project, but does come from someone with commit access to the GnuPG git repo.

Executive Summary

In the last week of June 2019 unknown actors deployed a certificate spamming attack against two high-profile contributors in the OpenPGP community (Robert J. Hansen and Daniel Kahn Gillmor, better known in the community as "rjh" and "dkg"). This attack exploited a defect in the OpenPGP protocol itself in order to "poison" rjh and dkg's OpenPGP certificates. Anyone who attempts to import a poisoned certificate into a vulnerable OpenPGP installation will very likely break their installation in hard-to-debug ways. Poisoned certificates are already on the SKS keyserver network. There is no reason to believe the attacker will stop at just poisoning two certificates. Further, given the ease of the attack and the highly publicized success of the attack, it is prudent to believe other certificates will soon be poisoned.

This attack cannot be mitigated by the SKS keyserver network in any reasonable time period. It is unlikely to be mitigated by the OpenPGP Working Group in any reasonable time period. Future releases of OpenPGP software will likely have some sort of mitigation, but there is no time frame. The best mitigation that can be applied at present is simple: stop retrieving data from the SKS keyserver network.

How Keyservers Work

When Phil Zimmermann first developed PGP ("Pretty Good Privacy") in the early 1990s there was a clear chicken and egg problem. Public key cryptography could revolutionize communications but required individuals possess each other's public keys. Over time terminology has shifted: now public key cryptography is mostly called "asymmetric cryptography" and public keys are more often called "public certificates", but the chicken-and-egg problem remains. To communicate privately, each party must have a small piece of public data with which to bootstrap a private communication channel.

Special software was written to facilitate the discovery and distribution of public certificates. Called "keyserver software", it can be thought of as analogous to a telephone directory. Users can search the keyserver by a variety of different criteria to discover public certificates which claim to belong to the desired user. The keyserver network does not attest to the accuracy of the information, however: that's left for each user to ascertain according to their own criteria.

Once a user has verified a certificate really and truly belongs to the person in question, they can affix an affidavit to the certificate attesting that they have reason to believe the certificate really belongs to the user in question.

For instance: John Hawley (john@example.org) and I (rjh@example.org) are good friends in real life. We have sat down face-to-face and confirmed certificates. I know with complete certainty a specific public certificate belongs to him; he knows with complete certainty a different one belongs to me. John also knows H. Peter Anvin (hpa@example.org) and has done the same with him. If I need to communicate privately with Peter, I can look him up in the keyserver. Whichever certificate bears an attestation by John, I can trust really belongs to Peter.

Keyserver Design Goals

In the early 1990s we were concerned repressive regimes would attempt to force keyserver operators to replace certificates with different ones of the government's choosing. (I speak from firsthand experience. I've been involved in the PGP community since 1992. I was there for these discussions.) We made a quick decision that keyservers would never, ever, ever, delete information. Keyservers could add information to existing certificates but could never, ever, ever, delete either a certificate or information about a certificate.

To meet this goal, we started running an international network of keyservers. Keyservers around the world would regularly communicate with each other to compare directories. If a government forced a keyserver operator to delete or modify a certificate, that would be discovered in the comparison step. The maimed keyserver would update itself with the content in the good keyserver's directory. This was a simple and effective solution to the problem of government censorship.

In the early 1990s this design seemed sound. It is not sound in 2019. We've known it has problems for well over a decade.

Why Hasn't It Been Fixed?

There are powerful technical and social factors inhibiting further keyserver development.

• The software is Byzantine. The standard keyserver software is called SKS, for "Synchronizing Key Server". A bright fellow named Yaron Minsky devised a brilliant algorithm that could do reconciliations very quickly. It became the keystone of his Ph.D thesis, and he wrote SKS originally as a proof of concept of his idea. It's written in an unusual programming language called OCaml, and in a fairly idiosyncratic dialect of it at that. This is of course no problem for a proof of concept meant to support a Ph.D thesis, but for software that's deployed in the field it makes maintenance quite difficult. Not only do we need to be bright enough to understand an algorithm that's literally someone's Ph.D thesis, but we need expertise in obscure programming languages and strange programming customs.

• The software is unmaintained. Due to the above, there is literally no one in the keyserver community who feels qualified to do a serious overhaul on the codebase.

• Changing a design goal is not the same as fixing a bug. The design goal of the keyserver network is "baked into" essentially every part of the infrastructure. This isn't a case where there's a bug that's inhibiting the keyserver network from functioning correctly. Bugs are generally speaking fairly easy to fix once you know where the problem is. Changing design goals often requires an overhaul of such magnitude it may be better to just start over with a fresh sheet of paper.

• There is no centralized authority in the keyserver network. The lack of centralized authority was a feature, not a bug. If there is no keyserver that controls the others, there is no single point of failure for a government to go after. On the other hand it also means that even after the software is overhauled and/or rewritten, each keyserver operator has to commit to making the upgrade and stomping out the difficulties that inevitably arise when new software is fielded. The confederated nature of the keyserver network makes changing the design goals even harder than it would normally be—and rest assured, it would normally be very hard!

The Vulnerabilities

The keyserver network is susceptible to a variety of attacks as a consequence of its write-only design. The keyserver network can be thought of as an extremely large, extremely reliable, extremely censorship-resistant distributed filesystem which anyone can write to.

Imagine if Dropbox allowed any Tom, Dick, or Harry to not only put information in your public Dropbox folder, but made it impossible for you to delete it. How would everyone from spammers to child pornographers abuse this?

Many of the same attacks are possible on the keyserver network. We have known about these vulnerabilities for well over a decade. Fixing the keyserver network is, however, problematic for the reasons listed above.

In order to limit the scope of this document a detailed breakdown of only one such vulnerability will be presented (see below).

The Certificate Spamming Attack

Consider public certificates. In order to make them easier to use, they have a list of attestations: statements from other people, represented by their own public certificates, that this certificate really belongs to the individual in question. In my example from before, John Hawley attested to H. Peter Anvin's certificate. When I looked for H. Peter Anvin's certificate I checked all the certificates which claimed to belong to him and selected the one John attested as being really his.

These attestations — what we call certificate signatures — can be made by anyone for any purpose. And once made, they never go away. Ever. Even when a certificate signature gets revoked the original remains on the certificate: all that happens is a second signature is affixed saying "don't trust the previous one I made".

The OpenPGP specification puts no limitation on how many signatures can be attached to a certificate. The keyserver network handles certificates with up to about 150,000 signatures.

GnuPG, on the other hand … doesn't. Any time GnuPG has to deal with such a spammed certificate, GnuPG grinds to a halt. It doesn't stop, per se, but it gets wedged for so long it is for all intents and purposes completely unusable.

My public certificate as found on the keyserver network now has just short of 150,000 signatures on it.

Further, pay attention to that phrase any time GnuPG has to deal with such a spammed certificate. If John were to ask GnuPG to verify my signature on H. Peter Anvin's certificate, GnuPG would attempt to comply and in the course of business would have to deal with my now-spammed certificate.

The Consequences

We've known for a decade this attack is possible. It's now here and it's devastating. There are a few major takeaways and all of them are bad.

• If you fetch a poisoned certificate from the keyserver network, you will break your GnuPG installation.
• Poisoned certificates cannot be deleted from the keyserver network.
• The number of deliberately poisoned certificates, currently at only a few, will only rise over time.
• We do not know whether the attackers are intent on poisoning other certificates.
• We do not even know the scope of the damage.

That last one requires some explanation. Any certificate may be poisoned at any time, and is unlikely to be discovered until it breaks an OpenPGP installation.

The number one use of OpenPGP today is to verify downloaded packages for Linux-based operating systems, usually using a software tool called GnuPG. If someone were to poison a vendor's public certificate and upload it to the keyserver network, the next time a system administrator refreshed their keyring from the keyserver network the vendor's now-poisoned certificate would be downloaded. At that point upgrades become impossible because the authenticity of downloaded packages cannot be verified. Even downloading the vendor's certificate and re-importing it would be of no use, because GnuPG would choke trying to import the new certificate. It is not hard to imagine how motivated adversaries could employ this against a Linux-based computer network.

Mitigations

At present I (speaking only for myself) do not believe the global keyserver network is salvageable. High-risk users should stop using the keyserver network immediately.

Users who are confident editing their GnuPG configuration files should follow the following process:

1. Open gpg.conf in a text editor. Ensure there is no line starting with keyserver. If there is, remove it.
2. Open dirmngr.conf in a text editor. Add the line keyserver hkps://keys.openpgp.org to the end of it.

keys.openpgp.org is a new experimental keyserver which is not part of the keyserver network and has some features which make it resistant to this sort of attack. It is not a drop-in replacement: it has some limitations (for instance, its search functionality is sharply constrained). However, once you make this change you will be able to run gpg --refresh-keys with confidence.

Repairs

If you know which certificate is likely poisoned, try deleting it: this normally goes pretty quickly. If your OpenPGP installation becomes usable again, congratulations. Acquire a new unpoisoned copy of the certificate and import that.

If you don't know which certificate is poisoned, your best bet is to get a list of all your certificate IDs, delete your keyrings completely, and rebuild from scratch using known-good copies of the public certificates.

A Personal Postscript

dkg wrote a blog post about this. He sums up my feelings pretty well, so I'm going to quote him liberally with only a trivial correction.

I've spent a significant amount of time over the years trying to push the ecosystem into a more responsible posture with respect to OpenPGP certificates, and have clearly not been as successful at it or as fast as I wanted to be. Complex ecosystems can take time to move.

To have my own certificate directly spammed in this way felt surprisingly personal, as though someone was trying to attack or punish me, specifically. I can't know whether that's actually the case, of course, nor do I really want to. And the fact that Robert J. Hansen's certificate was also spammed makes me feel a little less like a singular or unique target, but I also don't feel particularly proud of feeling relieved that someone else is also being "punished" in addition to me.

But this report wouldn't be complete if I didn't mention that I've felt disheartened and demotivated by this situation. I'm a stubborn person, and I'm trying to make the best of the situation by being constructive about at least documenting the places that are most severely broken by this. But I've also found myself tempted to walk away from this ecosystem entirely because of this incident. I don't want to be too dramatic about this, but whoever did this basically experimented on me (and Rob) directly, and it's a pretty shitty thing to do.

If you're reading this, and you set this off, and you selected me specifically because of my role in the OpenPGP ecosystem, or because I wrote the abuse-resistant-keystore draft, or because I'm part of the Autocrypt project, then you should know that I care about making this stuff work for people. If you'd reached out to me to describe what you were planning to do, we could have done all of the above bug reporting and triage using demonstration certificates, and worked on it together. I would have happily helped. I still might! But because of the way this was done, I'm not feeling particularly happy right now. I hope that someone is, somewhere.

To which I'd like to add: I have never in my adult life wished violence on any human being. I have witnessed too much of it and its barbaric effects, stood by the graves of too many people cut down too young. I do not hate you and I do not wish any harm to befall you.

But if you get hit by a bus while crossing the street, I'll tell the driver everyone deserves a mulligan once in a while.

You fool. You absolute, unmitigated, unadulterated, complete and utter, fool.

Peace to everyone — including you, you son of a bitch.

— Rob

Poisoned certificates cannot be deleted from the keyserver network.

can't the key become revoked ?

sure. But then they won't be deleted. That'd be silly as then nobody could learn about their revocation. The certifications could probably be stripped, though.

The missing feature of deletion is the reason for hosting my own keyserver. I created my keypair with ed25519 for primary and nistp521 for subkeys. But, after figuring out that the nistp521 authentication subkey cannot be used for ssh I decided to use nistp384 for that subkey. Using something like hkps://keys.openpgp.org would make the obsolete nistp521 auth subkey linger around although that subkey is not needed for communication with others. This is not something that I wish for, because I want to keep my pubkey slim as long as it makes sense.

Reposting here too.

If you come across this thread and you're interested in what could be done to solve the issue, I'd recommend you to look into Attested Certifications (also called 1PA3PC)

Maybe this has already been thought of or discussed, or is a silly solution.

But, what about only allowing mutual attestations in the keyserver? Most attestations are, after all, both ways, as they were done in-person between persons who presumable BOTH have certificates for the other to attest. Even at large keyparties, great logistical care was taken to facilitate full mesh NxN attestations between all involved.

@vontrapp why do you warm up a very old discussion? Most people have switched to age an no longer use such key servers with GnuPG and with the brand new minicrypt things are changing too.

@vontrapp why do you warm up a very old discussion? Most people have switched to age an no longer use such key servers with GnuPG and with the brand new minicrypt things are changing too.

Unfortunatelly, the most software vendors still use keys with are avaliable in gpg, gnupg and apt keyrings :-(

shame that the vendors of GnuPG did not show much will to fix it, with could be simple to do, like automatically revoke of compromised keys and cut-off the compromised servers from the keyring, informing also their administrators about it, until they don't fix the issue on their side

shame that the vendors of GnuPG did not show much will to fix it, with could be simple to do, like automatically revoke of compromised keys and cut-off the compromised servers from the keyring, informing also their administrators about it, until they don't fix the issue on their side

… the hell are you talking about?

SKS, the keyserver technology in question, is a completely separate project from GnuPG. These problems are ones that need to be solved at either the keyserver level, or the IETF OpenPGP working group level.

You don't even understand where the problem lies or who's best positioned to fix it, and yet you're sure fixing it would be simple to do.

… the hell are you talking about?

SKS, the keyserver technology in question, is a completely separate project from GnuPG. These problems are ones that need to be solved at either the keyserver level, or the IETF OpenPGP working group level.

You don't even understand where the problem lies or who's best positioned to fix it, and yet you're sure fixing it would be simple to do.

I know that is separate, but for now GnuPG seem to still use it. That why I had proposed that OpenPG should temporary disable connections to the SKS network to limit spreading and use of the compromised data, until somebody find a way to fix the problem ;-)

There is no need to get upset, aspecially if some one attempt's to find a temporary solutions, since I don't see any big progress in finding a permanent fix for it.

I know that is separate, but for now GnuPG seem to still use it.

Werner also loves emacs, but you don't expect him to address emacs bugs. SKS is a completely different project. Ask them to fix their bug. Don't expect people who have no involvement besides "I use SKS" to fix things.

There is no need to get upset

You don't understand the problem, and I'm saying this clearly so people don't go about thinking you have a solution.

… the hell are you talking [...] Don't expect people who have no involvement [...] You don't understand [...] I'm saying this clearly so people don't go about thinking you have a solution.

@rjhansen your tone is somewhat abrasive and dismissive of @mdziczkowski, not the best approach to foster constructive discussion.

not the best approach to foster constructive discussion.

I used to work at a really high-speed digital forensics lab. We kept two reminders on our whiteboard, and whenever anyone erased them we immediately replaced them:

1. MOST OF OUR IDEAS ARE BAD.
2. FAIL FASTER.

95% of all 'solutions' are awful. If you're serious about finding the 5% that aren't, the best way is to increase the speed with which you get rid of bad ideas.

You are not your ideas. Good people can believe things that are crazypants wrong. I'm sure @mdziczkowski is a nice person who's kind and motivated by a benevolent desire to improve the world. But I'm also sure they don't understand the problem and don't have a solution. If saying that clearly is abrasive or dismissive, well, get over it. Most ideas are bad, and the road to progress is to fail faster.

I used to work at a really high-speed digital forensics lab [...] I'm sure @mdziczkowski is a nice person [...] I'm also sure they don't understand the problem and don't have a solution [...] abrasive or dismissive, well, get over it. Most ideas are bad, and the road to progress is to fail faster.

@rjhansen dismissing the ideas of your interlocutors without consideration is not a recipe for progress, it's a recipe for alienation.
In modern free software community, constructive discussions depend on mutual respect and open-mindedness.

Every time you forget that fundamental principle of human collaboration, the projects and the associations you represent lose potential users and contributors. Callous interactions in one project tend to become a psychological barrier against further participation in other projects, harming the whole community. For such reasons, the real road to progress is... kindness.

I used to work at a really high-speed digital forensics lab [...] I'm sure @mdziczkowski is a nice person [...] I'm also sure they don't understand the problem and don't have a solution [...] abrasive or dismissive, well, get over it. Most ideas are bad, and the road to progress is to fail faster.

@rjhansen dismissing the ideas of your interlocutors without consideration is not a recipe for progress, it's a recipe for alienation. In modern free software community, constructive discussions depend on mutual respect and open-mindedness.

Are we voting on the Code of Conduct for a 6 year old gist comment section now? The necromancy discussing obsolete technical points was bad enough but we absolutely don't need to rehash being nice to people who don't know what they're talking about vs telling them bluntly in this gist.

Seeing a flood of nonsense in my inbox is making me lean towards @rjhansen's styke, but the only real answer is to unlike and unsubscribe.

@LorenzoAncora I am sorry to interject, but I see the "offended by facts" attitude equally alieanating. In the past 15-20 years people started to be offended by anything not sugarcoated or catered to the other person's views and "moral" understanding. Presenting facts and opinion is automatically perceived as hostile and abrasive.
I really dislike how people tend to put words in other people's mouth or interpret facts as something they "feel" is inappropriate.

I have really thought hard whether I should even state my opinion, because probably a myriad of people will be offended by my words, but I still have the same right as you to state my opinion.

If you are trying to establish a code of conduct, maybe read the "The Four Agreements" first. You should especially take the second one to heart.

dismissing the ideas of your interlocutors without consideration is not a recipe for progress, it's a recipe for alienation.

I considered their idea, found it was predicated in a deep misunderstanding of the problem, dismissed the idea, and moved on. This, you call 'abrasive', and tell me that my dismissal after consideration is somehow 'unkind'.

That's on you, man. I'm moving on.

I considered their idea, found it was predicated in a deep misunderstanding [...] dismissed the idea [...] moving on.

@rjhansen no Robert, it isn't a question of right or wrong, but of how you interact with the others: this kind of conduct is harmful to the whole free software community. You can "move on" as often as you want, but the userbase will remember each controversal interaction. When you close the window, people keep talking around exchanging opinions, they don't cease to exist! 🙂

When giving callous answers, on looks unreliable and unprofessional; as a consequence, the userbase can shrink, along with the number of potential collaborators available to other free software maintainers; some users might even transition to non-free software.

If a person on the other side of the world takes the time to propose something, be happy, even if you think they are wrong. Their interest is a reward in itself.

Nobody is forcing you to answer or debate about anything: I strongly suggest you partake the discussion if you feel overwhelmed by critique or it started causing you discomfort. Just don't forget my small advice the next time a user/volunteer/collaborator proposes something or is curious about something.

So, try to be kind, man. Kindness costs nothing and bears the sweetest fruits, which are serenity and collaboration. Be kind and take care of yourself man. 👋

When giving callous answers, on looks unreliable and unprofessional

The answer is "you don't understand the problem and you don't have a solution." That's an accurate answer, reached after giving the proposal a fair hearing. You have a moral problem with this (whether the accuracy or the fairness, I'm not sure) and are being insultingly condescending about it.

Okay. I'm done with you, too. Peace.

If you do not get the last word, you did not win the argument.