Re: [CFRG] NSA vs. hybrid

[Mike Ounsworth <[e-mail]>]

(resending since I was not subscribed to cfrg)

---
Mike Ounsworth

-----Original Message-----
From: Spasm <[e-mail]> On Behalf Of Mike Ounsworth
Sent: November 12, 2021 8:08 AM
To: [e-mail]; LAMPS WG <[e-mail]>
Subject: [EXTERNAL] Re: [lamps] [CFRG] NSA vs. hybrid

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.

______________________________________________________________________
Hi Dan,

Just to clarify / confirm a few points.

> My understanding of the terminology of the slides is that a "composite"
> certificate is one where the protocol is checking _one_ certificate 
> with _one_ signature from the CA as usual, but the signature details 
> are built _internally_ as requiring two component signatures to be valid.

Correct, both the NSA's slides and our Internet-Drafts function that way; the key holder has one PEM private key blob, the certificate has one public key octet string, the certificate has one signatureAlgorithm OID and one signatureValue octet string. If you ASN.1-decode those octet strings you will find that they are actually a sequence their respective object types:

CompositePrivateKey ::= SEQUENCE SIZE (2..MAX) OF OneAsymmetricKey CompositePublicKey ::= SEQUENCE SIZE (2..MAX) OF SubjectPublicKeyInfo CompositeSignatureValue ::= SEQUENCE SIZE (2..MAX) OF BIT STRING

So the design intent is exactly as you describe: the protocol sees a traditionally-structured X.509 certificate containing a public key and a signature as usual, and only inside the crypo lib's `bool verify()` do they need to get unpacked into multiple components.

Relevant I-Ds:
draft-ounsworth-pq-composite-keys-00
draft-ounsworth-pq-composite-sigs-05




> How is a P certificate plus a Q certificate easier to use than a P 
> certificate plus a P+Q certificate?

> Are we supposed to be envisioning a post-quantum signature system that 
> just barely fits into a UDP packet but not if one adds 64 bytes for an 
> Ed25519 signature? If this is supposed to be an objection to the cost 
> of the extra 64 bytes then there also has to be an analysis of how 
> much space is lost by the "non-composite" approach.

Yes! Exactly this!
What about the extra bytes of redundant data between non-composite P and Q certs?

I'll add another: what if the P and Q certs don't match; ie they don't have the same DN, or SANs, or email addresses, EKU, issuing CA, policy OIDs, etc? For example you could imagine an S/MIME system where an X.509 extension on a recipient's encryption cert dictates data retention period of any data encrypted for it. What if the recipient's P and Q certs specify different retention periods? I suppose you need extra logic to detect that and .. do what? Take the smaller of the two if it's security-driven or the larger of the two if it's legal-driven. Not all cert validation systems care about these things, but some do, and the potential for mismatch between the P and Q certs is a brand new dimension to X.509 validation that does not exist in a single-cert world; it's directly increasing the complexity of the X.509 validation computation process. I'm already imagining the CVEs that could crop if you try to use together two certs governed by different policies.




Thank you Dan for elevating this discussion. I think you have perfectly framed the discussion that needs to happen.

---
Mike Ounsworth

-----Original Message-----
From: CFRG <[e-mail]> On Behalf Of [e-mail]
Sent: November 12, 2021 6:04 AM
To: [e-mail]
Subject: [EXTERNAL] CFRG Digest, Vol 199, Issue 7

WARNING: This email originated outside of Entrust.
DO NOT CLICK links or attachments unless you trust the sender and know the content is safe.

______________________________________________________________________
Send CFRG mailing list submissions to
        [e-mail]

To subscribe or unsubscribe via the World Wide Web, visit
        https://urldefense.com/v3/__https://www.irtf.org/mailman/listinfo/cfrg__;!!FJ-Y8qCqXTj2!KdNX-_sVqfUAG8m1TmVITc5Fxc6clTw2t6tVPbK_yM84bwWmweJs0RJh1U3ZFlTEwR3Qq4OKcQ$
or, via email, send a message with subject or body 'help' to
        [e-mail]

