Research on Key Technologies of Side-channel Security Protection for Polynomial Multiplication in ML-KEM/Kyber Algorithm
-
摘要: 后量子密码算法CRYSTALS-Kyber已被美国国家标准与技术研究院(NIST)标准化为唯一的模块化格基密钥封装机制方案 (ML-KEM)，以抵御大规模量子计算机的攻击。虽然后量子密码通过数学理论保证了算法的安全性，但在密码实现运算过程中仍面临侧信道威胁。该文针对当前后量子密码算法硬件实现中存在的侧信道泄露风险，提出一种随机伪轮隐藏防护技术，通过动态插入冗余模运算与线性反馈移位寄存器(LFSR)随机调度机制，破坏多项式逐点乘法(PWM)关键操作的时序特征，从而混淆侧信道信息相关性。为了验证其有效性，在Xilinx Spartan-6 FPGA平台对安全增强前后的Kyber解密模块进行实现，并开展基于选择密文的相关功耗分析(CPA)。实验结果表明，防护前攻击者仅需897～1 650条功耗迹线即可恢复Kyber长期密钥；防护后在10 000条迹线下仍无法成功破解，破解密钥所需迹线数量显著提高。同时，相较现有的Kyber防护实现方案，该文的安全增强设计在面积开销上优于其他的隐藏方案。Abstract:
Objective As ML-KEM/Kyber is adopted as a post-quantum key encapsulation mechanism, securing its hardware implementations against Side-Channel Attacks (SCAs) has become critical. Although Kyber offers mathematically proven security, its physical implementations remain susceptible to timing-based side-channel leakage, particularly during Polynomial Point-Wise Multiplication (PWM), a core operation in decryption. Existing countermeasures, such as masking and static hiding, struggle to balance security, resource efficiency, and hardware feasibility. This study proposes a dynamic randomization strategy to disrupt execution timing patterns in PWM, thereby improving side-channel resistance in Kyber hardware designs. Methods A randomized pseudo-round hiding technique is developed to obfuscate the timing profile of PWM computations. The approach incorporates two key mechanisms: (1) dynamic insertion of redundant modular operations (e.g., dummy additions and multiplications), and (2) two-level pseudo-random scheduling based on Linear Feedback Shift Registers (LFSRs). These mechanisms randomize the execution order of PWM operations while reusing existing butterfly units to reduce hardware overhead. The design is implemented on a Xilinx Spartan-6 FPGA and evaluated using Correlation Power Analysis (CPA) and Test Vector Leakage Assessment (TVLA). Results and Discussions Experimental results demonstrate a substantial improvement in side-channel resistance. In unprotected implementations, attackers could recover Kyber’s long-term secret key using as few as 897 to 1,650 power traces. With the proposed countermeasure applied, no successful key recovery occurred even after 10,000 traces, representing more than a 10-fold increase in the number of traces required for key extraction. TVLA results ( Fig. 6 ) confirm the suppression of leakage, with t-test values maintained near the threshold (|t| < 4.5). The resource overhead remains within acceptable bounds: the area-time product increases by 17.99%, requiring only 157 additional Look-Up Tables (LUTs) and 99 Flip-Flops (FFs) compared with the unprotected design. The proposed architecture outperforms existing masking and hiding schemes (Table 3 ), delivering stronger security with lower resource consumption.Conclusions This work presents an efficient and lightweight countermeasure against timing-based SCAs for Kyber hardware implementations. By dynamically randomizing PWM operations, the design significantly enhances side-channel security while maintaining practical resource usage. Future research will focus on optimizing pseudo-round scheduling to reduce latency, extending protection to Kyber’s Fujisaki–Okamoto (FO) transformation modules, and generalizing the method to other Number-Theoretic Transform (NTT)-based lattice cryptographic algorithms such as Dilithium. These developments support the secure and scalable deployment of post-quantum cryptographic systems. -
1 Kyber.CPAPKE.Dec
输入：私钥$ \mathrm{s}\mathrm{k}\in {\mathcal{B}}^{12\cdot k\cdot n/8} $ 输出：密文$ c\in {\mathcal{B}}^{{d}_{u}\cdot k\cdot n/8+{d}_{v}\cdot n/8} $ 输出：消息$ m\in {\mathcal{B}}^{32} $ (1) $ \boldsymbol{u}:={\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}}_{q}({\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{e}}_{{d}_{{\boldsymbol{u}}}}\left(c\right),{d}_{{\boldsymbol{u}}}) $ (2) $ v:={\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}}_{q}({\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{e}}_{{d}_{v}}\left(c+{d}_{{\boldsymbol{u}}}\cdot k\cdot n/8\right),{d}_{v}) $ (3) $ \hat{\boldsymbol{s}}:={\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{e}}_{12}\left(\mathrm{s}\mathrm{k}\right) $ (4) $ m:={\mathrm{E}\mathrm{n}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{e}}_{1}\left(\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}\right(v-{\mathrm{N}\mathrm{T}\mathrm{T}}^{-1}\left({\hat{\boldsymbol{s}}}^{\mathrm{T}}\circ \mathrm{N}\mathrm{T}\mathrm{T}\left(\boldsymbol{u}\right)\right),1) $ (5) $ \triangleright m :={\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}}_{q}\left(v-{\boldsymbol{s}}^{\mathrm{T}}{\boldsymbol{u}},1\right) $ (6) 返回: $ m $ 
下载: 导出CSV
2 多项式逐点乘法(Point-Wise Multiplication)
输入：$ A\left(x\right)=\left({A}_{0},{A}_{1},\cdots ,{A}_{n-1}\right) $, $ B\left(x\right)=\left({B}_{0},{B}_{1},\cdots ,{B}_{n-1}\right) $
(按位反序排列)，$ \zeta (\mathrm{s}.\mathrm{t}.{\zeta }^{n}\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}q) $输出：$ C\left(x\right)=\left({C}_{0},{C}_{1},\cdots ,{C}_{n-1}\right) $(按位反序排列) (1) $ l={\mathrm{l}\mathrm{o}\mathrm{g}}_{2}^{}n $ (2) 循环 $ i $从$ 1 $～$ {n}/{2} $执行 (3) $ w={\zeta }^{\mathrm{b}{\mathrm{r}}_{l-1}\left(i\right)+1}\left(\mathrm{m}\mathrm{o}\mathrm{d}q\right) $ (4) $ {C}_{2i}={A}_{2i+1}\cdot {B}_{2i+1}\cdot w+{A}_{2i}\cdot {B}_{2i}\left(\mathrm{m}\mathrm{o}\mathrm{d}q\right) $ (5) $ {C}_{2i+1}={A}_{2i}\cdot {B}_{2i+1}+{A}_{2i+1}\cdot {B}_{2i}\left(\mathrm{m}\mathrm{o}\mathrm{d}q\right) $ (6) 结束循环 (7) 返回：$ C\left(x\right)=\left({C}_{0},{C}_{1},\cdots ,{C}_{n-1}\right) $
下载: 导出CSV
表 1 Kyber.CPAPKE.Dec详细运算的并行度和时钟周期数[9]
操作 并行度/周期数 Receive $ c={c}_{1}\left|\right|{c}_{2} $ -/713 $ \boldsymbol{u}\left[0\right]=\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}\left({c}_{1}\right),\hat{\boldsymbol{u}}\left[0\right]=\mathrm{N}\mathrm{T}\mathrm{T}\left(\boldsymbol{u}\right[0\left]\right) $ 2,4/576 $ {\mathrm{acc}}=\hat{\boldsymbol{u}}\left[0\right]\circ \hat{\boldsymbol{s}}\left[0\right]+0 $ 2/256 $ \boldsymbol{u}\left[1\right]=\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}\left({c}_{1}\right),\hat{\boldsymbol{u}}\left[1\right]=\mathrm{N}\mathrm{T}\mathrm{T}\left(\boldsymbol{u}\right[1\left]\right) $ 2,4/576 $ \mathrm{a}\mathrm{c}\mathrm{c}=\hat{\boldsymbol{u}}\left[1\right]\circ \hat{\boldsymbol{s}}\left[1\right]+\mathrm{a}\mathrm{c}\mathrm{c} $ 2/256 $ \boldsymbol{u}\left[2\right]=\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}\left({c}_{1}\right),\hat{\boldsymbol{u}}\left[2\right]=\mathrm{N}\mathrm{T}\mathrm{T}\left(\boldsymbol{u}\right[2\left]\right) $ 2,4/576 $ \hat{\boldsymbol{u}}\hat{\boldsymbol{s}}=\hat{\boldsymbol{u}}\left[2\right]\circ \hat{\boldsymbol{s}}\left[2\right]+\mathrm{a}\mathrm{c}\mathrm{c} $ 2/256 $ \boldsymbol{u}\boldsymbol{s}=\mathrm{I}\mathrm{N}\mathrm{T}\mathrm{T}\left(\hat{\boldsymbol{u}}\hat{\boldsymbol{s}}\right) $ 4/448 $ v=\mathrm{D}\mathrm{e}\mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}\left({c}_{2}\right) $ 2/128 $ m=\mathrm{E}\mathrm{n}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{e}\left(\mathrm{C}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{s}\right(v-\boldsymbol{u}\boldsymbol{s}\left)\right) $ 2/128
下载: 导出CSV
下载:
