Abuse-Resistant OpenPGP Keystores

1.1. Requirements Language

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all capitals, as shown here.¶

1.2. Terminology

• "OpenPGP certificate" (or just "certificate") is used interchangeably with [RFC4880]'s "Transferable Public Key". The term "certificate" refers unambiguously to the entire composite object, unlike "key", which might also be used to refer to a primary key or subkey.¶
• An "identity certification" (or just "certification") is an [RFC4880] signature packet that covers OpenPGP identity information -- that is, any signature packet of type 0x10, 0x11, 0x12, or 0x13. Certifications are said to (try to) "bind" a primary key to a User ID.¶
• The primary key that makes the certification is known as the "issuer". The primary key over which the certification is made is known as the "subject".¶
• A "first-party certification" is issued by the primary key of a certificate, and binds itself to a user ID in the certificate. That is, the issuer is the same as the subject. This is sometimes referred to as a "self-sig".¶
• A "third-party certification" is a made over a primary key and user ID by some other certification-capable primary key. That is, the issuer is different than the subject. The elusive "second-party" is presumed to be the verifier who is trying to interpret the certificate.¶
• All subkeys are bound to the primary key with an [RFC4880] Subkey Binding Signature. Some subkeys also reciprocate by binding themselves back to the primary key with an [RFC4880] Primary Key Binding Signature. The Primary Key Binding Signature is also known as a "cross-signature" or "cross-sig".¶
• A "keystore" is any collection of OpenPGP certificates. Keystores typically receive mergeable updates over the course of their lifetime which might add to the set of OpenPGP certificates they hold, or update the certificates.¶
• "Certificate validation" is the process whereby a user decides whether a given user ID in an OpenPGP certificate is acceptable for use. For example, if the certificate has a user ID of Alice <alice@example.org> and the user wants to send an e-mail to alice@example.org, the mail user agent might want to ensure that the certificate is valid for this e-mail address before encrypting to it. Some clients may rely on specific keystores for certificate validation, but some keystores (e.g., [SKS]) make no assertions whatsoever about certificate validity, and others offer only very subtle guarantees. See Section 3.4 for more details.¶
• "Certificate lookup" refers to the retrieval of a set of certificates from a keystore based on the user ID or some substring match of the user ID. See Section 3.3 for more details.¶
• "Certificate refresh" refers to retrieval of a certificate from a keystore based on the fingerprint of the primary key. See Section 3.1 for more details.¶
• "Certificate discovery" refers to the retrieval of a set of certificates from a keystore based on the fingerprint or key ID of any key in the certificate. See Section 3.2 for more details.¶
• A "keyserver" is a particular kind of keystore, typically a means of publicly distributing OpenPGP certificates or updates to them. Examples of keyserver software include [SKS] and [MAILVELOPE-KEYSERVER]. One common HTTP interface for keyservers is [I-D.shaw-openpgp-hkp].¶
• A "synchronizing keyserver" is a keyserver which gossips with other peers, and typically acts as an append-only log. Such a keyserver is typically useful for certificate lookup, certificate discovery, and certificate refresh (including revocation information). They are typically not useful for certificate validation, since they make no assertions about whether the identities in the certificates they server are accurate. As of the writing of this document, [SKS] is the canonical synchronizing keyserver implementation, though other implementations exist.¶
• An "e-mail validating keyserver" is a keyserver which attempts to verify the identity in an OpenPGP certificate's user ID by confirming access to the e-mail account, and optionally by confirming access to the secret key. Some implementations permit removal of a certificate by anyone who can prove access to the e-mail address in question. They are useful for certificate lookup based on e-mail address and certificate validation (by users who trust the operator), but some may not be useful for certificate refresh or certificate discovery, since a certificate could be simply replaced by an adversary who also has access to the e-mail address in question. [MAILVELOPE-KEYSERVER] is an example of such a keyserver.¶
• A "sovereignty-respecting" keystore is one that only distributes data associated with a given certificate that has been explicitly approved by the primary key of that certificate. See Section 8 for more details and example strategies.¶
• "Cryptographic validity" refers to mathematical evidence that a signature came from the secret key associated with the public key it claims to come from. Note that a certification may be cryptographically valid without the signed data being true (for example, a given certificate with the user ID Alice <alice@example.org> might not belong to the person who controls the e-mail address alice@example.org even though the self-sig is cryptographically valid). In particular, cryptographic validity for user ID in a certificate is typically insufficient evidence for certificate validation. Also note that knowledge of the public key of the issuer is necessary to determine whether any given signature is cryptographically valid. Some keyservers perform cryptographic validation in some contexts. Other keyservers (like [SKS]) perform no cryptographic validation whatsoever.¶
• OpenPGP revocations can have "Reason for Revocation" (see [RFC4880]), which can be either "soft" or "hard". The set of "soft" reasons is: "Key is superseded" and "Key is retired and no longer used". All other reasons (and revocations that do not state a reason) are "hard" revocations. See Section 12.1 for more detail.¶

2.1. Certificate Flooding

Many public keystores (including both the [SKS] keyserver network and [MAILVELOPE-KEYSERVER]) allow anyone to attach arbitrary data (in the form of third-party certifications) to any certificate, bloating that certificate to the point of being impossible to effectively retrieve. For example, some OpenPGP implementations simply refuse to process certificates larger than a certain size.¶

This kind of Denial-of-Service attack makes it possible to make someone else's certificate unretrievable from the keystore, preventing certificate lookup, discovery, or refresh. In the case of a revoked certificate that has been flooded, this potentially leaves the client of the keystore with the compromised certificate in an unrevoked state locally because it was unable to fetch the revocation information.¶

Additionally, even without malice, OpenPGP certificates can potentially grow without bound.¶

2.2. User ID Flooding

Public keystores that are used for certificate lookup may also be vulnerable to attacks that flood the space of known user IDs. In particular, if the keystore accepts arbitrary certificates from the public and does no verification of the user IDs, then any client searching for a given user ID may need to review and process an effectively unbounded set of maliciously-submitted certificates to find the non-malicious certificates they are looking for.¶

For example, if an attacker knows that a given system consults a keystore looking for certificates which match the e-mail address alice@example.org, the attacker may upload thousands of certificates containing user IDs that match that address. Even if those certificates would not be accepted by a client (e.g., because they were not certified by a known-good authority), the client still has to iterate through all of them in order to find the non-malicious certificates.¶

User ID flooding is only effective if the keystore offers a lookup interface at all.¶

2.3. Fingerprint Flooding

A malicious actor who wants to render a certificate unavailable for refresh may generate an arbitrary number of OpenPGP certificates with the targeted primary key attached as a subkey. If they can convince a keystore to accept all of those certificates, and the keystore returns them by subkey match during certificate refresh, then the certificate refresh client will need to spend an arbitrary amount of bandwidth and processing power filtering out the irrelevant data, and may potentially give up before discovering the certificate of interest.¶

A malicious actor may also want to confuse a certificate discovery request that was targeted at a particular subkey, by binding that subkey to multiple bogus certificates. If these bogus certificates are ingested and redistributed by the keystore, then a certificate discovery client may receive a set of certificates that cannot be adequately distinguished.¶

2.4. Keystore Flooding

