Release the Power of Rejected Signatures: An Efficient Side-Channel Attack on the ML-DSA Cryptosystem

The module-lattice-based digital signature standard, formerly known as CRYSTALS-DILITHIUM, is a lattice-based post-quantum cryptographic scheme. In August 2024, the National Institute of Standards and Technology officially standardized ML-DSA under FIPS 204. ML-DSA generates one valid signature and multiple rejected signatures during a single signing process. Most side-channel attacks targeting ML-DSA have focused solely on the valid signature, while largely neglecting the hints contained in rejected signatures. Building on prior SASCA frameworks originally proposed for ML-DSA, in this paper we present an efficient and fully practical instantiation of a private-key recovery attack on ML-DSA that jointly exploits side-channel leakages from both valid and rejected signatures within a unified factor graph. This concrete instantiation maximizes the information extracted from a single signing attempt and minimizes the number of required traces for full key recovery. We conducted a proof-of-concept experiment with both reference and ASM-optimized implementations on a Cortex-M4 core chip, where the results demonstrate that incorporating rejected signatures reduces the required number of traces by at least 50.0% for full key recovery. Moreover, we show that using only rejected signatures suffices to recover the key with fewer than 30 traces under our setup. Our findings highlight that protecting rejected signatures is crucial, as their leakage provides valuable side-channel information. We strongly recommend implementing countermeasures for rejected signatures during the signing process to mitigate potential threats.