You can reach the person managing the list at
        [e-mail]

When replying, please edit your Subject line so it is more specific than "Re: Contents of CFRG digest..."


Today's Topics:

   1. NSA vs. hybrid (D. J. Bernstein)
   2. Re: NSA vs. hybrid (Natanael)
   3. Re: NSA vs. hybrid (D. J. Bernstein)


----------------------------------------------------------------------

Message: 1
Date: 12 Nov 2021 09:28:11 -0000
From: "D. J. Bernstein" <[e-mail]>
To: [e-mail]
Subject: [CFRG] NSA vs. hybrid
Message-ID: <[e-mail]>

This looks to me like something that should be discussed in CFRG rather than LAMPS:

   https://urldefense.com/v3/__https://datatracker.ietf.org/meeting/112/materials/slides-112-lamps-hybrid-non-composite-multi-certificate-00__;!!FJ-Y8qCqXTj2!KdNX-_sVqfUAG8m1TmVITc5Fxc6clTw2t6tVPbK_yM84bwWmweJs0RJh1U3ZFlTEwR1qAwKISA$
   https://urldefense.com/v3/__https://mailarchive.ietf.org/arch/msg/spasm/McksDhejGgJJ6xG617FEWLbBq0k/__;!!FJ-Y8qCqXTj2!KdNX-_sVqfUAG8m1TmVITc5Fxc6clTw2t6tVPbK_yM84bwWmweJs0RJh1U3ZFlTEwR2-OkU0HA$

This is one part of a big push by NSA across multiple non-CFRG venues to convince everyone to

   * deploy small lattice systems---which _hopefully_ protects against
     quantum computers---and

   * _turn off ECC_---this is the scary part, since there's a serious
     risk that the small lattice systems are easier to break than ECC.

I would like to see CFRG instead advising integration of ECC into all post-quantum deployments for the foreseeable future. There's no reason that this advice has to wait for NISTPQC standards.

Specific comments follow.

> Rigorous, effective algorithm vetting is a must, NSA has confidence in 
> the NIST PQC process

After evaluations from 2017--2020, the "NIST PQC process" selected various third-round primitives for which NIST was subsequently so surprised by attacks that NIST in 2021 is suddenly promoting an "alternate" primitive and issuing a call for new primitives.

Given that 2017--2020 wasn't enough time for the process to reach safe decisions, why should anyone believe that decisions made by the same process in 2021 or 2022 are safe? It sounds bizarre to me that anyone would be declaring confidence in the process. Where does this confidence come from?

Most of NIST's evaluation process has been hidden from public view.
Anyone who skims

   https://urldefense.com/v3/__https://nvlpubs.nist.gov/nistpubs/ir/2019/NIST.IR.8240.pdf__;!!FJ-Y8qCqXTj2!KdNX-_sVqfUAG8m1TmVITc5Fxc6clTw2t6tVPbK_yM84bwWmweJs0RJh1U3ZFlTEwR1bkG1aCQ$
   https://urldefense.com/v3/__https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8309.pdf__;!!FJ-Y8qCqXTj2!KdNX-_sVqfUAG8m1TmVITc5Fxc6clTw2t6tVPbK_yM84bwWmweJs0RJh1U3ZFlTEwR1LVgZRFw$
   https://urldefense.com/v3/__https://nvlpubs.nist.gov/nistpubs/jres/104/5/j45nec.pdf__;!!FJ-Y8qCqXTj2!KdNX-_sVqfUAG8m1TmVITc5Fxc6clTw2t6tVPbK_yM84bwWmweJs0RJh1U3ZFlTEwR366zhD8A$
   https://urldefense.com/v3/__https://nvlpubs.nist.gov/nistpubs/jres/106/3/j63nec.pdf__;!!FJ-Y8qCqXTj2!KdNX-_sVqfUAG8m1TmVITc5Fxc6clTw2t6tVPbK_yM84bwWmweJs0RJh1U3ZFlTEwR19N4uq5w$

can see that NIST's reports on the post-quantum competition are much less detailed than NIST's reports on the AES competition, even though the post-quantum competition is much more complicated.