A public keystore that accepts arbitrary OpenPGP material and is append-only is at risk of being overwhelmed by sheer quantity of malicious uploaded packets. This is a risk even if the user ID space is not being deliberately flooded, and if individual certificates are protected from flooding by any of the mechanisms described later in this document.¶

The keystore itself can become difficult to operate if the total quantity of data is too large, and if it is a synchronizing keyserver, then the quantities of data may impose unsustainable bandwidth costs on the operator as well.¶

Effectively mitigating against keystore flooding requires either abandoning the append-only property that some keystores prefer, or imposing very strict controls on initial ingestion.¶

2.5. Toxic Data

Like any large public dataset, it's possible that a keystore ends up hosting some content that is legally actionable in some jurisdictions, including libel, child pornography, material under copyright or other "intellectual property" controls, blasphemy, hate speech, etc.¶

A public keystore that accepts and redistributes arbitrary content may face risk due to uploads of toxic data.¶

3.1. Certificate Refresh

This is the simplest keystore operation. The client sends the keystore the full fingerprint of the certificate's primary key, and the keystore sends the client the corresponding certificate (or nothing, if the keystore does not contain a certificate with a matching primary key).¶

keystore.cert_refresh(primary_fpr) -> certificate?

A client uses certificate refresh to retrieve the full details of a certificate that it already knows about. For example, it might be interested in refreshes to the certificate known to the keystore, including revocations, expiration refreshes, new third-party certifications, etc.¶

Upon successful refresh, the client SHOULD merge the retrieved certificate with its local copy.¶

Not all keystores offer this operation. For example, clients cannot use WKD ([I-D.koch-openpgp-webkey-service]) or OPENPGPKEY ([RFC7929]) for certificate refresh.¶

3.2. Certificate Discovery

If a client is aware of an OpenPGP signature or certification that it cannot verify because it does not know the issuing certificate, it may consult a keystore to try to discover the certificate based on the Issuer or Issuer Fingerprint subpacket in the signature or certification it is trying to validate.¶

keystore.cert_discovery(keyid|fpr) -> certificate_list

This is subtly different from certificate refresh (Section 3.1) in three ways:¶

• it may return more than one certificate (e.g., when multiple certificates share a subkey, or when a primary key on one certificate is a subkey on another)¶
• it is willing to accept searches by short key ID, not just fingerprint¶
• it is willing to match against a subkey, not just a primary key¶

While a certificate discovery client does not initially know the certificate it is looking for, it's possible that the returned certificate is one that the client already knows about. For example, a new subkey may have been added to a certificate.¶

Upon successful discovery, the client SHOULD merge any retrieved certificates with discovered local copies (as determined by primary key), and then evaluate the original signature against any retrieved certificate that appears to be valid and reasonable for use in the signing context.¶

It is unclear what a client should do if multiple certificates do appear to be valid for a given signature, because of ambiguity this represents about the identity of the signer. However, this ambiguity is similar to the ambiguity of a certificate with multiple valid user IDs, which the client already needs to deal with.¶

