Multivariate Template Attack Against NTT-Based Polynomial Multiplication of Dilithium

Previous studies identified NTT-based polynomial multiplication in Dilithium as a primary target for side-channel analysis. Specifically, the leakage of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\hat {\mathbf {u}} = \hat {\mathbf {c}} \hat {\mathbf {s}}_{1}$ </tex-math></inline-formula> has been exploited to recover the private key <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbf {s}_{1}$ </tex-math></inline-formula> using correlation power analysis (CPA). However, evaluating the side-channel resistance of NTT-based polynomial multiplication solely through CPA is insufficient. Given that template attack (TA) is information-theoretically the most powerful form of side-channel attack, it is imperative to evaluate the resistance of NTT-based polynomial multiplication in Dilithium under TA. Moreover, previous studies have not exploited the leakage of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\hat {\mathbf {w}} = \hat {\mathbf {A}} \hat {\mathbf {y}}$ </tex-math></inline-formula> to recover <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbf {s}_{1}$ </tex-math></inline-formula>. In this paper, we demonstrate for the first time that the leakage of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\hat {\mathbf {w}} = \hat {\mathbf {A}} \hat {\mathbf {y}}$ </tex-math></inline-formula> can be effectively exploited in TA to recover <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbf {s}_{1}$ </tex-math></inline-formula>. Notably, the leakage of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\hat {\mathbf {w}} = \hat {\mathbf {A}} \hat {\mathbf {y}}$ </tex-math></inline-formula> can be up to <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">K</i> times the leakage of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\hat {\mathbf {u}} = \hat {\mathbf {c}} \hat {\mathbf {s}}_{1}$ </tex-math></inline-formula>, offering significant improvements in the efficiency of TA. We further propose a multivariate template attack (MTA) that jointly exploits both leakage sources <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\hat {\mathbf {w}} = \hat {\mathbf {A}} \hat {\mathbf {y}}$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\hat {\mathbf {u}} = \hat {\mathbf {c}} \hat {\mathbf {s}}_{1}$ </tex-math></inline-formula> to recover <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbf {s}_{1}$ </tex-math></inline-formula>, thus achieving even higher efficiency in key recovery. We evaluate three versions of TA in both simulated and real-world scenarios. In the simulated scenario where the signal-to-noise ratio of both leakage sources ranges from 1 to 0.1, MTA consistently performs the best. In a real-world scenario targeting the Dilithium reference implementation on a Cortex-M4 processor, MTA again achieves the best performance, requiring only 15, 11, and 9 traces to recover <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathbf {s}_{1}$ </tex-math></inline-formula> for Dilithium 2, 3, and 5, respectively. Overall, MTA is proved to be a powerful tool for evaluating the side-channel resistance of NTT-based polynomial multiplication in Dilithium in leakage profiling scenarios.