NIST refuses to call this a "competition", doesn't follow NIST's rules for "competitions", and doesn't follow the transparency rules from NIST's Dual EC post-mortem. FOIA requests have revealed _some_ useful information, but the public can't see most of NIST's work. What the public _can_ see is deeply concerning; see, e.g., Section 5 of https://urldefense.com/v3/__https://cr.yp.to/papers.html*categories__;Iw!!FJ-Y8qCqXTj2!KdNX-_sVqfUAG8m1TmVITc5Fxc6clTw2t6tVPbK_yM84bwWmweJs0RJh1U3ZFlTEwR34GhTXhg$ .

If NSA's "confidence in the NIST PQC process" is based on NSA's special access to that process (apparently stretching back to the outset in 2015, kept secret until July 2020) then NSA should publish the details for everyone else to evaluate. NIST has recently stated in

   https://urldefense.com/v3/__https://web.archive.org/web/20211027161303/https:/*www.nist.gov/blogs/taking-measure/post-quantum-encryption-qa-nists-matt-scholl__;Lw!!FJ-Y8qCqXTj2!KdNX-_sVqfUAG8m1TmVITc5Fxc6clTw2t6tVPbK_yM84bwWmweJs0RJh1U3ZFlTEwR1pd1P1pA$

that "We operate transparently. We???ve shown all our work" so I don't think NSA can point to NIST's privacy as a reason to avoid disclosure.

> NSA only anticipates using hybrid solutions to maintain 
> interoperability during the transition (or where direct drop-in is not
> feasible)

This sounds reckless to me, especially in conjunction with NSA pushing specifically for small lattice-based encryption systems. We've seen breaks of "provably secure" lattice submissions, we've seen continued degradation of security for all lattice submissions, and we've seen one claimed "barrier" after another being broken by new lattice attacks. See

   https://urldefense.com/v3/__https://ntruprime.cr.yp.to/latticerisks-20211031.pdf__;!!FJ-Y8qCqXTj2!KdNX-_sVqfUAG8m1TmVITc5Fxc6clTw2t6tVPbK_yM84bwWmweJs0RJh1U3ZFlTEwR3aBtP_EA$

for how complicated and unstable the security analysis is.

> Any hybrid method adopted should allow for a quick transition to 
> PQ-only solutions

Why is this particular transition important, and what concretely is this goal supposed to mean? How would a choice of "hybrid method" end up delaying such a transition beyond the natural costs of any upgrade?

_If_ everybody sees that big quantum computers have been built _and_ are so cost-effective that ECC obviously no longer has any security value, _then_ there will be a push to declare ECC obsolete and to remove it from protocols, simplifying implementations. I don't see how any particular choice of hybrid approach is an obstacle in this scenario.

> Ensure interoperability with PQ-only systems is included for forward 
> compatibility and to allow for use of direct drop-in of PQ

Is this saying something different from the previous goal, aside from adding the words "forward compatibility" and "direct"?

The slides continue by comparing two approaches to hybrid certificates.
The idea of having certificates work as usual, except for upgrading to a
P+Q signature system that internally requires pre-quantum signature P
and post-quantum signature Q to be valid, is labeled here as "composite certs". The idea of requiring two separate certificates, one using P and one using Q (maybe with some effort to compress redundancy), is what seems to be labeled here as "non-composite certs".

  [ under "PROS" of "composite" certs ]
> Matching security levels of algorithms is built into composite pairs

"Matching security levels" is usually a tool to reduce security rather than to ensure security. See the first three paragraphs of Section 3.2 of https://urldefense.com/v3/__https://cr.yp.to/papers/footloose-20210705.pdf__;!!FJ-Y8qCqXTj2!KdNX-_sVqfUAG8m1TmVITc5Fxc6clTw2t6tVPbK_yM84bwWmweJs0RJh1U3ZFlTEwR0Vr-2smw$ .

As a concrete example (with encryption rather than signatures), the typical concept of "matching security levels" would object to the new

   [e-mail]

