Cryptography Dispatches: Hello World, and OpenPGP Is Broken

Hello World

This is the inaugural issue of Cryptography Dispatches, meant to be quick, frequent and lightly edited discussions of cryptographic topics. Longer form can be found at blog.filippo.io. If you are not reading this in your email client, you can subscribe here.

For my first round, I am writing about the recent attack on the PGP keyservers. The overall goal of the newsletter is to explain cryptography rather than to comment on the news, so we will cover context and mechanics, not the last minute updates. Issues about Ristretto, Ed25519 in Go, AES-GCM-SIV, and OPRF based contact discovery are still coming as promised!

The point of these newsletters is to write more, so please forgive me a lower level of polish. Since I don't have any invasive tracking in these emails, reply to let me know what you think and what you'd like to read about!

This PGP flooding attack is not sophisticated

OpenPGP is an encryption and signing protocol from the 90's. It comes with a pretty idealistic solution to identity management and key distribution called the "web of trust". How it works is that you and I have a private and a public key, and once we meet and you verify that I am who I say am, you sign my public key, effectively making the statement "I am Alice and I verified that this is indeed Filippo's key". The idea is that if enough statements like that are published, they form a web, and two people who did not meet can chain a path through it to securely find each other's public key, to send each other emails, 0-days, or whatever.

I never got this to work for a number of reasons¹. For example, it was never clear to me whether signing a key meant that I'd verified the person's identity, or that I then trusted them to verify other people's identities. In the latter case I would never sign a stranger's key, and in the former case there is no transitive trust to build chains out of. Nevertheless it's important to understand that the tooling and ecosystem exist to serve this model.

OpenPGP keys are implemented as a sequence of statements, or packets. A packet can bind a key to a user ID, it can add a short-lived subkey, it can specify the recipient preferences, it can revoke a key, or it can attach someone else's signature. Packets are never deleted; instead, a new packet is added that revokes or supersedes the old one. This property makes it possible to efficiently and automatically sync keys from multiple sources: packets are simply joined and sorted by their timestamp, and the result is a full view of the key.

The final piece of the puzzle are keyservers. Keyservers are public services that host arbitrary OpenPGP keys, so that clients can fetch unknown ones by fingerprint or user ID (in theory to then verify them via the web of trust), or update known ones to discover new related packets. There is a network of public keyservers that sync contents with each other called the SKS pool.

Critically, anyone can upload a key to an SKS keyserver, and its content will be joined with the current view of that key across the SKS network. New subkeys and preferences need to be signed by the master key to be valid, but web of trust signatures can be uploaded by anyone².

Now, here's a question you could ask in a job interview for a security role: what can go wrong in a system like this? It would be fair to expect an answer about abuse: an attacker might upload fake signatures in an attempt to disrupt operations. There are more subtle issues and sophisticated attacks, but this is the most straightforward one.

Well, that's exactly what's happening, and there's apparently little to do about it, even if people have been talking about this attack for years. Last year, someone even made a FUSE filesystem that stores data on the keyservers to make the point.

It took a long time to download the attacked keys to have a look at them: GnuPG—the primary implementation of OpenPGP—would flatly refuse to import them in its default mode, instead printing confusing and contradicting messages.

$ gpg --homedir=$PWD --recv C4BC2DDB38CCE96485EBE9C2F20691179038E5C6
gpg: key F20691179038E5C6: 4 duplicate signatures removed
gpg: key F20691179038E5C6: 54614 signatures not checked due to missing keys
gpg: key F20691179038E5C6: 4 signatures reordered
gpg: error writing keyring '/Users/filippo/tmp/sksfire/pubring.kbx': Provided object is too large
gpg: key F20691179038E5C6: public key "[User ID not found]" imported
gpg: Total number processed: 1
gpg:               imported: 1
gpg:           not imported: 1

After forcing the use of an older local keyring format, I managed to have it download one of the keys. It took a few tries, presumably because some of the keyservers were falling over, too. Just the import took more than 10 minutes of CPU time.

$ rm -f pubring.kbx*
$ touch pubring.gpg
$ gpg --homedir=$PWD --recv C4BC2DDB38CCE96485EBE9C2F20691179038E5C6
gpg: key F20691179038E5C6: 4 duplicate signatures removed
gpg: key F20691179038E5C6: 54614 signatures not checked due to missing keys
gpg: key F20691179038E5C6: 4 signatures reordered
gpg: key F20691179038E5C6: public key "Daniel Kahn Gillmor <dkg@fifthhorseman.net>" imported
gpg: no ultimately trusted keys found
gpg: Total number processed: 1
gpg:               imported: 1
$ ls -lh pubring.gpg
-rw-r--r--  1 filippo  staff    17M  2 Jul 16:30 pubring.gpg

