OpenPGP certificate flooding

A problem with the way that OpenPGP public-key certificates are handled by key servers and applications is wreaking some havoc, but not just for those who own the certificates (and keys)—anyone who has those keys on their keyring and does regular updates will be affected. It is effectively a denial of service attack, but one that propagates differently than most others. The mechanism of this "certificate flooding" is one that is normally used to add attestations to the key owner's identity (also known as "signing the key"), but because of the way most key servers work, it can be used to fill a certificate with "spam"—with far-reaching effects.

The problems have been known for many years, but they were graphically illustrated by attacks on the keys of two well-known members of the OpenPGP community, Daniel Kahn Gillmor ("dkg") and Robert J. Hansen ("rjh"), in late June. Gillmor first reported the attack on his blog. It turned out that someone had added multiple bogus certifications (or attestations) to his public key in the SKS key server pool; an additional 55,000 certifications were added, bloating his key to 17MB in size. Hansen's key got spammed even worse, with nearly 150,000 certifications—the maximum number that the OpenPGP protocol will support.

The idea behind these certifications is to support the "web of trust". If user Alice believes that a particular key for user Bob is valid (because, for example, they sat down over beers and verified that), Alice can so attest by adding a certification to Bob's key. Now if other users who trust Alice come across Bob's key, they can be reasonably sure that the key is Bob's because Alice (cryptographically) said so. That is the essence of the web of trust, though in practice, it is often not really used to do that kind of verification outside of highly technical communities. In addition, anyone can add a certification, whether they know the identity of the key holder or not.

The problem with the keys for Gillmor and Hansen that are stored in the SKS key-server network is that GNU Privacy Guard (GnuPG or GPG), the most widely used OpenPGP implementation, cannot even import the certificates into its newer keybox (.kbx) format due to the number of certifications they have. But using the older format (.gpg) leads to performance problems for any operation that uses the key. That leads to failures with the Enigmail Thunderbird add-on, for Git to take minutes to PGP sign a tag, for authentication to Monkeysphere to use an enormous amount of CPU, and probably other things as well, Gillmor said.

All of that is a pain for him, but it is worse than that. Anyone who has his key on their keyring will run into problems if they practice good "key hygiene" by periodically updating the keys on their keyring from the SKS servers. That will pick up key revocations, new subkeys, and the like, so their keyring will be up to date. But if they have Gillmor or Hansen on their keyrings and use the older format, that will lead to strange and hard to diagnose problems. If they use the newer format, they won't get updates for those keys, which may lead to other problems.

As Hansen details in his post on the subject, the problem can be traced to a decision made in the early 1990s about how key servers should function. There was concern that repressive governments would try to "coerce" key-server operators into substituting keys for ones controlled by the government. In order to combat that, key servers would not delete any information, so certificates and any information about them (e.g. certifications) would live forever. Multiple key servers were run in widely disparate locations and information would be synchronized between them regularly. If a key server did remove or modify a certificate, that would be recognized and the previous state would be restored.

That well-intentioned choice was fine for the time, but that time has passed. Unfortunately, according to Hansen, the SKS software is effectively unmaintained, in part because it was written in an idiosyncratic dialect of OCaml, but also because it was created as a proof of concept for a Ph.D. thesis:

He noted that the idea of the immutability of certificate information is wired deeply into the guts of SKS. Changing that would be a much bigger job than simply fixing a bug or adding a small feature. He recommended that high-risk users not use the SKS key server network any longer. Both he and Gillmor pointed out that the new, experimental keys.openpgp.org key server is resistant to the certificate flooding attack. The keys.openpgp.org FAQ explains:

The keys.openpgp.org server is also set up to separate the identity and non-identity information of certificates. It will not distribute identity information (i.e. "user IDs" that include a name and email address) unless the owner verifies the email address. Meanwhile, the non-identity information (the key material and metadata) will be stored and distributed freely, though without the certifications. GnuPG and other OpenPGP software can refresh the key material regularly from the server for keys they already have on their keyrings, even if the owner has not consented to the distribution of the key's user ID information.

The News entry for keys.openpgp.org mentions some of the reasons behind starting a new key server. It noted that the SKS key server suffered from a number of problems with abuse, performance, and privacy (including GDPR compliance). Beyond that, SKS is not really being developed any longer as Hansen also pointed out. So keys.openpgp.org is based on a completely new key server, Hagrid, written in Rust using the Sequoia OpenPGP library. The plan is to eventually add more servers to create a pool, but it will not be an open federation model like SKS due to privacy and reliability concerns.

Gillmor's first post has some pointers on other ways to handle certificate flooding, including a link to an internet draft he created back in April for "Abuse-Resistant OpenPGP Keystores". His followup blog post reiterates many of those options as part of an effort to look at the impact of certificate flooding on the community. Hansen was rather more blunt in his post and in a followup that described some of the fallout he sees from the attack. He is particularly angry that advice he gave to Venezuelan activists and others to check his signature on documents may now lead them to effectively break their GnuPG installation.

Both Gillmor and Hansen are obviously distressed, personally, over the fact that their keys are affected by all of this. OpenPGP is already hard enough to use that adding unexpected hurdles impacts other people in ugly ways. As Gillmor put it:

Other flooded keys have been found; in an LWN comment, Gillmor said that Tor project keys have been spammed. More keys undoubtedly will be flooded and the nature of the SKS key servers makes them a permanent part of the key store. Illegal content could perhaps be attached as certifications; those would also be "impossible" to remove. It is a little hard to see the SKS network surviving this incident in its current form—that may be for the best, in truth.

Daniel Lange has some suggestions on how to easily clean up these spammed keys, though it takes a huge amount of CPU time (he reports 1h45m for Hansen's key). That is rather distressing in its own right; as Filippo Valsorda put it:

Clearly GnuPG needs a fix for that; Gillmor filed a bug to that effect. He also filed bugs in other components that failed, which he links from his post.

But apparently the problems with the SKS key server have been known for a long time. It is a bit reminiscent of the state of OpenSSL development pre-Heartbleed; SKS was largely unmaintained, chugging along in the background but not really having much attention paid to it. Those "in the know" were aware of its flaws, but did not have the resources to fix them. As with Heartbleed, it makes one wonder what other projects are out there, seemingly humming along, when, in reality, that hum may be the quiet ticking of a time bomb.