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

[Stephen Farrell <[e-mail]>]

Hiya,

Partial answers to djb and dkg below.

On 16/03/2024 16:02, D. J. Bernstein wrote:
> Stephen Farrell writes: [ rolling things out takes time ]
>> That doesn't speak as to whether separate or composite sigs are 
>> needed at all that I can see.
> 
> Right. The overall rationale is structured as a rationale for 
> post-quantum signatures, then a rationale for hybrids, then a
> rationale for composites. I think this structure is useful in
> pinpointing where disagreements occur. My feeling is that divergence
> typically happens at the first step.

I believe I diverge from both your opinions at the last step.

> 
>>> Another argument is that there are big applications where you
>>> find people in court referring to signature keys from, say, 15
>>> years earlier,
>> Do you have any references to such cases?
> 
> Here's a recent case that comes to mind: 
> https://protos.com/did-craig-wright-use-staged-laptop-at-satoshi-key-signing-ceremony/
>
> 
https://www.wired.com/story/craig-wright-not-satoshi-nakamoto-bitcoin-creator-ruling/

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.

>>> So I think it's useful to start the post-quantum-signature
>>> rollout. My understanding is that consensus has already been
>>> established in some WGs (e.g., OpenPGP) on rolling out
>>> post-quantum signatures.
>> That's not correct. Doing so has been proposed but is not something
>> on which consensus has been declared so far.
> 
> Hmmm. I must have misunderstood the part saying "My takeaway from
> that is that we'd be better off waiting a few years before even
> addressing PQ sigs, but (as co-chair) I have to recognise that the WG
> had consensus to try tackle this issue now, along with KEMs."

Fair 'nuff - what I meant to say (but didn't) was that we didn't yet
have consensus on e.g. whether composite sigs were useful/needed.

> In any case, given that there's a WG with consensus to try tackling
> the issue of post-quantum signatures, it seems appropriate for CFRG
> to look at the protocol-independent cryptographic security questions
> that show up in post-quantum signatures.
> 
>>> Security analysis is easiest if this is presented to applications
>>> as a unified ("composite") signature system.
>> I don't agree. On what basis do you claim "simplest"?
> 
> The basic question is which layer is responsible for the combination
> of (say) Ed25519 with whichever PQ signature system.
> 
> It's important to note that, even if this is as trivial as "check
> both signatures" (which is typically just fine, but there are papers
> arguing that one should do more, and probably it's good to do more
> since it's so cheap to do so, just as in the case of KEM combiners),
> this is the sort of triviality that we see people screwing up all the
> time. Most people never learn how to do negative tests.

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.)

> 
> If the answer to the basic question is that the combination is
> handled centrally in, say, a CFRG document specifying Ed25519+PQ,
> then the reviewer checks
> 
> * whether that document is correctly handling the combination, *
> whether application 1 is correctly upgrading to Ed25519+PQ, * whether
> application 2 is correctly upgrading to Ed25519+PQ, * whether
> application 3 is correctly upgrading to Ed25519+PQ, * etc.,
> 
> with each application treating Ed25519+PQ as a black box.
> 
> If the answer to the basic question is instead that the combination
> is handled by every application, then the reviewer checks
> 
> * whether application 1 is correctly upgrading to PQ, * whether
> application 1 is correctly combining this with Ed25519, * whether
> application 2 is correctly upgrading to PQ, * whether application 2
> is correctly combining this with Ed25519, * whether application 3 is
> correctly upgrading to PQ, * whether application 3 is correctly
> combining this with Ed25519, * etc.,
> 
> which is more things that can go wrong and more things for the
> reviewer to read.

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



On 16/03/2024 19:56, Daniel Kahn Gillmor wrote:
> On Sat 2024-03-16 13:09:11 +0000, Stephen Farrell wrote:
>> It means the so-called complexity of handling hybrid sigs above
>> the crypto API will need to be dealt with in any case, if there is
>> ever any option defined for a "pure" pq-sig for an application in
>> which one is interested.
> 
> I'm not convinced by this argument, at least in OpenPGP contexts,
> where i've thought about and experimented with this rather more than
> in other places.
> 
> In the OpenPGP context, it seems quite clear that the primary
> preferred form of signature verification at the application layer is
> that there can be any number of signers, and the verifier's job is to
> determine which signers are acceptable.

I think the above assumes the solution you currently prefer.

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.

> 
> This is not a complex operation, and the semantics are
> well-understood and simple: if any acceptable signer has made a
> signature, then the object is successfully signed.

Again, you're assuming the answer there and not setting up an
analysis of the relative complexities involved in different
approaches.

> 
> These are the semantics of the "sop verify" and "sop inline-verify" 
> interfaces 
> (https://datatracker.ietf.org/doc/draft-dkg-openpgp-stateless-cli/), 
> which have a wide range of implementations.  They were derived 
> specifically from the needs of e-mail signing and code signing.
> (see for example this decade-old discussion around debian's apt
> multisig handling: https://bugs.debian.org/618445)
> 
> Composite signatures leave these application layer semantics intact. 
> The verifier's job remains the same: identify which signers are 
> acceptable.
> 
> 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.

Cheers,
S.

> 
> What an adoption of a composite sig "below" the crypto API does mean
> is: if there is a desire to move to a solely PQ signature scheme in
> the future, we will have to have another transition, to "pure"
> algorithms from hybrids.  But i don't think that cost is particularly
> high, and we can make that decision in the future, once we have
> gathered more cryptanalytic knowledge.
> 
>> If one believes that situation can be handled, then great, but
>> then why bother with composities? If one believes it "too hard"
>> then that seems fatal for arguments that composites save the day.
> 
> As i see it, the advantage of introducing a composite signature
> scheme "below" the cryptographic API is that the "too hard" part
> stays cabined among a core set of implementers who understand
> cryptographic requirements like signature bindings.  But each
> application-level mechanism simply needs to walk through their usual
> steps in dealing with the introduction of a new signing algorithm.
> 
> If we don't introduce a composite scheme, and some application layer 
> decides that they want to ensure that they get a PQ sig *and* a 
> traditional sig, then they do need to introduce new business logic
> that they have never needed before.
> 
> It seems plausible to me that at least some of the application
> layers that struggle to do this will get that business logic subtly
> wrong, or that there will be some funny business with signature
> splicing, replay, etc.  My instinct is to avoid giving the
> application layer enough flexibility to make those mistakes.  And
> indeed, it seems kinder to the application layer developers to not
> ask them to think about any of this at all.
> 
> Rather, we're just saying: here's new signature algorithm.  It's at 
> least as good as the old one.  Sorry that it costs a little more in 
> terms of CPU and bandwidth.
> 
> And we can argue later as a research community about whether it's
> time to let go of the classical component.
> 
> --dkg