Re: [openpgp] PQC signature algorithm selection

[Falko Strenzke <[e-mail]>]

Hi Stephen,

thanks for the detailed answers. I think I understand your concerns a 
bit better now. See my comments inline


Sure, I fully agree we need a way to handle key mgmt that
>>> doesn't fall in either of the breakage scenarios being
>>> considered (busted new alg, or CRQC).
>>
>> Could you please explain more what you envision here? 
>
> Fair question. Sorry about the longish answer:-)
>
>> I think is highly relevant to the discussion because only with a 
>> picture (of whatever granularity) of the respective complete 
>> solution, the advantages and disadvantages of both approaches 
>> (composite vs. using only dual signatures) can be compared.
>
> So I think in all cases the WG will need to define how
> to manage keys for dual signatures - as Daniel said, a
> typical signer is quite likely to emit both a classic sig
> and at least one more sig that involves a pq alg (and that
> 2nd one may involve composite sigs or not). I'm not sure
> that there's that much difference in terms of key mgnt
> requirements or mechanisms for supporting all that well,
> whether or not we have composite sigs.

Here I would say that we have to distinguish two different aspects of 
the PQC migration which I would like to relate to two different (but 
overlapping) phases of the migration. I started to elaborate on that 
thought already in a previous post in this thread, but let me try to 
draw the picture still more clearer:

1. The first type of transition phase could be called "trust 
transition": it is the phase in which neither PQC nor traditional 
signatures alone receive sufficient long term trust. Regarding PQC 
signatures (probably except for the hash-based), in this phase we might 
even expect – maybe only with a very low probability, though – a full 
break of the scheme without any previous warning. Andrew called this a 
"cryptographic zero day" in a recent post on this list. In this phase, 
the function of the composite signatures is to ensure that without any 
changes to the protocol and higher level applications such as mail 
clients and key servers, we have secure signatures as long as one of the 
two component schemes is secure. We clearly cannot achieve the same 
(namely, without any changes to higher level applications) with dual 
signatures on the protocol level, as that requires

  * applications to support
      o multiple signing keys for generating signatures
      o potentially multiple certificates of the recipient for verifying
        signatures
      o enable the user to configure multiple signing keys
      o potentially enable the user to configure trust in different
        certificates of another party
      o signal to the user how a message was signed with multiple signatures
  * users to create and manage multiple certificates

Contrary to that, composite signatures do not require any of that. 
However, we need to acknowledge that for keys held in hardware, as you 
write further down, composite signatures may lead to difficulties in key 
management, if hardware is used that cannot hold both of the component keys.

2. The second type of transition phase (with respect to signatures) is 
the time window in which users are by and by upgrading their clients to 
support PQC signatures. During this phase, backwards compatibility may 
be tried to achieve via dual signatures in the way we all understand it. 
This implies all the problems listed under 1.

Accordingly, I would conclude achieving backwards compatibility with 
dual signatures during the second type of transition phase will give us 
varied results. In some cases it might work as intended, in some cases 
it will not. What I think is important to consider now is that

     a. the second type of transition phase is less important for 
security, as the first ensures the avoidance of the risk of a 
"cryptographic zero day" through a full break of the PQC scheme and the 
second just ensures backwards compatibility
     b. the second type of transition phase may be shorter than the first
     c. the second type of transition phase may not be relevant to all 
users of OpenPGP. Namely, that is the case where (mainly) closed user 
groups communicate internally and where the support for PQC signatures 
can be assumed a priori.

On this background I come to the conclusion that despite the fact that 
we may aim at dual signatures for backwards compatibility, composite 
signatures have clear advantages over them when considering mainly a 
single certificate for each user (that is, per application or pertaining 
to the number of certificates used for signing a single message), which 
is how OpenPGP is currently used and supported.

>
> Where composite sigs would make a difference is that they
> have the combinatoric problem that any signer that wants
> to be able to emit all sorts of composite sigs ends up
> having to manage lots more private key material, which
> seems at least unwieldy and maybe more risky. For a verifier
> that wants to be able to verify all sorts of composite sigs,
> they would end up with a plethora of public values, but I'm
> not sure if that's any harder than handling info for lots
> of signers.

