Practical Public Template Attack Attacks on CRYSTALS-Dilithium With Randomness Leakages

Side-channel security has become a significant concern in the NIST post-quantum cryptography standardization process. The lattice-based CRYSTALS-Dilithium (abbr. Dilithium) becomes the primary signature standard algorithm recommended by NIST for most use cases in July 2022 due to its excellent performance in security and efficiency. Compared to Dilithium’s rich theoretical security analysis results, the side-channel security of its physical implementations needs to be further explored. In 2021, Liu et al. proposed a two-stage randomness leakage attack against Dilithium, in which only one randomness bit with a probability >0.5 per signature is enough to recover the private key. However, they only carried out proof-of-concept experiments on “research-oriented” reference implementation of polynomial addition. Whether this method applies to complete real-world implementations of Dilithium is unknown. In this paper, we put this randomness leakage attack into real-world and recover the private key of unprotected and masked Dilithium on Arm Cortex-M4 processor using non-profiled power analysis attacks. Since randomness is introduced in the signing process, it is challenging to recover the randomness bit of Dilithium with high success rate in only one trace. Inspired by Liu et al., we propose a new non-profiled attack called Public Template Attack (PTA), a template-attack-like method that builds templates using public information. With PTA, we recover the randomness bit of unprotected and masked Dilithium with a success rate of 95% and 62% in one power trace, respectively. To demonstrate practicality, we perform practical power analysis attacks against different security levels of round 3 unprotected and masked Dilithium on STM32F405 microprocessor. Using 10,000 traces, the private key of unprotected Dilithium2 is recovered in 0.5 hours with an ordinary PC desktop. Our attack is 240 times faster than the state-of-the-art non-profiled attack. Moreover, the private key...

The invention of Shor algorithm [1] provides a polynomial time method to solve large integer factorization [2] and discrete logarithm problems [3] by general-purpose quantum computers. This will make existing digital signature schemes (e.g., RSA, ECC) based on these two types of problems insecure in the future. To address these threats, the National Institute of Standards and Technology (NIST) launched the post-quantum cryptography (PQC) standardization process in 2016. Among all the participating algorithms, lattice-based cryptography is considered one of the most promising candidates for the PQC standard due to its good security and competitive performance. According to the NIST PQC standardization process status report [4] published in July 2022, CRYSTALS-Dilithium (abbr. Dilithium) [5] is recommended to be the primary signature standard algorithm for most use cases.