See #384

Motivation

The current SKS protocol (v1.1.6) has many issues, including:

• It does not deal well with eventual inconsistency, e.g. when peers have different filter policies
• It cannot tell which peer has newer changes, so often makes a wasteful wrong-way sync
• It is prone to DoS attacks such as spam third-party signatures
• Non-semantic changes such as reordering and invalid packets can cause sync failure

Modifications to the SKS protocol have been discussed previously; this HIP is an attempt to lay out a concrete design based on an earlier comment on #137.

SKS v1.1.6 uses an MD5 hash of the entire public key bundle as the object identifier. This is efficient at detecting changes, but is overly sensitive. In particular, it detects non-semantic differences such as packet reordering and malformed packets, which can cause key update churn if peers do not treat such non-semantic information identically. It also cannot detect which end of a peering connection has new information, only that the objects differ - this makes the object recovery process inefficient because up to half of all recovery requests may be in the wrong direction and elicit no new information.

Design

The proposed SKS v2 protocol creates a semantically-aware object identifier by annotating a digest with unhashed metadata. This will eliminate many of the issues that arise from treating public keys as opaque blobs. v2 annotated hashes will not be generated from TPKs, but from individual self-signature packets. This is conceptually similar to the differential public key proposed previously, except that a TPK does not need to be deconstructed into separate DPKs at any point - annotated hashes are just identifiers, and a query for any of the v2 hashes associated with a given key should return the full TPK.

The v2 annotated hash will be 256 bits long, constructed as follows:

• signature version (2 bits)
• signature context (2 bits)
• least significant 124 bits of the MD5 digest of the signature packet
• least significant 128 bits of the key fingerprint

When taking the digest of the signature packet, the unhashed subpacket area must first be emptied and its length field set to zero.

Only the least significant two bits of the signature version are included. This ensures that all version information of interest to a keyserver with restricted version support is contained in the first bit-quantum, at the expense of only being able to represent four consecutive signature versions (e.g. 3,4,5,6).

The signature context is indicated as follows:

• 0: primary key
• 1: subkey
• 2: user ID
• 3: user attribute

This ensures that all packet type information of interest to a keyserver that does not support user IDs and/or user attributes is contained in the second bit-quantum.

V2 recon proceeds using the same algorithm as V1, with modifications:

• The finite field is 257 bits long

• A peer may improve recon performance by omitting branches of the ptree that are known to contain nothing of interest. (TBC: we may also need to define a response message to politely refuse such requests)

• A peer acting as a client may improve recovery performance by deduplicating queries that appear to belong to the same primary key. A peer acting as a server may improve recovery performance by deduplicating entries in its response.

Out of scope

This proposal is orthogonal to first-party attested third-party certifications (1pa3pc) as described in rfc4880bis and implemented in some client software. 1pa3pc packets would be treated as self-sigs under the above scheme, and are therefore compatible, however some of the advantages of 1pa3pc can be obtained with v2 recon alone, as third-party sigs will not readily propagate.

Updates to the merge strategy and treatment of revocations are treated in HIP 3 and HIP 4 respectively, however it is recommended that all three be taken together for maximum effect.

Security considerations

The use of a deprecated digest algorithm in recon is not a concern. If we require that all keyserver implementations that support SKS v2 also validate self-sigs, they should not expose a cryptographically invalid signature packet to their peers. This significantly constrains the preimage space available to an attacker, and a hash collision will only impact recon performance of the colliding keys, not their integrity.

Note that restricting the distribution of third-party sigs may also restrict the distribution of revocations of those sigs, which is undesirable. See HIP 4 for a solution.

Compatibility

Recon-as-client can detect the protocol version number of the server at connection time and support SKS v1.1.6 or v2 as appropriate for the peer server. Since bidirectional peering is the established norm, this will allow for backwards compatibility with peers that only support SKS v1.1.6, even if those peers will refuse to connect to a server that advertises v2.

Only changes that involve a new self-signature will be visible to v2 recon, however this encompasses the vast majority of meaningful use cases (expiry, revocation, updates to IDs and subkeys). The only significant use case that does not require a new self-sig is the attachment of a third-party sig - however this lack of support can be considered a feature as it will slow down the propagation of key poisoning attacks. Note that third-party sigs will still propagate, but only after a new self-sig is attached.

See HIP 3 and HIP 4 for further proposals to better handle third-party signatures. See also #246.