Paper 2024/512
Single Trace is All It Takes: Efficient Sidechannel Attack on Dilithium
Abstract
As we enter 2024, the postquantum cryptographic algorithm Dilithium, which emerged from the National Institute of Standards and Technology postquantum 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 sidechannel 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 Regressionbased 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 CNNbased 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 optimizationbased 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)
 Category
 Attacks and cryptanalysis
 Publication info
 Preprint.
 Keywords
 DilithiumLatticebased CryptographyCNNSidechannel Attacks
 Contact author(s)

qiaozehua @ iie ac cn
liuyuejun @ njust edu cn  History
 20240414: last of 2 revisions
 20240401: 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 Sidechannel 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} }