gpg drops flooded certificates entirely if the certficate is too large, and gpg is using `pubring.kbx`
Closed, ResolvedPublic

Description

My OpenPGP certificate 0xC4BC2DDB38CCE96485EBE9C2F20691179038E5C6 was flooded with spam on or about June 18 2019. The version of it on the SKS keyserver network is now ~17MiB. gpg chokes on it:

0 dkg@alice:/tmp/cdtemp.7QJ3xD$ gpg --homedir=$(pwd) --recv C4BC2DDB38CCE96485EBE9C2F20691179038E5C6
gpg: keybox '/tmp/cdtemp.7QJ3xD/pubring.kbx' created
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 '/tmp/cdtemp.7QJ3xD/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
2 dkg@alice:/tmp/cdtemp.7QJ3xD$

But, if i force gpg into using an old-style keyring instead of a keybox, it does import:

0 dkg@alice:/tmp/cdtemp.7QJ3xD$ rm -f pubring.kbx*
0 dkg@alice:/tmp/cdtemp.7QJ3xD$ touch pubring.gpg
0 dkg@alice:/tmp/cdtemp.7QJ3xD$ 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
0 dkg@alice:/tmp/cdtemp.7QJ3xD$

Note that i'm not suggesting that it would be *good* for gpg to do this import. In fact, i think the import limit could maybe even be reduced. Once the flooded certificate is imported, it incurs a huge performance penalty for even the most basic tasks in GnuPG (which i'll document in a separate ticket), so it is actively bad to have such a thing in your local keyring.

Using keybox again, I also tried to receive that key using --import-options import-clean, and --import-options import-minimal. In neither case was any certificate merged. This suggests that (for example):

  • a certificate revocation will not be merged
  • expiration updates will not be merged
  • new subkeys will not be merged

Here's what i think *should* happen, if we want gpg to be able to safely refresh keys from the keyservers:

  • if the certificate overall is too large to import, gpg should preferentially drop all packets that would have been dropped had the certificate been "cleaned" (as though --import-options import-clean were present, and functional)
  • If the cleaned certificate is still larger than the importable size, gpg should drop all the packets that would have been dropped had it been minimized. (as though --import-options import-minimal were present, and functional).
  • if the minimized certificate is still too large to merge, then the primary key packet and the earliest "hard" revocation direct key signature should be merged.
dkg created this task.Fri, Jun 28, 8:15 AM
dkg updated the task description. (Show Details)Fri, Jun 28, 8:18 AM
werner added a subscriber: werner.Fri, Jun 28, 11:52 AM

I know this problem very well and it let to the introduction the import filters. For example I can update my own key only using filters like

import-filter drop-sig=   sig_created_d=2015-12-24
import-filter drop-sig=|| sig_created_d=2016-03-16

in my gpg.conf. The OpenPGP format as used in the past is subject to easy DoS regarding key signatures. Some people had the very same problem already with PGP-2. The only useful mitigation I can see is to allow the im,port of key signatures only from trusted source and not from keyservers.

dkg added a comment.Fri, Jun 28, 2:32 PM

i'm aware of the filters you're using, but they are not a principled response to this kind of certificate flooding attack. An attacker who wants to be really abusive can easily create certifications that bypass any import-filter gpg is capable of.

In the body of the message above, I describe a specific set of mitigations that would be concretely helpful (filtering incoming keys that are too large before attempting to put them in the keyring). Can you comment on those please? If you think they are not useful, i'm happy to hear an explanation.

With those mitigations, keyservers (not "trusted sources") are still useful for revocation and subkey updates, as long as we have fixed T4393.

georg added a subscriber: georg.Fri, Jun 28, 3:37 PM
dkg added a comment.Sat, Jun 29, 12:53 AM

Note also that some keyservers like keys.openpgp.org will distribute only verified self-sigs (including revocations and subkey updates) without distributing the floodable third-party certifications. We can and should distinguish "updates-only" keyservers from discovery-by-address mecahnisms.

