Keep Calm and Carry On: the recent side-channel attacks on Kyber

In response to the threat that quantum computers pose to public key cryptography, NIST is conducting a standardization process for post-quantum secure public key encryption and encapsulation schemes. Kyber, so far, is the only one recommended for standardization (besides the other three algorithms that have been selected for digital signatures). Side-channel attack claims (1,2) on Kyber have prompted news outlets and social media to raise alarms regarding Kyber’s security (4). This blog post outlines the scope of these attacks. In short, these attacks apply only when presented with special access to a particular implementation of Kyber. They have little to say about the intrinsic security of Kyber or the hardness of the underlying lattice-based computational problem. Side-channel attacks are important reminders that guide us towards secure cryptographic implementations, and the papers mentioned above are more examples targeting Kyber. We must not panic about the security of Kyber due to these attacks.

Side-channel attacks

Side-channel attacks encompass a collection of methods that exploit special access or extra information that may leak from improper implementations of a cryptographic system. Foremost examples of such attacks include measuring the power consumption of a hardware device implementing the protocol or timing the execution of certain steps. If the protocols are not properly implemented, power consumption or execution time may leak information about the private key or the message being used. The scope of such attacks is limited in the sense that the adversary typically needs extraordinary, often physical, access to devices performing the protocol. These are not attacks that merely have access to information that is meant to be public in the design of the cryptographic scheme. In essence, such attacks target behaviors when translating from protocol design to implementation. They are of utmost importance, as they inform about hazards to look out for in implementations and consequently are pivotal to be able to suggest countermeasures. However, they should not be misinterpreted as attacks against the underlying cryptographic scheme.

Kyber

Kyber is a key encapsulation mechanism whose security relies on the hardness of the module Learning-With-Errors (module-LWE) problem arising from certain algebraic lattices. Module-LWE is a twist on the Learning-With-Errors (LWE) problem; the latter has withstood more than a decade of attempts to break it, even when the adversary is assumed to have access to quantum computers. The module-LWE problem underlying Kyber has some more algebraic structure than LWE. However, there are no known algorithms, quantum or classical, that have exploited this algebraic structure to make inroads into the security parameters chosen for Kyber. In addition, there are complexity theoretic arguments in favour of the hardness of LWE and module-LWE. Regev (3) proved that certain worst-case lattice problems reduce to LWE. There is a similar reduction for the module-LWE problem underlying Kyber. This reduction places the asymptotic security of Kyber on a firm complexity theoretic foundation.

Recent side-channel attacks on Kyber

Like most cryptographic schemes, Kyber is vulnerable to power analysis when implemented without countermeasures. An adversary with access to a device performing operations involving a sensitive variable (such as the message or the secret key) may infer information about the variable by power/electromagnetic analysis. Masking is a countermeasure for this in certain scenarios. First-order masking writes the sensitive boolean string $s$ as the XOR of two shares $s_1$ and $s_2$. The operations are then performed on the shares. In the arithmetic context, the XOR may be replaced by addition or addition modulo a prime. Kyber was already known to be vulnerable to side-channel power attacks despite first-order masking. One may look for a higher order (say $r$) masking, where $s$ is split into $r+1$ shares. Recently, Dubrova, Ngo, and Gartner devised a side-channel power attack incorporating methods from deep learning (1). They claim that Kyber remains vulnerable to their attack when masked to an order of at most 5. They suspect their methods do not apply to much higher orders of masking. As is evident, this attack applies to a particular implementation of Kyber and requires extraordinary side-channel access. A similar caveat applies to another recent side-channel attack on Kyber by Guo, Nabokov, Nilsson, and Johansson (2). Theirs again is a power attack and the focus is on reducing the number of power traces required to infer the secret in a masked Kyber implementation. To this end, they devise a side-channel power attack that requires many chosen ciphertext queries. In summary, these attacks are important cautionary tales towards proper implementation of Kyber, but must not be mistaken as threats to fundamentally break Kyber.

References

• [1] E. Dubrova, K. Ngo, and J. Gartner, Breaking a Fifth-Order Masked Implementation of CRYSTALS-Kyber by Copy-Paste
• [2] Q. Guo, D. Nabokov, A. Nilsson, and T. Johansson, SCA-LDPC: A Code-Based Framework for Key-Recovery Side-Channel Attacks on Post-Quantum Encryption Schemes
• [3] O. Regev, On lattices, learning with errors, random linear codes, and cryptography, Journal of the ACM, Volume 56, Issue 6, Article No.: 34, pp 1–40.
• [4] Security week, AI Helps Crack NIST-Recommended Post-Quantum Encryption Algorithm.