One (noisy) bit to rule them all: Key recovery from randomness leakage in ML-DSA

The Fiat-Shamir transform is one of the most widely applied methods for secure signature construction. Fiat-Shamir starts with an interactive zero-knowledge identification protocol and transforms this via a hash function into a non-interactive signature. The protocol's zero-knowledge property ensures that a signature does not leak information on its secret key $s$, which is achieved by blinding $\vec{s}$ via proper randomness $y$. Most prominent Fiat-Shamir examples are EC-DSA signatures and the new post-quantum standard ML-DSA (aka Dilithium). In practice, EC-DSA signatures have experienced fatal attacks via leakage of a few bits of the randomness $y$ per signature. Similar attacks now emerge for lattice-based signatures, such as ML-DSA. We build on, improve and generalize the pioneering leakage attack on ML-DSA by Liu, Zhou, Sun, Wang, Zhang, and Ming. Using a transformation to Integer LWE (ILWE), their attack can recover a 256-dimensional subkey of ML-DSA-44 from leakage in a single bit of $y$ per signature, in any bit position $j≥6$. However, the number of required signatures grows exponentially as $4^j$. In this work, we show that not all leaky signatures carry information about the secret subkey. We introduce the notion of informative signature relations. This notion allows us to define a preprocessing step, called filter-and-shift that leads to ILWE instances that require a smaller sample amount. Unlike the standard ILWE transformation, filter-and-shift exploits the smallness of secret keys, and therefore might be of independent cryptanalytic interest. In comparison to Liu et al., for $j=6$ we require only a quarter of the signatures and reduce the exponential growth to $2^j$. In addition, we show that the secret subkey can be recovered even with a leak bit corrupted by a large amount of noise, in theory up to the maximum of 50%. Experimentally, we still recover the secret with 43% noise, where we need 170 times as many signatures as in the noise-free setting. The attack applies more generally to all Fiat-Shamir-type lattice-based signatures. For a signature scheme based on module LWE over an $\ell$-dimensional module, the attack uses a 1-bit leak per signature to efficiently recover a 1$\ell$-fraction of the secret key. In the ring LWE setting, which can be seen as module LWE with $\ell=1$, the attack recovers the whole key.

• View at Publisher
• View at Scopus

Free Full Text ( Final Version , 993kb )