Not all keystores offer this operation. For example, clients cannot use WKD ([I-D.koch-openpgp-webkey-service]) or OPENPGPKEY ([RFC7929] for certificate discovery.¶

3.3. Certificate Lookup

If a client wants to encrypt a message to a particular e-mail address, or wants to encrypt a backup to some identity that it knows of but does not have a certificate for, it may consult a keystore to discover certificates that claim that identity in their user ID packets. Both [I-D.koch-openpgp-webkey-service] and [I-D.shaw-openpgp-hkp] offer certificate lookup mechanisms.¶

[RFC4880] User IDs are constrained only in that they are a UTF-8 string, but some conventions govern their practical use. See Section 12.2 for more discussion of some common conventions around user ID structure.¶

Note that lookup does not necessarily imply user ID or certificate validation. It is entirely possible for a keystore to return a certificate during lookup that the client cannot validate.¶

Abuse-resistant keystores that offer a lookup interface SHOULD distinguish interfaces that perform full-string-match lookup from interfaces that perform e-mail address based lookup.¶

keystore.cert_lookup(uid) -> certificate_list

keystore.cert_lookup(addr) -> certificate_list

3.4. Certificate Validation

An OpenPGP client may assess certificate and user ID validity based on many factors, some of which are directly contained in the certificate itself (e.g., third-party certifications), and some of which are based on the context known to the client, including:¶

• Whether it has seen e-mails from that address signed by that certificate in the past,¶
• How long it has known about the certificate,¶
• Whether the certificate was fetched from a keystore that asserts validity of the user ID or some part of it (such as the e-mail address).¶

A keystore MAY facilitate clients pursuing this last point of contextual corroboration via a direct interface:¶

keystore.cert_validate(primary_fpr, uid) -> boolean

In an e-mail-specific context, the client might only care about the keystore's opinion about the validity of the certificate for the e-mail address portion of the user ID only:¶

keystore.cert_validate(primary_fpr, addr) -> boolean

For some keystores, the presence of a certificate in the keystore alone implies that the keystore asserts the validity of all user IDs in the certificate retrieved. For others, the presence in the keystore applies only to some part of the user ID. For example, [PGP-GLOBAL-DIRECTORY] will only return user IDs that have completed an e-mail validation step, so presence in that keystore implies an assertion of validity of the e-mail address part of the user IDs returned, but makes no claim about the display-name portion of any returned user IDs. Note that a client retrieving a certificate from such a keystore may merge the certificate with a local copy -- but the validity asserted by the keystore of course has no bearing on the packets that the keystore did not return.¶

In a more subtle example, the retrieval of a certificate looked up via WKD ([I-D.koch-openpgp-webkey-service]) or DANE ([RFC7929]) should only be interpreted as a claim of validity about any user ID which matches the e-mail address by which the certificate was looked up, with no claims made about any display-name portions, or about any user ID that doesn't match the queried e-mail address at all.¶

A keystore that offers some sort of validation interface may also change its opinion about the validity of a given certificate or user ID over time; the interface described above only allows the client to ask about the keystore's current opinion, but a more complex interface might be capable of describing the keystore's assertion over time. See also Section 11.5.¶

An abuse-resistant keystore that clients rely on for any part of their certificate validation process SHOULD offer a distinct interface for making assertions about certificate and user ID validity to help clients avoid some of the subtleties involved with inference based on presence described above.¶

Note that the certificate validation operation as described above has a boolean response. While a "true" response indicates that keystore believes the user ID or e-mail address is acceptable for use with the certificate referred to by the public key fingerprint, a "false" response doesn't necessarily mean that the keystore actively thinks that the certificate is actively bad, or must not be used for the referenced identity. Rather, "false" is the default state: no opinion is expressed by the keystore, and the client is left to make their own inference about validity based on other factors. A keystore MAY offer a more nuanced validity interface; if it does, it SHOULD explicitly document the semantics of the different response types so that clients can make appropriate judgment.¶

3.5. Certificate Submission

Different keystores have different ways to submit a certificate for consideration for ingestion, including:¶

• a simple upload of a certificate via HTTP¶
• round-trip e-mail verification¶
• proof of presence in some other service¶
• vouching, or other forms of multi-party attestation¶

Because these schemes vary so widely, this document does not attempt to describe the keystore certificate submission process in detail. However, guidance can be found for implementations that generate, manage, and submit certificates in Section 10.¶

4.1. Decline Large Packets

While [RFC4880] permits OpenPGP packet sizes of arbitrary length, OpenPGP certificates rarely need to be so large. An abuse-resistant keystore SHOULD reject any OpenPGP packet larger than 8383 octets. (This cutoff is chosen because it guarantees that the packet size can be represented as a one- or two-octet [RFC4880] "New Format Packet Length", but it could be reduced further)¶

This may cause problems for user attribute packets that contain large images, but it's not clear that these images are concretely useful in any context. Some keystores MAY extend this limit for user attribute packets specifically, but SHOULD NOT allow even user attributes packets larger than 65536 octets.¶

4.2. Enforce Strict User IDs

[RFC4880] indicates that User IDs are expected to be UTF-8 strings. An abuse-resistant keystore MUST reject any user ID that is not valid UTF-8.¶

Some abuse-resistant keystores MAY only accept User IDs that meet even stricter conventions, such as an [RFC5322] name-addr or addr-spec, or a URL like ssh://host.example.org (see Section 12.2).¶

As simple text strings, User IDs don't need to be nearly as long as any other packets. An abuse-resistant keystore SHOULD reject any user ID packet larger than 1024 octets.¶

4.3. Scoped User IDs

Some abuse-resistant keystores may restrict themselves to publishing only certificates with User IDs that match a specific pattern. For example, [RFC7929] encourages publication in the DNS of only certificates whose user IDs refer to e-mail addresses within the DNS zone. [I-D.koch-openpgp-webkey-service] similarly aims to restrict publication to certificates relevant to the specific e-mail domain.¶

4.4. Strip or Standardize Unhashed Subpackets

[RFC4880] signature packets contain an "unhashed" block of subpackets. These subpackets are not covered by any cryptographic signature, so they are ripe for abuse.¶

An abuse-resistant keystore SHOULD strip out all unhashed subpackets but the following exceptions:¶

4.5. Decline User Attributes

Due to size concerns, some abuse-resistant keystores MAY choose to ignore user attribute packets entirely, as well as any certifications that cover them.¶

4.6. Decline Non-exportable Certifications

An abuse-resistant keystore MUST NOT accept any certification that has the "Exportable Certification" subpacket present and set to 0. While most keystore clients will not upload these "local" certifications anyway, a reasonable public keystore that wants to minimize data has no business storing or distributing these certifications.¶

4.7. Decline Data From the Future

Many OpenPGP packets have time-of-creation timestamps in them. An abuse-resistant keystore with a functional real-time clock MAY decide to only accept packets whose time-of-creation is in the past.¶

Note that some OpenPGP implementations may pre-generate OpenPGP material intended for use only in some future window (e.g. "Here is the certificate we plan to use to sign our software next year; do not accept signatures from it until then."), and may use modified time-of-creation timestamps to try to achieve that purpose. This material would not be distributable ahead of time by an abuse-resistant keystore that adopts this mitigation.¶

4.8. Accept Only Profiled Certifications

An aggressively abuse-resistant keystore MAY decide to only accept certifications that meet a specific profile. For example, it MAY reject certifications with unknown subpacket types, unknown notations, or certain combinations of subpackets. This can help to minimize the amount of room for garbage data uploads.¶

Any abuse-resistant keystore that adopts such a strict posture should clearly document what its expected certificate profile is, and should have a plan for how to extend the profile if new types of certification appear that it wants to be able to distribute.¶

Note that if the profile is ever restricted (rather than extended), and the restriction is applied to the material already present, such a keystore is no longer append-only (see Section 7).¶

4.9. Accept Only Certificates Issued by Designated Authorities

An abuse-resistant keystore capable of cryptographic validation MAY retain a list of designated authorities, typically in the form of a set of known public keys. Upon receipt of a new OpenPGP certificate, the keystore can decide whether to accept or decline each user ID of the certificate based whether that user ID has a certification that was issued by one or more of the designated authorities.¶

If no user IDs are certified by designated authority, such a keystore SHOULD decline the certificate and its primary key entirely. Such a keystore SHOULD decline to retain or propagate all certifications associated with each accepted user ID except for first-party certifications and certifications by the designated authorities.¶

The operator of such a keystore SHOULD have a clear policy about its set of designated authorities.¶

Given the ambiguities about expiration and revocation, such a keyserver SHOULD ignore expiration and revocation of authority certifications, and simply accept and retain as long as the cryptographic signature is valid.¶

Note that if any key is removed from the set of designated authorities, and that change is applied to the existing keystore, such a keystore may no longer be append-only (see Section 7).¶

4.10. Decline Packets by Blocklist

The maintainer of the keystore may keep a specific list of "known-bad" material, and decline to accept or redistribute items matching that blocklist. The material so identified could be anything, but most usefully, specific public keys or User IDs could be blocked.¶

Note that if a blocklist grows to include an element already present in the keystore, it will no longer be append-only (see Section 7).¶

Some keystores may choose to apply a blocklist only at retrieval time and not apply it at ingestion time. This allows the keystore to be append-only, and permits synchronization between keystores that don't share a blocklist, and somewhat reduces the attacker's incentive for flooding the keystore (see Section 5 for more discussion).¶

Note that development and maintenance of a blocklist is not without its own potentials for abuse. For one thing, the blocklist may itself grow without bound. Additionally, a blocklist may be socially or politically contentious as it may describe data that is toxic (Section 2.5) in one community or jurisdiction but not another. There needs to be a clear policy about how it is managed, whether by delegation to specific decision-makers, or explicit tests. Furthermore, the existence of even a well-intentioned blocklist may be an "attractive nuisance," drawing the interest of would-be censors or other attacker interested in controlling the ecosystem reliant on the keystore in question.¶

5.1. Redacting User IDs

Some abuse-resistant keystores may accept and store user IDs but decline to redistribute some or all of them, while still distributing the certifications that cover those redacted user IDs. This draft refers to such a keystore as a "user ID redacting" keystore.¶

The certificates distributed by such a keystore are technically invalid [RFC4880] "transferable public keys", because they lack a user ID packet, and the distributed certifications cannot be cryptographically validated independently. However, an OpenPGP implementation that already knows the user IDs associated with a given primary key will be capable of associating each certification with the correct user ID by trial signature verification.¶

5.2. Primary-key Only Certificate Refresh

Abuse-resistant keystores can defend against a fingerprint flooding Section 2.3 attack during certificate refresh by implementing a narrowly-constrained certificate refresh interface.¶

Such a keystore MUST accept only a full fingerprint as the search parameter from the certificate refresh client, and it MUST return at most a single certificate whose primary key matches the requested fingerprint. It MUST NOT return more than one certificate, and it MUST NOT return any certificate whose primary key does not match the fingerprint. In particular, it MUST NOT return certificates where only the subkey fingerprint matches.¶

Note that [I-D.shaw-openpgp-hkp] does not offer the primitive described in Section 3.1 exactly. In that specification, the set of keys returned by a "get" operation with a "search" parameter that appears to be a full fingerprint is ambiguous. Some popular implementations (e.g., [SKS]) do not currently implement this mitigation, because they return certificates with subkeys that match the fingerprint.¶

5.3. Require Valid Cross-Sigs for Certificate Discovery

By definition, certificate discovery needs to be able to match subkeys, not just primary keys. This means that the mitigation in Section 5.2 is ineffective for a keystore that offers a certificate discovery interface.¶

An abuse-resistant keystore that aims to defend its certificate discovery interface from a fingerprint flooding (Section 2.3) attack can follow the following procedure.¶

Such a keystore MUST accept only a full fingerprint or a 64-bit key ID as the search parameter from the certificate discovery client. It MUST only match that fingerprint against the following:¶

• the fingerprint or key ID of a primary key associated with a valid certificate¶
• the fingerprint or key ID of a cryptographically-valid subkey that also has a cross-sig.¶

This defends against the fingerprint flooding attack because a certificate will only be returned by subkey if the subkey has agreed to be associated with the primary key (and vice versa).¶

Note that this mitigation means that certificate discovery will fail if used for subkeys that lack cross-sigs. In particular, this means that a client that tries to use the certificate discovery interface to retrieve a certificate based on its encryption-capable subkey (e.g., taking the key ID from a Public Key Encrypted Session Key (PKESK) packet) will have no success.¶

This is an acceptable loss, since the key ID in a PKESK is typically unverifiable anyway.¶

6.1. Accept Only Cryptographically-verifiable Certifications

An abuse-resistant keystore that is capable of doing cryptographic validation MAY decide to reject certifications that it cannot cryptographically validate.¶

This may mean that the keystore rejects some packets while it is unaware of the public key of the issuer of the packet.¶

As long as the keystore implements the verification algorithm, Any self-signature should always be cryptographically-verifiable, since the public key of the issuer is already present in the certificate under consideration.¶

6.2. Accept Only Certificates Issued by Known Certificates

This is an extension of Section 4.9, but where the set of authorities is just the set of certificates already known to the keystore. An abuse-resistant keystore that adopts this strategy is effectively only crawling the reachable graph of OpenPGP certificates from some starting core.¶

A keystore adopting the mitigation SHOULD have a clear documentation of the core of initial certificates it starts with, as this is effectively a policy decision.¶

This mitigation measure may fail due to a compromise of any secret key that is associated with a primary key of a certificate already present in the keystore. Such a compromise permits an attacker to flood the rest of the network. In the event that such a compromised key is identified, it might be placed on a blocklist (see Section 4.10). In particular, if a public key is added to a blocklist for a keystore implementing this mitigation, and it is removed from the keystore, then all certificates that were only "reachable" from the blocklisted certificate should also be simultaneously removed.¶

FIXME: There are complexities associated with this strategy when certificates expire or are revoked. If expiration or revocation cause some certificates to become "unreachable", what should such a keystore do?¶

6.3. Rate-limit Submissions by IP Address

Some OpenPGP keystores accept material from the general public over the Internet. If an abuse-resistant keystore observes a flood of material submitted to the keystore from a given Internet address, it MAY choose to throttle submissions from that address. When receiving submissions over IPv6, such a keystore MAY choose to throttle entire nearby subnets, as a malicious IPv6 host is more likely to have multiple addresses.¶

This requires that the keystore maintain state about recent submissions over time and address. It may also be problematic for users who appear to share an IP address from the vantage of the keystore, including those behind a NAT, using a VPN, or accessing the keystore via Tor.¶

6.4. Accept Certificates Based on Exterior Process

Some public keystores resist abuse by explicitly filtering OpenPGP material based on a set of external processes. For example, [DEBIAN-KEYRING] adjudicates the contents of the "Debian keyring" keystore based on organizational procedure and manual inspection.¶

6.5. Accept Certificates by E-mail Validation

Some keystores resist abuse by declining any certificate until the user IDs have been verified by e-mail. When these "e-mail validating" keystores review a new certificate that has a user ID with an e-mail address in it, they send an e-mail to the associated address with a confirmation mechanism (e.g., a high-entropy HTTPS URL link) in it. The e-mail itself MAY be encrypted to an encryption-capable key found in the proposed certificate. If the keyholder triggers the confirmation mechanism, then the keystore accepts the certificate.¶

Some e-mail validating keystores MAY choose to distribute certifications over all user IDs for any given certificate, but will redact (see Section 5.1) those user IDs that have not been e-mail validated.¶

[PGP-GLOBAL-DIRECTORY] describes some concerns held by a keystore operator using this approach. [MAILVELOPE-KEYSERVER] is another example.¶

7.1. Drop Superseded Signatures

An abuse-resistant keystore SHOULD drop all signature packets that are explicitly superseded. For example, there's no reason to retain or distribute a self-sig by key K over User ID U from 2017 if the keystore have a cryptographically-valid self-sig over <K,U> from 2019.¶

Note that this covers both certifications and signatures over subkeys, as both of these kinds of signature packets may be superseded.¶

Getting this right requires a nuanced understanding of subtleties in [RFC4880] related to timing and revocation.¶

One problem with dropping superseded signature packets is that a point-in-time view of a certificate becomes difficult to recover from the keystore. Following the example above, imagine encountering signature issued by key K in over an e-mail message from 2018. What happens when the e-mail reader evaluates it in 2022, after the 2019 superseding self-sig has appeared? If the keystore dropped the earlier self-sig, then a signature verifier depending on the keystore for access to the certificate will not find a binding for User ID U that was valid at the time the message was signed.¶

A more lenient approach that grants some amount of historical depth while still avoiding arbitrarily-large flooding would be for a keystore to retain the N most recent signatures in a chain of superseded signatures.¶

7.2. Drop Expired Signatures

If a signature packet is known to only be valid in the past, there is no reason to distribute it further. An abuse-resistant keystore with access to a functional real-time clock SHOULD drop all certifications and subkey signature packets with an expiration date in the past.¶

Note that this assumes that the keystore and its clients all have roughly-synchronized clocks. If that is not the case, then there will be many other problems!¶

This has a similar problem with point-in-time verifications as the problems described in Section 7.1.¶

7.3. Drop Dangling User IDs, User Attributes, and Subkeys

If enough signature packets are dropped, it's possible that some of the things that those signature packets cover are no longer valid.¶

An abuse-resistant keystore which has dropped all certifications that cover a User ID SHOULD also drop the User ID packet.¶

Note that a User ID that becomes invalid due to revocation MUST NOT be dropped, because the User ID's revocation signature itself remains valid, and needs to be distributed.¶

A primary key with no User IDs and no subkeys and no revocations MAY itself also be removed from distribution, though note that the removal of a primary key may make it impossible to cryptographically validate other certifications held by the keystore.¶

7.4. Drop All Other Elements of a Directly-Revoked Certificate

If the primary key of a certificate is revoked via a key revocation signature (type 0x20), an abuse-resistant keystore SHOULD drop all the rest of the associated data (user IDs, user attributes, and subkeys, and all attendant certifications and subkey signatures). This defends against an adversary who compromises a primary key and tries to flood the certificate to hide the revocation.¶

Note that the key revocation signature MUST NOT be dropped.¶

In the event that an abuse-resistant keystore is flooded with key revocation signatures, it should retain the hardest, earliest revocation (see also Section 12.1).¶

In particular, if any of the key revocation signatures is a "hard" revocation, the abuse-resistant keystore SHOULD retain the earliest such revocation signature (by signature creation date).¶

Otherwise, the abuse-resistant keystore SHOULD retain the earliest "soft" key revocation signature it has seen.¶

If either of the above date comparisons results in a tie between two revocation signatures of the same "hardness", an abuse-resistant keystore SHOULD retain the signature that sorts earliest based on a binary string comparison of the key revocation signature packet itself.¶

7.5. Implicit Expiration Date

In combination with some of the dropping mitigations above, a particularly aggressive abuse-resistant keystore MAY choose an implicit expiration date for all signature packets. For example, a signature packet that claims no expiration could be treated by the keystore as expiring 3 years after issuance. This would permit the keystore to eject old packets on a rolling basis.¶

An abuse-resistant keystore that adopts this mitigation needs a policy for handling signature packets marked with an explicit expiration that is longer than implicit maximum. The two obvious strategies are:¶

• cap the packet's expiration to the system's implicit expiration date, or¶
• accept the explicit expiration date.¶

Warning: Any implementation of this idea is pretty radical, and it's not clear what it would do to an ecosystem that depends on such a keystore. It probably needs more thinking.¶

8.1. Refresh-only Keystores

Some soveriegnty-respecting keystores may resist abuse by declining to accept any user IDs or certifications whatsoever.¶

Such a keystore MUST be capable of cryptographic validation. It accepts primary key packets, cryptographically-valid direct-key and revocation signatures from a primary key over itself, subkeys and their cryptographically-validated binding signatures (and cross-sigs, where necessary).¶

A client of a refresh-only keystore cannot possibly use the keystore for certificate lookup, because there are no user IDs to match. And it is not particularly useful for certificate discovery, because the returned certificate would have no identity information. However, such a keystore can be used for certificate refresh, as it's possible to ship revocations, new subkeys, updates to subkey expiration, subkey revocations, and updates of direct key signature-based certificate expiration or other OpenPGP properties.¶

Note that many popular OpenPGP implementations do not implement direct primary key expiration mechanisms, relying instead on user ID expirations. These user ID expiration dates or other metadata associated with a self-certification will not be distributed by an refresh-only keystore.¶

Certificates shipped by an refresh-only keystore are technically invalid [RFC4880] "transferable public keys," because they lack a user ID packet. However many OpenPGP implementations will accept such a certificate if they already know of a user ID for the certificate, because the composite certificate resulting from a merge will be a standards-compliant transferable public key.¶

8.2. First-party-only Keystores

Slightly more permissive than the refresh-only keystore described in Section 8.1 is a sovereignty-respecting keystore that also permits user IDs and their self-sigs.¶

A first-party-only keystore only accepts and distributes cryptographically-valid first-party certifications. Given a primary key that the keystore understands, it will only attach user IDs that have a valid self-sig, and will only accept and re-distribute subkeys that are also cryptographically valid (including requiring cross-sigs for signing-capable subkeys as recommended in [RFC4880]).¶

This effectively avoids certificate flooding attacks, because the only party who can make a certificate overly large is the holder of the secret corresponding to the primary key itself.¶

Note that a first-party-only keystore is still problematic for those people who rely on the keystore for retrieval of third-party certifications. Section 8.4 attempts to address this lack.¶

8.3. Mutual Certifications

Another approach is to permit re-distribution of certifications only when they are mutually corroborated. That is, if key X has a self-signed UID A, and key Y has a self-signed UID B, then the keystore MAY store a certification from Y over (X,A) or from X over (Y,B), but it will not redistribute either certification until it sees both of them.¶

Attention to detail is needed when deploying this strategy over time. When one certification of a mutually-corroborative pair expires, is revoked or superseded, or otherwise becomes invalid, the other certification in the pair also needs to be marked as not for redistribution.¶

8.4. First-party-attested Third-party Certifications

We can augment a first-party-only sovereignty-respecting keystore to allow it to distribute third-party certifications as long as the first-party has signed off on the specific third-party certification.¶

This can be done by placing an Attested Certifications subpacket in the most recent self-sig of the certificate (see [Attested-Certifications]).¶

- A. Primary key
- B. User ID
- C. Self-sig (from A, binding A to B)
- D. Subkey
- E. Subkey binding signature (from A, binds D to A)
- F. Certification revocation signature
     (from A over some other key+userID, targets other
      certification)

9.1. Use Constrained Keystores for Lookup

When performing certificate lookup, an abuse-resistant client SHOULD prefer to query abuse-resistant keystores to avoid the risks described in Section 13.1. In particular, keystores that defend against User ID Flooding are significantly more reliable for certificate lookup.¶

9.2. Normalize Addresses and User IDs for Lookup

When performing lookup by e-mail address, an abuse-resistant client SHOULD consider canonicalizing the e-mail address before searching (see Section 12.3).¶

When searching by full User ID, unless there is a strong reason to believe that a specific non-normalized form is preferable, an abuse-resistant client SHOULD normalize the entire user ID into [UNICODE-NORMALIZATION] Form C (NFC) before performing certificate lookup.¶

9.3. Avoid Fuzzy Lookups

Certificate lookup by arbitrary substring matching, or regular expression is prone to abuse. An abuse-resistant client SHOULD prefer exact-uid or exact-email match lookups where possible.¶

In particular, an abuse-resistant client should avoid trying to offer reliable functionality that performs these sort of fuzzy lookups, and SHOULD warn the user about risks of abuse if the user triggers a codepath that unavoidably performs such a fuzzy lookup.¶

9.4. Prefer Full Fingerprint for Discovery and Refresh

Key IDs are inherently weaker and easier to spoof or collide than full fingerprints. Where possible, an abuse-resistant keystore client SHOULD use the full fingerprint when interacting with the keystore.¶

9.5. Use Caution with Keystore-provided Validation

When an abuse-resistant client relies on a keystore for certificate validation, many things can go subtly wrong if the client fails to closely track the specific semantics of the keystore's validation claims.¶

For example, a certificate published by WKD ([I-D.koch-openpgp-webkey-service]) at https://openpgpkey.example.org/.well-known/openpgpkey/hu/iy9q119eutrkn8s1mk4r39qejnbu3n5q?l=joe.doe offers a validation claim only for the e-mail address joe.doe@example.org. If the certificate retrieved at that address contains other user IDs, or if the user ID containing that e-mail address contains an [RFC5322] display-name, none of that information should be considered "validated" by the fact that the certificate was retrieved via certificate lookup by WKD.¶

When certificate validation is represented more generally by a keystore via certificate retrieval (e.g. from an e-mail validating keyserver that has no distinct certificate validation interface), the thing validated is the certificate received from the keystore, and not the result of the merge into any local copy of the certificate already possessed by the client.¶

Consider also timing and duration of these assertions of validity, which represent a subtle tradeoff between privacy and risk as described in Section 14.4.¶

10.1. Canonicalized E-Mail Addresses

E-mail addresses can be written in many different ways. An abuse-sensitive implementation considering attaching a user ID containing an e-mail address on a certificate SHOULD ensure that the e-mail address is structured as simply as possible. See Section 12.3 for details about e-mail address canonicalization.¶

For example, if the e-mail domain considers the local part to be case-insensitive (as most e-mail domains do today), if a proposed user ID contains the addr-spec: Alice@EXAMPLE.org, the implementation SHOULD warn the user and, if possible, propose replacing the addr-spec part of the user ID with alice@example.org.¶

10.2. Normalized User IDs

User IDs are arbitrary UTF-8 strings, but UTF-8 offers several ways to represent the same string. An abuse-sensitive implementation considering attaching a user ID to a certificate SHOULD normalize the string using [UNICODE-NORMALIZATION] Form C (NFC) before creating the self-sig.¶

At the same time, the implementation MAY also warn the user if the "compatibility" normalized form (NFKC) differs from the candidate user ID and, if appropriate, offer to convert the user ID to compatibility normalized form at the user's discretion.¶

10.3. Avoid Large User Attributes

An abuse-sensitive implementation SHOULD warn the user when attaching a user attribute larger than 8383 octets, and SHOULD refuse to attach user attributes entirely larger than 65536 octets. (See Section 4.1)¶

10.4. Provide Cross-Sigs

[RFC4880] requires cross-sigs for all signing-capable subkeys, but is agnostic about the use of cross-sigs for subkeys of other capabilities.¶

An abuse-sensitive implementation that wants a certificate to be discoverable by subkey SHOULD provide cross-sigs for any subkey capable of making a cross-sig.¶

10.5. Provide Issuer Fingerprint Subpackets

Issuer subpackets contain only 64-bit key IDs. Issuer Fingerprint subpackets contain an unambiguous designator of the issuing key, avoiding the ambiguities described in Section 11.2. Abuse-sensitive implementations SHOULD provide Issuer Fingerprint subpackets.¶

10.6. Put Cross-Sigs and Issuer Fingerprint in Hashed Subpackets

Unhashed subpackets may be stripped or mangled. Placing cross-sigs and issuer fingerprint subpackets in the hashed subpackets will ensure that they are propagated by any cryptographically-validating keystore, even if that keystore fails to observe the exceptions in Section 4.4.¶

10.7. Submit Certificates to Restricted, Lookup-Capable Keystores

If an abuse-sensitive implementation wants other peers to be able to to retrieve the managed certificate by certificate lookup (that is, by searching based on user ID or e-mail address), it needs to be aware that submission to an unrestricted keystore is not reliable (see Section 13.1 for more details).¶

Consequently, such an implementation SHOULD submit the managed certificate to restricted, lookup-capable keystores where possible, as those keystores are more likely to be able to offer reliable lookup.¶

11.1. Designated Revoker

A first-party-only keystore as described in Section 8.2 might decline to distribute revocations made by the designated revoker. This is a risk to certificate-holder who depend on this mechanism, because an important revocation might be missed by clients depending on the keystore.¶

FIXME: adjust this document to point out where revocations from a designated revoker SHOULD be propagated, maybe even in first-party-only keystores.¶

11.2. Key IDs vs. Fingerprints in Certificate Discovery

During signature verification, a user performing certificate discovery against a keystore SHOULD prefer to use the full fingerprint as an index, rather than the 64-bit key ID. Using a 64-bit key ID is more likely to run into collision attacks; and if the retrieved certificate has a matching key ID but the signature cannot be validated with it, the client is in an ambiguous state -- did it retrieve the wrong certificate, or is the signature incorrect? Using the fingerprint resolves the ambiguity: the signature is incorrect, because the a fingerprint match is overwhelmingly stronger than a key ID match.¶

Unfortunately, many OpenPGP implementations distribute signatures with only an Issuer subpacket, so a client attempting to find such a certificate MAY perform certificate discovery based on only the key ID.¶

A keystore that offers certificate discovery MAY choose to require full fingerprint, but such a keystore will not be useful for a client attempting to verify a bare signature from an unknown party if that signature only has an Issuer subpacket (and no Issuer Fingerprint subpacket).¶

11.3. In-band Certificates

There are contexts where it is expected and acceptable that the signature appears without its certificate: for example, if the set of valid signers is already known (as in some OpenPGP-signed operating system updates), shipping the certificate alongside the signature would be pointless bloat.¶

However, OpenPGP signatures are often found in contexts where the certificate is not yet known by the verifier. For example, many OpenPGP-signed e-mails are not accompanied by the signing certificate.¶

In another example, the use of authentication-capable OpenPGP keys in standard SSH connections do not contain the full OpenPGP certificates, which means that the SSH clients and servers need to resort to out-of-band processes if evaluation of the OpenPGP certificates is necessary.¶

The certificate discovery interface offered by keystores is an attempt to accommodate these situations. But in the event that a keystore is unavailable, does not know the certificate, or suffers from a flooding attack, signature validation may fail unnecessarily. In an encrypted e-mail context specifically, such a failure may also limit the client's ability to reply with an encrypted e-mail.¶

Certificate discovery also presents a potential privacy concern for the signature verifier, as noted in Section 14.5.¶

These problematic situations can be mitigated by shipping the certificate in-band, alongside the signature. Signers SHOULD adopt this practice where possible to reduce the dependence of the verifier on the keystores for certificate discovery. [AUTOCRYPT] is an example of e-mail recommendations that include in-band certificates.¶

11.4. Certification-capable Subkeys

Much of this discussion assumes that primary keys are the only certification-capable keys in the OpenPGP ecosystem. Some proposals have been put forward that assume that subkeys can be marked as certification-capable. If subkeys are certification-capable, then much of the reasoning in this draft becomes much more complex, as subkeys themselves can be revoked by their primary key without invalidating the key material itself. That is, a subkey can be both valid (in one context) and invalid (in another context) at the same time. So questions about what data can be dropped (e.g. in Section 7) are much fuzzier, and the underlying assumptions may need to be reviewed.¶

If some OpenPGP implementations accept certification-capable subkeys, but an abuse-resistant keystore does not accept certifications from subkeys in general, then interactions between that keystore and those implementations may be surprising.¶

11.5. Assessing Certificates in the Past

Online protocols like TLS perform signature and certificate evaluation based entirely on the present time. If a certificate that signs a TLS handshake message is invalid now, it doesn't matter whether it was valid a week ago, because the present TLS session is the context of the evaluation.¶

But OpenPGP signatures are often evaluated at some temporal remove from when the signature was made. For example, software packages are signed at release time, but those signatures are validated at download time. A verifier that does not already know the certificate that made the signature will need to perform certificate discovery against some set of keystores to find a certificate with which to check the signature.¶

Further complicating matters, the composable nature of an OpenPGP certificate means that the certificate associated with any particular signing key (primary key or subkey) can transform over time. So when evaluating a signature that appears to have been made by a given certificate, it may be better to try to evaluate the certificate at the time the signature was made, rather than the present time.¶

11.6. Global Append-only Ledgers ("Blockchain")

The append-only aspect of some OpenPGP keystores encourages a user of the keystore to rely on that keystore as a faithful reporter of history, and one that will not misrepresent or hide the history that they know about. An unfaithful "append-only" keystore could abuse the trust in a number of ways, including withholding revocation certificates, offering different sets of certificates to different clients doing certificate lookup, and so on.¶

However, the most widely used append-only OpenPGP keystore, the [SKS] keyserver pool, offers no cryptographically verifiable guarantees that it will actually remain append-only. Users of the pool have traditionally relied on its distributed nature, and the presumption that coordination across a wide range of administrators would make it difficult for the pool to reliably lie or omit data. However, the endpoint most commonly used by clients to access the network is hkps://hkps.pool.sks-keyservers.net, the default for [GnuPG]. That endpoint is increasingly consolidated, and currently consists of hosts operated by only two distinct administrators, increasing the risk of potential misuse.¶

Offering cryptographic assurances that a keystore could remain append-only is an appealing prospect to defend against these kinds of attack. Many popular schemes for providing such assurances are known as "blockchain" technologies, or global append-only ledgers.¶

With X.509 certificates, we have a semi-functional Certificate Transparency ([RFC6962], or "CT") ecosystem that is intended to document and preserve evidence of (mis)issuance by well-known certificate authorities (CAs), which implements a type of global append-only ledger. While the CT infrastructure remains vulnerable to certain combinations of colluding actors, it has helped to identify and sanction some failing CAs.¶

Like other global append-only ledgers, CT itself is primarily a detection mechanism, and has no enforcement regime. If a widely-used CA were identified by certificate transparency to be untrustworthy, the rest of the ecosystem still needs to figure out how to impose sanctions or apply a remedy, which may or may not be possible.¶

CT also has privacy implications -- the certificates published in the CT logs are visible to everyone, for the lifetime of the log.¶

For spam abatement, CT logs decline all X.509 certificates except those issued by certain CAs (those in popular browser "root stores"). This is an example of the strategy outlined in Section 4.9).¶

