Re: [CFRG] Google's (current) Threat model for Post-Quantum Cryptography

[Daniel Kahn Gillmor <[e-mail]>]

On Sun 2024-03-17 20:49:53 +0000, Stephen Farrell wrote:
> It seems telling to me that that's the best case that comes to
> mind. I take it from that that discussion of technical mechanisms
> that attempt to provide non-repudiation ought be treated as noise,
> and we ought consider requirements related to code-signing as the
> ones most important to meet.

Agreed that code-signing seems like the simplest case to tackle, and is
worth prioritizing as there are pretty clear functional consequences
here.

> Doing "more" also has costs, e.g. related to the time available from
> busy analysts as I think someone has pointed out:-) If we do anything
> other than "check both" then we also run a real risk of ending up with
> a load of ways to do that. (Which would make the already horrible
> combinatorics related to composite sigs worse.)

Agreed: if we bake "check both" with reasonably matched primitives into
the lower level signature cryptographic APIs, and don't change the
application layer semantics, then we avoid extra costs associated with
fragmentation, combinatorics and lack of cryptanalytic resources.

Explicitly encoding a composite signature as a new signature algorthm
seems like the way to do that.

> The above ignores the costs related to the combinatorics of composite
> sigs, esp when it comes to key management.

Key management is a cost at the application layer only when the fact of
how the combinations work is exposed to the application layer.  if a
composite sig is just a "new signature type", then the application layer
just has to do what it always has to do when a new signature type is
introduced.

> A better phrasing might be that the verifier has to decide which
> sets of signatures are acceptable, noting that until now, being
> presented with multiple signatures was extremely uncommon.

If we're talking about code-signing, being presented with multiple
signatures is actually quite common.

Debian apt manifests ("Release files"), for example, tend to contain
multiple OpenPGP signatures:

$ curl 'http://deb.debian.org/debian/dists/bookworm/InRelease' | \
> sq toolbox packet dump 2>/dev/null | \
> grep -e ^Signature -e Pk.algo
Signature Packet, old CTB, 563 bytes
    Pk algo: RSA
Signature Packet, old CTB, 563 bytes
    Pk algo: RSA
Signature Packet, old CTB, 150 bytes
    Pk algo: EdDSA
$ 

When debian wants to introduce a new signing algorithm (or just a new
key), they sign the release with the old signing key for a while
alongside the new key.

In this case, you can see that the manifest is signed by two legacy RSA
keys, and one from the newer EdDSA (Ed25519) signature algorithm.  three
versions ago, many older Debian systems couldn't even verify an Ed25519
signature.

If the next release for debian is also signed by a composite sig, i
suspect they would just add the new composite sig and phase out the
older of the legacy RSA signing keys.

>> And yes, a signer might still want to sign twice during the
>> transition period, where not every verifier is capable of verifying
>> the new composite signatures.  That's something that already happens
>> whenever *any* new signing algorithm is introduced, composite or
>> otherwise.
>
> Twice? That ignore the combinatorics. We might end up needing a whole
> pile of signatures for code-signing, or worse, might end up with some
> verifiers who can't handle sigs from some distributions and so skip
> signature verification entirely.

I'm pretty sure i mean just twice for a simple transition:

 - once with a new composite signature algorithm, for updated verifiers,
   and
   
 - once with the existing legacy classical algorithm, for legacy
   verifiers.

In the event that you need to support "legacy-legacy" clients, i.e.,
those that have never heard about even the newer legacy key, you can
sign three times, like the InRelease file above does.

If there's a known QC break for one of the legacy algorithms, you just
stop signing with the keys; installations that haven't received the new
signing algorithm, or don't know about the signing key, are out of luck.
But then, they're out of luck anyway, because the QC operator can forge
code signatures that they'll accept.

There is a clear, simple upgrade path with this approach, but it is
linear, *not* combinatorial.  And it's already happening.  We just need
to make it work safely with the new algorithms, and not require every
application layer to sort out some complex new semantics in order to be
safe.

For signature algorithms with weaker cryptanalytic history than we'd
like, like ML-DSA, composite sigs offer that kind of safety.

        --dkg