But yes, if we do that, this might mean that the SKS network falls away. GnuPG currently uses dirmngr's keyserver directive for both --search (by uid) and --recv (by fingerprint or keyid). Can we make that distinct somehow? or just deprecate --search entirely, and encourage --locate-key instead?

ilf added a subscriber: ilf.Sun, Jun 30, 9:28 PM
werner added a comment.Mon, Jul 1, 9:56 AM

I have mentioned it several times in the past that I would like to see the search by user id feature be removed from keyservers so that there is less incentive to use them as a perpetual and searchable database for maybe illegitimate data.

gpg would then do a locate-key instead of a --search-key. Given the current state of things we may remove/redefine --search-keys even without changes by the keyservers.

werner added a comment.Mon, Jul 1, 3:30 PM

That is probably not what you want but at least it allows to import your key

$ gpg --recv-key -v --keyserver-options import-self-sigs-only 0xC4BC2DDB38CCE96485EBE9C2F20691179038E5C6
gpg: data source: https://51.38.91.189:443
gpg: armor header: Version: SKS 1.1.6
gpg: armor header: Comment: Hostname: pgpkeys.eu
gpg: key F20691179038E5C6: number of dropped non-self-signatures: 54614
gpg: pub  ed25519/F20691179038E5C6 2019-01-19  Daniel Kahn [...]
gpg: key F20691179038E5C6: 4 duplicate signatures removed
gpg: key F20691179038E5C6: 4 signatures reordered

I will see what else can be done as a quick solution. Regarding my former comment: At that time I had not yet read the thread about this problem.

dkg added a comment.EditedMon, Jul 1, 6:20 PM

thanks for working on this @werner. rG2e349bb61737 is definitely not useful for me. If i am going to tell anyone "hey, do this weird thing differently in order to fetch my key", i will tell them "pull it from https://dkg.fifthhorseman.net/dkg-openpgp.key". I will never tell anyone to use import-self-sigs-only.

Not only that, but the current implementation of import-self-sigs-only also does not appear to be robust against a malicious certificate flood given SKS's lack of cryptographic validation. Adding a new option to an already-crowded space is not the right solution. the right solution is for gpg to be more defensive about the OpenPGP packets it receives, regardless of who it receives them from. Again, i described a series of fallbacks that (a) don't require the user to set any options, and (b) make more sense than import-self-sigs-only in the first place. Could you please comment on that proposal?

I've opened T4599 about deprecating --search explicitly, so we should have that separate discussion over there.

werner added a comment.Mon, Jul 1, 7:54 PM

Even if you can't use it the option is still useful to avoid other kinds of DoS. As written in the comments it is not a full solution but it helps to side-step issues with key-signature. In particular for sites which do not have a need for them.
BTW, revocation certificates are still merged with the new option.

The problem you see with your key is the keyblock limit of 5 MiB we use with keyboxes. This has been been set to avoid, surprise, DoS. Now we could increase that limit but it is not really helpful. You suggestions are to try to keep the keyblock within that limit using a several step fallback scheme. This is quite some overhead so I hesitate to implement it in this way.

But we can do a it with one fallback step: If we run into the image-larger-than-5MiB error, we try again but this time using the new option. In contrast to --import-clean this is much faster than running the full import step again and we can do an import-clean anyway in this case. I need to check the details, though.

werner added a comment.Mon, Jul 1, 9:44 PM

I implemented that in master. The first output is from an update of your key and the second from an insert of a new key.

gpg: pub  ed25519/F20691179038E5C6 2019-01-19  Daniel Kahn Gill[...]
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 '[...]/pubring.kbx': Provided object is too large
gpg: the keyblock was too large, retrying with only self-sigs
gpg: pub  ed25519/F20691179038E5C6 2019-01-19  Daniel Kahn Gill[...]
gpg: key F20691179038E5C6: number of dropped non-self-signatures: 54614
gpg: key F20691179038E5C6: "[User ID not found]" not changed
gpg: Total number processed: 1
gpg:              unchanged: 1

