Re: [saag] SSH & Ntruprime

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

I'm a member of the NTRU Prime team (and the Classic McEliece team and
the SPHINCS+ team) but am speaking for myself in this message.

The elephant in the room is the patent minefield surrounding Kyber. NIST
says it has bought Kyber licenses for the two oldest patent families, but

   * those licenses are only for exactly what NIST ends up standardizing
     (supposedly the standards will appear this year), so IETF doesn't
     have change control---for example, if security continues to degrade
     (as I expect it will), then presumably IETF will consider modifying
     Kyber to provide security levels beyond Kyber-1024, but this would
     go beyond what's allowed by the licenses; and

   * there are other patents in the area, including at least one patent
     holder publicly claiming Kyber coverage, with no public response
     from NIST or from the Kyber team.

To quickly see the change-control problem, look at the last paragraph of
the text posted by NIST here:

   https://web.archive.org/web/20221130033932/https://csrc.nist.gov/csrc/media/Projects/post-quantum-cryptography/documents/selected-algos-2022/nist-pqc-license-summary-and-excerpts.pdf

I should note that NIST hasn't posted the full signed licenses---it
labeled this text as edited excerpts from the licenses---so the actual
licenses might say something different. Seeing this possibility raises
even more questions and falls far short of ensuring change control.

To see another patent holder claiming Kyber coverage, look at

   https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/Fm4cDfsx65s/m/F63mixuWBAA

saying "Kyber is covered by our patents". The author of that message
holds patents CN107566121 etc., filed before Kyber was published.

