[openpgp] Re: PQC requires urgent semantic cleanup

On 01/12/2025 15:37, Daniel Huigens wrote:
> Hi Andrew & all (again),

:wave:

> There are a bunch of possible solutions to this:
> 1. In the case of message signatures, as the verifier, record the
>     verification result (perhaps using a persistent symmetric key to
>     store the verification result) and refer back to it later rather than
>     re-verifying old signatures.

This pushes a lot of ongoing responsibility onto the client/user, and 
introduces novel failure modes - for example if you roll your symmetric 
secret key material and discover you can no longer validate historical 
messages. To be clear, I think such local signatures are a useful tool - 
but it is too much to recommend them as standard procedure for all 
users/implementations.

> 2. When updating certs from a keyserver, merge them rather than copying
>     them. This allows the keyserver to prune old signatures for new users
>     (who are unlikely to need them) without breaking old signatures for
>     old users that already had the cert (and thus are more likely to have
>     received old message signatures as well).

IMO "unlikely" is not strong enough for a keyserver to delete data. I 
would not be comfortable cleaning old selfsigs unless this was 
strengthened to "under no reasonable circumstances". General-purpose 
keyservers cannot afford to make weakly-supported assumptions about user 
requirements.

> 3. When cleaning up certificates, only remove old signatures when the
>     newest signature is older than some grace period (e.g. a week) to
>     make it less likely that you receive an old/delayed message right
>     after you've cleaned up the cert.

Sure, although this is at best a partial mitigation. ;-)

> 4. When distributing long-lived artifacts, re-sign them when updating
>     the certificate.

IMO this is an unreasonable expectation. For example, software 
distributors could easily sign hundreds if not thousands of release 
packages with the same key material.

> 5. When updating the certificate, keep the binding signature timestamps
>     the same (or bump them by one second to make it clear that the
>     signature is newer) rather than setting them to the current time
>     (this is a bit of a hack but it is e.g. what Sequoia does already,
>     as well as Proton CA, if that's a thing you care about :)).

This seems the most reasonable workaround given the existing ambiguity, 
but it places requirements on the generating implementation to keep 
track of existing signature dates etc., perhaps even at the application 
level. I see semi-regular complaints in the #sequoia IRC channel about 
it causing unexpected breakage, particularly when users have a 
multi-device or multi-implementation environment.

Further, the one-second increment is not completely free of side-effects 
even if implemented diligently. Imagine an automated system that 
generates a new key, creates selfsigs, and then immediately signs 
something else, say for example a certification over an intermediate CA 
cert. Incrementing the signing key's validity start date by even a few 
seconds could potentially invalidate the first signature(s) made using 
such an automated system. Yes, you could also recommend that these early 
signatures should be regenerated, but this imposes new obligations on 
the application, and adds new avenues for breakage.

> 6. Specify the semantics and update implementations to not require a
>     self-signature that predates the message signature being validated
>     (as you're proposing).
> 
> Now - I don't want to claim outright that any of options 1-5 are
> strictly better than option 6, but I do think option 6 is perhaps the
> most heavy-handed so we should consider the others first.

I believe that RECOMMENDing 5 would be a more heavy-handed approach than 
6. IMO option 6 is a conceptually elegant solution that results in much 
simpler reasoning and smaller artifacts. (That doesn't mean that the 
*process* of updating existing implementations will be elegant, of course!)

> Also because, in some of the relevant interop test suite results,
> such as [2], the majority of implementations actually agree with the
> current test expectations, _including GnuPG_, only excluding PGPy
> (which does not implement revocations at all :s) and since recently
> rPGP (which was updated to match the behavior suggested by
> draft-gallagher-openpgp-signatures).

Is it that far fetched to believe that the majority of implementations 
have got it wrong in this one case? With the exception of GnuPG and RNP, 
they are most likely doing it this way because the interop suite told 
them so, and it has been phenomenally successful in gamifying compliance 
- which is a good thing! Let's not overlook the many, many test cases 
where we all agree on the expectations.

But we have to reserve the right to revisit previous decisions and admit 
we got it wrong, as a matter of principle. If we wrap ourselves in the 
interop suite to avoid engaging with a potentially difficult decision, 
then we are giving it the same veto power we created it to liberate us from.

To be clear, I'm not saying that I'm obviously right, and everyone else 
is obviously wrong! But I'm saying we should be *very* careful before 
employing "we did what the interop suite told us, and now it's too late" 
as an argument.

> I don't think we want to throw out the concept of soft revocations
> (as both RFC9580 and draft-gallagher-openpgp-signatures require it),
> so then if we implement the proposed change in our implementations, we
> would start accepting the signature (unlike most other implementations),
> which sounds risky.

What signatures are we proposing should be accepted that would not 
currently be accepted? Ones genuinely made by the key in question after 
its embedded creation date, but before the creation date of the earliest 
available binding signature? Under what scenario could this arise, other 
than subsequent cert minimisation? What are the actual risks of 
accepting such a signature?

> It also means we need to convince 6 implementations (including GnuPG)
> to flip their behavior on that particular test, which sounds more
> difficult than asking 2 (rPGP and PGPy). Though, you could argue that
> GnuPG and RNP still need to implement soft revocations (properly),
> which then would lead to further changes being necessary, which evens
> the playing field a bit.
> 
> In any case, at least for our implementations, I would prefer not to
> implement this change and explore the other mentioned options first.

I do agree that it is unfair that people who implemented something in 
good faith would now be asked to undo their hard work, at their own 
expense. But I believe it is a net saving in the long run, and I'm 
personally very willing to get stuck in to help with any changes that 
may be required if we do agree that they are necessary. I will 
personally do the work to update go-crypto, for example.

> I agree, however, with the proposal to get rid of un-revocation /
> re-legitimization, partially because it's much more poorly supported
> (only Sequoia and PGPainless implement it properly; gopenpgp has a
> partial implementaiton).

Great! :-)

> For my opinion on expiring revocations; see my previous email :)

I recall you mentioning expiring revocations elsewhere, but it's not in 
your previous mail in this thread - that only explicitly mentions 
expiring primary key binding sigs.

For the record, I would be OK with leaving it that signature expirations 
SHOULD NOT be generated in binding sigs - I still think it would be 
cleaner if we also required that they be ignored, but I'm willing to 
settle for a partial win. ;-)

But I strongly believe signature expiration subpackets MUST be ignored 
in revocations, for the same reason that I believe subsequent 
"un-revocation" binding signatures MUST be ignored - if revocation is 
not permanent, it is not effective.

> And, it should be obvious but as always, thanks for pushing forward the
> clarification of the semantics of OpenPGP!

Thanks for the discussion! I agree that we should explore the 
alternatives thoroughly, but I hope that we can make progress - even if 
it's just the low hanging fruit first. ;-)

A

_______________________________________________
openpgp mailing list -- [email protected]
To unsubscribe send an email to [email protected]