gpg: pub  ed25519/F20691179038E5C6 2019-01-19  Daniel Kahn Gill[...]
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 '[...]/pubring.kbx': Provided object is too large
gpg: the keyblock was too large, retrying with only self-sigs
gpg: pub  ed25519/F20691179038E5C6 2019-01-19  Daniel Kahn Gill[...]
gpg: key F20691179038E5C6: number of dropped non-self-signatures: 54614
gpg: using pgp trust model
gpg: key F20691179038E5C6: public key "[User ID not found]" imported
gpg: Total number processed: 1
gpg:               imported: 1

Note the final stats. It takes some time to import and process the key and all its signatures during the first phase but the fallback is then much quicker. The fallback uses --import-clean,self-sigs-only. I need to cleanup a few string and will then commit to master. More on this the tomorrow.

werner triaged this task as High priority.Mon, Jul 1, 9:44 PM
pert added a subscriber: pert.Tue, Jul 2, 2:08 AM
werner changed the task status from Open to Testing.Tue, Jul 2, 9:35 AM

Also pushed to 2.2. Right now I can't see what else can be done, so I change the status to testing.

dkg added a comment.Wed, Jul 3, 12:09 AM

Thanks for working on this fallback, Werner.

On the issue of flooding attacks:

  • if an adversary first provides a certificate that is just barely under 5MiB, it will be imported in full, correct?
  • if such a certificate is imported, and then in a separate fetch, gpg receives a certificate with the same primary key, but with a revocation (perhaps even just a two-packet certificate, with just a primary key and a revocation certificate, or even just a raw revocation certificate), what happens? The aggregated certificate (including the revocation) will be > 5MiB.

Does this limit mean that an attacker can block a GnuPG user from receiving and importing a revocation by padding out their certificates to 5MiB?

Angel added a subscriber: Angel.Wed, Jul 3, 2:49 AM
dkg added a comment.Wed, Jul 3, 6:48 AM

as a separate variant: if the attacker floods the certificate with bogus self-signatures -- that is, certifications that have an issuer fingerprint or issuer key id subpacket, whether hashed or unhashed -- will that make it impossible to import any of them?

werner changed the task status from Testing to Open.Wed, Jul 3, 9:59 AM

I don't think so. The fallback mechnanism will still work and remove everything but valid self-signatures. This gives enough space to write the keyblock with the new revocation certificates. I am not sure about designated revokers in this case.

But we have a different code patch for standalone revocation certificates; there is no fallback yet and thus in corner case they would not work.

dkg added a comment.Wed, Jul 3, 2:53 PM

my initial scenario is where an adversarial keystore floods a certificate right up to (but within) the 5MiB boundary, so that the user has stored it in the keyring already. Then, the user encounters the certificate again, with revocation attached.

Are you saying that if the fallback case is hit during import, then all previously-stored third-party certifications will also be stripped from the keyring?

If so, that strikes me as a bad outcome: an adversarial keystore can force the removal of all locally-stored third-party certifications, potentially making the certificate no longer valid.

If not, then it seems that the certificate + revocation will be above the 5MiB boundary, which means it will be rejected before storage, leaving the user with a non-revoked certificate. This is also a bad outcome (albeit in a different direction).

werner added a comment.Wed, Jul 3, 5:51 PM

Okay, if an attacker exactly hist that limit your case is valid. I see no easy fix here, though. What we can do is what is done on Unix file systems to give average users a disk full erroreven if there a few percent of the disk is free; root can use that extra space then. Revocation certificates would be what root is on Unix file systems.

Needs a bit of work in gpg; the question is whether it can wait until the after next release.

werner moved this task from Backlog to For next release on the gnupg (gpg22) board.Wed, Jul 3, 6:02 PM
werner closed this task as Resolved.Thu, Jul 4, 4:25 PM
werner claimed this task.

Fix will be in 2.2.17.
See T4612 for the revocation case.

dkg added a comment.Mon, Jul 15, 7:34 PM

The fact that import-clean modifies already-held certifications makes me think it is inappropriate to have as the default for keyserver access (see T4628 for more details).

Given that self-sigs-only is enabled by default, what additional value does import-clean have for the user?

Is the attempt to defend against an abusively large list of self-sigs?