Paper 2023/050

Exploiting Intermediate Value Leakage in Dilithium: A Template-Based Approach

Alexandre Berzati, Thales (France)
Andersson Calle Viera, Thales (France), Laboratoire de Recherche en Informatique de Paris 6
Maya Chartouny
Steven Madec, Thales (France)
Damien Vergnaud, Laboratoire de Recherche en Informatique de Paris 6
David Vigilant, Thales (France)
Abstract

This paper presents a new profiling side-channel attack on CRYSTALS-Dilithium, 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 700000 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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
A major revision of an IACR publication in TCHES 2023
Keywords
DilithiumLattice-based cryptographyPost-quantum cryptographySide-channel attacksTemplate Attacks
Contact author(s)
alexandre berzati @ thalesgroup com
andersson calle-viera @ thalesgroup com
maya saab-chartouni @ thalesgroup com
steven madec @ thalesgroup com
david vigilant @ thalesgroup com
History
2023-07-17: revised
2023-01-16: received
See all versions
Short URL
https://ia.cr/2023/050
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/050,
      author = {Alexandre Berzati and Andersson Calle Viera and Maya Chartouny and Steven Madec and Damien Vergnaud and David Vigilant},
      title = {Exploiting Intermediate Value Leakage in Dilithium: A Template-Based Approach},
      howpublished = {Cryptology ePrint Archive, Paper 2023/050},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/050}},
      url = {https://eprint.iacr.org/2023/050}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.