Re: [Pqc] Mapping the state of PQC and IETF - ssh

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

Kampanakis, Panos writes:
> OpenSSH supports X25519+SNTRU for some time now. SNTRU is a
> quantum-safe algorithm that got eliminated earlier in the NIST PQ
> process.

The timeline was actually as follows:

   * 2022.02: OpenSSH 8.9 enabled [e-mail] on
     the server by default (after experimental support before that).
     https://www.openssh.com/txt/release-8.9

   * 2022.04: OpenSSH 9.0 enabled [e-mail] as
     the default choice by the client.
     https://www.openssh.com/txt/release-9.0

   * 2022.07: NIST announced selection of Kyber as its only lattice KEM,
     and its only KEM option for the moment. (NIST announced that it
     would continue to consider BIKE, Classic McEliece, HQC, and SIKE in
     the next round; SIKE was then broken.) This is when NIST eliminated
     NTRU (e.g., ntruhrss701) and NTRU Prime (e.g., sntrup761).

   * 2022.11: Google announced deployment of ntruhrss701+X25519 for all
     of its internal communication.
     https://cloud.google.com/blog/products/identity-security/why-google-now-uses-post-quantum-cryptography-for-internal-comms

The available evidence (see https://nist.pqcrypto.org/foia/index.html)
suggests that NIST actually selected Kyber in 2021.12, but then delayed
the announcement for several months trying to deal with patents. I'm
saying "trying" here because the patent situation is still a mess:

   * NIST's patent buyouts don't activate until after NIST issues its
     Kyber standard (currently predicted to be 2024---probably there
     will be a draft standard early summer 2023);

   * NIST's buyouts are only for _exactly the version of Kyber in that
     standard_ (patching security problems would require new buyouts);
     and

   * NIST doesn't appear to have analyzed whether Kyber is safe from the
     other five patent families that were already identified on GAM/LPR
     systems. (See https://ntruprime.cr.yp.to/faq.html.)

NIST's 2022.07 report said that NIST could still select NTRU as the
patent-free option if something went wrong with patents. NIST retracted
this after the buyout agreements were signed. (This could be undertsood
as saying the other patent families aren't an issue, but by default I'd
chalk this up to NIST not realizing how courts stretch patents.)

NIST could instead have issued a 2021 announcement encouraging immediate
deployment of NTRU. NIST's report said that "the overall performance of
any of these KEMs would be acceptable for general-use applications" and
that NIST finds Kyber's security "marginally" more convincing than
NTRU's security. "Marginally" is an awfully thin rationale for diving
into a patent minefield and delaying post-quantum deployment until 2024.

It's important to remember that attackers systematically collect user
data and keep it in the hopes of decrypting it later:

   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/

Delaying post-quantum deployment means security damage.

> There was nothing wrong with it, it just didn't move forward,
> so there will be no final spec for it.

NTRU Prime already has a complete specification and a Sage reference
implementation (see https://ntruprime.cr.yp.to) along with the deployed
software. Every detail of the internal PKE stabilized five years ago,
and every remaining KEM detail stabilized four years ago.

Obviously _NIST_ isn't about to issue an NTRU Prime specification, but
IETF and IRTF aren't bound by what NIST does. When NIST's standards
aren't in line with IETF priorities, IETF sets its own standards, as
illustrated by the usage of Curve25519 in IETF standards for several
years (starting with an IRTF informational spec, preceded by a detailed
CFRG investigation of options) before NIST finally managed to issue a
Curve25519 standard in 2023.

For post-quantum cryptography, there's a security problem _right now_,
and IETF should endorse taking action _right now_ in response. Given the
patent situation, this isn't compatible with following NIST.

> Also, OpenSSH currently does not support ECDH+PQ for "quantum-safe
> FIPS" compliance. 

I'm not sure exactly which distinction you're drawing here, but I'd
suggest that the top priority should be protecting users, even if this
is negatively correlated with FIPS compliance.

> Although it is a great that OpenSSH was an early adopter, in the long
> run it makes sense to standardize on a consensus-based, peer-reviewed
> spec

The Kyber and NTRU Prime specs have both undergone peer review. This is
more meaningful for NTRU Prime than for Kyber, for two basic reasons:
(1) Kyber has a larger attack surface; (2) the Kyber design is a moving
target, for example with discoveries of flaws in the security analysis
leading to cryptosystem modifications 4 years ago and 2.5 years ago.

As for "consensus-based", the process of reaching consensus in IETF
starts with IETF investigation of the merits of the options at hand.
Seeing deployment of various options can provide indirect information
but shouldn't substitute for an IETF investigation.

> instead of complying with the choices one widely-used
> implementation made. 

OpenSSH's deployment of post-quantum cryptography began with TinySSH
from Jan Mojzis. Two implementations of a protocol are sufficient for
IETF standardization.

There's security value in focusing cryptographic review on a limited
number of options, but, given the GAM/LPR patent minefield, IETF and
IRTF shouldn't restrict attention purely to GAM/LPR cryptosystems such
as Kyber.

> Currently SSH is an orphan protocol; there is no IETF WG to work on it
> and PQUIP will not do any standardizations.

I would like to see the X25519+PQ hybrids specified centrally so that
they don't require protocol-specific work.

---D. J. Bernstein