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. 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.
Note: We will continue to revise the work
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Number Theoretic TransformationSide-channel AttacksShort Integer SolutionDilithiumKyber
- Contact author(s)
-
qiaozehua @ iie ac cn
liuyuejun @ njust edu cn
shaomingyao @ iie ac cn - History
- 2024-07-01: last of 2 revisions
- 2023-12-05: received
- See all versions
- Short URL
- https://ia.cr/2023/1866
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1866,
author = {Zehua Qiao and Yuejun Liu and Yongbin Zhou and Mingyao Shao and Shuo Sun},
title = {When {NTT} Meets {SIS}: Efficient Side-channel Attacks on Dilithium and Kyber},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1866},
year = {2023},
url = {https://eprint.iacr.org/2023/1866}
}