Additional projects that provide some aspects of global append-only ledgers that try to address some of the concerns described here include [KEY-TRANSPARENCY] and [CONIKS], though they are not specific to OpenPGP. Both of these systems are dependent on servers operated by identity providers, however. And both offer the ability to detect a misbehaving identity provider, but no specific enforcement or recovery strategies against such an actor.¶

It's conceivable that a keystore could piggyback on the CT logs or other blockchain/ledger mechanisms like [BITCOIN] to store irrevocable pieces of data (such as revocation certificates). Further work is needed to describe how to do this in an effective and performant way.¶

11.7. Certificate Lookup for Identity Monitoring

While certificate lookup is classically used to find a key to encrypt an outbound message to, another use case for certificate lookup is for the party in control of a particular identity to determine whether anyone else is claiming that identity.¶

That is, a client in control of the secret key material associated with a particular certificate with user ID X might search a keystore for all certificates matching X in order to find out whether any other certificates claim it.¶

This is an important safeguard as part of the ledger-based detection mechanisms described in Section 11.6, but may also be useful for keystores in general.¶

However, identity monitoring against a keystore that does not defend against user ID flooding (Section 2.2) is expensive and potentially of limited value. In particular, a malicious actor with a certificate which duplicates a given User ID could flood the keystore with similar certificates, hiding whichever one is in malicious use.¶

