Screening Least Square Technique Assisted Multivariate Template Attack Against the Random Polynomial Generation of Dilithium
Haopeng Fan, Hailong Zhang, Yongjuan Wang, Wenhao Wang, Yanbei Zhu, Haojin Zhang, Qingjun Yuan · IEEE Transactions on Information Forensics and Security · 2024
In recent years, the security of Dilithium against side-channel attacks (SCA) has attracted great attentions from the cryptographic engineering community. However, existing power analysis attacks cannot fully utilize the side-channel leakages of the Dilithium reference implementation to efficiently recover the private key. In light of this, a screening least square technique assisted multivariate template attack (SLST assisted MTA) is proposed in this paper. In SLST assisted MTA, side-channel leakages of coefficient$y_{i}$of random polynomial y, unsigned number$x_{i}$and random byte string$a_{i^{\prime }}$can be utilized simultaneously to recover coefficient$y_{i}$of random polynomial y with MTA. Then, one can build error-tolerant equations, and the private key$\mathbf {s_{1}}$can be solved with SLST efficiently. We evaluate the private key recovery efficiency of SLST assisted MTA with real traces measured from the Cortex-M4 processor based Dilithium reference implementation, and the evaluation results show that with MTA, 19.41%, 15.70% and 16.88% of the coefficients of y can be accurately recovered in cases of Dilithium 2, 3 and 5. Besides, using SLST, after five times screening, only 38, 40 and 39 power traces are enough to recover private key$\mathbf {s_{1}}$of Dilithium 2, 3 and 5 with 100% of success rate.