Paper 2023/1866

When NTT Meets SIS: Efficient Side-channel Attacks on Dilithium and Kyber

Abstract

In 2022, NIST selected Kyber and Dilithium as post-quantum cryptographic standard algorithms. The Number Theoretic Transformation (NTT) algorithm, which facilitates polynomial multiplication, has become a primary target for side-channel attacks. Among these, Correlation Power Analysis (CPA) attacks against NTT have received much attention, which aims to recover all the coefficients of the private key in NTT domain. The necessity to recover all these coefficients not only limits efficiency but also directly impacts the feasibility of such attacks. Thus, a crucial question emerges: can the remaining coefficients be recovered using only a subset of known ones? In this work, we respond affirmatively by introducing overdetermined system-based and SIS-assisted key recovery methods for both Dilithium and Kyber, tailored for scenarios with incomplete NTT domain private keys. The SIS-assisted method, by embedding NTT transform matrix into the SIS search problem, offers a complete key recovery with the minimum known coefficients in NTT domain. For Kyber512 and Dilithium2, only 64 and 32 coefficients are enough to recover a subset of the private key with 256 coefficients, respectively. Furthermore, we propose a parameter-adjustable CPA scheme to expedite the recovery of a single coefficient in NTT domain. Combining this CPA scheme with the SIS-assisted approach, we executed practical attacks on both unprotected and masked implementations of Kyber and Dilithium on an ARM Cortex-M4. The results demonstrate that we can recover a subset of 256 private key coefficients for Dilithium2 using 2,000 power traces in 0.5 minutes, while Kyber512 requires 0.4 minutes and 500 power traces. These attacks achieve a 400$\times$ speedup compared to the best-known attacks against Dilithium. Moreover, we successfully break the first-order mask implementations and explore the potential applicable to higher-order implementations.