Since such a keystore is not considered authoritative by any reasonable client for the user ID in question, this attack forces the identity-monitoring defender to spend arbitrary resources fetching and evaluating each certificate in the flood, without knowing which certificate other clients might be evaluating.¶

12.1. Revocations

It's useful to classify OpenPGP revocations of key material into two categories: "soft" and "hard".¶

If the "Reason for Revocation" of an OpenPGP key is either "Key is superseded" or "Key is retired and no longer used", it is a "soft" revocation.¶

An implementation that interprets a "soft" revocation will typically not invalidate signatures made by the associated key with a creation date that predates the date of the soft revocation. A "soft" revocation in some ways behaves like a non-overridable expiration date.¶

All other revocations of OpenPGP keys (with any other Reason for Revocation, or with no Reason for Revocation at all) should be considered "hard".¶

The presence of a "hard" revocation of an OpenPGP key indicates that the user should reject all signatures and certifications made by that key, regardless of the creation date of the signature.¶

Note that some OpenPGP implementations do not distinguish between these two categories.¶

A defensive OpenPGP implementation that does not distinguish between these two categories SHOULD treat all revocations as "hard".¶

An implementation aware of a "soft" revocation or of key or certificate expiry at time T SHOULD accept and process a "hard" revocation even if it appears to have been issued at a time later than T.¶

