Re: [CFRG] What I want from the "KEM hybrids"

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

Filippo Valsorda writes:
> Speed is of the essence.

Indeed, attackers are already recording user data in the hopes of
decrypting it with future quantum computers:

   https://www.forbes.com/sites/andygreenberg/2013/06/20/leaked-nsa-doc-says-it-can-collect-and-keep-your-encrypted-data-as-long-as-it-takes-to-crack-it
   https://www.bbc.com/news/technology-25588605

Applications that haven't upgraded already should upgrade _right now_
from (e.g.) X25519 to X25519+KEM, for some choice of KEM that hopefully
resists quantum computers. Maybe the KEM will be broken---it's deeply
concerning to see how the security levels of lattice systems keep
dropping---but that possibility isn't an excuse for inaction; we should
be _trying_ to protect the confidentiality of user data.

> Every week between the day FIPS 203 is
> published and the day these hybrids are specified is pretty much
> directly pushing back deployment.

Note that waiting for FIPS 203 in the first place is also pushing back
deployment. There's a specific reason that choosing Kyber has been
creating this type of delay for years: the text of

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

indicates that NIST has a patent license only for the exact version of
Kyber that has appeared in a "NIST Special Publication or Federal
Information Processing Standard". NIST modified round-3 Kyber to produce
a draft of FIPS 203; hasn't issued FIPS 203 yet; hasn't said that FIPS
203 will match the draft; and, despite my December 2022 question on this
point, hasn't published the license's definition of "EFFECTIVE DATE". So
any application using Kyber today could easily be outside the license.

Furthermore, Yunlei Zhao said in

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

that "Kyber is covered by our patents". Those patents (for example,
https://patents.google.com/patent/CN107566121A/en) predate Kyber and
haven't seen any comments from NIST. There's a clear inventive for
companies to wait to see a buyout of those patents or a convincing
public analysis of why these patents _don't_ cover Kyber.

Of course, big enough companies can go ahead without serious risks since
they won't be put out of business by a patent lawsuit, and then patent
holders have a clear incentive to act within six years in the U.S. (see
https://www.law.cornell.edu/uscode/text/35/286) three years in China,
etc. But this doesn't guarantee safety after that period, and having
smaller companies wait for years on deployment is a security problem.

There are alternatives that as far as we know are patent-free and that
applications can simply roll out right now, such as NTRU-HRSS. But this
says something important about combiner design: we want a combiner that
isn't going to fail when Kyber is replaced with an alternative.

It's already well known how to achieve this: simply have the combiner
hash the transcript. The combiner is then simply asking the input KEM to
be IND-CCA2, which is exactly what most KEMs were explicitly designed to
achieve.

X-Wing doesn't hash the transcript. This creates unnecessary load on
security reviewers to figure out what happens if Kyber is replaced with
NTRU-HRSS, and---if the result is a security disaster, or if security is
unclear---to split efforts between a Kyber-specific combiner and a safer
combiner. So X-Wing should be changed to hash the transcript.

To be clear, many KEMs have been shown to _not_ provide IND-CCA2. See
https://cr.yp.to/papers.html#qrcsp for statistics. But asking KEMs for
further security properties beyond the standard IND-CCA2 property makes
failures even more likely.

---D. J. Bernstein