Cryptology ePrint Archive: Report 2018/672

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

Martin R. Albrecht and 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.

Category / Keywords: public-key cryptography / cold boot attack, lattice reduction, number theoretic transform, post-quantum cryptography, ring learning with errors, module learning with errors

Original Publication (with minor differences): IACR-CHES-2018

Date: received 12 Jul 2018

Contact author: amit deo 2015 at rhul ac uk

Available format(s): PDF | BibTeX Citation

Note: full version including proof of concept code snippets

Version: 20180713:140713 (All versions of this report)

Short URL: ia.cr/2018/672

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]