12.2. User ID Conventions

[RFC4880] requires a user ID to be a UTF-8 string, but does not constrain it beyond that. In practice, a handful of conventions predominate in how User IDs are formed.¶

The most widespread convention is a name-addr as defined in [RFC5322]. For example:¶

Alice Jones <alice@example.org>

But a growing number of OpenPGP certificates contain user IDs that are instead a raw [RFC5322] addr-spec, omitting the display-name and the angle brackets entirely, like so:¶

alice@example.org

Some certificates have user IDs that are simply normal human names (perhaps display-name in [RFC5322] jargon, though not necessarily conforming to a specific ABNF). For example:¶

Alice Jones

Still other certificates identify a particular network service by scheme and hostname. For example, the administrator of an ssh host participating in the [MONKEYSPHERE] might choose a user ID for the OpenPGP representing the host like so:¶

ssh://foo.example.net

12.3. E-mail Address Canonicalization

When an OpenPGP user IDs includes an addr-spec, there still may be multiple ways of representing the addr-spec that refer to the same underlying mailbox. Having a truly canonical form of an addr-spec is probably impossible because of legacy deployments of mailservers that do odd things with the local part, but e-mail addresses used in an abuse-resistant ecosystem SHOULD be constrained enough to admit to some sensible form of canonicalization.¶

