International Association
for Cryptologic Research

Lattice-based signatures like Dilithium (ML-DSA) prove knowl- edge of a secret key $s \in \mathbb{Z}_n$ by using Integer LWE (ILWE) samples $z = \langle \vec c, \vec s \rangle +y $, for some known hash value $c \in \mathbb{Z}_n$ 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 $\langle c, s \rangle$ —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 = \langle c, s \rangle$ 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.

At SAC 2016, Espitau et al. presented a loop-abort fault attack against lattice-based signature schemes following the Fiat–Shamir with aborts paradigm. Their attack recovered the signing key by injecting faults in the sampling of the commitment vector (also called masking vector) y, leaving its coefficients at their initial zero value. As possible countermeasures, they proposed to carry out the sampling of the coefficients of y in shuffled order, or to ensure that the masking polynomials in y are not of low degree. In this paper, we show that both of these countermeasures are insufficient. We demonstrate a new loop-abort fault injection attack against Fiat–Shamir with aborts lattice-based signatures that can recover the secret key from faulty signatures even when the proposed countermeasures are implemented. The key idea of our attack is that faulted signatures give rise to a noisy linear system of equations, which can be solved using integer linear programming. We present an integer linear program that recovers the secret key efficiently in practice, and validate the efficacy of our attack by conducting a practical end-to-end attack against a shuffled version of the Dilithium reference implementation, mounted on an ARM Cortex M4. We achieve a full (equivalent) key recovery in under 3 minutes total execution time (including signature generation), using only 5 faulted signatures. In addition, we conduct extensive theoretical simulations of the attack against Dilithium. We find that our method can achieve key recovery in under 5 minutes given a (sufficiently large) set of signatures where just one of the coefficients of y is zeroed out (or left at its initial value of zero). Furthermore, we find that our attack works against all security levels of Dilithium. Our attack shows that protecting Fiat–Shamir with aborts lattice-based signatures against fault injection attacks cannot be achieved using the simple countermeasures proposed by Espitau et al. and likely requires significantly more expensive countermeasures.