1. OpenPGP flooding attack mitigations
    1. Mitigation strategies
    2. Discussion on mitigations in GnuPG itself
    3. Recovering from a damaged keyring
    4. Known flooded keys
    5. How to check for flooded keys
    6. Credits

TL;DR: stop using keyservers, they're dangerous, at least with GnuPG. Start deploying WKD and consider replacing GnuPG in your workflows.

This blog post was originally posted to the tor-project mailing list. It has been edited to take new information into account. A few other people wrote about this problem since my first email, see also:

Since the Tor project uses OpenPGP and GnuPG extensively in its operations, I figured it was important to let the community know of an ongoing attack against the keyserver infrastructure and GnuPG. The longer story is available on dkg's blog, but a summary is that at least two prominent OpenPGP users have seen their public key flooded with thousands of signatures, to the point where their keys are now completely unusable.

Note that a different attack was fielded against the deb.torproject.org Debian archive signing key, back in February. The key was signed by a key with a large UID which made GPG's life harder. It's a different attack, but that can be mitigated in similar ways. The good key is still available on the archive site itself.

Mitigation strategies

I recommend you consider taking the following immediate actions, either:

  1. in the short term, disable automated key refreshes on your keyring (either Parcimonie or manual scripts calling gpg --refresh in some other way), or;

  2. switch to the new keys.openpgp.org keyserver, by setting the following in your gpg.conf:

    keyserver hkps://keys.openpgp.org/
    

The first action should only be used in the short term, to give yourself time to evaluate your options. It should mitigate the problem, but it will mean you will not update your keyring for precious revocation certificates users post when their key is compromised. It's therefore not an acceptable long-term solution in any way.

The second action mitigates the problem, but has several downsides as well:

  1. keys.openpgp.org does not store UIDs unless they are verified and asked for explicitly (workaround: keys can be shipped in-band with Autocrypt or found through other mechanisms like WKD, Web Key Directory)

  2. keys.openpgp.org does not store third-party UID certifications at all, which means it doesn't propagate the "web of trust" (workaround: same as above, and you should send signed keys by email anyways to verify ownership of the UID, using tools like caff, pius, gnome-keysign or monkeysign)

  3. GnuPG cannot read refresh keys from keys.openpgp.org (workaround: use the custom patch shipped in Debian testing and unstable, see Debian bug #930665 and bug #932684 for stable)

  4. keys.openpgp.org does not currently receive updates from the SKS pool (workaround: upload key updates to keys.openpgp.org directly as well as the SKS pool)

Note that keys.openpgp.org has been seeded with the global SKS keyserver datastore, so it contains all the keys you would expect to be present on the latter, except they are sanitized to avoid this problem. The UID are also "hidden" from public view until validated by the user.

I encourage users to:

  1. upload their keys to the keys.openpgp.org keyserver if they are not already present

  2. validate their email address on keys.openpgp.org

  3. either switch to keys.openpgp.org by default or carefully review their key update configuration to make sure it is not vulnerable to this attack

  4. make sure your own keys are not affected by this problem (see below)

Discussion on mitigations in GnuPG itself

GnuPG released a new version (2.2.17) that supposedly address those issues. Unfortunately, the workaround ("Ignore all key-signatures received from keyservers") has the same limitation as switching to keys.openpgp.org, in that it ignores UID signatures. The change has already been reverted in Arch Linux is it broke their authentication chain.

The underlying problem is that GPG has serious performance flaws in its implementation, with certain lookups taking O(N^2) where N is the number of signatures (or keys?). OpenPGP packets are basically a list of blobs, but GnuPG also represents those internally (and on disk) as a linked list as well, which has obvious performance limitations.

Patches have been submitted to fix this particular performance problem, but have yet to find their way in an official release, for some inexplicable reason. The original bug reported by dkg about his key has been marked as fixed, even though the fix is actually to ignore all signatures from the keyservers, which is hardly a fix at all...

I have high hopes that sequoia eventually replaces GnuPG as the canonical OpenPGP implementation. It has already grown by leaps and bounds and seems to have a much better approach to solving the various problems:

  1. it's a library, not only an executable
  2. it has a sane commandline interface
  3. it's written in a somewhat safer language (Rust)

The downsides?

  1. it's not packaged in Debian
  2. it's written in an unusual and fast moving language (Rust)
  3. it doesn't have support for smartcard readers and key cards like the Yubikey

I'm sometimes using sequoia through the Docker image I built but I am still using GnuPG on a day to day basis.

I did write some scripts to work around some problems in dirmngr as well. Finally, hOpenPGP has some interesting Haskell tools to process OpenPGP packets, along with pgpdump.

Recovering from a damaged keyring

If you have fetched an hostile key and GnuPG has become unusable, you can recover by deleting the key with:

gpg --delete-key C4BC2DDB38CCE96485EBE9C2F20691179038E5C6

Note that this may take anywhere from 20 minutes to an hour.

And then fetch dkg's key via WKD:

gpg --locate-keys dkg@fifthhorseman.net

or his website, https://dkg.fifthhorseman.net/dkg-openpgp.key.

If your key is the one that has been damaged, the above will obviously not work as you probably don't want to delete your own key. Daniel Lange's Cleaning a broken GNUpg (gpg) key article has an excellent tutorial on how to deal with that situation, fortunately.

Known flooded keys

At the time of writing, the keys known to be affected by such an attack are, according to Marcus Brinkmann:

I have linked to a canonical, non-flooded version of the key when I found one on the web. Keys on debian.org and torproject.org are now available through WKD. The Tor browser documentation has been updated to follow those instructions.

(Note that I added the full fingerprint for the keys I could find. Those with the long key ID are those that I could not find on the keyservers, for whatever reason. This takes a surprisingly long time: neither gpg --list-packets or pgpdump shows the key fingerprint, and I need a much more costly --show-key to get the actual key fingerprint. I also have a copy of the above keys, in flooded version, for testing purposes if people are interested in doing research and optimization for them. I won't link to them here to avoid confusion.)

How to check for flooded keys

To check if your key is affected without importing it into your keyring, you can use the following command:

FINGERPRINT=0x8DC901CE64146C048AD50FBB792152527B75921E # for example mine
curl --cacert /usr/share/gnupg/sks-keyservers.netCA.pem -sSL "http://hkps.pool.sks-keyservers.net/pks/lookup?op=get&search=$FINGERPRINT&options=mr&fingerprint=on&exact=on" \
    | pgpdump | grep -E -c '^(Old|New): Signature Packet'

This counts the number of signatures on your key. The key part (pgpdump | grep -E -c '^(Old|New): Signature Packet') can be used to check any keyring or blob, so it can also be used on your own keyring, in ~/.gnupg/pubring.gpg.

If you do not have pgpdump installed, the equivalent in GnuPG would be:

gpg --list-packets |  grep -c '^:signature packet:'

A reasonable number is less or around a thousand. dkg's key has now around 55 000 signatures on his key, which (naturally) causes some trouble in all OpenPGP implementations. Thankfully, both pgpdump and GnuPG are able to walk the packets fast enough to parse the raw form, it's when they are loaded in memory by GnuPG that things go south...

Credits

A million thanks to Daniel Kahn Gillmor for the incredible work he's done bringing sense in the GnuPG upstream but also in reviewing my many writings over the years, and of course particularly this one.

Created . Edited .