Subject: [CFRG] NSA vs. hybrid

From: "D. J. Bernstein" <[email-masked]>
Date: 12 Nov 2021 09:28:11 -0000

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

   https://datatracker.ietf.org/meeting/112/materials/slides-112-lamps-hybrid-non-composite-multi-certificate-00
   https://mailarchive.ietf.org/arch/msg/spasm/McksDhejGgJJ6xG617FEWLbBq0k/

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://nvlpubs.nist.gov/nistpubs/ir/2019/NIST.IR.8240.pdf
   https://nvlpubs.nist.gov/nistpubs/ir/2020/NIST.IR.8309.pdf
   https://nvlpubs.nist.gov/nistpubs/jres/104/5/j45nec.pdf
   https://nvlpubs.nist.gov/nistpubs/jres/106/3/j63nec.pdf

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://cr.yp.to/papers.html#categories.

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://web.archive.org/web/20211027161303/https://www.nist.gov/blogs/taking-measure/post-quantum-encryption-qa-nists-matt-scholl

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://ntruprime.cr.yp.to/latticerisks-20211031.pdf

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://cr.yp.to/papers/footloose-20210705.pdf.

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

   [email-masked]

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

---

From: Natanael <[email-masked]>
Date: Fri, 12 Nov 2021 12:16:43 +0100

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

> [...]

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

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

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

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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 12 Nov 2021 12:03:49 -0000

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

> 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

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Fri, 12 Nov 2021 13:38:09 +0000

To me, having multiple signatures in one certificate is asking for troubles.

Using Dan's terminology: you want P chain of trust - ask for it, you want Q chain of trust - request that. In the unlikely case of wanting both - get both, AFAICT, the overhead would be small.

In practice, large PKI that have multiple intermediary CAs, will likely have separate CAs for P and Q certs.

<soapbox>Oh, speaking of how cert validation can be screwed up - how about validating email signatures in MS Outlook and Apple Mail? They totally ignore DN, and can only parse *one* SAN - because, hey, who's ever heard of a person with more than one email address, right?  And you expect P+Q certificates to be validated correctly? Oh well...</soapbox>
--
Regards,
Uri
 
There are two ways to design a system. One is to make is so simple there are obviously no deficiencies.
The other is to make it so complex there are no obvious deficiencies.
                                                                                                                                     -  C. A. R. Hoare

    ---Dan

---

From: "D. J. Bernstein" <[email-masked]>
Date: 13 Nov 2021 13:53:39 -0000

Blumenthal, Uri - 0553 - MITLL writes:
> Using Dan's terminology: you want P chain of trust - ask for it, you
> want Q chain of trust - request that. In the unlikely case of wanting
> both - get both, AFAICT, the overhead would be small.

Google's CECPQ1 experiment and the Google-Cloudflare CECPQ2 experiment
both combined P (ECC) with Q (the post-quantum option). The motivation
was clearly stated, and applies verbatim to signatures too:

   The post-quantum algorithm might turn out to be breakable even with
   today's computers, in which case the elliptic-curve algorithm will
   still provide the best security that today’s technology can offer.
   Alternatively, if the post-quantum algorithm turns out to be secure
   then it'll protect the connection even against a future, quantum
   computer.

The post-quantum situation since then hasn't become _less_ scary. We've
seen almost every NISTPQC submission losing security, often so much as
to be declared broken. Exciting new attacks are appearing, and the study
of post-quantum implementation failures is in its infancy. Why would it
be unlikely for people to want to combine post-quantum crypto with ECC?

If the answer is that NSA's declaration of confidence is influential:
This is where it would be valuable for CFRG to advise ECC integration
into all post-quantum deployments for the foreseeable future.

> And you expect P+Q certificates to be validated correctly?

I agree that certificate validation is a mess. This is why, regarding
the mechanisms for doing both P and Q, I'd expect that having a new
signature system _internally_ combining P+Q is safer than changing the
certificate-validation logic. I'm puzzled by NSA's unexplained
statements to the contrary. See also Mike's message.

> In practice, large PKI that have multiple intermediary CAs, will
> likely have separate CAs for P and Q certs.

Why? If a CA is interested in offering Q certificates, why would it not
want to provide

   * the extra security value of offering P+Q certificates (which are
     practically the same size as Q certificates) plus

   * the extra compatibility value of offering P certificates?

