Note: This mechanism is no longer supported, due to concerns raised in #136. Readers should refer to HIP-5 instead.

Note: This comes out of thinking about #79, and is partially implemented in #89.

Motivation

Summary of the key spam problem

Once a key grows beyond a reasonable size (1MB is probably a sensible limit), its entire contents become suspect. We don't know if the entire key was maliciously created, or if parts of it are legitimate with signature spam added to an innocent user's key. The only way to overcome this is by authenticating the content in such keys.

PGP lacks objective mutual authentication. Keyservers are not intended to guarantee or certify the authenticity of a key for any particular purpose -- instead, they merely relay key content. The one job a keyserver has to do, is to make sure that new signatures are available to all who might want to communicate with the key's owner, or verify the authenticity of that key's signatures.

Ultimately it should be the responsibility of the key owner to decide which key signatures they want to trust and advertise in their WoT. Anyone can create keys purporting to be anyone, and upload their keys to a keyserver. Because of this rootless nature, there is no objective means of authenticating keys in the global pool of OpenPGP keyservers. Troublemakers have exploited this property and attacked the global keyserver network in the following ways:

• Submitting keys with a large number of small attestations, which appear to have been made by automatically generated unique signing keys. Some of these are quite weak (making it computationally easier to generate them) but some use modern fast secure algorithms like EdDSA.
• Adding a large number of these small attestations to keys that appear to be legitimate OpenPGP users.
• Adding large sized signatures to generated or existing keys.

This is effectively a denial-of-service (DoS) attack on the global keyserver pool and the users served by it. Keys with a sufficiently large amount of attestations can waste resources on a keyserver, cause it to run out of memory and crash, and generally increase the operating and maintenance costs.

Limiting key size

The DoS problem can be mitigated for the keyserver operators by limiting the amount of content allowed per key, as was done in #85. This prevents keys from wasting server resources, and significantly reduces the amount of memory required to operate a Hockeypuck keyserver.

However, this still leaves WoT users still exposed.

There still remains a problem where an attacker only needs to add enough garbage signatures to a key to get any further updates rejected by keyservers, by incrementally inflating over the keyserver's size limit. At that point, no further attestations on that key will be accepted. This could be used to block communications with the target key, or compromise security, since revocations could be blocked as well.

GDPR and the Right to be Forgotten

GDPR gives EU citizens the "right to be forgotten", which apparently means an individual can request that an entity remove all digital records they have of said person. Whether this is a privacy win or a new form of censorship is beside the point, keyserver operators in some jurisdictions are subject to it, and it's a commonly requested feature.

Using an authenticated request, users could perform this self-deletion themselves.

Putting the key owner back in control

This can all be mitigated by authenticating requests to the owner -- the holder of the private key. This proposal introduces a backward-compatible extension to the HTTP Keyserver Protocol (HKP) that would allow key owners to determine the content of their public key material on the keyservers which implement it.

Examples of interactions

Authenticated key replacement

The owner of a key may set the signature content they wish to distribute on a keyserver, by adding a detached signature with a replace directive.

This tells the keyserver to completely replace all the content for the signed, uploaded key. All other keys uploaded will be merged with the keyserver's existing public key signatures.

It should be safe to always sign and set the replace directive when uploading keys. It has no effect for keys that did not make the signature. The signature and replace directive should be ignored by older keyservers.

Example

#!/bin/bash

set -eu

if [[ -z "${1:-}"  || -z "${2:-}" ]]; then
        >&2 echo "Usage: $0 <key id> <keyserver URL>"
        exit 1
fi

keytext=$(mktemp)
trap "rm -f $keytext" EXIT

keysig=$(mktemp)
trap "rm -f $keytext $keysig" EXIT

gpg --export -a $1 >$keytext
gpg --detach-sign -a <$keytext >$keysig

curl -i -v \
        --data-urlencode keytext@$keytext \
        --data-urlencode keysig@$keysig \
        --data-urlencode replace=true \
        $2/pks/add

The keytext is the preferred (armored) key material. The keysig is a detached gpg signature over the keytext, made by itself.

The right to be forgotten

While the global pool of keyservers operates across many jurisdictions, keyserver operators subject to GDPR may find authenticated key management to be useful to allow users to exercise their right to be forgotten.

User makes a signed HTTP request in a similar format to the replace procedure above, but using the /pks/delete endpoint:

POST /pks/delete keytext=...&keysig=...

