Paper 2023/1866 Original: eprint.iacr.org/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. In this work, we embed the NTT transformation matrix in Dilithium and Kyber into the SIS search problem, and further, we propose a divide and conquer strategy for dimensionality reduction of the SIS problem by utilizing the properties of NTT, and discuss the effectiveness of the BKZ algorithm for solving the problem by using the LLL and with different blocksize, respectively. When using BKZ-60, the time required to recover private keys $\mathbf{s}_1$ for Dilithium2 after using the dimensionality reduction strategy is reduced from 82 hours to 1 minute, which is a 4,900$\times$ improvement, and the minimum number of coefficients required is reduced from 65 to 32, which is close to the theoretical lower limit value of 28. 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 Dilithium and Kyber on an ARM Cortex-M4. The results demonstrate that, using 5,000 power traces, we can recover complete $\mathbf{s}_1$ of Dilithium2 in 2.4 minutes, which achieve a 400$\times$ speedup compared to the best-known attacks. And Kyber512 takes only 0.5 minutes, a 7.5$\times$ improvement over what's already working. Moreover, we successfully break the first-order masked implementations and explore the potential applicable to higher-order implementations.