Power Side-Channel Leakage Assessment and Chosen-Ciphertext Attack on the Decoding Function of Kyber
-
摘要: 本文针对抗量子格基密码算法Kyber实现中潜在的能量侧信道泄露风险，研究了Kyber各核心模块的脆弱点与泄露原理，并对其嵌入式平台实现中各模块的能量侧信道泄露风险进行了评估。评估结果表明Kyber算法实现中多个模块可能存在侧信道安全脆弱性。针对泄露相对最严重的解码函数，本文提出了一种高效的选择密文能量侧信道攻击方法。该方法通过构造特定密文输入，结合简单能量分析，实现了私钥的高效恢复。实验结果显示，攻击Kyber512仅需6次选择密文输入，攻击Kyber768仅需9次，与现有工作相比，所需密文条数均降低了25.0%。本研究揭示了Kyber算法在实现层面潜在的安全脆弱性，可为其侧信道防护设计提供评估依据和手段。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. -
表 1 针对解码函数的Kyber768选择密文攻击表
s 的
系数$ \left({k}_{u},{k}_{v}\right) $ ( 1251 ,0)( 1251 ,2912 )(627, 2912 )–2 0 1 1 –1 1 1 0 0 0 0 0 1 1 1 1 2 0 0 1 
下载: 导出CSV
1 $ \text{PoI} $搜索和阈值建立算法
输入：$ {r}_{1}\left(t\right) $ $ {r}_{0}\left(t\right) $：参考轨迹 输出：PoI：256个局部极大值点的集合，$ {T}_{0} $，$ {T}_{mid} $，$ {T}_{7} $ 1 寻找局部极值点： 2 在$ {r}_{1}\left(t\right) $中执行局部极值搜索，得到256个局部最大值： 3 $ \text{PoI =}\left\{\text{PoI}\left(0\right),\cdots\text{, PoI}\left(255\right)\right\} $//局部极大值点集合 4 计算最大值与最小值之间的平均差异： 5 $ \text{for}i=0\cdots 255\text{do} $ 6 $ {a}_{0}\left(i\right)={r}_{0}\left(\text{PoI}\left(i\right)\right) $//波形$ {r}_{0} $的极大值 7 $ {a}_{1}\left(i\right)={r}_{1}\left(\text{PoI}\left(i\right)\right) $//波形$ {r}_{1} $的极大值 8 计算平均阈值： 9 $ \text{for}i=0\cdots 255\text{do} $ 10 $ \text{if}i\% 8=0 $ 11 $ su{m}_{0,0}+={a}_{0}(i) $ 12 $ su{m}_{0,1}+={a}_{1}(i) $ 13 $ \text{else if}i\% 8=7 $ 14 $ su{m}_{7,0}+={a}_{0}(i) $ 15 $ su{m}_{7,1}+={a}_{1}(i) $ 16 $ \text{else} $ 17 $ su{m}_{other,0}+={a}_{0}(i) $ 18 $ su{m}_{other,1}+={a}_{1}(i) $ 19 $ {T}_{0}=0.5\cdot (su{m}_{0,0}/32+su{m}_{0,1}/32) $ 20 $ {T}_{7}=0.5\cdot (su{m}_{7,0}/32+su{m}_{7,1}/32) $ 21 $ {T}_{mid}=0.5\cdot (su{m}_{mid,0}/192+su{m}_{7,1}/192) $ 22 $ \text{return PoI,}{T}_{0},{T}_{7},{T}_{other} $
下载: 导出CSV
2 消息m恢复算法
输入：$ p(t) $：攻击波形，PoI：256个局部极大值点的集合，
$ {T}_{0} $，$ {T}_{mid} $，$ {T}_{7} $输出：$ m $ 1 $ \text{for}i\text{=0···255 do} $ 2 $ \partial \left(i\right)=p\left(\text{PoI}\left(i\right)\right) $//波形$ {r}_{0} $的极大值 3 $ \text{if}i\%8= 0 $ 4 $ {m}_{i}=\partial \left(i\right)> {T}_{0}? 1 : 0 $ 5 $ \text{else if}i\%8=7 $ 6 $ {m}_{i}=\partial \left(i\right)> {T}_{7}? 1 : 0 $ 7 $ \text{else} $ 8 $ {m}_{i}=\partial \left(i\right)> {T}_{other}? 1 : 0 $ 9 $ \text{return}m $
下载: 导出CSV
表 3 实验平台配置与关键参数
类别 项目 配置/参数 软件环境 操作系统 Windows 10 开发工具 Arduino 1.8.19 分析工具 PyCharm 2023.1.2 算法实现 PQClean Kyber C implementation 硬件环境 目标板 STM32F407IG MCU 架构 ARM Cortex-M4 工作电压 3.3 V Flash / SRAM 1024 KB / 192 KB时钟频率 53.76 MHz 采集设备 示波器 PicoScope 6406E 带宽 1 GHz 采样率 5 GS/s 采集设置 每组轨迹数 50 攻击对象 目标函数 poly_reduce / poly_tomsg /
poly_frommsg / G()统计标准 泄露判定阈值 TVLA = ±4.5
下载: 导出CSV
-
[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. -
图(11) / 表(5)
计量
- 文章访问数: 12
- HTML全文浏览量: 6
- PDF下载量: 1
- 被引次数: 0
下载:
