OpenPGP installations can break and fail to verify the authenticity of downloaded packages as the key server network has been flooded with thousands of spam signatures attesting ownership of a certificate.
Trust in OpenPGP certificates is maintained by distributing the public keys over a network of key servers that allow their discovery. To certify the ownership of the keys, users can attach a statement (certificate signature) to vouch that a key really belongs to the user listed in the database. The key servers' role is to store the information and synchronize it, without ever deleting any data, not even when certificates are revoked.
This system was created back in the 90s to prevent adversaries from replacing public certificates. As Hansen points out “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.” The system is vulnerable to certificate spoofing and an attacker can add as many as 150,000 signatures for a certificate in the key server network, the maximum it can handle. OpenPGP does not have a limit to this and GnuPG cannot process this many signatures, Hansen explains.
Both Hansen and Gillmor had their certificates spammed so much that their public keys became unusable with GnuPG as it has to validate all the signatures. “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,” Hansen said.
According to Hansen, the effects are quite serious:
Hansen notes that any certificate can be poisoned this way and discovering the attack is likely to happen only when the OpenPGP installation breaks. The risks are significant, considering that GnuPG is a complete and free implementation of the OpenPGP standard and enjoys wide adoption among Linux-based operating systems. Its package is present in the repositories of the major distributions to ensure secure package management. Without being able to check if a package is authentic, upgrades are no longer possible, leaving systems vulnerable to security or performance problems that could be leveraged by an attacker.
Certificate flooding is not a new thing and attacks have been recorded before.
Matthew Green, a cryptographer and associate professor at Johns Hopkins University, said that the attack points out some of the weaknesses in the entire OpenPGP infrastructure. “PGP is old and kind of falling apart. There's not enough people maintaining it and it's full of legacy code. There are some people doing the lord's work in keeping it up, but it's not enough,” Green said.
This is admitted by Hansen as well. Hansen notes that key servers use an algorithm that can do fast reconciliations and rely on software called SKS, short for “Synchronizing Key Server”, which were developed by Yaron Minsky “in an unusual programming language called OCaml, and in a fairly idiosyncratic dialect of it at that.” According to Hansen, the problem is that “the software is Byzantine” and there is no one in the key server community that has sufficient "expertise in obscure programming languages and strange programming customs." As a result, the software remains “unmaintained” and a serious overhaul on the codebase is not possible at this time.
Daniel Gimor wrote in a post that “SKS is known to be vulnerable to this kind of Certificate Flooding, and is difficult to address due to the synchronization mechanism of the SKS pool. (SKS's synchronization assumes that all key servers have the same set of filters).” This vulnerability is not due to a bug that inhibits the key server network from functioning correctly. Bugs, generally speaking, are fairly easy to fix once you know where the problem is. The vulnerability is hard-coded into the actual key server design goals. “Changing design goals often requires an overhaul of such magnitude it may be better to just start over with a fresh sheet of paper,” says Hansen.
Both Hansen and Gilmor admit that a timely fix or mitigation is nowhere in sight, neither from the key server network community nor the OpenPGP Working Group. In fact, Hansen urges that “high-risk users should stop using the key server network immediately.”
A short-term mitigation is to disable automatic refreshing of the certificates. If this is needed, though, an abuse-resistant key server is the solution such as the keys.openpgp.org, “which is a new experimental key server that is not part of the key server network and has some features which make it resistant to this sort of attack,” as Hansen explains.
Gillmor said the attacks illustrate both the fragility and necessity of projects such as OpenPGP. “One of the points I've been driving at for years is that the goals of much of the work I care about (confidentiality; privacy; information security and data sovereignty; healthy communications systems) are not individual goods. They are interdependent, communally-constructed and communally-defended social properties,” he said.