Single Trace is All It Takes: Efficient Side-channel Attack on Dilithium

Zehua Qiao; Yuejun Liu; Yongbin Zhou; Yuhan Zhao; Shuyi Chen

Paper 2024/512

Single Trace is All It Takes: Efficient Side-channel Attack on Dilithium

Zehua Qiao

, University of Chinese Academy of Sciences, School of Cyber Security, University of Chinese Academy of Sciences

Yuejun Liu, Nanjing University of Science and Technology

Yongbin Zhou, Nanjing University of Science and Technology, School of Cyber Security, University of Chinese Academy of Sciences

Yuhan Zhao, Nanjing University of Science and Technology

Shuyi Chen, Nanjing University of Science and Technology

Abstract

As we enter 2024, the post-quantum cryptographic algorithm Dilithium, which emerged from the National Institute of Standards and Technology post-quantum cryptography competition, has now reached the deployment stage. This paper focuses on the practical security of Dilithium. We performed practical attacks on Dilithium2 on an STM32F4 platform. Our results indicate that an attack can be executed with just two signatures within five minutes, with a single signature offering a 60% probability of recovering the private key within one hour. Specifically, we analyze the polynomial addition $z=y+\mathbf{cs}_1$. The attack is conducted in two phases: initially applying side-channel analysis to recover the values of $y$ or $\mathbf{cs}_1$, followed by solving an equation system of $\mathbf{cs}_1$ with error. We introduce using Linear Regression-based profiled attack to recover $y$, leveraging the mathematical properties of adding large and small numbers, requiring only one trace to achieve a 40% success rate. In contrast, a CNN-based template attack, trained with leakage from 200 signatures, enables $\mathbf{cs}_1$ recovery from a single trace with a 74% success rate. Further, by exploiting the constraint $z=y+\mathbf{cs}_1$, the combined leakages of $y$ and $\mathbf{cs}_1$ increase the success rate for $\mathbf{cs}_1$ recovery to 92%. Additionally, we propose a constrained optimization-based residual analysis to solve the equation set $\mathbf{cs}_1 = b$ with error. This method can function independently or as a preprocessing step in combination with Belief Propagation or Integer Linear Programming. Experimental results show that with a 95% correctness rate in the equation set, this method can directly recover the private key $\mathbf{s}_1$ with an 83% success rate in just five seconds. Even with a correctness rate as low as 5%, the method can still recover the private key $\mathbf{s}_1$ in 5 minutes using the system of equations generated by about 200 signatures.

Note: We will continue to revise the paper.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Dilithium Lattice-based Cryptography CNN Side-channel Attacks
Contact author(s): qiaozehua @ iie ac cn
liuyuejun @ njust edu cn
History: 2024-04-14: last of 2 revisions; 2024-04-01: received; See all versions
Short URL: https://ia.cr/2024/512
License: CC BY

BibTeX

@misc{cryptoeprint:2024/512,
      author = {Zehua Qiao and Yuejun Liu and Yongbin Zhou and Yuhan Zhao and Shuyi Chen},
      title = {Single Trace is All It Takes: Efficient Side-channel Attack on Dilithium},
      howpublished = {Cryptology ePrint Archive, Paper 2024/512},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/512}},
      url = {https://eprint.iacr.org/2024/512}
}