13.1. Tension Between Unrestricted Uploads and Certificate Lookup

Note that there is an inherent tension between accepting arbitrary certificate uploads and permitting effective certificate lookup. If a keystore accepts arbitrary certificate uploads for redistribution, it appears to be vulnerable to user ID flooding (Section 2.2), which makes it difficult or impossible to rely on for certificate lookup.¶

In the broader ecosystem, it may be necessary to use gated/controlled certificate lookup mechanisms. For example, both [I-D.koch-openpgp-webkey-service] and [RFC7929] enable the administrator of a DNS domain to distribute certificates associated with e-mail addresses within that domain, while excluding other parties. As a rather different example, [I-D.mccain-keylist] offers certificate lookup on the basis of interest -- a client interested in an organization can use that mechanism to learn what certificates that organization thinks are worth knowing about, associated with a range of identities regardless of the particular DNS domain. Note that [I-D.mccain-keylist] does not provide the certificates directly, but instead expects the client to be able to retrieve them by primary key fingerprint through some other keystore capable of (and responsible for) certificate refresh.¶

14.1. Publishing Identity Information

Public OpenPGP keystores often distribute names or e-mail addresses of people. Some people do not want their names or e-mail addresses distributed in a public keystore, or may change their minds about it at some point. Append-only keystores are particularly problematic in that regard. The mitigation in Section 7.4 can help such users strip their details from keys that they control. However, if an OpenPGP certificate with their details is uploaded to a keystore, but is not under their control, it's unclear what mechanisms can be used to remove the certificate that couldn't also be exploited to take down an otherwise valid certificate.¶

