SKS poisoning, keys.openpgp.org / Hagrid and other non-solutions

The recent key poisoning attack on SKS keyservers shook the world of OpenPGP. While this isn’t a new problem, it has not been exploited on this scale before. The attackers have proved how easy it is to poison commonly used keys on the keyservers and effectively render GnuPG unusably slow. A renewed discussion on improving keyservers has started as a result. It also forced Gentoo to employ countermeasures. You can read more on them in the ‘Impact of SKS keyserver poisoning on Gentoo’ news item.

Coincidentally, the attack happened shortly after the launch of keys.openpgp.org, that advertises itself as both poisoning-resistant and GDPR-friendly keyserver. Naturally, many users see it as the ultimate solution to the issues with SKS. I’m afraid I have to disagree — in my opinion, this keyserver does not solve any problems, it merely cripples OpenPGP in order to avoid being affected by them, and harms its security in the process.

In this article, I’d like to shortly explain what the problem is, and which of the different solutions proposed so far to it (e.g. on gnupg-users mailing list) make sense, and which make things even worse. Naturally, I will also cover the new Hagrid keyserver as one of the glorified non-solutions.

The attack — key poisoning

OpenPGP uses a distributed design — once the primary key is created, additional packets can be freely appended to it and recombined on different systems. Those packets include subkeys, user identifiers and signatures. Signatures are used to confirm the authenticity of appended packets. The packets are only meaningful if the client can verify the authenticity of their respective signatures.

The attack is carried through third-party signatures that normally are used by different people to confirm the authenticity of the key — that is, to state that the signer has verified the identity of the key owner. It relies on three distinct properties of OpenPGP:

1. The key can contain unlimited number of signatures. After all, it is natural that very old keys will have a large number of signatures made by different people on them.
2. Anyone can append signatures to any OpenPGP key. This is partially keyserver policy, and partially the fact that SKS keyserver nodes are propagating keys one to another.
3. There is no way to distinguish legitimate signatures from garbage. To put it other way, it is trivial to make garbage signatures look like the real deal.

The attacker abuses those properties by creating a large number of garbage signatures and sending them to keyservers. When users fetch key updates from the keyserver, GnuPG normally appends all those signatures to the local copy. As a result, the key becomes unusually large and causes severe performance issues with GnuPG, preventing its normal usage. The user ends up having to manually remove the key in order to fix the installation.

The obvious non-solutions and potential solutions

Let’s start by analyzing the properties I’ve listed above. After all, removing at least one of the requirements should prevent the attack from being possible. But can we really do that?

Firstly, we could set a hard limit on number of signatures or key size. This should obviously prevent the attacker from breaking user systems via huge keys. However, it will make it entirely possible for the attacker to ‘brick’ the key by appending garbage up to the limit. Then it would no longer be possible to append any valid signatures to the key. Users would suffer less but the key owner will lose the ability to use the key meaningfully. It’s a no-go.

Secondly, we could limit key updates to the owner. However, the keyserver update protocol currently does not provide any standard way of verifying who the uploader is, so it would effectively require incompatible changes at least to the upload protocol. Furthermore, in order to prevent malicious keyservers from propagating fake signatures we’d also need to carry the verification along when propagating key updates. This effectively means an extension of the key format, and it has been proposed e.g. in ‘Abuse-Resistant OpenPGP Keystores’ draft. This is probably a wortwhile option but it will take time before it’s implemented.

Thirdly, we could try to validate signatures. However, any validation can be easily worked around. If we started requiring signing keys to be present on the keyserver, the attackers can simply mass-upload keys used to create garbage signatures. If we went even further and e.g. started requiring verified e-mail addresses for the signing keys, the attackers can simply mass-create e-mail addresses and verify them. It might work as a temporary solution but it will probably cause more harm than good.

There were other non-solutions suggested — most notably, blacklisting poisoned keys. However, this is even worse. It means that every victim of poisoning attack would be excluded from using the keyserver, and in my opinion it will only provoke the attackers to poison even more keys. It may sound like a good interim solution preventing users from being hit but it is rather short-sighted.

keys.openpgp.org / Hagrid — a big non-solution

A common suggestion for OpenPGP users — one that even Gentoo news item mentions for lack of alternative — is to switch to keys.openpgp.org keyserver, or switch keyservers to their Hagrid software. It is not vulnerable to key poisoning attack because it strips away all third-party signatures. However, this and other limitations make it a rather poor replacement, and in my opinion can be harmful to security of OpenPGP.

Firstly, stripping all third-party signatures is not a solution. It simply avoids the problem by killing a very important portion of OpenPGP protocol — the Web of Trust. Without it, the keys obtained from the server can not be authenticated otherwise than by direct interaction between the individuals. For example, Gentoo Authority Keys can’t work there. Most of the time, you won’t be able to tell whether the key on keyserver is legitimate or forged.

The e-mail verification makes it even worse, though not intentionally. While I agree that many users do not understand or use WoT, Hagrid is implicitly going to cause users to start relying on e-mail verification as proof of key authenticity. In other words, people are going to assume that if a key on keys.openpgp.org has verified e-mail address, it has to be legitimate. This makes it trivial for an attacker that manages to gain unauthorized access to the e-mail address or the keyserver to publish a forged key and convince others to use it.

Secondly, Hagrid does not support UID revocations. This is an entirely absurd case where GDPR fear won over security. If your e-mail address becomes compromised, you will not be able to revoke it. Sure, the keyserver admins may eventually stop propagating it along with your key, but all users who fetched the key before will continue seeing it as a valid UID. Of course, if users send encrypted mail the attacker won’t be able to read it. However, the users can be trivially persuaded to switch to a new, forged key.

Thirdly, Hagrid rejects all UIDs except for verified e-mail-based UIDs. This is something we could live with if key owners actively pursue having their identities verified. However, this also means you can’t publish a photo identity or use keybase.io. The ‘explicit consent’ argument used by upstream is rather silly — apparently every UID requires separate consent, while at the same time you can trivially share somebody else’s PII as the real name of a valid e-mail address.

Apparently, upstream is willing to resolve the first two of those issues once satisfactory solutions are established. However, this doesn’t mean that it’s fine to ignore those problems. Until they are resolved, and necessary OpenPGP client updates are sufficiently widely deployed, I don’t believe Hagrid or its instance at keys.openpgp.org are good replacements for SKS and other keyservers.

So what are the solutions?

Sadly, I am not aware of any good global solution at the moment. The best workaround for GnuPG users so far is the new self-sigs-only option that prevents it from importing third-party signatures. Of course, it shares the first limitation of Hagrid keyserver. The future versions of GnuPG will supposedly fallback to this option upon meeting excessively large keys.

For domain-limited use cases such as Gentoo’s, running a local keyserver with restricted upload access is an option. However, it requires users to explicitly specify our keyserver, and effectively end up having to specify multiple different keyservers for each domain. Furthermore, WKD can be used to distribute keys. Sadly, at the moment GnuPG uses it only to locate new keys and does not support refreshing keys via WKD (gemato employs a cheap hack to make it happen). In both cases, the attack is prevented via isolating the infrastructure and preventing public upload access.

The long-term solution probably lies in the ‘First-party-attested Third-party Certifications‘ section of the ‘Abuse-Resistant OpenPGP Keystores’ draft. In this proposal, every third-party signature must be explicitly attested by the key owner. Therefore, only the key owner can append additional signatures to the key, and keyservers can reject any signatures that were not attested. However, this is not currently supported by GnuPG, and once it is, deploying it will most likely take significant time.