as overkill, since _known attacks_ against sntrup761 are much more expensive than attacks against X25519. However, an analysis that properly accounts for _risks_ is much more complicated and isn't structurally compatible with the "security level" oversimplification.

  [ under "CONS" of "composite" certs ]
> Can require reworking of certificate validation

Yikes---sounds scary given how tricky certificate validation is. But wait a minute. Isn't certificate validation simply calling signature verification as a black box? What has to be reworked here?

  [ under "CONS" of "composite" certs ]
> Maintenance concerns surrounding deprecated algorithms

Why is this supposed to be more of an issue for "composite" certs than for "non-composite" certs?

  [ under "CONS" of "composite" certs ]
> Requires another transition and set of standards from hybrid to PQ

Even _if_ this transition is something we definitely want and something to be worrying about now (see above), how would "non-composite" certs avoid the need for new standards and a transition? For interoperability someone would have to say "Okay, clients have to stop requiring ECC"
followed eventually by "Okay, now servers should stop sending ECC"; sounds to me like transitioning to a new standard!

  [ under "PROS" of "non-composite" certs ]
> Computational processes remain unchanged (but perhaps multiple
> iterations)

This sounds weird, given that the whole point is to be adding new post-quantum primitives into the picture. Perhaps I'm missing some restricted definition of "computational process".

  [ under "PROS" of "non-composite" certs ]
> UDP-based protocols potentially avoid fragmentation issues

I'm puzzled. Are we supposed to be envisioning a post-quantum signature system that just barely fits into a UDP packet but not if one adds 64 bytes for an Ed25519 signature? It would help to have pointers to the specific protocol and specific post-quantum signature system showing that this is a problem, and an explanation of why the correct fix isn't to have the protocol upgraded to be able to use multiple packets so as to support higher-security post-quantum primitives.

  [ under "PROS" of "non-composite" certs ]
> Ease of use for backward compatibility

How is a P certificate plus a Q certificate easier to use than a P certificate plus a P+Q certificate? If this is supposed to be an objection to the cost of the extra 64 bytes then there also has to be an analysis of how much space is lost by the "non-composite" approach.

  [ under "PROS" of "non-composite" certs ]
> Facilitates seamless transition to PQonly, no new standards needed

This sounds like another repetition of the ideas that (1) "PQonly" is the desired goal and (2) specifying "composite" certificates somehow interferes with this. See above.

  [ under "PROS" of "non-composite" certs ]
> Requires support for only two types of structures (traditional and PQ)

Not sure what this is supposed to mean.

> The quantum-resistant algorithms resulting from the NIST program are 
> well-vetted, and NSA has no concerns in this area regarding their 
> security.

Was GeMSS "well-vetted" in mid-2020? Is the same process suddenly risk-free a year later?

> Based on our analysis and experience, NSA has decided that the NSS 
> path forward is toward strictly-PQ solutions, and thus we require 
> flexibility in the architecture of hybrid protocols.

As a procedural note, I don't believe that CFRG, IRTF, and IETF are under any obligation to do what NSA wants, even if NSA labels this as a requirement, even if NSA uses its power to skew the market. The top goal here has to be security.

> As you pointed out, implementation errors in current cryptographic 
> algorithms are quite common, and the statistics you provided on CVEs 
> for 2020 are telling that issue is prevalent even today, with 
> well-established algorithms. As such, if implementation errors are 
> your largest concern, doubling up on algorithms introduces a larger 
> surface for error.

No, it's not that simple. The fact that _both_ primitives are being independently asked to protect the user's data means that one primitive could save the user from errors in the implementation of the other primitive.

Obviously a buffer overflow in one implementation can destroy security, and there are always systems-level concerns regarding extra software, but the risks from the existing X25519/Ed25519 software ecosystem are much smaller than the risks being added by the much more complicated new post-quantum software ecosystem.

> I will emphasize that our non-composite approach does propose changes 
> to existing protocol logic; however, in most instances this is 
> primarily a matter of duplicating existing processes, and not 
> introducing entirely new structure.

So building a signature system that verifies a P signature and a Q signature is "entirely new structure", while building a protocol that verifies a certificate using a P signature and that verifies a certificate using a Q signature isn't "entirely new structure"? I don't get it.