I don't understand why you think a signer would want to emit many 
signatures with many different signatures schemes. That would be 
possible today as well, since OpenPGP supports different signature 
algorithms and especially different curves for ECDSA. So why will that 
change with the introduction of composite signatures?

>
> Then, as a user, I would like to be able to use e.g.
> ML-KEM+x25519 now/soon, but without relying on any PQ sig
> algs at all for the next few years. I'm not sure how common
> or oddball that may be, but I guess it impacts on e.g. the
> key mgmt UIs or configs that applications may want to
> support. (For the present discussion, that's independent
> of whether or not we support a composite KEM with v4 keys
> or only with v6 keys.)
Key management (with the exception of the two component keys residing on 
different hardware, which is clearly a topic; I address that further 
down) for composite schemes will not be different from key management of 
non-composite schemes. That is the great advantage of composite schemes.

>
> Lastly, composite sigs create the potential for dodgy re-use
> of e.g. the same ed25519 private value for a non-PQ sig and
> for making a composite sig. I assume we'll say that MUST NOT
> be done, but of course someone will, and that would likely
> need to be considered when thinking about revocation and
> how verifiers check public key status. I guess we'll have
> to tackle that issue for composite KEMs anyway though so
> again whether or not we have composite sigs might not make
> so much difference to what's needed for key mgmt.
In the current draft in the repo, we are saying "SHOULD NOT" for reuse 
of existing keys. We had "MUST NOT" before (still in the latest 
published version), but it was pointed out that reusing existing 
hardware tokens may be desired. Since OpenPGP does naturally prevent 
signature stripping attacks, this specific concern does not apply. What 
you mention regarding revocation would indeed have to be handled in that 
case. It might be worth to mention that in the security considerations.
>
> So overall, I don't think composite PQ sigs change the
> requirements for key mgmt that much, but they might make
> the (already awful today) key mgmt UI issues intractable
> due to the combinatorics.

I only see any impact of composites on key management when

- the two component keys reside on different hardware tokens (including 
of course the case of one held as a soft token). This is indeed a case 
to consider in my view.
- when existing keys are reused as component keys. This is already 
violating a SHOULD NOT and in my view it can be accepted that 
applications or users going down that road have to find a way to handle 
key revocation properly in this case

I hope I could make it clear, that – as others have pointed out in this 
discussion already – the challenges for key management with multiple 
certificates and dual signatures is far more challenging than that for 
composite schemes. Please correct me if you come to a different conclusion.