Some jurisdictions may present additional legal risk for keystore operators that distribute names or e-mail addresses of non-consenting parties.¶

Refresh-only keystores (Section 8.1) and user ID redacting keystores (Section 5.1) may reduce this particular privacy concern because they distribute no user IDs at all.¶

14.2. Social Graph

Third-party certifications effectively map out some sort of social graph. A certification asserts a statement of belief by the issuer that the real-world party identified by the user ID is in control of the subject cryptographic key material. But those connections may be potentially sensitive, and some people may not want these maps built.¶

A first-party-only keyserver (Section 8.2) avoids this privacy concern because it distributes no third-party privacy concern.¶

First-party attested third-party certifications described in Section 8.4 are even more relevant edges in the social graph, because their bidirectional nature suggests that both parties are aware of each other, and see some value in mutual association.¶

14.3. Tracking Clients by Queries

Even without third-party certifications, the acts of certificate lookup, certificate discovery, and certificate refresh represent a potential privacy risk, because the keystore queried gets to learn which user IDs (in the case of lookup) or which certificates (in the case of refresh or discovery) the client is interested in. In the case of certificate refresh, if a client attempts to refresh all of its known certificates from the same keystore, that set is likely to be a unique set, and therefore identifies the client. A keystore that monitors the set of queries it receives might be able to profile or track those clients who use it repeatedly.¶

A privacy-aware client which wants to to avoid such a tracking attack MAY try to perform certificate refresh from multiple different keystores. To hide network location, a client making a network query to a keystore SHOULD use an anonymity network like [TOR]. Tools like [PARCIMONIE] are designed to facilitate this type of certificate refresh. Such a client SHOULD also decline to use protocol features that permit linkability across interactions with the same keystore, such as TLS session resumption, HTTP cookies, and so on.¶

Keystores which permit public access and want to protect the privacy of their clients SHOULD NOT reject access from clients using [TOR] or comparable anonymity networks. Additionally, they SHOULD minimize access logs they retain.¶

Alternately, some keystores may distribute their entire contents to any interested client, in what can be seen as the most trivial form of private information retrieval. [DEBIAN-KEYRING] is one such example; its contents are distributed as an operating system package. Clients can interrogate their local copy of such a keystore without exposing their queries to a third-party.¶

14.4. "Live" Certificate Validation Leaks Client Activity

If a client relies on a keystore's certificate validation interface, or on the presence of a certificate in a keystore as a part of its validation calculations, it's unclear how long the assertion from the keystore is or should be considered to hold. One seemingly simple approach is to simply query the keystore's validation interface each time that the client needs to validate the certificate.¶

This "live" validation approach poses a quandary to the client in the event that the keystore is unavailable. How should in interpret the "unknown" result? In addition, live validation reveals the client's activity to the keystore with fine precision.¶

A privacy-aware client that depends on keystores for certificate validation SHOULD NOT perform "live" certificate validation on each use it makes of the certificate. Rather, it SHOULD cache the validation information for some period of time and make use of the cached copy where possible. If such a client does a regular certificate refresh from the same keystore, it SHOULD also pre-emptively query the keystore for certificate validation at the same time.¶

Choosing the appropriate time intervals for this kind of caching has implications for the windows of risk for the client that might use a revoked certificate. Defining an appropriate schedule to make this tradeoff is beyond the scope of this document.¶

14.5. Certificate Discovery Leaks Client Activity

The act of doing certificate discovery on unknown signatures offers a colluding keystore and remote peer a chance to track a client's consumption of a given signature.¶

An attacker with access to keystore logs could sign a message with a unique key, and then watch the keystore activity to determine when a client consumes the signature. This is potentially a tracking or "phone-home" situation.¶

A signer that has no interest in this particular form of tracking can mitigate this concern by shipping their certificate in-band, alongside the signature, as recommended in Section 11.3.¶

A privacy-aware client MAY insist on in-band certificates by declining to use any certificate discovery interface at all, and treat a bare signature by an unknown certificate as an invalid signature.¶

14.6. Certificate Refresh Leaks Client Activity

The act of doing certificate refresh itself reveals some information that the client is interested in a given certificate and how it may have changed since the last time the client refreshed it, or since it was first received by the client.¶

This is essentially the same privacy problem presented by OCSP [RFC6960] in the X.509 world. In the online world of TLS, this privacy leak is mitigated by the CertificateStatus TLS handshake extension ([RFC4366]), a.k.a. "OCSP stapling". There is no comparable solution for the store-and-forward or non-online scenarios where OpenPGP is often found.¶

Privacy-aware clients MAY prefer to access refresh interfaces from anonymity-preserving networks like [TOR] to obscure where they are on the network, but if the certificate being refreshed is known to be used only by a single client that may not help.¶

Privacy-aware clients MAY prefer to stage their certificate refreshes over time, but longer delays imply greater windows of vulnerability for use of an already-revoked certificate. This strategy also does not help when a previously-unknown certificate is encountered in-band (see Section 11.3), and the OpenPGP client wants to evaluate it for use in the immediate context.¶

14.7. Distinct Keystore Interfaces Leak Client Context and Intent

The distinct keystore interfaces documented in Section 3 offer subtly different semantics, and are used by a reasonable keystore client at different times. A keystore that offers distinct discovery and refresh interfaces may infer that a client visiting the refresh interface already knows about the certificate in question, or that a client visiting the discovery interface is in the process of verifying a signature from a certificate it has not seen before.¶

HKP itself ([I-D.shaw-openpgp-hkp]) conflates these two interfaces -- the same HKP query is be used to perform both discovery and refresh (though implementations like [SKS] are not at all abuse-resistant for either use), which may obscure the context and intent of the client from the keystore somewhat.¶

A privacy-aware client that can afford the additional bandwidth and complexity MAY use the keystore's discovery interface for both refresh and discovery, since the discovery interface is a proper superset of the refresh interface.¶

14.8. Cleartext Queries

If access to the keystore happens over observable channels (e.g., cleartext connections over the Internet), then a passive network monitor could perform the same type profiling or tracking attack against clients of the keystore described in Section 14.3. Keystores which offer network access SHOULD provide encrypted transport.¶

14.9. Traffic Analysis

Even if a keystore offers encrypted transport, the size of queries and responses may provide effective identification of the specific certificates fetched during lookup, discovery, or refresh, leaving open the types of tracking attacks described in Section 14.3. Clients of keystores SHOULD pad their queries to increase the size of the anonymity set. And keystores SHOULD pad their responses.¶

The appropriate size of padding to effectively anonymize traffic to and from keystores is likely to be mechanism- and cohort-specific. For example, padding for keystores accessed via the DNS ([RFC7929] may use different padding strategies that padding for keystores accessed over WKD ([I-D.koch-openpgp-webkey-service]), which may in turn be different from keystores accessed over HKPS ([I-D.shaw-openpgp-hkp]). A keystore which only accepts user IDs within a specific domain (e.g., Section 4.3) or which uses custom process (Section 6.4) for verification might have different padding criteria than a keystore that serves the general public.¶

Specific padding policies or mechanisms are out of scope for this document.¶