Alexandre Berzati
Thales DIS, Meudon, France

Andersson Calle Viera
Thales DIS, Meudon, France; Sorbonne Université, CNRS, Inria, LIP6, F-75005 Paris, France

Maya Chartouny
Thales DIS, Meudon, France; Université Paris-Saclay, UVSQ, CNRS, Laboratoire de mathématiques de Versailles, 78000, Versailles, France

Steven Madec
Thales DIS, Meudon, France

Damien Vergnaud
Sorbonne Université, CNRS, Inria, LIP6, F-75005 Paris, France

David Vigilant
Thales DIS, Meudon, France

Keywords: Dilithium, Digital signature, Lattice-based cryptography, Postquantum cryptography, Side-channel attacks, Template Attacks, Learning with Errors

Abstract

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.