Quantum Solace: Timing Leaks in RustCrypto's ML-DSA

Rust is the golden child of modern systems programming. It promises memory safety, concurrency without data races, and a compiler that yells at you until your code is correct. But there is one thing the Borrow Checker doesn't care about: Time. In the world of cryptography, correct answers delivered at variable speeds are just as dangerous as wrong answers.

CVE-2026-22705 targets the ml-dsa crate, a Rust implementation of Module-Lattice-Based Digital Signature Standard (formerly Dilithium). This is Post-Quantum Cryptography (PQC)—the math designed to save us when quantum computers eventually crack RSA and Elliptic Curves. The irony? We don't need a quantum computer to break this implementation; we just need a stopwatch.

The vulnerability lies in a classic cryptographic sin: performing mathematical operations on secret data using CPU instructions that take variable amounts of time to execute. Specifically, the implementation used standard integer division during the decompose step and runtime loop calculations in the Number Theoretic Transform (NTT). To a CPU, dividing a small number is faster than dividing a big one. To a hacker, that speed difference is a beacon broadcasting the private key bits.

To understand why this breaks, you have to look at the silicon. Modern CPUs (x86, ARM, etc.) are obsessed with speed. When you ask a CPU to divide two numbers (DIV or IDIV instruction), the Arithmetic Logic Unit (ALU) doesn't just churn for a fixed number of cycles. It optimizes. If the numbers are small, or if the high bits are zero, the CPU takes a shortcut, returning the result fewer cycles than if it were crunching a full 64-bit integer.

In ml-dsa/src/algebra.rs, the code was performing decompose on coefficients derived from the secret key ($s_2, t_0$). The code looked innocent enough—using the / operator. However, because the operands were secret-dependent, the "early exit" optimization in the hardware meant that the total time to sign a message fluctuated based on the values of the secret key.

Furthermore, in ml-dsa/src/ntt.rs, the loop strides were calculated at runtime. The compiler (LLVM), trying to be helpful, often inserts division or modulo instructions to handle loop bounds that aren't known at compile time. This introduced a second layer of timing noise correlated with the structure of the data being transformed. By collecting enough traces, the noise cancels out, and the signal—the secret key—emerges.

The fix involves purging the / operator from critical paths. Since we can't trust the CPU's division instruction, we have to simulate division using operations that are constant time: multiplication and bit-shifting. This technique is known as Barrett Reduction.

The patch replaces the raw division with a ConstantTimeDiv trait. Instead of calculating q = x / m, we precompute a magic multiplier roughly equal to $2^k / m$. Then, at runtime, we multiply the input by this magic number and shift the result right by $k$ bits.

Here is the critical change in ml-dsa/src/algebra.rs:

// THE VULNERABLE WAY:
// let q = r / M; // Hardware division. Fast? Yes. Constant time? No.
 
// THE FIXED WAY (Barrett Reduction):
// Precomputed: CT_DIV_MULTIPLIER = ceil(2^48 / M)
fn ct_div(x: u32) -> u32 {
    let x64 = u64::from(x);
    // Multiplication and Shift are constant-time on most ALUs
    let quotient = (x64 * Self::CT_DIV_MULTIPLIER) >> Self::CT_DIV_SHIFT;
    quotient as u32
}

Additionally, the developers switched to using const generics for the NTT loops. By making the loop bounds (LEN) a compile-time constant, the compiler can unroll loops or use immediate values, eliminating the need for runtime division instructions entirely.

Exploiting this isn't like popping a shell with a buffer overflow. It's a statistical attack. The attacker needs to trigger a few thousand (or million) signatures and record the time delta between the request and the response.

Here is the attack logic:

1. Collection: The attacker sets up a listener (if local) or a network client (if adjacent/remote) and requests signatures for random messages.
2. Filtering: They filter out network jitter (outliers) to isolate the CPU processing time.
3. Hypothesis Testing: The attacker guesses a byte of the secret key. Using a model of the decompose function, they predict whether that guess would result in a 'fast' or 'slow' division for a specific message.
4. Correlation: They correlate the actual measured times with their predictions. If the correlation spikes for a specific key guess, that's the correct key byte.

The beauty (and horror) of this exploit is that it leaves no trace on the server. No crash logs, no segfaults. Just a slightly warm CPU and a stolen identity.

The impact here is total compromise of the cryptographic identity. If an attacker recovers the private key, they can forge signatures for any message.

This is particularly devastating for ml-dsa because it is a signature scheme. If this were used for, say, software signing or PKI root CAs (which is exactly where PQC is headed), an attacker could sign malicious updates or issue fraudulent certificates that are mathematically indistinguishable from legitimate ones.

While the CVSS score is a 'Medium' 6.4 due to the complexity of the attack (High Complexity, Adjacent Vector), the consequences are Critical. In a controlled environment—like a Hardware Security Module (HSM) or a secure enclave sharing resources with an attacker—this is a game-over scenario.

The remediation is straightforward: Update to 0.1.0-rc.2 or later immediately.

For developers writing cryptographic code, the lesson is stark: Never trust the compiler, and never trust the ALU. If your operation involves secrets, you cannot use standard division (/), modulo (%), or data-dependent branching (if secret { ... }).

If you are auditing Rust crypto code, grep for / and %. If you see them applied to anything that smells like a key or a nonce, you likely have a CVE on your hands. Always prefer bitwise operations (&, |, ^, >>, <<) which are historically guaranteed to be constant-time on general-purpose architectures.