libntruprime
libntruprime: Security

Lattice-based cryptography is dangerous. Fast attacks have been demonstrated breaking, e.g., Compact LWE, HILA5, and Round2, all of which were small lattice-based cryptosystems submitted to the NIST post-quantum competition. The supposedly well-studied problems at the heart of all lattice-based cryptosystems continue to lose security. The "constant-time" reference software for Kyber (ML-KEM) has had two rounds of security patches for two different timing attacks demonstrated to be exploitable.

Unlike most proposals of lattice-based cryptosystems, sntrup acknowledges lattice risks and is designed accordingly. Furthermore, the sntrup software in libntruprime includes state-of-the-art defenses against timing attacks. But small lattice-based cryptosystems, even when carefully designed, remain dangerous, both at the mathematical level and at the software level. When you're deploying post-quantum cryptography, make sure to deploy it as an extra layer of encryption on top of your existing use of ECC, not as a replacement for ECC.

One risk for libntruprime is the risk of bugs getting past the libntruprime tests. The main defense in progress is software verification. Until verification is complete, libntruprime is limiting code size: it includes general AVX2 optimizations but skips the software from nine publications with further sntrup speedups.

Regarding timing attacks: libntruprime is designed to avoid all data flow from secret data to memory addresses and branch conditions. libntruprime uses operations that naturally avoid such data flow, and includes valgrind tests (based on TIMECOP from SUPERCOP) designed to catch any such data flow introduced by compilers. Fully protecting the user against timing attacks requires addressing more issues, such as the following:

See https://timing.attacks.cr.yp.to for a timing-attack survey and many references.

Speculative-execution attacks: Some countermeasures against speculative-execution attacks are planned but are not included in the current version of libntruprime. Full protection again requires addressing issues at other system layers.

Further side-channel attacks: Even if all legitimate user sensors are successfully kept isolated from attackers, attackers can set up their own power sensors, electromagnetic sensors, acoustic sensors, etc. Keeping cryptographic operations physically separated from sensors tends to make such attacks much more expensive but is often infeasible. "Masking" cryptographic computations seems to help and can be affordable, although the security of masking is difficult to evaluate and there are many broken masked implementations. Currently libntruprime does not include any masked implementations, so presumably it is easily breakable by power attacks in environments where attackers can see power consumption.

Further attacks: Presumably libntruprime is easily breakable by fault attacks in environments where attackers can trigger faults. Beyond attacker-triggered faults, natural DRAM faults occur surprisingly often. Implicit rejection fails to provide IND-CCA2 security when DRAM faults corrupt the secret key used for implicit rejection, although attacks can be stopped by "plaintext confirmation", another layer of defense included in sntrup. Error correction is in any case recommended (and often not provided by hardware), and there is a general-purpose libsecded library that applies error correction to any array, although this does not catch errors that occur during computations.


Version: This is version 2024.08.15 of the "Security" web page.