Simon Damm
Faculty of Computer Science, Ruhr University Bochum, Bochum, Germany

Asja Fischer
Faculty of Computer Science, Ruhr University Bochum, Bochum, Germany

Alexander May
Faculty of Computer Science, Ruhr University Bochum, Bochum, Germany

Soundes Marzougui
Deutsches Elektronen-Synchrotron, Hamburg, Germany

Leander Schwarz
Technische Universität Berlin – SecT, Berlin, Germany; STMicroelectronics, Machelen, Belgium

Henning Seidler
Technische Universität Berlin – SecT, Berlin, Germany

Jean-Pierre Seifert
Technische Universität Berlin – SecT, Berlin, Germany

Jonas Thietke
Faculty of Computer Science, Ruhr University Bochum, Bochum, Germany

Vincent Quentin Ulitzsch
Technische Universität Berlin – SecT, Berlin, Germany

Keywords:

Abstract

Lattice-based signatures like Dilithium (ML-DSA) prove knowledge of a secret key s ∈ Zⁿ by using Integer LWE (ILWE) samples z = ⟨c, s⟩ + y, for some known hash value c ∈ Zⁿ of the message and unknown error y. Rejection sampling guarantees zero-knowledge, which makes the ILWE problem, that asks to recover s from many z’s, unsolvable.

Side-channel attacks partially recover y, thereby obtaining more informative samples resulting in a—potentially tractable—ILWE problem. The standard method to solve the resulting problem is Ordinary Least Squares (OLS), which requires independence of y from ⟨c, s⟩—an assumption that is violated by zero-knowledge samples.

We present efficient algorithms for a variant of the ILWE problem that was not addressed in prior work, which we coin Concealed ILWE (CILWE). In this variant, only a fraction of the ILWE samples is zero-knowledge. We call this fraction the concealment rate. This ILWE variant naturally occurs in side-channel attacks on lattice-based signatures. A case in point are profiling side-channel attacks on Dilithium implementations that classify whether y = 0. This gives rise to either zero-error ILWE samples z = ⟨c, s⟩ with y = 0 (in case of correct classification), or ordinary zero-knowledge ILWE samples (in case of misclassification).

As we show, OLS is not practical for CILWE instances, as it requires a prohibitively large amount of samples for even small (under 10%) concealment rates. A known integer linear programming-based approach can solve some CILWE instances, but suffers from two short-comings. First, it lacks provable efficiency guarantees, as ILP is NP-hard in the worst case. Second, it does not utilize small, independent error y samples, that could occur in addition to zero-knowledge samples.

We introduce two statistical regression methods to cryptanalysis, Huber and Cauchy regression. They are both efficient and can handle instances with all three types of samples. At the same time, they are capable of handling high concealment rates, up to 90% in practical experiments. While Huber regression comes with theoretically appealing correctness guarantees, Cauchy regression performs best in practice.

We use this efficacy to execute a novel profiling attack against a masked Dilithium implementation. The resulting ILWE instances suffer from both concealment and small, independent errors. As such, neither OLS nor ILP can recover the secret key. Cauchy regression, however, allows us to recover the secret key in under two minutes for all NIST security levels