One (Noisy) Bit to Rule Them All: Key Recovery from Randomness Leakage in ML-DSA

Abstract

Abstract 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 $${\textbf{s}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>s</mml:mi> </mml:math> , which is achieved by blinding $$\vec {s}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mover> <mml:mi>s</mml:mi> <mml:mo>→</mml:mo> </mml:mover> </mml:math> via proper randomness $${\textbf{y}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>y</mml:mi> </mml:math> . 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 $${\textbf{y}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>y</mml:mi> </mml:math> 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 $$\textbf{y}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>y</mml:mi> </mml:math> per signature, in any bit position $$j \ge 6$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>j</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>6</mml:mn> </mml:mrow> </mml:math> . However, the number of required signatures grows exponentially as $$4^j$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>4</mml:mn> <mml:mi>j</mml:mi> </mml:msup> </mml:math> . 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>j</mml:mi> <mml:mo>=</mml:mo> <mml:mn>6</mml:mn> </mml:mrow> </mml:math> we require only a quarter of the signatures and reduce the exponential growth to $$2^j$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>j</mml:mi> </mml:msup> </mml:math> . 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\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>50</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> . Experimentally, we still recover the secret with $$43\%$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>43</mml:mn> <mml:mo>%</mml:mo> </mml:mrow> </mml:math> 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 $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ℓ</mml:mi> </mml:math> -dimensional module, the attack uses a 1-bit leak per signature to efficiently recover a $$\frac{1}{\ell }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mi>ℓ</mml:mi> </mml:mfrac> </mml:math> -fraction of the secret key. In the ring LWE setting, which can be seen as module LWE with $$\ell = 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>ℓ</mml:mi> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , the attack recovers the whole key.