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 > 2026 >

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( 2822 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.
Acyber, Beijing 100144, China

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

Accepted Date: 2026-05-12
Rev Recd Date: 2026-05-12

Available Online: 2026-05-27

Abstract

Abstract

Objective The standardization of post-quantum cryptography makes the implementation security of Kyber a practical and urgent problem rather than a purely theoretical concern. As a lattice-based key encapsulation mechanism selected by NIST, Kyber achieves favorable efficiency and security based on the hardness of the Module Learning With Errors problem; however, its real-world deployment on embedded devices still exposes measurable physical leakage. Existing studies have shown that side-channel attacks can target several modules of Kyber, but two issues remain insufficiently addressed. First, the leakage strengths of different auxiliary functions along the decapsulation and reencryption path have not been compared within a unified assessment framework, which makes it difficult to identify the most dangerous implementation-level weak point. Second, although chosen-ciphertext attacks and power analysis have both been studied, the decoding function poly_frommsg() has not been fully exploited from the perspective of periodic leakage modeling and low-query key recovery. To address these problems, this work performs function-level leakage assessment for the key operations involved in Kyber decapsulation and then develops a chosen-ciphertext simple power analysis attack against the most vulnerable decoding function. The study is intended to provide both a practical attack method and implementation-oriented security insights for the protection of post-quantum cryptographic software on embedded platforms. Methods A function-oriented evaluation-and-attack framework is established around 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 that exhibits the largest data-dependent bit transition under crafted ciphertext inputs is first analyzed from the viewpoint of Hamming-distance leakage. Two ciphertext sets are then constructed so that the selected intermediate variable takes two maximally distinguishable values, and 50 power traces are collected for each set. The experiments are implemented on an STM32F407IG embedded platform, and the power signals are captured by a PicoScope 6406E oscilloscope at a sampling rate of 5 GS/s. Welch’s t-test based TVLA is adopted to quantify leakage significance, with ±4.5 used as the decision threshold for leakage existence. After the decoding function 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, then extracts 256 points of interest from reference traces by local-maximum search, and finally builds a grouped threshold model according to the periodic energy structure of the points of interest. 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 demonstrates a clear difference among the four target functions. For poly_reduce(), the intermediate variable t depends directly on the coefficients of the intermediate polynomial mp, and the maximum Hamming distance reaches 13; accordingly, the measured TVLA peaks are 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, approximately 6 (Fig.6). For poly_frommsg(), the message-dependent mask flips between 0 and 0xffff, yielding a Hamming distance of 16 and the strongest leakage among all tested functions; the TVLA peaks reach about 60, which identifies 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, indicating that theoretical IND-CCA reinforcement through the FO transform does not automatically eliminate physical leakage (Fig.8). These results show that implementation-level vulnerability is highly correlated with data-dependent bit transitions and that linearly expanded message-processing functions may expose more stable power signatures than some arithmetic modules.Based on this observation, the proposed attack focuses on poly_frommsg(). The local-extrema analysis shows that the 256 message-bit operations generate 256 stable points of interest, and their energy values exhibit a periodic pattern with an approximate period length of 8 (Fig.10, Fig.11). Instead of applying a single global threshold to all points of interest, the proposed grouped threshold model divides the points 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 can reliably reconstruct 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 needs 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 both higher decision stability and equal or better overall efficiency. The periodic points-of-interest model is thus not merely an empirical phenomenon; it directly supports the attack design and explains the practical gain in low-query key recovery. Conclusions This work shows that Kyber contains heterogeneous implementation-level vulnerabilities along its decapsulation path and that the decoding function poly_frommsg() is the most critical leakage point under the tested software implementation. By combining function-level TVLA assessment with a chosen-ciphertext SPA attack, the study not only pinpoints leakage sources in poly_reduce(), poly_tomsg(), poly_frommsg(), and G(), but 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 and explicitly consider masking, execution randomization, balanced implementations, and function-level leakage testing 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]	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.
[25]	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.