Grafted Trees Bear Better Fruit : An Improved Multiple-Valued Plaintext-Checking Side-Channel Attack Against Kyber
(2025) 2025 Design, Automation and Test in Europe Conference, DATE 2025- 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... (More)
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 pqm4, aligns well with our simulations.
(Less)
- author
- Li, Jinnuo ; Cheng, Chi ; Shen, Muyan ; Chen, Peng ; Guo, Qian LU ; Liu, Dongsheng ; Wu, Liji and Weng, Jian
- organization
- publishing date
- 2025
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- keywords
- Kyber, Lattice-based cryptography, multiple-valued plaintext-checking oracle, NIST post-quantum cryptography standardization, Side-channel attacks
- host publication
- 2025 Design, Automation and Test in Europe Conference, DATE 2025 - Proceedings
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- conference name
- 2025 Design, Automation and Test in Europe Conference, DATE 2025
- conference location
- Lyon, France
- conference dates
- 2025-03-31 - 2025-04-02
- external identifiers
-
- scopus:105006927399
- ISBN
- 9783982674100
- DOI
- 10.23919/DATE64628.2025.10992764
- language
- English
- LU publication?
- yes
- id
- ea55ec61-ec3f-498d-997f-4159e9d533df
- date added to LUP
- 2025-09-24 15:44:07
- date last changed
- 2025-10-14 11:02:16
@inproceedings{ea55ec61-ec3f-498d-997f-4159e9d533df,
abstract = {{<p>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 pqm4, aligns well with our simulations.</p>}},
author = {{Li, Jinnuo and Cheng, Chi and Shen, Muyan and Chen, Peng and Guo, Qian and Liu, Dongsheng and Wu, Liji and Weng, Jian}},
booktitle = {{2025 Design, Automation and Test in Europe Conference, DATE 2025 - Proceedings}},
isbn = {{9783982674100}},
keywords = {{Kyber; Lattice-based cryptography; multiple-valued plaintext-checking oracle; NIST post-quantum cryptography standardization; Side-channel attacks}},
language = {{eng}},
publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
title = {{Grafted Trees Bear Better Fruit : An Improved Multiple-Valued Plaintext-Checking Side-Channel Attack Against Kyber}},
url = {{http://dx.doi.org/10.23919/DATE64628.2025.10992764}},
doi = {{10.23919/DATE64628.2025.10992764}},
year = {{2025}},
}