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

Zehua Qiao; Yuejun Liu; Yongbin Zhou; Mingyao Shao; Shuo Sun

Paper 2023/1866

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

Zehua Qiao

, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Yuejun Liu, School of Cyber Science and Engineering, Nanjing University of Science and Technology, Nanjing, China

Yongbin Zhou, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Science and Engineering, Nanjing University of Science and Technology, Nanjing, China

Mingyao Shao, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China

Shuo Sun, China Mobile Internet

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 Transformation Side-channel Attacks Short Integer Solution Dilithium Kyber
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},
      note = {\url{https://eprint.iacr.org/2023/1866}},
      url = {https://eprint.iacr.org/2023/1866}
}