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.

3 Replies to “SKS poisoning, keys.openpgp.org / Hagrid and other non-solutions”

  1. “Abuse resistant keystores” is a collection of good ideas but as you say possibly a part of a solution much down the line. And looking at the glacial speed of development in the gpg-space that may be a decade or two.
    The item “First-party-attested third-party Certifications” from the above RFC is better solved by requiring mutual cross-signatures for re-publishing such signatures via keyservers. That works now without any change in the client side tooling. The necessary steps towards a reasonable restoration of the SKS keyserver network are listed at the bottom of https://daniel-lange.com/archives/159-Cleaning-a-broken-GNUpg-gpg-key.html .

    BTW, the “OpenPGP Web Key Directory” draft is another of those half-baked bolted-on non-solutions to the mess that is gpg. As you said already, the current implementation does not allow for key updates, the spec is mixing unrelated technologies into yet another mess and – of course – the gpg client implementation itself does not conform to the latest v8 of the spec either (https://dev.gnupg.org/T4590, https://dev.gnupg.org/T4603, etc).

    Both the current Gentoo and the Debian incarnations of WKD are not conforming to the spec. They just happen to work with gpg –locate-key.

    From https://tools.ietf.org/html/draft-koch-openpgp-webkey-service-08:
    The server MUST serve a Policy Flags file as specified below. That
    file is even required if the Web Key Directory Update Protocol is not
    supported.

    Neither Gentoo nor Debian serve that as of now.
    (FTR: It would have to be a zero-length file. But it MUST be there. May be in v9 of the spec we get useful flags in there like “no-submission”.)

    Thank you very much for your writeup. It is one of the useful ones in the current omg-gpg-keys-can-be-flooded discussion.

    1. The item “First-party-attested third-party Certifications” from the above RFC is better solved by requiring mutual cross-signatures for re-publishing such signatures via keyservers. That works now without any change in the client side tooling.

      I haven’t analyzed the RFC in detail but I think that idea also remains backwards-compatible with clients. However, the problem is that unless you update clients, they remain vulnerable to malicious keyservers, and given the nature of SKS rotation that’s a real problem.

      Do I understand correctly that your idea boils down to ‘if you sign my UID, I have to sign yours as well’? In that case, I agree it’s simpler for regular usage. However, I think we have valid cases for non-mutual signatures. For example, the Gentoo CA-like structure assumes CA signs all developers but developers aren’t strictly required to sign the CA key.

      BTW, the “OpenPGP Web Key Directory” draft is another of those half-baked bolted-on non-solutions to the mess that is gpg.

      I agree. I feel like it’s one of the cases where implementation was widely deployed before draft was reasonably complete, and now it’s too late to clean it up. One of the things I really hate about it is using z-Base32 which has no real benefit over, say, plain hexstrings (saving a few bytes in URL?) but at the same time is not provided by the majority of standard programming language libraries (Python, Ruby) and requires either completely custom implementation or cheap hackery (if you can replace the alphabet in the standard implementation).

      Both the current Gentoo and the Debian incarnations of WKD are not conforming to the spec. They just happen to work with gpg –locate-key.

      I built the Gentoo implementation on v6, if I recall correctly. I need to update it one day, at least as far as the obligatory elements go.

      Thank you very much for your writeup. It is one of the useful ones in the current omg-gpg-keys-can-be-flooded discussion.

      Thanks.

  2. I find much of the logic in this blog post flawed, and I could largely sum up the flaw by quoting, “Sadly, I am not aware of any good global solution at the moment. ”

    Some of the mitigation techniques were practically dismissed as useless because they can be circumvented. Verifying the packets added to keys are valid has nothing to do with the problem of an attacker being able to create disposable keys, emails, etc to use valid keys to sign with. That will increase the complexity of the attack. It does not stop the attack, but then neither do locks on the doors of our homes. For that matter, even if our homes had the best locks, strongest doors, and bars on our windows, thieves could cut a hole in the wall. Does that mean we shouldn’t bother using locks?

    The key servers being attacked after keys.openpgp.org was launched could be either a coincidence or because there is now more attention being paid to key servers. There was actually an open source program published to github that makes an attack on keys published to sks key servers simple for even the most novice users. I’m not going to provide the link here.

    Doing nothing is not an option. I don’t have the time to explain here why many of the features of GPG/PGP are not as important to key servers as the author believes, but the bottom line is trust should not come easy. Manual verification of keys though direct contact is the only sure way to know the key is valid, and if the data you are exchanging is important or private enough to require that level of trust, then you would be a fool to use a key server to shortcut the process.

Comments are closed.