For the RSA->ECC upgrade there's (1) a stable ECC security picture and
(2) clear performance reasons to not have the ECC signatures accompanied
by RSA signatures. For the post-quantum upgrade, the story is reversed:
the post-quantum security picture isn't stable, and keeping ECC as a
security layer has low cost.

---Dan

---

From: Stephen Farrell <[email-masked]>
Date: Sat, 13 Nov 2021 14:57:15 +0000

Hiya,

I think I'm in general agreement with djb on this. One note
though...

On 13/11/2021 13:53, D. J. Bernstein wrote:
> I agree that certificate validation is a mess.

For protocols like TLS (likely to remain the most important
for quite a while) I don't think we need care about changes
to the web PKI for a much longer while. Maybe we should add
some PQC algorithm into some TLS handshakes soon, but there
is no need to change the PKI for that in the same timeframe.

In general, I'd be for slowing down much of this transition
stuff, and having CFRG opine to that effect might be a good
thing.

Cheers,
S.

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Sat, 13 Nov 2021 18:50:25 +0000

While I agree that updating TLS with new KEMs doesn't have to be done at the same time as we update the certificates, I don't believe we want to take too long.

One complication that certificates have over KEMs (in the context of TLS) is that there are more parties involved.  For the KEM, we need to update the client and the server; once we do that, the client will propose the updated postquantum 'groups', the server will accept that proposal and we are good to go.

In contrast, to update the certificate, we also need to get a third party involved (the CA, which needs to issue both the new postquantum certificate root, as well as the postquantum certificate to the servers - there may be even more parties involved, if the RAs are run by separate entities).  Because there are more parties involved that all need to be upgraded before we're protected, we can expect the timeframes to take longer.

Hence, even though postquantum authentication might appear to be a less urgent need, the task of upgrading could plausibly be expected to take longer.

-----Original Message-----
From: CFRG <[email-masked]> On Behalf Of Stephen Farrell
Sent: Saturday, November 13, 2021 9:57 AM
To: [email-masked]
Subject: Re: [CFRG] NSA vs. hybrid

Hiya,

I think I'm in general agreement with djb on this. One note though...

> I agree that certificate validation is a mess.

For protocols like TLS (likely to remain the most important for quite a while) I don't think we need care about changes to the web PKI for a much longer while. Maybe we should add some PQC algorithm into some TLS handshakes soon, but there is no need to change the PKI for that in the same timeframe.

In general, I'd be for slowing down much of this transition stuff, and having CFRG opine to that effect might be a good thing.

Cheers,
S.

---

From: Loganaden Velvindron <[email-masked]>
Date: Sun, 14 Nov 2021 09:33:58 +0400

I also tend to agree with Dr Bernstein's points. I hope to see more
transparency in the process.

On Sat, Nov 13, 2021 at 6:57 PM Stephen Farrell
<[email-masked]> wrote:
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Soatok Dreamseeker <[email-masked]>
Date: Sun, 14 Nov 2021 16:06:49 -0500

Hi Dan,

> security layer has low cost.

Coming from the world outside of academic cryptography, I expect more logic
bugs from software trying to validate separate P-chains and Q-chains than
with an additional, unified, P+Q signature scheme.

Additionally, why can't we define a unified mode that generates both
keypairs from a single random secret? i.e.

primary_seed := randombytes_buf(64) // store this

ed25519_seed := hash_sha512256(PREFIX_PREQUANTUM || primary_seed)

pq_seed := hash_sha512256(PREFIX_POSTQUANTUM || primary_seed)

ed25519_keypair := crypto_sign_seed_keypair(ed25519_seed)

pq_keypair := pqcrypto_sign_seed_keypair(pq_seed)

This turns a 512-bit secret into two distinct 256-bit seeds. For ed25519,
this can be the unclamped sk. For PQ, it can be a seed for a DRBG used to
generate the (sk, pk) pair.

Even if you can break ECC and recover the secret key, you would also need
to be able to preimage attack SHA512 from only half of its output. The
input being 512 bits is chosen to have a birthday bound at the 256-bit
security level.

Why would we do this? Because specifying a higher-level composite protocol
for signatures makes it less likely that implementors will get it wrong.

---

From: Jeff Burdges <[email-masked]>
Date: Sun, 14 Nov 2021 22:49:29 +0100

I agree with Dan here..  

It should become standard best practices that certificates for relatively young unproven primitives pair them with older proven primitives, and specify a correct hybrid protocol.  There exist exceptions of course, like protocols that intentionally tolerate a lower security level, but default best practice should be exactly what Dan describes.

