Re: [Pqc] Listing pointers to not-yet-standardized PQC algorithms

["D. J. Bernstein" <[e-mail]>]

Paul Hoffman writes:
> NIST has said that it will publish standards for CRYSTALS-Kyber,
> CRYSTALs-Dilithium, Falcon, and SPHINX+ next year, and has more
> informally said that it will publish standards for other KEM finalists
> (Classic McEliece, BIKE, and HQC).

No, this is going beyond what NIST has said and could easily turn out to
be wrong in various ways.

For example, NIST IR 8413 says, regarding Classic McEliece, BIKE,
HQC, and SIKE, that NIST "anticipates standardizing at least one of them
at the conclusion of the fourth round", and says that NIST "may select
at most one" of BIKE and HQC.

Obviously SIKE is no longer under consideration. This doesn't mean that
NIST is going to standardize all of the rest. "Anticipates" isn't even a
promise to standardize _anything_. NIST also hasn't committed to any
particular schedule for issuing draft standards and final standards for
Kyber, Dilithium, Falcon, and SPHINCS+; there are only estimates.

I'm one of the members of the Classic McEliece team. I'm happy that NIST
is _considering_ Classic McEliece standardization, and I'm happy to see
Classic McEliece already rolled out to protect users in, e.g., Mullvad
and Rosenpass. It's important for this information to be tracked
accurately---no exaggerations.

I'm also on the NTRU Prime team and the SPHINCS+ team, and I'm happy to
see the deployment of NTRU Prime starting in TinySSH and continuing with
OpenSSH. It's important to note, however, that lattices have lost much
more security than Classic McEliece has, and the latest advances in
lattice attacks certainly aren't the end of the story. See generally
https://ntruprime.cr.yp.to/warnings.html.

> FrodoKEM is being standardized in ISO.

Hmmm. https://frodokem.org/ says

   October, 2022: ISO/IEC JTC 1/SC 27/WG 2 establishes a preliminary
   work item to consider standardization of FrodoKEM.
   April, 2023: ISO/IEC JTC 1/SC 27/WG 2 has agreed to move forward with
   the standardization of FrodoKEM as an approved mechanism in a
   revision of ISO/IEC 18033-2, Encryption algorithms — Part 2:
   Asymmetric ciphers.

but

   https://web.archive.org/web/20230401090854/https://secdev.ieee.org/wp-content/uploads/2022/10/LaMacchia-Keynote-IEEESecDev2022.pdf

gave a strikingly different description of what happened in October,
with FrodoKEM as just one of multiple options:

   Last week ISO/IEC JTC1/SC27/WG2 approved a Preliminary Work Item
   “Inclusion of key encapsulation mechanisms for Post-Quantum
   Cryptography in ISO/IEC standards”
   * Solicited comments on proposed inclusion of FrodoKEM, Classic
   McEliece, and CRYSTALS-Kyber

As a procedural matter, ISO work items go through multiple layers of
votes and can fail to produce ISO standards. The same ISO working group
had, for example, a work item for NSA's Simon and Speck ciphers; those
didn't meet ISO's minimum requirements for ciphers and were ultimately
rejected. Furthermore, ISO activities aren't public by default---it's
not as if there are ISO web pages where the public can see what's
actually going on. Claims that ISO is standardizing X should thus be
treated with caution.

> Should this WG let IETF developers know about these algorithms?
> If so, how do we bound this list to prevent us from promoting
> MyMostlyUnreviewedKEM without enough context?

Please clarify. How is "mostly unreviewed" evaluated? Concretely, would
SIKE a year ago count as "mostly unreviewed"?

Kampanakis, Panos writes:
> Crypto developers are following NIST's work and there are plenty of
> resources that explain what these algorithms are. I don't see a
> benefit in encyclopedically documenting something that have been
> documented many times before. 

I agree. There are many redundant post-quantum overviews from people and
organizations that feel the need to prove that they're doing something.
PQUIP shouldn't be following that path; it should instead be looking at
what IETF should be doing to protect users.

The charter says that PQUIP is supposed to "facilitate the evolution of
IETF protocols" with respect to post-quantum cryptography. Comments on
various post-quantum algorithms have already played a role in various
IETF discussions; having PQUIP collect this information centrally would
reduce the risk of error and the risk of missing more suitable options.

> Frodo is in the LWE family. It is not RLWE or MLWE, so as a primitive
> it has less structure and could be assumed to be more conservatively
> secure

It's not that simple.

Yes, adding structure adds to the security risks of lattices, as
illustrated by the quantum polynomial-time break (and non-quantum
subexponential-time break) of Gentry's original STOC 2009 FHE system for
power-of-2 cyclotomic fields. Yes, the core of FrodoKEM avoids this
source of added security risks.

However, it's a mistake to equate the security of the FrodoKEM core with
the security of FrodoKEM. For example, FrodoKEM's security claims were
disproven in https://cr.yp.to/papers.html#lprrr, which uses just 2^88
guesses, a feasible computation, to break one out of 2^40 ciphertexts
for a FrodoKEM-640 public key. Nothing so efficient has been published
against Kyber-512: the attack exploits aspects of FrodoKEM-640 that
aren't shared by Kyber-512.

FrodoKEM-1344, the largest proposed FrodoKEM size, is big enough to
solidly avoid the problem exploited in that paper, and overall I think
it has somewhat lower risks than Kyber-1024. But the situation isn't
that FrodoKEM is simply Kyber minus structure; comparing risks requires
looking at many further cryptographic details.

> The Frodo public key and ciphertext are pretty big.

