Cold Boot Attacks on Ring and Module LWE Keys Under the NTT

Martin R.  Albrecht; Amit Deo; Kenneth G.  Paterson

Paper 2018/672

Cold Boot Attacks on Ring and Module LWE Keys Under the NTT

Martin R. Albrecht, Amit Deo, and Kenneth G. Paterson

Abstract

In this work, we consider the ring- and module- variants of the LWE problem and investigate cold boot attacks on cryptographic schemes based on these problems, wherein an attacker is faced with the problem of recovering a scheme's secret key from a noisy version of that key. The leakage resilience of cryptography based on the learning with errors (LWE) problem has been studied before, but there are only limited results considering the parameters observed in cold boot attack scenarios. There are two main encodings for storing ring- and module-LWE keys, and, as we show, the performance of cold boot attacks can be highly sensitive to the exact encoding used. The first encoding stores polynomial coefficients directly in memory. The second encoding performs a number theoretic transform (NTT) before storing the key, a commonly used method leading to more efficient implementations. We first give estimates for a cold boot attack complexity on the first encoding method based on standard algorithms; this analysis confirms that this encoding method is vulnerable to cold boot attacks only at very low bit-flip rates. We then show that, for the second encoding method, the structure introduced by using an NTT is exploitable in the cold boot setting: we develop a bespoke attack strategy that is much cheaper than our estimates for the first encoding when considering module-LWE keys. For example, at a \(1\%\) bit-flip rate (which corresponds roughly to what can be achieved in practice for cold boot attacks when applying cooling), a cold boot attack on Kyber KEM parameters has a cost of \(2^{43}\) operations when the second, NTT-based encoding is used for key storage, compared to \(2^{70}\) operations with the first encoding. On the other hand, in the case of the ring-LWE-based KEM, New Hope, the cold boot attack complexities are similar for both encoding methods.

Note: full version including proof of concept code snippets

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in TCHES 2018
Keywords: cold boot attack lattice reduction number theoretic transform post-quantum cryptography ring learning with errors module learning with errors
Contact author(s): amit deo 2015 @ rhul ac uk
History: 2018-07-13: received
Short URL: https://ia.cr/2018/672
License: CC BY

BibTeX

@misc{cryptoeprint:2018/672,
      author = {Martin R.  Albrecht and Amit Deo and Kenneth G.  Paterson},
      title = {Cold Boot Attacks on Ring and Module LWE Keys Under the NTT},
      howpublished = {Cryptology ePrint Archive, Paper 2018/672},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/672}},
      url = {https://eprint.iacr.org/2018/672}
}