---Dan



------------------------------

Message: 2
Date: Fri, 12 Nov 2021 12:16:43 +0100
From: Natanael <[e-mail]>
To: IRTF CFRG <[e-mail]>
Subject: Re: [CFRG] NSA vs. hybrid
Message-ID:
        <CAAt2M18seCg-Z_QZRma6nOiXS5SpESc=[e-mail]>
Content-Type: text/plain; charset="utf-8"

Den fre 12 nov. 2021 10:29D. J. Bernstein <[e-mail]> skrev:

> This looks to me like something that should be discussed in CFRG 
> rather than LAMPS:
>
>
> https://urldefense.com/v3/__https://datatracker.ietf.org/meeting/112/m
> aterials/slides-112-lamps-hybrid-non-composite-multi-certificate-00__;
> !!FJ-Y8qCqXTj2!KdNX-_sVqfUAG8m1TmVITc5Fxc6clTw2t6tVPbK_yM84bwWmweJs0RJ
> h1U3ZFlTEwR1qAwKISA$
>
> https://urldefense.com/v3/__https://mailarchive.ietf.org/arch/msg/spas
> m/McksDhejGgJJ6xG617FEWLbBq0k/__;!!FJ-Y8qCqXTj2!KdNX-_sVqfUAG8m1TmVITc
> 5Fxc6clTw2t6tVPbK_yM84bwWmweJs0RJh1U3ZFlTEwR2-OkU0HA$
>
> This is one part of a big push by NSA across multiple non-CFRG venues 
> to convince everyone to
>
>    * deploy small lattice systems---which _hopefully_ protects against
>      quantum computers---and
>
>    * _turn off ECC_---this is the scary part, since there's a serious
>      risk that the small lattice systems are easier to break than ECC.
>
> I would like to see CFRG instead advising integration of ECC into all 
> post-quantum deployments for the foreseeable future. There's no reason 
> that this advice has to wait for NISTPQC standards.
>
> Specific comments follow.
>
> [...]

  [ under "CONS" of "composite" certs ]
> > Can require reworking of certificate validation
>
> Yikes---sounds scary given how tricky certificate validation is. But 
> wait a minute. Isn't certificate validation simply calling signature 
> verification as a black box? What has to be reworked here?
>

In theory it should be simple, in practice there's constant mistakes made in validating certificate chains and certificate properties. In theory this should be as simple as requiring dual and identical certificate chains with no difference but the asymmetric primitives, requiring both to be valid at once. In practice, I expect this to get messed up in a million different ways.