Note the "54614 signatures not checked due to missing keys" message. Running gpg --list-packets reveals that most of the 17MB key is just an endless sequence of signature packets from unknown keys.

[...]
# off=158847 ctb=89 tag=2 hlen=3 plen=307
:signature packet: algo 1, keyid A331A582DB0D646A
    version 4, created 1560894259, md5len 0, sigclass 0x10
    digest algo 8, begin of digest 34 6d
    hashed subpkt 33 len 21 (issuer fpr v4 034977180A6C3D0706A9A02BA331A582DB0D646A)
    hashed subpkt 2 len 4 (sig created 2019-06-18)
    subpkt 16 len 8 (issuer key ID A331A582DB0D646A)
    data: [2046 bits]
# off=159157 ctb=b0 tag=12 hlen=2 plen=6
:trust packet: sig flag=00 sigcache=00
# off=159165 ctb=89 tag=2 hlen=3 plen=307
:signature packet: algo 1, keyid AF00DF1DD08B9796
    version 4, created 1560890675, md5len 0, sigclass 0x10
    digest algo 8, begin of digest 0d 21
    hashed subpkt 33 len 21 (issuer fpr v4 0349A8E8BE2AA7B63233F9B9AF00DF1DD08B9796)
    hashed subpkt 2 len 4 (sig created 2019-06-18)
    subpkt 16 len 8 (issuer key ID AF00DF1DD08B9796)
    data: [2048 bits]
# off=159475 ctb=b0 tag=12 hlen=2 plen=6
:trust packet: sig flag=00 sigcache=00
[...]

The distribution of the packed data lengths³ is consistent with them being real signatures, where there's 1 / 2^n probability of the value having n leading zero bits, which get omitted. It looks like all the attacker did was generate a bunch of keys, sign the target key with them, and throw them away. It could have been scripted in bash.

$ gpg --list-packets pubring.gpg | grep "data: \[20" | sort | uniq -c | sort -n
   1    data: [2033 bits]
   2    data: [2032 bits]
   3    data: [2035 bits]
   5    data: [2034 bits]
   8    data: [2036 bits]
  19    data: [2037 bits]
  28    data: [2038 bits]
  80    data: [2039 bits]
 135    data: [2040 bits]
 277    data: [2041 bits]
 567    data: [2042 bits]
1099    data: [2043 bits]
2216    data: [2044 bits]
4567    data: [2045 bits]
9024    data: [2046 bits]
18265   data: [2047 bits]
18304   data: [2048 bits]

This was truly the most straightforward attack possible. The attacker did what the system is designed to support—they signed a key with another key, they just did it a lot. (Not even GBs worth of it, a meager 17MB.) And basically the whole ecosystem came crashing down.

GnuPG can't even import my certificate from the keyservers any more in the common case. This also has implications for ensuring that revocations are discovered, or new subkeys rotated, as described in that ticket.

In the situations where it's possible to have imported the large certificate, gpg exhibits severe performance problems for even basic operations over the keyring.

This causes Enigmail to become unusable if it encounters a flooded certificate.

It also causes problems for monkeysphere-authentication if it encounters a flooded certificate.

If this spammed certificate is in the GnuPG keyring, just verifying an OpenPGP-signed tag in the git revision control system made by this certificate is now extremely expensive. git tag -v $tagname, for a tag that is signed with the signing-capable subkey of this certificate consumes 145 seconds of CPU time (tag signature verification often happens as part of an automated process, and typically takes much less than 1 second of CPU time).

It's worth noting that there is no cryptography involved in what GnuPG gets stuck on: since the public keys are not available, none of the signatures get cryptographically verified. It's taking minutes to traverse a 17MB database of 50K rows. Even running gpg -k to list the available public keys takes one minute of CPU time.

/Users/filippo/tmp/sksfire/pubring.gpg
--------------------------------------
pub   ed25519 2019-01-19 [C] [expires: 2021-01-18]
      C4BC2DDB38CCE96485EBE9C2F20691179038E5C6