>
>>
>> In that course I would also like to ask you about your actual 
>> concerns regarding composite signatures. So far I understand that you 
>> think that they are "not needed". In my understanding that is not 
>> exactly a counterargument, but rather an opinion. 
>
> I totally disagree. If composite sigs are not needed for some
> application then they would represent unnecessary complexity
> and I'd argue such complexity is always the enemy of security.
> I do think it's therefore important that we justify their use
> in real application scenarios, and not just accept that we
> ought define 'em, just because we need composite KEMs and
> most PQ-sig algs are newish.
To point out the advantages of composite signatures over dual signatures 
on the protocol level is what I tried above. In my view we need to think 
in terms of advantages and disadvantages, rather than the binary 
"needed" / "not needed", as obviously both sides are coming up with 
valid arguments.
>
> Another point wrt necessity - as already pointed out we
> will need to support signers who want to emit separate
> ed25519 and SLH-DSA signatures, so I think that means we
> have to describe how to handle independent classic and
> PQ sigs in any case. So even if we do specify composite
> sigs, we still need things to work for the separated case,
> which to me implies that composite sigs may again just be
> a source of added complexity.
Above I tried to make clear the different roles that the backwards 
compatible dual signatures and the composite signatures take on in 
different transition phases above which might put these considerations 
of yours into a different perspective (?)
>
>> So could you please give the 
>> concrete drawbacks that you see if composite signatures where standardized?
>
> I also worry that implementers may run into issues with
> composites when e.g. updating a library that has external APIs
> that are used by applications, and algorithm-specific internal
> SPIs. Some of the latter might be e.g. h/w implementations,
> have some FIPS or other approvals or otherwise be such that
> it's non-trivial and error-prone to try handle composite sigs
> using the single-sig algorithm implementations.
Indeed, if cryptographic hardware support limited to the PQC algorithm 
could be a concern. I (personally) think this could be addressed by 
offering stand-alone ML-DSA as well. In that case, the implementation 
using a hardware token restricted to ML-DSA could decide to only offer 
that algorithm as stand-alone. Would you agree that  this is a solution 
for that problem?
>
> I'd hate to see people having to re-implement alg internals
> for that reason as that's so hard to do correctly. And the
> more combinations we specify, I'd argue the more likely someone
> will run into such issues, so again the combinatorics is the
> problem there.
>
> Composite sigs also create the potential for all sorts of
> mix'n'match certificates, much more than would be the case
> without composite sigs, and I'd hate to see people arguing
> in 5 years time that e.g. signing an ed25519 public key with
> ML-DSA-65+ECDSA-brainpoolP256r1 is or isn't valid or is or
> isn't required.
The case here is simple: a composite signature is valid as long as one 
of the component keys is still trustworthy. But agreed, not every user 
may understand this.
>
> Finally on this one, the more codepoints we create the more
> chances for non-interoperability. So minimising the number
> of codepoints and algorithms that are defined is IMO always
> a good thing. (Here I'm regarding each composite sig as a
> single alg with it's own codepoint.)

That we have an increased number of code points for the composite 
algorithms is true. I also fear that at least in the course of the next 
decade, further waves of algorithms will be integrated into OpenPGP: The 
round 4 of the NIST selection will produce up to two new KEMs and the 
new call for signatures will also produce new algorithms. Then outside 
the NIST selection algorithms will be standardized. We have seen already 
concrete proposals for OpenPGP on this list. If the proliferation of 
code points is a concern, then I advise that we challenge the decision 
for a "flat" allocation (one code point per algorithm and parameter set) 
over "deep" allocation (one code point per PQC algorithm and the 
parameters in a different registry). But using the argument of code 
point scarcity to not standardize certain algorithms is hard to justify 
in my view, because what is worth standardizing then will always depend 
on personal preference.

- Falko

>
>> For instance Simo has given the argument that standardizing 
>> composites now would delay the removal of traditional public-key 
>> algorithms from cryptographic libraries (which I personally don't 
>> count as a strong one, as I explained in my answer to him, but that's 
>> another thing). Do you 
>> see any other disadvantages of composite signatures?
>>
>> With the editor's hat on, I think the lists of pros and cons for each 
>> solution (composite (in conjunction with dual) and purely dual 
>> signatures that people give on this list will be the best ground for 
>> the WG to come to a decision.
>
> Yeah, it's a hard task to try capture these issues in the draft
> and/or presentation materials, esp when one has an opinion (as
> we all do). That's why our document editors get the big bucks:-)
>
> I'd say for now, just noting there's ongoing discussion would be
> ok for the draft, and it may be better to try focus on capturing
> the issues in presentation materials for IETF-119. (That's still
> a tricky task though.)
>
> Cheers,
> S.
>
-- 

*MTG AG*
Dr. Falko Strenzke
Executive System Architect

Phone: [phone]
E-Mail: [e-mail]
Web: mtg.de <https://www.mtg.de>

<https://www.linkedin.com/search/results/all/?fetchDeterministicClustersOnly=true&heroEntityKey=urn%3Ali%3Aorganization%3A13983133&keywords=mtg%20ag&origin=RICH_QUERY_SUGGESTION&position=0&searchId=d5bc71c3-97f7-4cae-83e7-e9e16d497dc2&sid=3S5&spellCorrectionEnabled=false>
Follow us
------------------------------------------------------------------------
<https://www.mtg.de/de/aktuelles/MTG-AG-erhaelt-Innovationspreis-des-Bundesverbands-IT-Sicherheit-e.V-00001.-TeleTrust/> 
<https://www.itsa365.de/de-de/companies/m/mtg-ag>

MTG AG - Dolivostr. 11 - 64293 Darmstadt, Germany
Commercial register: HRB 8901
Register Court: Amtsgericht Darmstadt
Management Board: Jürgen Ruf (CEO), Tamer Kemeröz
Chairman of the Supervisory Board: Dr. Thomas Milde

This email may contain confidential and/or privileged information. If 
you are not the correct recipient or have received this email in error,
please inform the sender immediately and delete this email.Unauthorised 
copying or distribution of this email is not permitted.

Data protection information: Privacy policy 
<https://www.mtg.de/en/privacy-policy>