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 s , which is achieved by blinding s⃗ s → via proper randomness y 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 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 y per signature, in any bit position j ≥ 6 j ≥ 6 . However, the number of required signatures grows exponentially as 4ʲ 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$$ j = 6 we require only a quarter of the signatures and reduce the exponential growth to 2ʲ 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%$$ 50 % . Experimentally, we still recover the secret with $$43%$$ 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 ℓ -dimensional module, the attack uses a 1-bit leak per signature to efficiently recover a 1/ 1 ℓ -fraction of the secret key. In the ring LWE setting, which can be seen as module LWE with = 1 ℓ = 1 , the attack recovers the whole key.