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 (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. -
表 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
表 2 针对解码函数的Kyber512 选择密文攻击表
s 的
系数$ \left({k}_{u},{k}_{v}\right) $ ( 1388 ,0)(835, 1664 )(835, 2496 )–3 1 1 1 –2 0 0 1 –1 1 0 0 0 0 1 1 1 1 0 1 2 0 0 0 3 1 1 0
下载: 导出CSV
1 $ \text{PoI} $搜索和阈值建立算法
输入：$ {r}_{1}\left(t\right) $, $ {r}_{0}\left(t\right) $：参考轨迹 输出：PoI：256个局部极大值点的集合，$ {T}_{0} $, $ {T}_{{\mathrm{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 $ {{\mathrm{sum}}}_{0,0}+={a}_{0}(i) $ 12 $ {{\mathrm{sum}}}_{0,1}+={a}_{1}(i) $ 13 $ \text{else if}\;i\% 8=7 $ 14 $ {{\mathrm{sum}}}_{7,0}+={a}_{0}(i) $ 15 $ {{\mathrm{sum}}}_{7,1}+={a}_{1}(i) $ 16 $ \text{else} $ 17 $ {{\mathrm{sum}}}_{{\mathrm{other}},0}+={a}_{0}(i) $ 18 $ {{\mathrm{sum}}}_{{\mathrm{other}},1}+={a}_{1}(i) $ 19 $ {T}_{0}=0.5\cdot ({{\mathrm{sum}}}_{0,0}/32+{{\mathrm{sum}}}_{0,1}/32) $ 20 $ {T}_{7}=0.5\cdot ({{\mathrm{sum}}}_{7,0}/32+{{\mathrm{sum}}}_{7,1}/32) $ 21 $ {T}_{{\mathrm{mid}}}=0.5\cdot ({{\mathrm{sum}}}_{mid,0}/192+{{\mathrm{sum}}}_{7,1}/192) $ 22 $ \text{return PoI,}{T}_{0},{T}_{7},{T}_{{\mathrm{other}}} $
下载: 导出CSV
2 消息m恢复算法
输入：$ p(t) $：攻击波形，PoI：256个局部极大值点的集合，
$ {T}_{0} $, $ {T}_{{\mathrm{mid}}} $, $ {T}_{7} $输出：$ m $ 1 $ \text{for}\;i\text{=0,\cdots, 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}_{{\mathrm{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] 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. -
下载:
图(11) / 表(6)
计量
- 文章访问数: 209
- HTML全文浏览量: 79
- PDF下载量: 27
- 被引次数: 0