There is ample evidence that the patent minefield has been to some
extent delaying and to some extent deterring deployment of Kyber (which,
obviously, means delaying and deterring post-quantum deployment _if_
people don't use other post-quantum systems). For example: NIST's
deadline for round-3 input was October 2021, but NIST did not announce
its Kyber selection until July 2022. NIST said in

   https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/fvnhyQ25jUg/m/izNIg5BABwAJ

that "the delay is not due to technical considerations". NIST's July
2022 report

   https://nvlpubs.nist.gov/nistpubs/ir/2022/NIST.IR.8413.pdf

said that "Issues relating to patents were a factor in NIST's decision
during the third round as NIST became aware of various third-party
patents. As noted in Section 2.2.3, NIST negotiated with several third
parties to enter into various agreements to overcome potential adoption
challenges posed by third-party patents" and said that "If the
agreements are not executed by the end of 2022, NIST may consider
selecting NTRU instead of KYBER". NIST's announcement in November 2022
that it had signed some licenses for Kyber didn't settle the issue, as
illustrated by

   https://datatracker.ietf.org/meeting/116/materials/slides-116-pquip-patents-and-pqc-00

in March 2023 stating the following: "Some people have said in private
that they are very worried about the patents and may not be able to
implement CRYSTALS-KYBER". Some large companies have announced Kyber
applications since then, but smaller companies can be put out of
business by patent lawsuits.

IETF's IPR policy (https://datatracker.ietf.org/doc/rfc8179/) includes
the following two statements:

   In general, IETF working groups prefer technologies with no known IPR
   claims or, for technologies with claims against them, an offer of
   royalty-free licensing. ... An IETF consensus has developed that no
   mandatory-to-implement security technology can be specified in an
   IETF specification unless it has no known IPR claims against it or a
   royalty-free license is available to implementers of the
   specification.

Working groups can make exceptions to the first statement "if they feel
that this technology is superior enough to alternatives with fewer IPR
claims or free licensing to outweigh the potential cost of the
licenses", and can make exceptions to the second statement if there is a
"very good reason to do so and if that reason is documented and agreed
to through IETF consensus". If these exceptions are applicable, and if
the change-control requirement can somehow be met, then it might be
possible for IETF to go ahead with Kyber without violating IETF's IPR
policy. But unpatented alternatives are playing a big role in real-world
efforts to protect user data against future quantum computers, and
should play a similarly major role in IETF's post-quantum activities.

Paul Wouters writes, regarding sntrup:
> It's not broken but the IETF Crypto Panel also said the cryptographic
> method used was somewhat dated and would no longer be recommended by
> the larger cryptographic community at this point.

Hmmm. No citation is provided here, and readers are forced to wonder
whether this could possibly be an accurate summary of a review from the
Crypto Review Panel:

   * Whatever exactly this claim about the "community" is supposed to
     be referring to (let me guess: NIST and other Kyber supporters who,
     in fact, never recommended sntrup in the first place?), attributing
     this (fictional) evolution of positions to the "community" clearly
     isn't consistent with the word "objective" in the panel charter.

   * Similarly, whatever exactly the claim about "dated" is supposed to
     be referring to, why is this being described with the negative word
     "dated" rather than, say, "having been studied for longer" or "more
     stable" or "less likely to be covered by patents"? This again isn't
     consistent with the word "objective" in the panel charter.

Content-wise, these "dated" and "community" claims appear to be
insinuating that sntrup has held up worse from a security perspective
than other lattice KEMs. That's simply not true. The actual situation is
as follows:

   * Attack advances have degraded security levels for all lattice
     KEMs---including sntrup, definitely, but also including Kyber.

   * sntrup offers parameters with larger security margins than Kyber
     does, and has consistently refused to provide anything as small as
     Kyber-512.

   * Kyber has repeatedly had security patches---I'm not just talking
     about https://kyberslash.cr.yp.to, but about non-interoperable
     design changes in response to flaws identified in Kyber's earlier
     security analyses---while sntrup has never needed any.

   * Some security claims for specific proposals of lattice KEMs have
     been broken outright by attacks that were already proactively
     blocked by clear sntrup design features.

References: https://ntruprime.cr.yp.to/latticerisks-20211031.pdf;
https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/o2roJXAlsUk/m/EHW9h87kAAAJ;
https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/YsGkKEJTt5c/m/V0eivEroAAAJ;
https://cr.yp.to/papers.html#lprrr; https://cr.yp.to/papers.html#hila5;
https://eprint.iacr.org/2020/241.

What did the Crypto Review Panel actually say about sntrup? A search
finds

   https://mailarchive.ietf.org/arch/msg/crypto-panel/kDiLLcVOhwoix5BUDdv4r91ZhfY/

whose comments about sntrup (1) are purely political and (2) fail to say
anything about patents. Here are the comments:

   It is true that sntrup was a rather popular candidate during the
   first years of the NIST Post-Quantum Cryptography (PQC)
   standardization process. However, the situation is much different
   since the NIST report on round-3 candidates [NISTR3]. sntrup was not
   selected for standardization, nor as a part of round-4 candidates for
   possible late standardization.  Knowing that an official FIPS
   post-quantum KEM standard (ML-KEM) will be soon released, it is not
   clear why the authors are focusing on sntrup and this should be then
   motivated.

In context, the "rather popular" claim here seems to be referring to the
wide deployment already mentioned in the draft, but then how exactly did
NIST's round-3 report (selecting Kyber and de-selecting all other
lattice systems) supposedly change the situation? Is there any actual
content to the above "review" of sntrup beyond delegating IETF/IRTF
cryptographic decisions to NIST?

Maybe I've missed some other Crypto Review Panel text on topic, but this
doesn't appear to be "critical, objective, timely and consistent review
of cryptographic algorithms". The failure to consider patents is a clear
error and seems impossible to reconcile with IETF's IPR policy. It's not
as if the patent situation is some sort of secret.

Procedurally, I'm not sure what the right way forward is here. Maybe the
Crypto Review Panel should be asked to scrap this "review" and evaluate
the patent situation. Of course, IETF and IRTF can't make decisions on
patent validity, but IETF and IRTF _can_ observe that there are enough
patent questions around Kyber to justify standardizing other options.

---D. J. Bernstein