Power Side-channel Leakage Assessment and Chosen-ciphertext Attack on the Decoding Function of Kyber

QIU Yubo; LI Ziqi; YUAN Chaoxuan; ZHOU Zijian; HU Wandi; HU Wei

doi:10.11999/JEIT251243

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2025 >

QIU Yubo, LI Ziqi, YUAN Chaoxuan, ZHOU Zijian, HU Wandi, HU Wei. Power Side-channel Leakage Assessment and Chosen-ciphertext Attack on the Decoding Function of Kyber[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT251243

Citation:

QIU Yubo, LI Ziqi, YUAN Chaoxuan, ZHOU Zijian, HU Wandi, HU Wei. Power Side-channel Leakage Assessment and Chosen-ciphertext Attack on the Decoding Function of Kyber[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT251243

Citation:

PDF( 2799 KB)

Power Side-channel Leakage Assessment and Chosen-ciphertext Attack on the Decoding Function of Kyber

doi: 10.11999/JEIT251243 cstr: 32379.14.JEIT251243

1.
School of Cyberspace Security, Northwestern Polytechnical University, Xi’an 710072, China
2.
Academy of Cyber, Beijing 100144, China

Funds: The National Key R&D Program (2022YFB3103800), The National Natural Science Foundation of China (U23B2041)

Received Date: 2025-11-25
Accepted Date: 2026-05-12
Rev Recd Date: 2026-04-27

Available Online: 2026-05-27

Abstract

Abstract

Objective The standardization of Post-Quantum Cryptography (PQC) has made the implementation security of Kyber a practical concern. Kyber, standardized as Module-Lattice-based Key-Encapsulation Mechanism (ML-KEM), is a lattice-based scheme with favorable efficiency and security based on the hardness of the Module Learning With Errors (MLWE) problem. However, its deployment on embedded devices can still produce measurable physical leakage. Existing studies have shown that side-channel attacks can target several Kyber modules, but two issues remain insufficiently studied. First, the leakage strengths of different auxiliary functions on the decapsulation and re-encryption path have not been compared under a unified assessment framework. This limits the identification of the most vulnerable implementation-level weak point. Second, although chosen-ciphertext attacks and power analysis have been studied, the decoding function poly_frommsg() has not been fully examined from the perspective of periodic leakage modeling and low-query key recovery. To address these issues, this work evaluates function-level leakage in the key operations of Kyber decapsulation and develops a chosen-ciphertext Simple Power Analysis (SPA) attack against the most vulnerable decoding function. The study provides a practical attack method and implementation-oriented security insights for protecting post-quantum cryptographic software on embedded platforms. Methods A function-oriented evaluation-and-attack framework is established for the execution path of Kyber.CCAKEM.Dec(). Four representative target functions are selected: the Barrett reduction function poly_reduce(), the encoding function poly_tomsg(), the decoding function poly_frommsg(), and the hash function G(). For each function, the intermediate variable with the largest data-dependent bit transition under crafted ciphertext inputs is first analyzed from the perspective of Hamming-distance leakage. Two ciphertext sets are then constructed so that the selected intermediate variable takes two maximally distinguishable values. For each set, 50 power traces are collected. The experiments are performed on an STM32F407IG embedded platform, and power signals are captured using a PicoScope 6406E oscilloscope at a sampling rate of 5 GS/s. Welch’s t-test-based Test Vector Leakage Assessment (TVLA) is used to quantify leakage significance, with ±4.5 used as the decision threshold for leakage detection. After poly_frommsg() is identified as the most vulnerable point, a chosen-ciphertext SPA attack is designed. The attack first constructs ciphertexts according to the coefficient range of the secret polynomial. It then extracts 256 Points of Interest (PoIs) from reference traces through local-maximum search. Finally, a grouped threshold model is built according to the periodic energy structure of the PoIs. The recovered message bits are mapped back to the coefficients of the secret polynomial, enabling full private-key reconstruction for Kyber512 and Kyber768. Results and Discussions The leakage assessment shows clear differences among the four target functions. For poly_reduce(), the intermediate variable t directly depends on the coefficients of the intermediate polynomial mp, and the maximum Hamming distance reaches 13. The measured TVLA peaks are therefore concentrated around 50 for both Kyber512 and Kyber768 (Fig. 5). For poly_tomsg(), the relevant binary transition corresponds to a Hamming distance of only 1, and the observed TVLA values are much smaller, at approximately 6 (Fig. 6). For poly_frommsg(), the message-dependent mask flips between 0 and 0xffff, producing a Hamming distance of 16 and the strongest leakage among all tested functions. The TVLA peaks reach about 60, identifying this module as the primary attack target (Fig. 7). For the hash function G(), the leakage is weaker and less regular, but several sampling points still exceed the TVLA threshold. This result indicates that theoretical indistinguishability under chosen-ciphertext attack (IND-CCA) reinforcement through the Fujisaki-Okamoto (FO) transform does not automatically remove physical leakage (Fig. 8). These results show that implementation-level vulnerability is strongly associated with data-dependent bit transitions. They also show that linear message-expansion functions may expose more stable power signatures than some arithmetic modules. Based on this observation, the proposed attack focuses on poly_frommsg(). Local-extrema analysis shows that the 256 message-bit operations generate 256 stable PoIs. Their energy values show a periodic pattern with an approximate period length of 8 (Fig. 10, Fig. 11). Instead of applying a single global threshold to all PoIs, the proposed grouped threshold model divides the PoIs according to their positions within the period and computes location-aware thresholds. This design suppresses position-dependent drift and improves the consistency of bit decisions. The resulting message-recovery procedure reliably reconstructs the bit sequence from one attack trace under each chosen ciphertext. Combined with the precomputed ciphertext table, only 6 chosen ciphertexts are required to recover the private key of Kyber512, and only 9 chosen ciphertexts are required for Kyber768. Compared with the prior poly_frommsg()-based method, which requires 8 and 12 ciphertexts, respectively, the proposed method reduces the ciphertext requirement by 25.0% while maintaining a 100% success rate (Table 4). Compared with the attack on poly_tomsg(), the proposed method exploits a function with stronger leakage observability and therefore achieves higher decision stability and equal or better overall efficiency. The periodic PoI model is thus not only an empirical observation, but also a direct basis for the attack design and a key reason for the practical gain in low-query key recovery. Conclusions This work shows that Kyber contains different implementation-level vulnerabilities along its decapsulation path and that poly_frommsg() is the most critical leakage point in the tested software implementation. By combining function-level TVLA assessment with a chosen-ciphertext SPA attack, the study identifies leakage sources in poly_reduce(), poly_tomsg(), poly_frommsg(), and G(). It also converts the observed periodic leakage structure of poly_frommsg() into an effective grouped threshold model for key recovery. The resulting attack reduces the number of required ciphertexts for Kyber512 and Kyber768 to 6 and 9, respectively, while preserving a 100% success rate. These findings indicate that practical protection of post-quantum software should go beyond algorithm-level security claims. Masking, execution randomization, balanced implementations, and function-level leakage testing should be considered explicitly during deployment and validation.
- Post-Quantum Cryptography (PQC),
- Power side-channel analysis,
- Chosen-ciphertext attack,
- Kyber cryptographic algorithm

FullText(HTML)

References(25)

References

[1]	SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer[J]. SIAM Review, 1999, 41(2): 303–332. doi: 10.1137/S0036144598347011.
[2]	GROVER L K. A fast quantum mechanical algorithm for database search[C]. Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, USA, 1996: 212–219. doi: 10.1145/237814.237866.
[3]	CHERKAOUI DEKKAKI K, TASIC I, and CANO M D. Exploring post-quantum cryptography: Review and directions for the transition process[J]. Technologies, 2024, 12(12): 241. doi: 10.3390/technologies12120241.
[4]	KOCHER P C, JAFFE J, and JUN B. Differential power analysis[C]. 19th Annual International Cryptology Conference on Advances in Cryptology, Santa Barbara, USA, 1999: 388–397. doi: 10.1007/3-540-48405-1_25.
[5]	HUANG Zitian, WANG Huanyu, CAO Bijia, et al. A comprehensive side-channel leakage assessment of CRYSTALS-Kyber in IIoT[J]. Internet of Things, 2024, 27: 101331. doi: 10.1016/j.iot.2024.101331.
[6]	CHARI S, RAO J R, and ROHATGI P. Template attacks[C]. 4th International Workshop on Cryptographic Hardware and Embedded Systems, Redwood Shores, USA, 2002: 13–28. doi: 10.1007/3-540-36400-5_3.
[7]	HAMBURG M, HERMELINK J, PRIMAS R, et al. Chosen ciphertext k-trace attacks on masked CCA2 secure Kyber[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021, 2021(4): 88–113. doi: 10.46586/tches.v2021.i4.88-113.
[8]	SAHA D and FARAHMANDI F. DL-SCADS: Deep learning-based post-silicon side-channel analysis using decomposed signal[C]. 2024 58th Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, United States, 2024: 1787–1791. doi: 10.1109/IEEECONF60004.2024.10942736.
[9]	YANG Yipei, WANG Zongyue, YE Jing, et al. Chosen ciphertext correlation power analysis on Kyber[J]. Integration, 2023, 91: 10–22. doi: 10.1016/j.vlsi.2023.02.012.
[10]	PARK A and HAN D G. Chosen ciphertext simple power analysis on software 8-bit implementation of ring-LWE encryption[C]. 2016 IEEE Asian Hardware-Oriented Security and Trust(AsianHOST), Yilan, China, 2016: 1–6. doi: 10.1109/AsianHOST.2016.7835555.
[11]	PRIMAS R, PESSL P, and MANGARD S. Single-trace side-channel attacks on masked lattice-based encryption[C]. 19th International Conference on Cryptographic Hardware and Embedded Systems, Taipei, China, 2017: 513–533. doi: 10.1007/978-3-319-66787-4_25.
[12]	WANG Ruize, BRISFORS M, and DUBROVA E. A side-channel attack on a higher-order masked CRYSTALS-Kyber implementation[C]. 22nd International Conference on Applied Cryptography and Network Security, Abu Dhabi, United Arab Emirates, 2024: 301–324. doi: 10.1007/978-3-031-54776-8_12.
[13]	DING Jintai, CHENG Chi, and QIN Yue. A simple key reuse attack on LWE and Ring-LWE encryption schemes as key encapsulation mechanisms (KEMs)[EB/OL]. https://eprint.iacr.org/2019/271, 2019.
[14]	RAVI P, SINHA ROY S, CHATTOPADHYAY A, et al. Generic side-channel attacks on CCA-secure lattice-based PKE and KEMs[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020, 2020(3): 307–335. doi: 10.13154/tches.v2020.i3.307-335.
[15]	胡伟, 袁超绚, 郑健, 等. 一种针对格基后量子密码的能量侧信道分析框架[J]. 电子与信息学报, 2023, 45(9): 3210–3217. doi: 10.11999/JEIT230267. HU Wei, YUAN Chaoxuan, ZHENG Jian, et al. A power side-channel attack framework for lattice-based post quantum cryptography[J]. Journal of Electronics & Information Technology, 2023, 45(9): 3210–3217. doi: 10.11999/JEIT230267.
[16]	HOANG A T, KENNAWAY M, PHAM T D, et al. Deep learning enhanced side channel analysis on CRYSTALS-Kyber[C]. The 25th International Symposium on Quality Electronic Design (ISQED), San Francisco, United States, 2024: 1–8. doi: 10.1109/ISQED60706.2024.10528674.
[17]	KENNAWAY M, HOANG T, KHALID A, et al. An enhanced two-step CPA side-channel analysis attack on ML-KEM[C]. The 22nd International Conference on Security and Cryptography SECRYPT, Bilbao, Spain, 2025: 263–274. doi: 10.5220/0013638600003979.
[18]	BOS J, DUCAS L, KILTZ E, et al. CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM[C]. 2018 IEEE European Symposium on Security and Privacy (EuroS&P), London, UK, 2018: 353–367. doi: 10.1109/EuroSP.2018.00032.
[19]	LANGLOIS A and STEHLÉ D. Worst-case to average-case reductions for module lattices[J]. Designs, Codes and Cryptography, 2015, 75(3): 565–599. doi: 10.1007/s10623-014-9938-4.
[20]	KREUZER K. Verification of correctness and security properties for CRYSTALS-Kyber[C]. 2024 IEEE 37th Computer Security Foundations Symposium (CSF), Enschede, Netherlands, 2024: 511–526. doi: 10.1109/CSF61375.2024.00016.
[21]	GONZÁLEZ DE LA TORRE M Á, HERNÁNDEZ ENCINAS L, and QUEIRUGA-DIOS A. Analysis of the FO transformation in the lattice-based post-quantum algorithms[J]. Mathematics, 2022, 10(16): 2967. doi: 10.3390/math10162967.
[22]	ZHANG Kuang, YANG Mengya, YUAN Zeyu, et al. Optimized quantum-resistant cryptosystem: Integrating Kyber-KEM with hardware TRNG on Zynq platform[J]. Electronics, 2025, 14(13): 2591. doi: 10.3390/electronics14132591.
[23]	GHIBAN C and CHOUDARY M O. Improved correlation power analysis attack on the latest Cortex M4 Kyber implementation[J]. Cryptography, 2025, 9(1): 19. doi: 10.3390/cryptography9010019.
[24]	XU Zhuang, PEMBERTON O, ROY S S, et al. Magnifying side-channel leakage of lattice-based cryptosystems with chosen ciphertexts: The case study of Kyber[J]. IEEE Transactions on Computers, 2022, 71(9): 2163–2176. doi: 10.1109/TC.2021.3122997.
[25]	RAVI P, BHASIN S, ROY S S, et al. On exploiting message leakage in (few) NIST PQC candidates for practical message recovery attacks[J]. IEEE Transactions on Information Forensics and Security, 2022, 17: 684–699. doi: 10.1109/TIFS.2021.3139268.