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.