Magnifying Side-Channel Leakage of Lattice-Based Cryptosystems With Chosen Ciphertexts: The Case Study of Kyber

Lattice-based cryptography, as an active branch of post-quantum cryptography (PQC), has drawn great attention from side-channel analysis researchers in recent years. Despite the various side-channel targets examined in previous studies, detail on revealing the secret-dependent information efficiently is less studied. In this paper, we propose adaptive EM side-channel attacks with carefully constructed ciphertexts on Kyber, which is a finalist of NIST PQC standardization project. We demonstrate that specially chosen ciphertexts allow an adversary to modulate the leakage of a target device and enable full key extraction with a small number of traces through simple power analysis. Compared to prior research, our techniques require fewer traces and avoid building complex templates. We practically evaluate our methods using both a reference implementation and the ARM-specific implementation in pqm4 library. For the reference implementation, we target the leakage of the output of the inverse NTT computation and recover the full key with only four traces. For the pqm4 implementation, we develop a message-recovery attack that leads to extraction of the full secret key with between eight and 960 traces, depending on the compiler optimization level. We discuss the relevance of our findings to other lattice-based schemes and explore potential countermeasures.

1 Introduction

Invented in 1970s, Public-Key Cryptography (PKC) made it possible to establish a shared key between two parties communicating over a public channel without using a prior shared secret. Since then, PKC research has resulted in Public-Key Encryption (PKE), key agreement and digital signature schemes. The most widely used PKC algorithms are the RSA and Elliptic Curve Cryptography (ECC). The security of these two cryptosystems relies on the hardness of the integer factorization and discrete logarithm problems respectively. These problems are presumed to be computationally infeasible to solve using traditional computers. However, Shor’s algorithm [1] can solve these problems in polynomial time and thus break the RSA and ECC efficiently using a large-scale quantum computer. Rapid advancement in quantum computing in recent years have made the development of small-scale quantum computers possible [2]. Many scientists anticipate that large-scale quantum computers able to break RSA and ECC will be feasible within the next 20 years [3]. If such quantum computers are ever built, they will completely destroy the present-day public-key infrastructure. Hence, we need next-generation PKC algorithms that cannot be broken by quantum computers.