Multivariate Template Attack against NTT based Polynomial Multiplication of Dilithium Reference Implementation

According to previous works, NTT based polynomial multiplication of Dilithium can be a main target for side-channel analyzers. In detail, the leakage of ˆ u = ˆ cˆ s1 can be used to recover the private key s1 with correlation power analysis (CPA). However, it is not enough to evaluate the side-channel resistance of NTT based polynomial multiplication of Dilithium with CPA. Considering that template attack (TA) is information theoretically the strongest side-channel attack style, one should evaluate the side-channel resistance of NTT based polynomial multiplication of Dilithium with TA. Besides, previous works did not use the leakage of ˆ w = ˆ Aˆ y to recover s1. In light of this, the leakage of ˆ w = ˆ Aˆ y is used in TA to recover s1 for the first time. In fact, the leakage of ˆ w = ˆ Aˆ y can be K times the leakage of ˆ u = ˆ cˆ s1, which can significantly optimize the efficiency of TA. Finally, the leakage of ˆ w = ˆ Aˆ y and the leakage of ˆ u = ˆ cˆ s1 can be used simultaneously to recover s1. In light of this, multivariate template attack (MTA) against NTT based polynomial multiplication of Dilithium is proposed for the first time. The performances of three versions of TA are evaluated in both simulated scenario and real scenario. The evaluation results show that, in simulated scenario where the signal-to-noise ratio (SNR) of both the leakage of ˆ w = ˆ Aˆ y and the leakage of ˆ u = ˆ cˆ s1 is varied from 1 to 0.1, MTA can perform the best among three versions of TA; in real scenario where NTT based polynomial multiplication of Dilithium reference implementation on Cortex M4 is targeted, MTA also performs the best, and only 15, 11, 9 traces are needed in the attack phase of MTA to recover s1 used by Dilithium 2, 3, 5. Overall, a powerful tool which can be used to evaluate the side-channel resistance of NTT based polynomial multiplication of Dilithium in a leakage profiling scenario is proposed.

据现有研究可知，基于数论变换（Number Theoretic Transform，NTT）的多项式乘法是Dilithium签名算法侧信道分析的主要攻击目标。具体而言，利用相关性功耗分析（Correlation Power Analysis，CPA）可通过泄露的$hat{u} = hat{c}hat{s}_1$恢复私钥$s_1$。然而，仅通过相关性功耗分析不足以评估Dilithium中基于NTT的多项式乘法的侧信道抗性。考虑到模板攻击（Template Attack，TA）是信息论意义上最强的侧信道攻击范式，应当采用模板攻击来评估Dilithium中基于NTT的多项式乘法的侧信道抗性。此外，现有研究尚未利用$hat{w} = hat{A}hat{y}$的泄露信息来恢复$s_1$。鉴于此，本文首次将$hat{w} = hat{A}hat{y}$的泄露信息应用于模板攻击以恢复$s_1$。事实上，$hat{w} = hat{A}hat{y}$的泄露强度可达$hat{u} = hat{c}hat{s}_1$的$K$倍，可显著优化模板攻击的效率。进一步地，可同时利用$hat{w} = hat{A}hat{y}$与$hat{u} = hat{c}hat{s}_1$的泄露信息恢复$s_1$。据此，本文首次提出针对Dilithium中基于NTT的多项式乘法的多变量模板攻击（Multivariate Template Attack，MTA）。本文在仿真场景与真实场景下分别评估了三类模板攻击变体的性能。评估结果表明：在仿真场景中，当$hat{w} = hat{A}hat{y}$与$hat{u} = hat{c}hat{s}_1$的泄露信号信噪比（Signal-to-Noise Ratio，SNR）从1降至0.1时，多变量模板攻击在三类模板攻击变体中表现最优；在以Cortex-M4平台上的Dilithium参考实现为攻击目标的真实场景中，多变量模板攻击同样表现最优，且针对Dilithium 2、3、5版本，仅需15、11、9条功耗轨迹即可在攻击阶段恢复所需的$s_1$。综上，本文提出了一种可用于侧信道泄露分析场景下，评估Dilithium中基于NTT的多项式乘法侧信道抗性的有效工具。

搜集汇总

背景与挑战

背景概述

该数据集包含针对Dilithium参考实现中基于NTT的多项式乘法的多变量模板攻击研究数据，首次结合ˆ w = ˆ Aˆ y和ˆ u = ˆ cˆ s1的泄漏信息进行私钥恢复，并在模拟和实际场景中验证了其高效性。数据量为2.33 GB，包含27个文件。