Single-Trace Side-Channel Attacks on CRYSTALS-Dilithium: Myth or Reality?

We present a side-channel attack on CRYSTALS-Dilithium, a post-quantum secure digital signature scheme, with two variants of post-processing. The side-channel attack exploits information leakage in the secret key unpacking procedure of the signing algorithm to recover the coefficients of the polynomials in the secret key vectors s1 and s2 by profiled deep learning-assisted power analysis. In the first variant, one half of the coefficients of s₁ and s₂ is recovered by power analysis and the rest is derived by solving a system of linear equations based on t = As₁ + s₂, where A and t are parts of the public key. This case assumes knowledge of the least significant bits of the vector t, t₀. The second variant waives this requirement. However, to succeed, it needs a larger portion of s₁ to be recovered by power analysis. The remainder of s₁ is obtained by lattice reduction. Once the full s₁ is recovered, all the other information necessary for generating valid signatures can be trivially derived from the public key. We evaluate both variants on an ARM Cortex-M4 implementation of Dilithium-2. The profiling stage (trace capture and neural network training) takes less than 10 hours. In the attack assuming that t0 is known, the probability of successfully recovering the full vector s₁ from a single trace captured from a different from profiling device is non-negligible (9%). The success rate approaches 100% if multiple traces are available for the attack. Our results demonstrate the necessity of protecting the secret key of CRYSTALS-Dilithium from single-trace attacks and call for a reassessment of the role of compression of the public key vector t in the security of CRYSTALS-Dilithium implementations.