The keytext is the (armored) key to be deleted with endpoint prefix:

op="/pks/delete\n"
echo -ne "$op" >$keytext
gpg --export -a $1 >>$keytext

(hockeypuck < 2.2 didn't use any prefix, i.e. op=""). The keysig is a detached gpg signature over the keytext, made by itself.

A POST method is used rather than DELETE for compatibility. While DELETE technically allows for a request body, some HTTP middleware such as reverse-proxies may not.

When verified, the keyserver deletes the signing key fingerprint from its database.

Distribution among keyservers (Not yet implemented)

When a peering keyserver receives an authenticated key replacement request, it could relay the authenticated key replacement request to its peers via HTTP. This will reset the key contents across the pool.

For example, keyserver host A is peering with recon hosts B, C, and D.

Alice makes an authenticated replace request to A:

POST /pks/add keytext=...&keysig=...&replace=true

A then relays the same HTTP request to B, C, and D with a peers directive, a set enumerating the source and targets of the relayed request.

POST /pks/add keytext=...&keysig=...&replace=true&peers=A,B,C,D

B, C, and D may further relay the request to their peers. They'll skip themselves and the other peers already in the peers set. So B might relay to E, F, G:

POST /pks/add keytext=...&keysig=...&replace=true&peers=A,B,C,D,E,F,G

A keyserver may decide to ignore these relay requests past a certain length, requests from unknown peers, etc.

Out of scope

Consistency among keyservers

The ability for key owners to manage their keys across keyservers depends on the cooperation of the individual keyserver operators to deploy these features. Some may not cooperate. However, over time, the ones that do, will likely better serve their users by mitigating the issues outlined above.

Compliance with GDPR

While authenticated key management may be useful to a keyserver operator needing to comply with GDPR, corporate policy or other regulations, there is of course no guarantee of this (or of fitness for any other purpose) under the terms of the AGPL.

Guaranteed delivery of relayed requests

Relaying replace or delete requests may be made by keyservers with best effort. There is no guaranteed delivery, though a keyserver might implement a backoff retry strategy that yields good empirical results.

OpenPGP signature certification features

There are some features being proposed that would allow third-party signatures to be signed by the key owner. The keyserver could use these signatures to possibly add weight or precedence to signatures. Ideally, all signatures would become certified by default (and automatically migrated to certified), and then keyservers could drop uncertified third-party signatures.

Hockeypuck could certainly add support for this, if the go.crypto implementation of OpenPGP, or ProtonMail's fork of it were to support it. It would also need a critical mass of adoption to realize benefits.

Security considerations

DoS on signature verifications

An attacker could potentially flood a keyserver with generated authenticated requests, just to consume CPU resources. Some public key algorithms may require more cycles to verify signatures than others. This is just a hypothetical risk; it hasn't been quantified or benchmarked.

Fortunately, these type of requests should be low frequency per key/user IP address, and are not time-critical, so they may be rate-limited. Keyserver peers may be partitioned into a separate rate limited group to distinguish between misbehaving users and server peers.

Replaying authenticated requests

Keyservers could potentially revert key material to a prior version by replaying old authenticated replace requests -- blocking a revocation, for example. They could also delete a key that was re-uploaded at a later time.

The author does not consider this to be a valid threat because reverting to an old backup would have the same effect. Operators can do what they want and OpenPGP keyservers do not make strong consistency guarantees -- for that you probably want a blockchain.

Compatibility

Adding new endpoints and optional request parameters does not conflict with existing keyservers. New keyservers can use it to authenticate key replacement. Clients can regard a 404 response as a legacy keyserver that does not support authenticated key management.

Notes

Futility of incomplete implementation

Deletion of key material does not prevent it from being re-added in the future. This will happen very quickly through keyserver sync. Without global support of authenticated distribution, or the automatic addition of deleted keys to the blacklist, deleted keys will simply reappear. [ABG]

Empirical observations of spam attacks

Tor project signing key has been targeted by spammers: http://pool.sks-keyservers.net:11371/pks/lookup?op=vindex&search=0xa3c4f0f979caa22cdba8f512ee8cbc9e886ddd89.

During a backload, lots of recurring packets of this length: WARN[131825] dropped packet length=300006 max=8192.

This key is > 1MB, but signatures appear to be legit when spot checking. No obvious vandalism. http://pool.sks-keyservers.net:11371/pks/lookup?op=vindex&search=0x7420df86bce15a458dce997639278da8109e6244