FrozenTRU: Cold Boot Attacks on NTRU-Based Hash-and-Sign Signatures
TL;DR
This paper investigates cold boot attacks against NTRU-based signature scheme Falcon and its ancestor, the signature scheme of Ducas–Lyubashevsky–Prest (DLP), and proposes countermeasures with negligible computational cost that significantly reduce the memory footprint of signing keys for Falcon and DLP, and at the same time make cold boot attacks considerably harder.
Abstract
Cold boot attacks, first introduced by Halderman et al. (USENIX’08), are a class of attacks that aim at recovering cryptographic secrets stored in volatile memory after a computer is powered off, using the fact that DRAM modules retain their contents to a large extent for some time, especially at low temperatures. Cold boot attackers can recover the original contents of memory with some flipped bits, with bit flip probabilities of < 10% for one-to-zero and much lower (< 0.1%) for zero-to-one shown to be easily achievable. The cryptanalytic goal is then to recover full secret keys based on this noisy data. Successful key recoveries from cold boot attacks have been shown to be feasible for various symmetric and public-key schemes, including AES, RSA, and more recently some lattice-based encryption schemes with secret keys stored in the number-theoretic transform (NTT) domain.In this paper, we investigate cold boot attacks against NTRU-based signature scheme Falcon and its ancestor, the signature scheme of Ducas–Lyubashevsky–Prest (DLP). Those schemes significantly differ from other schemes previously considered for cold boot attacks, since, in particular, the memory representation of secret signing keys mostly consists of floating point values. As a result, the various relations existing between key coefficients only hold up to floating point errors, which makes key recovery more complex. Nevertheless, at the typical bit flip probabilities achievable with cold boot attacks, we manage to fully recover Falcon and DLP keys with good probability across all parameters in simulations carried out in a simple bit flip model. Furthermore, we validate our techniques using concrete cold boot experiments against Falcon on a Raspberry Pi single board computer.Finally, we propose countermeasures with negligible computational cost that significantly reduce the memory footprint of signing keys for Falcon and DLP, and at the same time make cold boot attacks considerably harder.