International Association
for Cryptologic Research

In Dilithium, the rejection sampling step is crucial for the proof of security and correctness of the scheme. However, to our knowledge, there is no attack in the literature that takes advantage of an attacker knowing rejected signatures. The aim of this paper is to create a practical black-box attack against Dilithium with a weakened rejection sampling. We succeed in showing that an adversary with enough rejected signatures can recover Dilithium's secret key in less than half an hour on a desktop computer. There is one possible application for this result: by physically preventing one of the rejection sampling tests from happening, we obtain two fault attacks against Dilithium.

This paper presents a new profiling side-channel attack on CRYSTALSDilithium, the new NIST primary standard for quantum-safe digital signatures. An open source implementation of CRYSTALS-Dilithium is already available, with constant-time property as a consideration for side-channel resilience. However, this implementation does not protect against attacks that exploit intermediate data leakage. We show how to exploit a new leakage on a vector generated during the signing process, for which the costly protection by masking is still a matter of debate. With a corpus of 700 000 messages, we design a template attack that enables us to efficiently predict whether a given coefficient in one coordinate of this vector is zero or not. By gathering signatures and being able to make the correct predictions for each index, and then using linear algebra methods, this paper demonstrates that one can recover part of the secret key that is sufficient to produce universal forgeries. While our paper deeply discusses the theoretical attack path, it also demonstrates the validity of the assumption regarding the required leakage model from practical experiments with the reference implementation on an ARM Cortex-M4. We need approximately a day to collect enough representatives and one more day to perform the traces acquisition on our target.