Warnings regarding cryptosystems

[latticerisks] 99pp. (PDF) NTRU Prime Risk-Management Team. "Risks of lattice KEMs." Date: 2021.10.31.

Lattice-based cryptography is much more risky than commonly acknowledged. This applies, in particular, to lattice KEMs under consideration within the NIST Post-Quantum Cryptography Standardization Project (NISTPQC) as of October 2021. The above document

• surveys recent attack advances;
• classifies ongoing risks, fully defining the following table;
• reviews incorrect claims that proofs control these risks;
• analyzes performance, since performance issues can exacerbate security risks; and
• compares the KEMs according to the official NISTPQC evaluation criteria.

submission	NTRU		NTRU Prime		SABER	Kyber	Frodo
KEM family	ntruhrss	ntruhps	sntrup	ntrulpr	saber	kyber	frodo
KEM	701	40961229	1277	1277	fire	1024	640
Basics
pk+ct bytes	2276	3684	3914	3822	2784	3136	19336
ct bytes	1138	1842	1847	1975	1472	1568	9720
errors	Noisy	Noisy	Rounded	Rounded	Rounded	Noisy	Noisy
Q or P	Quotient	Quotient	Quotient	Product	Product	Product	Product
modulus	8192	4096	7879	7879	8192	3329	32768
dimension	700	1228	1277	1277	1024	1024	640
first 2-norm	21.6	22.6	22.2	20.7	39.2	32.0	52.4
second 2-norm	21.6	28.6	29.2	29.2	75.0	32.0	52.4
log_2(Core-SVP)	136	301	270	271	260	256	150
ct/log_2 ratio	8.4	6.1	6.8	7.3	5.7	6.1	64.8
Known attack avenues not ruled out by theorems
lattices	risk	risk	risk	risk	risk	risk	risk
derandomization				risk	risk	risk	risk
decryption failures					165	174	138
structured lattices	risk	risk	risk	risk	risk	risk
cyclotomics	risk	risk			risk	risk
reducibility	risk	risk			risk	risk
quotients	risk	risk	risk
extra samples				risk	risk	risk	risk
non-QROM FO	risk	risk	risk	risk	risk	risk	risk
non-QROM 2				risk	risk	risk	risk
Known patent threats
patent 9094189				risk	risk	risk
patent 9246675				risk	risk	risk
Systemic risks
PKE instability	2019.04	2019.04	2016.05	2017.12	2019.04	2020.10	2019.04
instability	2019.04	2019.04	2019.04	2019.04	2019.04	2020.10	2019.04

Warnings regarding software

Beyond the warnings above regarding the definitions of cryptographic functions, the following warnings are regarding software meant to implement those functions.

At the moment, the most concise implementations of lattice-based cryptography are implementations in the Sage computer-algebra system. However, these implementations leak secret information through timing.

C implementations are sometimes designed

• to avoid data-dependent branches and array indices (for example, conditional swaps are computed by arithmetic rather than by branches) and
• to avoid other C operations that often take variable time (for example, divisions by 3 are computed via multiplications and shifts).

The C implementations for NTRU Prime are designed this way. However, there are at least some platforms where multiplications take variable time, and fixing this requires platform-specific effort; see https://www.bearssl.org/ctmul.html and https://research.tue.nl/en/studentTheses/a-performance-study-of-x25519-on-cortex-m3-and-m4. Furthermore, C compilers generally do not make any guarantees regarding timing. Compiled implementations need to be reviewed for constant-time behavior.

The TIMECOP tools automatically review compiled implementations for constant-time behavior. The C implementations for NTRU Prime pass TIMECOP with several different compiler options. However, other compiler options could break constant-time behavior, and there are ways that variable-time behavior could escape TIMECOP.

Implementations also need to be reviewed for correctness. There is a close match between the structure of

• the NTRU Prime specification,
• the NTRU Prime Sage reference implementation, and
• the NTRU Prime C reference implementation,

but this is only the starting point for review; it does not mean that adequate review has taken place. Furthermore, optimized implementations require extra review work. There are many examples of cryptographic software where tests, even quite expensive tests, fail to catch bugs.

SUPERCOP's checksums of outputs from the C implementations of NTRU Prime match checksums computed by pure Sage software, but this does not guarantee that the implementations match on other inputs, and it does not rule out the possibility of bugs shared between the implementations. There are automated tools verifying that some subroutines work correctly for all inputs, and automated tools verifying that some of the vectorized subroutines match the reference subroutines for all inputs, but other subroutines still need verification.

---

Version: This is version 2021.10.31 of the "Warnings" web page.