Single-Trace Side-Channel Attacks on Masked Lattice-Based Encryption
Although lattice-based cryptography has proven to be a particularly efficient approach to post-quantum cryptography, its security against side-channel attacks is still a very open topic. There already exist some first works that use masking to achieve DPA
- PDF / 1,932,027 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 62 Downloads / 184 Views
Abstract. Although lattice-based cryptography has proven to be a particularly efficient approach to post-quantum cryptography, its security against side-channel attacks is still a very open topic. There already exist some first works that use masking to achieve DPA security. However, for public-key primitives SPA attacks that use just a single trace are also highly relevant. For lattice-based cryptography this implementationsecurity aspect is still unexplored. In this work, we present the first single-trace attack on lattice-based encryption. As only a single side-channel observation is needed for full key recovery, it can also be used to attack masked implementations. We use leakage coming from the Number Theoretic Transform, which is at the heart of almost all efficient lattice-based implementations. This means that our attack can be adapted to a large range of other lattice-based constructions and their respective implementations. Our attack consists of 3 main steps. First, we perform a template matching on all modular operations in the decryption process. Second, we efficiently combine all this side-channel information using belief propagation. And third, we perform a lattice-decoding to recover the private key. We show that the attack allows full key recovery not only in a generic noisy Hamming-weight setting, but also based on real traces measured on an ARM Cortex-M4F microcontroller. Keywords: Lattice-based cryptography · Side-channel analysis · Singletrace attack · Number theoretic transform
1
Introduction
The current public-key infrastructure is threatened by progress towards largescale quantum computing. Constructions based on RSA, DLP, or ECC, will succumb to Shor’s algorithm [32], which is able to defeat these systems in polynomial time. While estimates on the availability of powerful enough quantum computers vary greatly–they range from 15 years [18] to never [31]–the threat is still taken very seriously. This is demonstrated by, e.g., NIST’s current call for post-quantum secure proposals [19] and official recommendations regarding post-quantum security from the NSA [20]. c International Association for Cryptologic Research 2017 W. Fischer and N. Homma (Eds.): CHES 2017, LNCS 10529, pp. 513–533, 2017. DOI: 10.1007/978-3-319-66787-4 25
514
R. Primas et al.
When it comes to possible post-quantum secure algorithms, lattice-based cryptography appears to be a promising option and has garnered a lot of attention over the past decade. It proved to be versatile and efficient, as there already exist practical lattice-based constructions offering basic services such as publickey encryption, digital signatures, and key exchange. Furthermore, lattices also serve as the basis for new primitives such as homomorphic encryption. A very popular building block for lattice-based constructions is the ringvariant of the Learning with Errors problem, RLWE [16]. Recent implementations of RLWE-based public-key encryption, e.g., [7,24,29], have shown that its performance can compete with (or even exceed) that of RSA and ECC-based
Data Loading...