With that said, I do personally favor adding support for "multi-signature certs", of which composite certs with non PQ and PQ algorithms together is one variant. Fixing this once and making sure it stays fixed feels to me like the better option (in my layman's opinion).

  [ under "CONS" of "composite" certs ]
> > Maintenance concerns surrounding deprecated algorithms
>
> Why is this supposed to be more of an issue for "composite" certs than 
> for "non-composite" certs?
>

My best guess is that with non composite you can easily ignore the cert with non PQ algorithms (just don't supply it to the validator). However a validator with support for composite certs should equally easily be able to ignore non PQ chains.

  [ under "PROS" of "non-composite" certs ]
> > Computational processes remain unchanged (but perhaps multiple
> > iterations)
>
> This sounds weird, given that the whole point is to be adding new 
> post-quantum primitives into the picture. Perhaps I'm missing some 
> restricted definition of "computational process".
>

This is essentially a variant of the argument above, you run the validator twice on different certs with only the primitive being different. The validator needs additional changes to put both chains in the same cert.

  [ under "PROS" of "non-composite" certs ]
> > Ease of use for backward compatibility
>
> How is a P certificate plus a Q certificate easier to use than a P 
> certificate plus a P+Q certificate? If this is supposed to be an 
> objection to the cost of the extra 64 bytes then there also has to be 
> an analysis of how much space is lost by the "non-composite" approach.
>

Similar to above, some older strict validators might reject composite certs with an additional PQ chain even if the non PQ chain is valid. In this case you may need to identify the user agent and serve only a non PQ cert.

However, I don't see what kind of software would have issues with validating the non PQ part in composite certs but which would also happily accept double certificates and validate just the non PQ one and ignore that the other fails to validate (due to incompatibility), so this claim is odd.
Any software updated to support two certs can also update the validator code.

The ability to serve and receive and correctly process double certs will in itself essentially be a new standard.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://urldefense.com/v3/__https://mailarchive.ietf.org/arch/browse/cfrg/attachments/20211112/1a7e242b/attachment.htm__;!!FJ-Y8qCqXTj2!KdNX-_sVqfUAG8m1TmVITc5Fxc6clTw2t6tVPbK_yM84bwWmweJs0RJh1U3ZFlTEwR0hkKeCIQ$ >

------------------------------

Message: 3
Date: 12 Nov 2021 12:03:49 -0000
From: "D. J. Bernstein" <[e-mail]>
To: [e-mail]
Subject: Re: [CFRG] NSA vs. hybrid
Message-ID: <[e-mail]>

> > ?? [ under "CONS" of "composite" certs ]
> > > Can require reworking of certificate validation
> > Yikes---sounds scary given how tricky certificate validation is. But 
> > wait a minute. Isn't certificate validation simply calling signature 
> > verification as a black box? What has to be reworked here?
> In theory it should be simple, in practice there's constant mistakes 
> made in validating certificate chains and certificate properties. In 
> theory this should be as simple as requiring dual and identical 
> certificate chains with no difference but the asymmetric primitives, requiring both to be valid at once.
> In practice, I expect this to get messed up in a million different ways.

My understanding of the terminology of the slides is that a "composite"
certificate is one where the protocol is checking _one_ certificate with _one_ signature from the CA as usual, but the signature details are built _internally_ as requiring two component signatures to be valid.

This approach doesn't touch the logic of certificate validation outside the signature-verification black box. So I'm puzzled as to why NSA is pointing to "reworking of certificate validation" as a disadvantage for _this_ approach rather than for the _other_ approach.

> > ?? [ under "PROS" of "non-composite" certs ]
> > > Computational processes remain unchanged (but perhaps multiple
> > > iterations)
> > This sounds weird, given that the whole point is to be adding new 
> > post-quantum primitives into the picture. Perhaps I'm missing some 
> > restricted definition of "computational process".
> This is essentially a variant of the argument above, you run the 
> validator twice on different certs with only the primitive being 
> different. The validator needs additional changes to put both chains in the same cert.??

Say P is whichever ECC system and Q is whichever post-quantum system.
Here's my understanding of the two options under discussion:

   (1) Send a certificate with a "composite" P+Q signature to satisfy
       new clients; also, for however long the transition takes, send a
       certificate with a P signature to satisfy old clients.

   (2) To satisfy new clients, send a certificate with a Q signature and
       a certificate with a P signature; the second certificate will
       also satisfy old clients.

I don't see how either of these qualifies as "computational processes remain unchanged": new clients are in any case doing a new Q process.
For the first option, there's a new P+Q signature system; for the second option, there's a new Q signature system and new certificate logic.

---Dan



------------------------------

Subject: Digest Footer

_______________________________________________
CFRG mailing list
[e-mail]
https://urldefense.com/v3/__https://www.irtf.org/mailman/listinfo/cfrg__;!!FJ-Y8qCqXTj2!KdNX-_sVqfUAG8m1TmVITc5Fxc6clTw2t6tVPbK_yM84bwWmweJs0RJh1U3ZFlTEwR3Qq4OKcQ$


------------------------------

End of CFRG Digest, Vol 199, Issue 7
************************************
Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.

_______________________________________________
Spasm mailing list
[e-mail]
https://urldefense.com/v3/__https://www.ietf.org/mailman/listinfo/spasm__;!!FJ-Y8qCqXTj2!InWtIGiT2-mU-OAAqiKP1oE75Mb_qA5-yeVsc7n9GoiCbCPo1QtqRAB6qVQcudezPoHjqTTzQw$