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 the National Institute of Standards and Technology (NIST) concludes its post-quantum cryptography (PQC) competition, the winning algorithm, Dilithium, enters the deployment phase in 2024. This phase underscores the importance of conducting thorough practical security evaluations. Our study offers an in-depth side-channel analysis of Dilithium, showcasing the ability to recover the complete private key, ${s}_1$, within ten minutes using just two signatures and achieving a 60% success rate with a single signature. We focus on analyzing the polynomial addition in Dilithium, $z=y+{cs}_1$, by breaking down the attack into two main phases: the recovery of $y$ and ${cs}_1$ through side-channel attacks, followed by the resolution of a system of error-prone equations related to ${cs}_1$. Employing Linear Regression-based profiled attacks enables the successful recovery of the full $y$ value with a 40% success rate without the necessity for initial filtering. The extraction of ${cs}_1$ is further improved using a CNN model, which boasts an average success rate of 75%. A significant innovation of our research is the development of a constrained optimization-based residual analysis technique. This method efficiently recovers ${s}_1$ from a large set of error-containing equations concerning ${cs}_1$, proving effective even when only 10% of the equations are accurate. We conduct a practical attack on the Dilithium2 implementation on an STM32F4 platform, demonstrating that typically two signatures are sufficient for complete private key recovery, with a single signature sufficing in optimal conditions. Using a general-purpose PC, the full private key can be reconstructed in ten minutes.

Note: We will continue to revise the paper.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
DilithiumLattice-based CryptographyCNNSide-channel Attacks
Contact author(s)
qiaozehua @ iie ac cn
liuyuejun @ njust edu cn
History
2024-04-09: revised
2024-04-01: received
See all versions
Short URL
https://ia.cr/2024/512
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.