uid           [ unknown] Daniel Kahn Gillmor <dkg@fifthhorseman.net>
uid           [ unknown] Daniel Kahn Gillmor <dkg@debian.org>
sub   ed25519 2019-01-19 [S] [expires: 2020-01-19]
sub   ed25519 2019-01-19 [A] [expires: 2020-01-19]
sub   cv25519 2019-01-19 [E] [expires: 2020-01-19]

gpg --homedir=$PWD -k  59.70s user 0.62s system 93% cpu 1:04.55 total

There is no way to tell GnuPG to ignore signatures from unknown keys, and it looks at them for every operation.

Again, this is not a surprising or unexpected attack.

We've seen various forms of certificate flooding before, including spam on Werner Koch's key over a year ago, and abuse tools made available years ago under the name "trollwot". There's a keyserver-backed filesystem proposed as a proof of concept to point out the abuse.

There was even a discussion a few months ago about how the SKS keyserver network is dying.

So none of this is a novel or surprising problem. [...]

What should be surprising is that software designed to resist state-level adversaries, and advertised to at-risk users all over the world, has trivial, well-known O(n²) behavior, in an ecosystem based on permission-less append-only lists of attacker-provided inputs.

I really don't blame the volunteers that do what they can with the resources they have, but if the OpenPGP ecosystem is not equipped to serve its users, at some point we need to give up, stop recommending it to sensitive users who trust us, and move on to modern alternatives. Where they are missing, we'll have to build them.

Anyway, nobody knows how to fix it at the keyserver level, because the software is an unmaintained OCaml Ph.D thesis, and because the pool is decentralized and there's no one in charge to make the nodes upgrade. I don't really get the latter argument, because surely someone operates the pool.sks-keyservers.net DNS entry and they presumably can kick out out of date nodes, but ¯\(ツ)/¯

DKG convinced the GnuPG maintainer to filter third-party signatures during imports when there's too many, but it looks like it's still not a robust fix against actually malicious attacks. As for the code that takes minutes to traverse 17MB, it's going to be replaced at some point by an ad-hoc transactional database implementation. SQLite was rejected because of some concerns about its journaling implementation that don't match my understanding of how SQLite works⁴, which is not encouraging.

We know that. The problem is that we can't simply switch to sqlite for key storage because it is common that dozens of gpg processes are accessing the key data base. At least at some points we need proper transactional behaviour and Sqlite implements that by talking a temporary copy of the database - not an option for large keyrings.

We have a plan and already some code for 2.3 to fix that. This is why I set the priority to normal.

Finally, there is a new keyserver called keys.openpgp.org, which verifies email addresses before associating keys to them, and only accepts updates signed by the master key. While this solves the flooding attack, it also makes it impossible to distribute third-party signatures. Without even the possibility of using the web of trust, and with a mild guarantee that keys for alice@example.com weren't uploaded by random people, I expect it will become a trusted authority mapping recipients to keys. Without technical measures to guarantee its accountability and transparency in operating that trusted role, it wouldn't be considered acceptable in a modern system.

Alla prossima

Alla prossima with an issue about happier cryptography!

For reading through 2k words on OpenPGP, here's a picture of a fireplace in Argentina.

I'd like to thank Marf Foster for her encouragement, review, edits and comments.

Again, I don't believe in invasive tracking, so I won't get to know you read this unless you hit reply, and tell me what you think. Please do!

1. In my experience, neither has anyone else. Every use of PGP I'm aware of involves pre-shared keys, or just randomly trusting the first key you download. Notable exception, the Debian developer community built its own web of trust which seems to work.

2. It's considered best practice to email the updated public key with a new signature to its owner, as a way to verify their control of the email address in the user ID, but it's in no way a requirement: you can sign someone's key and upload your signature to the keyservers without the key owner's cooperation, and it will be fetched by anyone updating their key from the same keyserver pool.

3. RSA signatures are represented in OpenPGP as a number, which in turn is encoded as a variable size bit string. They call them MPIs. Both representing fixed size signatures as variable size numbers (by stripping leading zeroes), and encoding lengths at bit granularity are unwelcome complexity these days.

4. Even in PERSIST mode, the journal will only grow as large as the number of modified pages. If the entire database is modified in a single transaction, this will result in a journal as large as the database, but it's unclear to me how transactional behavior can be achieved otherwise: in order to be able to rollback the old content still needs to be somewhere.