I think that basic size numbers (e.g., 9616 bytes for a frodokem640
public key or 21520 bytes for a frodokem1344 public key) are already
very easy for people to find, although they might still be useful for
PQUIP to collate if there's reason to think that people in IETF are
missing those numbers.

> NIST's schemes offer better size-performance balance and math
> primitive family diversity.

Sorry, can you please clarify what "NIST's schemes" and
"size-performance balance" mean here?

> IETF should only go with primitives that make sense for use in its
> WGs. I am not sure I would pick Frodo over Kyber or BIKE in any
> use-cases.

If the only choices available were Frodo and Kyber then I would take
FrodoKEM-1344 _except_ for applications where FrodoKEM-1344 has been
conclusively demonstrated to be unaffordable.

Yes, FrodoKEM-1344 has tens of kilobytes in public keys and ciphertexts;
but the average web page is already over 2MB, and video now dominates
Internet traffic. Future users will have trouble understanding why NIST
was putting so much weight on performance, and specifically why NIST was
claiming that FrodoKEM isn't a "general-purpose" KEM.

FrodoKEM also appears to be freely usable today, whereas Kyber doesn't.
For example, the license that NIST signed for U.S. patent 9246675 hasn't
activated yet, and I haven't seen any public analysis of the impact of
Chinese patent 107566121.

As for BIKE, an argument for BIKE over FrodoKEM is that lattice security
levels are generally harder to analyze and less stable than code
security levels. On the other hand, BIKE's quasi-cyclic structure incurs
security risks that are analogous to the risks of using number fields to
build lattices; and BIKE's security relies on a hard-to-analyze question
regarding the failure rate of the specific decoder used in BIKE. So it's
not as if BIKE is a clear winner over FrodoKEM.

There are other KEMs that should also be considered, but I don't see how
any of the comparisons add up to a clear conclusion to ignore FrodoKEM.
The way NIST reached that conclusion was by starting from an unfounded
claim that FrodoKEM does not have "acceptable performance in widely used
applications overall".

Blumenthal, Uri - 0553 - MITLL writes:
> I vote with Panos here. No to both.

Please note that IETF discourages voting while encouraging attention to
technical comments and resolution of objections. See RFC 7282.

Mike Ounsworth writes:
> I see this list / github page as an index of *IETF* PQC work. Trying
> to document the PQC work in general beyond the IETF seems it is both
> not the IETF's responsibility, as well as a never-ending task.

I agree that PQUIP should be focusing on what's helpful for IETF.

Attackers are collecting ciphertexts _right now_ in the hope of
decrypting them with a future quantum computer. IETF can and should take
action in response. Having general IETF post-quantum strategy analysis
spread haphazardly across many protocol-specific lists slows this down.
PQUIP can usefully centralize and accelerate this analysis.

Florence D writes:
> I think we should focus on the NIST algorithms.

To clarify, does "the NIST algorithms" here mean only one KEM, namely
Kyber, plus three signature algorithms?

I'm specifically trying to figure out whether "the NIST algorithms"
matches what Panos was referring to in "NIST's schemes offer better ...
math primitive family diversity".

I would think that the "diversity" argument is an argument against
focusing on just one KEM, but the ambiguities in the terminology of
"NIST algorithms"/"NIST's schemes" seem to be obscuring this.

> These have been
> selected due to their security and usability and these are the
> features that IETF should be looking for when incorporating algorithms
> into our protocols.

Security was certainly job #1. That's why NIST prioritized the strongest
candidates _except_ for applications that need something more efficient.

Oops, sorry, no, it was the other way around. For example:

   * NIST IR 8309 said that NIST would delay SPHINCS+ _unless_ "NIST's
     confidence in better performing signature algorithms is shaken by
     new analysis".

   * NIST's confidence was then sufficiently shaken by attacks that NIST
     IR 8413 included SPHINCS+ in NIST's first round of selections---but
     NIST continued prioritizing efficiency over security, as
     illustrated by NIST recommending Dilithium "as the primary
     algorithm to be implemented".

See https://cr.yp.to/talks.html#2022.12.29 for further history, the same
oops, and relevant URLs.

It's important to be clear about how much weight NIST put upon factors
other than security---including usability factors that IETF is better
positioned than NIST to evaluate. IETF is also subject to more stringent
constraints than NIST is: for example, BCP 188 says

   Pervasive monitoring is a technical attack that should be mitigated
   in the design of IETF protocols, where possible. ... The IETF Will
   Work to Mitigate Pervasive Monitoring

which is very different from accepting years of patent-related delays,
and BCP 25 says

   The IETF must have change control over the technology described in
   any Standards Track IETF Documents in order to fix problems that may
   be discovered or to produce other derivative works.

which is very different from accepting a license that disallows any
"modification, extension, or derivation of the parameters of the PQC
ALGORITHM".

> If we start pointing to other algorithms then this group would need to
> start weighing up their security and relative merits outside of NIST's
> process, which is not in our remit.

Hmmm.

The charter says that PQUIP will not "assess whether a given
cryptographic mechanism is quantum-resistant" but will instead "rely on
outside entities (e.g., CFRG) to define and assess new PQC mechanisms".

I don't see how the charter gives any special authority to NIST on this
point. The charter mentions NIST, but only as part of a parenthetical
note giving two examples of work outside IETF to "develop and validate"
post-quantum mechanisms.

Realistically, abdicating to NIST regarding the selection of a KEM means
further delay in broad post-quantum deployment. Attackers collecting
today's ciphertexts, hoping to decrypt them with a future quantum
computer, are very happy with this delay. I don't see how this path is
compatible with BCP 188.

---D. J. Bernstein