Grafted Trees Bear Better Fruit: An Improved Multiple-Valued Plaintext-Checking Side-Channel Attack against Kyber

Jinnuo Li; Chi Cheng; Muyan Shen; Peng Chen; Qian Guo; Dongsheng Liu; Liji Wu; Jian Weng

Paper 2024/1174

Grafted Trees Bear Better Fruit: An Improved Multiple-Valued Plaintext-Checking Side-Channel Attack against Kyber

Jinnuo Li, China University of Geosciences (Wuhan)

Chi Cheng, China University of Geosciences (Wuhan)

Muyan Shen, University of Chinese Academy of Sciences

Peng Chen, China University of Geosciences (Wuhan)

Qian Guo, Lund University

Dongsheng Liu, Huazhong University of Science and Technology

Liji Wu, Tsinghua University

Jian Weng, Jinan University

Abstract

As a prominent category of side-channel attacks (SCAs), plaintext-checking (PC) oracle-based SCAs offer the advantages of generality and operational simplicity on a targeted device. At TCHES 2023, Rajendran et al. and Tanaka et al. independently proposed the multiple-valued (MV) PC oracle, significantly reducing the required number of queries (a.k.a., traces) in the PC oracle. However, in practice, when dealing with environmental noise or inaccuracies in the waveform classifier, they still rely on majority voting or the other technique that usually results in three times the number of queries compared to the ideal case. In this paper, we propose an improved method to further reduce the number of queries of the MV-PC oracle, particularly in scenarios where the oracle is imperfect. Compared to the state-of-the-art at TCHES 2023, our proposed method reduces the number of queries for a full key recovery by more than $42.5\%$. The method involves three rounds. Our key observation is that coefficients recovered in the first round can be regarded as prior information to significantly aid in retrieving coefficients in the second round. This improvement is achieved through a newly designed grafted tree. Notably, the proposed method is generic and can be applied to both the NIST key encapsulation mechanism (KEM) standard Kyber and other significant candidates, such as Saber and Frodo. We have conducted extensive software simulations against Kyber-512, Kyber-768, Kyber-1024, FireSaber, and Frodo-1344 to validate the efficiency of the proposed method. An electromagnetic attack conducted on real-world implementations, using an STM32F407G board equipped with an ARM Cortex-M4 microcontroller and Kyber implementation from the public library \textit{pqm4}, aligns well with our simulations.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: post-quantum cryptography Lattice-based cryptography Kyber Side-channel attacks
Contact author(s): chengchizz @ qq com
History: 2024-07-22: approved; 2024-07-20: received; See all versions
Short URL: https://ia.cr/2024/1174
License: CC BY

BibTeX

@misc{cryptoeprint:2024/1174,
      author = {Jinnuo Li and Chi Cheng and Muyan Shen and Peng Chen and Qian Guo and Dongsheng Liu and Liji Wu and Jian Weng},
      title = {Grafted Trees Bear Better Fruit: An Improved Multiple-Valued Plaintext-Checking Side-Channel Attack against Kyber},
      howpublished = {Cryptology ePrint Archive, Paper 2024/1174},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/1174}},
      url = {https://eprint.iacr.org/2024/1174}
}