[openpgp] PQC requires urgent semantic cleanup

[Andrew Gallagher <[e-mail]>]

Hi, all.

Hockeypuck currently imposes a default packet size limit of 8kiB, and a 
total certificate size limit of 1MiB. These numbers are arbitrary, but 
they have been effective at limiting the impact of third-party signature 
flooding.

PQC keys call for an adjustment to these defaults, however SLH 
self-signatures are particularly problematic and IMO will also require 
an ecosystem-wide realignment of temporal evolution semantics.

The largest SLH key specified in draft-pqc is 256s, which has a 
signature size of 29,792B. Let us consider some typical scenarios:

1. A "basic" SLH certificate consisting of:
   * a primary key (+direct-sig)
   * one userID (+self-cert)
   * an encryption subkey (+sbind)

will have a minimum of three signatures, for ~90kiB.

2. A "code signing" SLH certificate consisting of:
   * a primary key (+direct-sig)
   * one userID (+self-cert)
   * an SLH-256s CA certification
   * one SLH-256s signing subkey (+sbind +back-sig)

will have a minimum of five signatures, for ~150kiB.

3. A "kitchen sink" v6 certificate consisting of:

   * a primary key (+direct-sig)
   * two userIDs (+2 self-certs), each with
     * two SLH third-party signatures
     * a 1pa3pc signature
   * encryption, ECC auth and SLH signing subkeys (+3 sbinds +1 backsig)

will have a minimum of ten signatures, for ~300kiB.

Now consider a common scenario where each self-signature is only valid 
for 2 years, and therefore requires regular renewal. After six years, 
the kitchen sink certificate will have accumulated a further 24 
additional self-signatures, for a grand total of ~1.02MiB. And that's 
before we consider revocations, key replacement, or any number of other 
likely scenarios.

I believe such certificate sizes are untenable. I am therefore proposing 
that keyservers SHOULD automatically strip historical self-signatures 
made by SLH primary keys, to keep the total size of the certificates 
manageable.

This however only works if the historical self-signatures are no longer 
required, and implementations are not consistent here.

Currently, the interop test suite requires that if a new self-signature 
is made after the expiry of the previous self-signature, the certificate 
is temporarily invalid between the expiry of one signature and the 
creation of the next, even if both signatures are available to the 
receiving implementation.[1] This also means that if the previous 
self-signature were not available to the receiving implementation, the 
certificate was never valid before the date of the newer self-signature, 
*even if the creation date of the primary key indicates otherwise*.

This flows from an assumption that a self-signature over a certificate 
component only validates that component after the signature creation 
date, meaning that the most recent self-signature cannot be relied on to 
validate a signing key for the purposes of verifying earlier data 
signatures. This assumption is deeply problematic for many reasons IMO:

1. It has no explicit basis in the RFCs
2. It contradicts historical behaviour (GnuPG "fails" this test)
3. It assumes that key creation dates are meaningless
4. It adds no reasonable utility
5. It causes subtle, tricky validity errors
6. It prevents cleanup of outdated signatures

The last issue is the most relevant to the above discussion, but IMO the 
other issues are already sufficient to motivate a change in the 
"expected" behaviour.

I have specified an alternative, simpler interpretation in section 9 of 
draft-signatures [2], which defines the start of the validity period as 
the creation date of the primary key (or the subkey, in the case of 
subkey binding sigs). This has several advantages:

1. It more closely matches the historical behaviour of GnuPG
2. It is significantly more reliable
3. It allows older self-signatures to be cleaned up

I strongly believe this interpretation should be encoded in the interop 
suite, and that implementations should update their temporal logic to 
match, *before* we start distributing SLH certs on the keyservers.

I also strongly believe we should reject the interop suite's invention 
of "un-revocation" and "expiring revocations", for the exact same 
reasons that we should reject "temporary invalidity". This clarification 
is also specified in draft-signatures.

Thanks,
A

[1] 
https://sequoia-pgp.gitlab.io/openpgp-interoperability-test-suite/results.html?impls=171157#Temporary_validity

[2] 
https://datatracker.ietf.org/doc/html/draft-gallagher-openpgp-signatures#name-time-evolution-of-signature