It’s always possible logic bugs arise in validation code of course, but test vectors can trivially catch these bugs, assuming the certificate format specifies both key types and the hybrid protocol.  

It’s fairly clear separate P and Q certificate chains obstruct test vectors from enforcing this and invite more opportunities for downgrade attacks, etc. too.

It’s all trickier if you want the extreme algorithm agility of TLS of course, but not any harder than making separate P and Q certificate chains work correctly.  

Best,
Jeff

---

From: Loganaden Velvindron <[email-masked]>
Date: Mon, 15 Nov 2021 09:38:07 +0400

Apologies for my previous email. When I mentioned transparency, I was
referring to the NIST PQC
process.

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 15 Nov 2021 18:14:25 +0200

On Sun, Nov 14, 2021 at 10:49:29PM +0100, Jeff Burdges wrote:
> 
> It’s always possible logic bugs arise in validation code of course,
> but test vectors can trivially catch these bugs, assuming the
> certificate format specifies both key types and the hybrid protocol.

Catching those bugs may be far from trivial. Buggy signature
verification code might have false accepts that are not trivial to
generate, but still greatly weaken the security. One can not
catch those with test vectors.

I have not looked at if there are easy-to-make mistakes in
signature verification of NISTPQC candidates that would behave in
that way (not be obviously broken but still exploitable).

> It’s fairly clear separate P and Q certificate chains obstruct test
> vectors from enforcing this and invite more opportunities for
> downgrade attacks, etc. too.

IMO, The complexity of separate P and Q chain verification is
absolutely terrifying. As for downgrade attacks, it is not clear how to
deal with that even in theory, let alone in practice.

> It’s all trickier if you want the extreme algorithm agility of TLS of
> course, but not any harder than making separate P and Q certificate
> chains work correctly.  

Actually, separate chains do not work in TLS. The problem is that
there can be only one handshake signature and only one end entity
certificate, and thus only one CA signature for end-entity
certificate. 

-Ilari

---

From: Natanael <[email-masked]>
Date: Tue, 16 Nov 2021 22:17:18 +0100

> deal with that even in theory, let alone in practice.

Besides committing to the algorithm negotiation as in TLS 1.3 to prevent
regular downgrade attacks, there also needs to be a policy that post
quantum CA:s can only sign post quantum certs (or hybrid certs), and that
hybrid CA:s can ONLY sign hybrid certs up until some predefined transition
period has ended (under the assumption that the CA cert gets deprecated
then with hybrid requirement renewed if we're not yet certain of the
strength of post quantum algorithms).

If we feel certain enough at the end of that period that the post quantum
algorithm will hold, then it remains valid and gets to sign post quantum
only certs.

The next two problems are that nobody will agree on the length of that
period, and that CA rollover is still problematic (just see the recent
let's encrypt issues on older devices).

---

From: Dan Brown <[email-masked]>
Date: Thu, 18 Nov 2021 18:20:02 +0000

> D. J. Bernstein wrote (on Friday, November 12, 2021 4:28 AM)
>  ...
> 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.
> ...

I largely agree with the point above (as some might recall from my past CFRG 
messages).

Hybrid cryptography in IETF ought to be encouraged by CFRG. At minimum, hybrid 
ought to be an option for sensitive applications (high-value data, needing 
long-term protection), where the cost seems worth the benefit.  As an 
exception, an IETF WG with low-value, short-term data and little budget for 
cryptography, might opt for a single non-hybrid PQC algorithm option.

Real-time authentication (e.g., signature-based server authentication in TLS), 
might have less risk than other applications (e.g., TLS key exchange), because 
new attacks discovered in the future (e.g., relevant quantum computer) cannot 
retroactively break today's real-time authentication. Nonetheless, hybrid
signatures may still be worth the cost?

For certificate structuring, I don't know which is better: (1) certificates 
with hybrid-signatures, or (2) multiple certificates with a single-algorithm 
signatures (or (3)=(1)+(2)), but CFRG could contribute significantly to a 
recommendation on this issue (e.g. comments already made in this thread). 
Perhaps CFRG should defer this more protocol-specific detail to LAMPS?

Organizationally, NIST and IETF could continue to have some interoperable 
cryptography options, while working independently on non-interoperable 
cryptography options (i.e., hybrid interoperability ;).

Best regards,

Dan

PS. A simplistic cost-benefit approach to choosing hybrid cryptography:
https://eprint.iacr.org/2021/608
Better methods ought to be possible.   A discussion on this at
https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/OpFVbuMYk8c

----------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.