ml-dsa

Summary

There's a bug in the use_hint function where it adds 1 instead of subtracting 1 when the decomposed low bits r0 equal exactly zero. FIPS 204 Algorithm 40 is pretty clear that r0 > 0 means strictly positive, but the current code treats zero as positive. This causes valid signatures to potentially fail verification when this edge case gets hit.

Details

The issue is in ml-dsa/src/hint.rs in the use_hint function. Here's what FIPS 204 Algorithm 40 says:

3: if h = 1 and r0 > 0  return (r1 + 1) mod m
4: if h = 1 and r0 <= 0  return (r1 − 1) mod m

Line 3 uses r0 > 0 (strictly greater than zero), and line 4 uses r0 <= 0 (less than or equal, which includes zero). So when r0 = 0, the spec says to subtract 1.

But the current implementation does this:

if h && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h && r0.0 >= BaseField::Q - gamma2 {
    Elem::new((r1.0 + m - 1) % m)
}

The problem is r0.0 <= gamma2 includes zero. When r0 = 0, this condition is true (since 0 <= gamma2), so it adds 1. But according to the spec, r0 = 0 should fall into the r0 <= 0 case and subtract 1 instead.

The result is +1 when it should be -1, which is an off by two error mod m.

PoC

Take MLDSA 44 where γ2 = 95,232 and m = 44.

If use_hint(true, 0) is called:

• Decompose(0) gives (r1=0, r0=0)
• The condition r0.0 <= gamma2 is 0 <= 95232 which is true
• So it returns (0 + 1) % 44 = 1

But FIPS 204 says:

• r0 > 0 is 0 > 0 which is false
• r0 ≤ 0 is 0 ≤ 0 which is true
• So it should return (0 - 1) mod 44 = 43

The function returns 1 when it should return 43.

This can happen in real signatures whenever any coefficient of the w' vector happens to be a multiple of 2γ2, which makes its decomposed r0 equal zero. It's not super common but it's definitely possible, and when it hits, verification will fail for a completely valid signature.

Impact

This is a FIPS 204 compliance bug that affects signature verification. When the edge case triggers, valid signatures get rejected. Since MLDSA is supposed to be used for high security post quantum cryptography, having verification randomly fail isn't great. It's also theoretically possible that the mismatch between what signing expects and what verification does could be exploited somehow, though that would need more looking into.

The fix is straightforward, just change the condition to explicitly check for positive values:

if h && r0.0 > 0 && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h {
    Elem::new((r1.0 + m - 1) % m)
}

Affected Crate: ml-dsa
Affected Versions: v0.1.0-rc.2 (and commits since b01c3b7)
Severity: Medium
Reporter: Oren Yomtov (Fireblocks)

Summary

The ML-DSA signature verification implementation in the RustCrypto ml-dsa crate incorrectly accepts signatures with repeated (duplicate) hint indices. According to the ML-DSA specification (FIPS 204 / RFC 9881), hint indices within each polynomial must be strictly increasing. The current implementation uses a non-strict monotonic check (<= instead of <), allowing duplicate indices.

Note: This is a regression bug. The original implementation was correct, but commit b01c3b7 ("Make ML-DSA signature decoding follow the spec (#895)", fixing issue #894) inadvertently changed the strict < comparison to <=, introducing the vulnerability.

Vulnerability Details

Root Cause

The vulnerability is located in the monotonic helper function in ml-dsa/src/hint.rs:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] <= *x)
}

The comparison operator <= allows equal consecutive values, meaning duplicate hint indices are not rejected. The correct implementation should use strict less-than (<):

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Regression Analysis

• Original correct code (commit 1d3a1d1 - "Add support for ML-DSA (#877)"): Used < (strict)
• Bug introduced (commit b01c3b7 - "Make ML-DSA signature decoding follow the spec (#895)"): Changed to <=

The commit message suggests it was intended to fix issue #894 and make decoding follow the spec, but the change to the monotonic function was in the wrong direction. The other changes in that commit (to use_hint function) may have been correct, but this specific change introduced signature malleability.

Technical Impact

This vulnerability allows signature malleability - the same logical signature can have multiple valid byte-level encodings. An attacker can take a valid signature and create additional "valid" signatures by duplicating hint indices.

Per the ML-DSA specification (FIPS 204, Section 6.2 and Algorithm 26 HintBitUnpack), hint indices must be strictly increasing to ensure a unique, canonical encoding. Accepting non-canonical signatures can lead to:

1. Signature Malleability: Multiple distinct byte sequences verify as valid for the same message/key pair
2. Protocol-Level Vulnerabilities: Systems that rely on signature uniqueness (e.g., for transaction deduplication, replay protection, or signature-based identifiers) may be vulnerable
3. Interoperability Issues: Non-compliant signatures may be rejected by other conforming implementations

Affected Security Levels

All ML-DSA parameter sets are affected:

• ML-DSA-44 (NIST Security Level 2)
• ML-DSA-65 (NIST Security Level 3)
• ML-DSA-87 (NIST Security Level 5)

Proof of Concept

See the file poc_mldsa_repeated_hint.rs for a standalone proof of concept that demonstrates the vulnerability.

The PoC uses test vectors from the Wycheproof test suite that specifically test for this invalid encoding:

• Test Vector Source: Wycheproof ML-DSA Test Vectors
• Test Case ID 18: "signature with a repeated hint"
• Expected Result: invalid
• Actual Result: valid (BUG)

Remediation

Update the monotonic function in ml-dsa/src/hint.rs to use strict less-than comparison:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Design Intent: ML-DSA is NOT Intended to Allow Malleability

While some cryptographic libraries intentionally permit signature malleability for compatibility or performance reasons, ML-DSA is explicitly designed to prevent it:

1. FIPS 204 Specification: ML-DSA is designed to be strongly unforgeable under chosen message attacks (SUF-CMA). This security property explicitly prevents signature malleability.

2. NIST PQC Forum Discussion: In February 2024, there was a discussion on the NIST PQC forum about potential malleability in ML-DSA's hint unpacking. The consensus was that ML-DSA is intended to be SUF-CMA, meaning any malleability issues should be considered bugs and fixed.

3. No Documentation of Intentional Malleability: There is no documentation in the RustCrypto ml-dsa crate, FIPS 204, or RFC 9881 suggesting that signature malleability is an acceptable or intentional property.

4. Regression Bug: The fact that the original implementation had strict ordering (<) and this was changed to non-strict (<=) in a "fix" commit suggests this was an unintentional regression, not a design decision.

Summary

A timing side-channel was discovered in the Decompose algorithm which is used during ML-DSA signing to generate hints for the signature.

Details

The analysis was performed using a constant-time analyzer that examines compiled assembly code for instructions with data-dependent timing behavior. The analyzer flags:

• UDIV/SDIV instructions: Hardware division instructions have early termination optimizations where execution time depends on operand values.

The decompose function used a hardware division instruction to compute r1.0 / TwoGamma2::U32. This function is called during signing through high_bits() and low_bits(), which process values derived from secret key components:

• (&w - &cs2).low_bits() where cs2 is derived from secret key component s2
• Hint::new() calls high_bits() on values derived from secret key component t0

Original Code:

fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
    // ...
    let mut r1 = r_plus - r0;
    r1.0 /= TwoGamma2::U32;  // Variable-time division on secret-derived data
    (r1, r0)
}

PoC

I do not have an exploit written for this, currently.

Impact

The dividend (r1.0) is derived from secret key material. An attacker with precise timing measurements could extract information about the signing key by observing timing variations in the division operation.

Mitigation

Replacing division with constant-time Barrett reduction mitigates this risk. Since TwoGamma2 is a compile-time constant, we precompute the multiplicative inverse:

diff --git a/ml-dsa/src/algebra.rs b/ml-dsa/src/algebra.rs
index 559b68a..bb126ce 100644
--- a/ml-dsa/src/algebra.rs
+++ b/ml-dsa/src/algebra.rs
@@ -54,8 +54,50 @@ pub(crate) trait Decompose {
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem);
 }
 
+/// Constant-time division by a compile-time constant divisor.
+///
+/// This trait provides a constant-time alternative to the hardware division
+/// instruction, which has variable timing based on operand values.
+/// Uses Barrett reduction to compute `x / M` where M is a compile-time constant.
+pub(crate) trait ConstantTimeDiv: Unsigned {
+    /// Bit shift for Barrett reduction, chosen to provide sufficient precision
+    const CT_DIV_SHIFT: usize;
+    /// Precomputed multiplier: ceil(2^SHIFT / M)
+    const CT_DIV_MULTIPLIER: u64;
+
+    /// Perform constant-time division of x by Self::U32
+    /// Requires: x < Q (the field modulus, ~2^23)
+    #[inline(always)]
+    fn ct_div(x: u32) -> u32 {
+        // Barrett reduction: q = (x * MULTIPLIER) >> SHIFT
+        // This gives us floor(x / M) for x < 2^SHIFT / MULTIPLIER * M
+        let x64 = u64::from(x);
+        let quotient = (x64 * Self::CT_DIV_MULTIPLIER) >> Self::CT_DIV_SHIFT;
+        quotient as u32
+    }
+}
+
+impl<M> ConstantTimeDiv for M
+where
+    M: Unsigned,
+{
+    // Use a shift that provides enough precision for the ML-DSA field (Q ~ 2^23)
+    // We need SHIFT > log2(Q) + log2(M) to ensure accuracy
+    // With Q < 2^24 and M < 2^20, SHIFT = 48 is sufficient
+    const CT_DIV_SHIFT: usize = 48;
+
+    // Precompute the multiplier at compile time
+    // We add (M-1) before dividing to get ceiling division, ensuring we never underestimate
+    #[allow(clippy::integer_division_remainder_used)]
+    const CT_DIV_MULTIPLIER: u64 = ((1u64 << Self::CT_DIV_SHIFT) + M::U64 - 1) / M::U64;
+}
+
 impl Decompose for Elem {
     // Algorithm 36 Decompose
+    //
+    // This implementation uses constant-time division to avoid timing side-channels.
+    // The original algorithm used hardware division which has variable timing based
+    // on operand values, potentially leaking secret information during signing.
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
         let r_plus = self.clone();
         let r0 = r_plus.mod_plus_minus::<TwoGamma2>();
@@ -63,8 +105,9 @@ impl Decompose for Elem {
         if r_plus - r0 == Elem::new(BaseField::Q - 1) {
             (Elem::new(0), r0 - Elem::new(1))
         } else {
-            let mut r1 = r_plus - r0;
-            r1.0 /= TwoGamma2::U32;
+            let diff = r_plus - r0;
+            // Use constant-time division instead of hardware division
+            let r1 = Elem::new(TwoGamma2::ct_div(diff.0));
             (r1, r0)
         }
     }

See our blog post on how we avoided side-channels in our Go implementation of ML-DSA for more information.

Summary

There's a bug in the use_hint function where it adds 1 instead of subtracting 1 when the decomposed low bits r0 equal exactly zero. FIPS 204 Algorithm 40 is pretty clear that r0 > 0 means strictly positive, but the current code treats zero as positive. This causes valid signatures to potentially fail verification when this edge case gets hit.

Details

The issue is in ml-dsa/src/hint.rs in the use_hint function. Here's what FIPS 204 Algorithm 40 says:

3: if h = 1 and r0 > 0  return (r1 + 1) mod m
4: if h = 1 and r0 <= 0  return (r1 − 1) mod m

Line 3 uses r0 > 0 (strictly greater than zero), and line 4 uses r0 <= 0 (less than or equal, which includes zero). So when r0 = 0, the spec says to subtract 1.

But the current implementation does this:

if h && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h && r0.0 >= BaseField::Q - gamma2 {
    Elem::new((r1.0 + m - 1) % m)
}

The problem is r0.0 <= gamma2 includes zero. When r0 = 0, this condition is true (since 0 <= gamma2), so it adds 1. But according to the spec, r0 = 0 should fall into the r0 <= 0 case and subtract 1 instead.

The result is +1 when it should be -1, which is an off by two error mod m.

PoC

Take MLDSA 44 where γ2 = 95,232 and m = 44.

If use_hint(true, 0) is called:

• Decompose(0) gives (r1=0, r0=0)
• The condition r0.0 <= gamma2 is 0 <= 95232 which is true
• So it returns (0 + 1) % 44 = 1

But FIPS 204 says:

• r0 > 0 is 0 > 0 which is false
• r0 ≤ 0 is 0 ≤ 0 which is true
• So it should return (0 - 1) mod 44 = 43

The function returns 1 when it should return 43.

This can happen in real signatures whenever any coefficient of the w' vector happens to be a multiple of 2γ2, which makes its decomposed r0 equal zero. It's not super common but it's definitely possible, and when it hits, verification will fail for a completely valid signature.

Impact

This is a FIPS 204 compliance bug that affects signature verification. When the edge case triggers, valid signatures get rejected. Since MLDSA is supposed to be used for high security post quantum cryptography, having verification randomly fail isn't great. It's also theoretically possible that the mismatch between what signing expects and what verification does could be exploited somehow, though that would need more looking into.

The fix is straightforward, just change the condition to explicitly check for positive values:

if h && r0.0 > 0 && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h {
    Elem::new((r1.0 + m - 1) % m)
}

Affected Crate: ml-dsa
Affected Versions: v0.1.0-rc.2 (and commits since b01c3b7)
Severity: Medium
Reporter: Oren Yomtov (Fireblocks)

Summary

The ML-DSA signature verification implementation in the RustCrypto ml-dsa crate incorrectly accepts signatures with repeated (duplicate) hint indices. According to the ML-DSA specification (FIPS 204 / RFC 9881), hint indices within each polynomial must be strictly increasing. The current implementation uses a non-strict monotonic check (<= instead of <), allowing duplicate indices.

Note: This is a regression bug. The original implementation was correct, but commit b01c3b7 ("Make ML-DSA signature decoding follow the spec (#895)", fixing issue #894) inadvertently changed the strict < comparison to <=, introducing the vulnerability.

Vulnerability Details

Root Cause

The vulnerability is located in the monotonic helper function in ml-dsa/src/hint.rs:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] <= *x)
}

The comparison operator <= allows equal consecutive values, meaning duplicate hint indices are not rejected. The correct implementation should use strict less-than (<):

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Regression Analysis

• Original correct code (commit 1d3a1d1 - "Add support for ML-DSA (#877)"): Used < (strict)
• Bug introduced (commit b01c3b7 - "Make ML-DSA signature decoding follow the spec (#895)"): Changed to <=

The commit message suggests it was intended to fix issue #894 and make decoding follow the spec, but the change to the monotonic function was in the wrong direction. The other changes in that commit (to use_hint function) may have been correct, but this specific change introduced signature malleability.

Technical Impact

This vulnerability allows signature malleability - the same logical signature can have multiple valid byte-level encodings. An attacker can take a valid signature and create additional "valid" signatures by duplicating hint indices.

Per the ML-DSA specification (FIPS 204, Section 6.2 and Algorithm 26 HintBitUnpack), hint indices must be strictly increasing to ensure a unique, canonical encoding. Accepting non-canonical signatures can lead to:

1. Signature Malleability: Multiple distinct byte sequences verify as valid for the same message/key pair
2. Protocol-Level Vulnerabilities: Systems that rely on signature uniqueness (e.g., for transaction deduplication, replay protection, or signature-based identifiers) may be vulnerable
3. Interoperability Issues: Non-compliant signatures may be rejected by other conforming implementations

Affected Security Levels

All ML-DSA parameter sets are affected:

• ML-DSA-44 (NIST Security Level 2)
• ML-DSA-65 (NIST Security Level 3)
• ML-DSA-87 (NIST Security Level 5)

Proof of Concept

See the file poc_mldsa_repeated_hint.rs for a standalone proof of concept that demonstrates the vulnerability.

The PoC uses test vectors from the Wycheproof test suite that specifically test for this invalid encoding:

• Test Vector Source: Wycheproof ML-DSA Test Vectors
• Test Case ID 18: "signature with a repeated hint"
• Expected Result: invalid
• Actual Result: valid (BUG)

Remediation

Update the monotonic function in ml-dsa/src/hint.rs to use strict less-than comparison:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Design Intent: ML-DSA is NOT Intended to Allow Malleability

While some cryptographic libraries intentionally permit signature malleability for compatibility or performance reasons, ML-DSA is explicitly designed to prevent it:

1. FIPS 204 Specification: ML-DSA is designed to be strongly unforgeable under chosen message attacks (SUF-CMA). This security property explicitly prevents signature malleability.

2. NIST PQC Forum Discussion: In February 2024, there was a discussion on the NIST PQC forum about potential malleability in ML-DSA's hint unpacking. The consensus was that ML-DSA is intended to be SUF-CMA, meaning any malleability issues should be considered bugs and fixed.

3. No Documentation of Intentional Malleability: There is no documentation in the RustCrypto ml-dsa crate, FIPS 204, or RFC 9881 suggesting that signature malleability is an acceptable or intentional property.

4. Regression Bug: The fact that the original implementation had strict ordering (<) and this was changed to non-strict (<=) in a "fix" commit suggests this was an unintentional regression, not a design decision.

Summary

A timing side-channel was discovered in the Decompose algorithm which is used during ML-DSA signing to generate hints for the signature.

Details

The analysis was performed using a constant-time analyzer that examines compiled assembly code for instructions with data-dependent timing behavior. The analyzer flags:

• UDIV/SDIV instructions: Hardware division instructions have early termination optimizations where execution time depends on operand values.

The decompose function used a hardware division instruction to compute r1.0 / TwoGamma2::U32. This function is called during signing through high_bits() and low_bits(), which process values derived from secret key components:

• (&w - &cs2).low_bits() where cs2 is derived from secret key component s2
• Hint::new() calls high_bits() on values derived from secret key component t0

Original Code:

fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
    // ...
    let mut r1 = r_plus - r0;
    r1.0 /= TwoGamma2::U32;  // Variable-time division on secret-derived data
    (r1, r0)
}

PoC

I do not have an exploit written for this, currently.

Impact

The dividend (r1.0) is derived from secret key material. An attacker with precise timing measurements could extract information about the signing key by observing timing variations in the division operation.

Mitigation

Replacing division with constant-time Barrett reduction mitigates this risk. Since TwoGamma2 is a compile-time constant, we precompute the multiplicative inverse:

diff --git a/ml-dsa/src/algebra.rs b/ml-dsa/src/algebra.rs
index 559b68a..bb126ce 100644
--- a/ml-dsa/src/algebra.rs
+++ b/ml-dsa/src/algebra.rs
@@ -54,8 +54,50 @@ pub(crate) trait Decompose {
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem);
 }
 
+/// Constant-time division by a compile-time constant divisor.
+///
+/// This trait provides a constant-time alternative to the hardware division
+/// instruction, which has variable timing based on operand values.
+/// Uses Barrett reduction to compute `x / M` where M is a compile-time constant.
+pub(crate) trait ConstantTimeDiv: Unsigned {
+    /// Bit shift for Barrett reduction, chosen to provide sufficient precision
+    const CT_DIV_SHIFT: usize;
+    /// Precomputed multiplier: ceil(2^SHIFT / M)
+    const CT_DIV_MULTIPLIER: u64;
+
+    /// Perform constant-time division of x by Self::U32
+    /// Requires: x < Q (the field modulus, ~2^23)
+    #[inline(always)]
+    fn ct_div(x: u32) -> u32 {
+        // Barrett reduction: q = (x * MULTIPLIER) >> SHIFT
+        // This gives us floor(x / M) for x < 2^SHIFT / MULTIPLIER * M
+        let x64 = u64::from(x);
+        let quotient = (x64 * Self::CT_DIV_MULTIPLIER) >> Self::CT_DIV_SHIFT;
+        quotient as u32
+    }
+}
+
+impl<M> ConstantTimeDiv for M
+where
+    M: Unsigned,
+{
+    // Use a shift that provides enough precision for the ML-DSA field (Q ~ 2^23)
+    // We need SHIFT > log2(Q) + log2(M) to ensure accuracy
+    // With Q < 2^24 and M < 2^20, SHIFT = 48 is sufficient
+    const CT_DIV_SHIFT: usize = 48;
+
+    // Precompute the multiplier at compile time
+    // We add (M-1) before dividing to get ceiling division, ensuring we never underestimate
+    #[allow(clippy::integer_division_remainder_used)]
+    const CT_DIV_MULTIPLIER: u64 = ((1u64 << Self::CT_DIV_SHIFT) + M::U64 - 1) / M::U64;
+}
+
 impl Decompose for Elem {
     // Algorithm 36 Decompose
+    //
+    // This implementation uses constant-time division to avoid timing side-channels.
+    // The original algorithm used hardware division which has variable timing based
+    // on operand values, potentially leaking secret information during signing.
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
         let r_plus = self.clone();
         let r0 = r_plus.mod_plus_minus::<TwoGamma2>();
@@ -63,8 +105,9 @@ impl Decompose for Elem {
         if r_plus - r0 == Elem::new(BaseField::Q - 1) {
             (Elem::new(0), r0 - Elem::new(1))
         } else {
-            let mut r1 = r_plus - r0;
-            r1.0 /= TwoGamma2::U32;
+            let diff = r_plus - r0;
+            // Use constant-time division instead of hardware division
+            let r1 = Elem::new(TwoGamma2::ct_div(diff.0));
             (r1, r0)
         }
     }

See our blog post on how we avoided side-channels in our Go implementation of ML-DSA for more information.

Summary

There's a bug in the use_hint function where it adds 1 instead of subtracting 1 when the decomposed low bits r0 equal exactly zero. FIPS 204 Algorithm 40 is pretty clear that r0 > 0 means strictly positive, but the current code treats zero as positive. This causes valid signatures to potentially fail verification when this edge case gets hit.

Details

The issue is in ml-dsa/src/hint.rs in the use_hint function. Here's what FIPS 204 Algorithm 40 says:

3: if h = 1 and r0 > 0  return (r1 + 1) mod m
4: if h = 1 and r0 <= 0  return (r1 − 1) mod m

Line 3 uses r0 > 0 (strictly greater than zero), and line 4 uses r0 <= 0 (less than or equal, which includes zero). So when r0 = 0, the spec says to subtract 1.

But the current implementation does this:

if h && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h && r0.0 >= BaseField::Q - gamma2 {
    Elem::new((r1.0 + m - 1) % m)
}

The problem is r0.0 <= gamma2 includes zero. When r0 = 0, this condition is true (since 0 <= gamma2), so it adds 1. But according to the spec, r0 = 0 should fall into the r0 <= 0 case and subtract 1 instead.

The result is +1 when it should be -1, which is an off by two error mod m.

PoC

Take MLDSA 44 where γ2 = 95,232 and m = 44.

If use_hint(true, 0) is called:

• Decompose(0) gives (r1=0, r0=0)
• The condition r0.0 <= gamma2 is 0 <= 95232 which is true
• So it returns (0 + 1) % 44 = 1

But FIPS 204 says:

• r0 > 0 is 0 > 0 which is false
• r0 ≤ 0 is 0 ≤ 0 which is true
• So it should return (0 - 1) mod 44 = 43

The function returns 1 when it should return 43.

This can happen in real signatures whenever any coefficient of the w' vector happens to be a multiple of 2γ2, which makes its decomposed r0 equal zero. It's not super common but it's definitely possible, and when it hits, verification will fail for a completely valid signature.

Impact

This is a FIPS 204 compliance bug that affects signature verification. When the edge case triggers, valid signatures get rejected. Since MLDSA is supposed to be used for high security post quantum cryptography, having verification randomly fail isn't great. It's also theoretically possible that the mismatch between what signing expects and what verification does could be exploited somehow, though that would need more looking into.

The fix is straightforward, just change the condition to explicitly check for positive values:

if h && r0.0 > 0 && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h {
    Elem::new((r1.0 + m - 1) % m)
}

Summary

There's a bug in the use_hint function where it adds 1 instead of subtracting 1 when the decomposed low bits r0 equal exactly zero. FIPS 204 Algorithm 40 is pretty clear that r0 > 0 means strictly positive, but the current code treats zero as positive. This causes valid signatures to potentially fail verification when this edge case gets hit.

Details

The issue is in ml-dsa/src/hint.rs in the use_hint function. Here's what FIPS 204 Algorithm 40 says:

3: if h = 1 and r0 > 0  return (r1 + 1) mod m
4: if h = 1 and r0 <= 0  return (r1 − 1) mod m

Line 3 uses r0 > 0 (strictly greater than zero), and line 4 uses r0 <= 0 (less than or equal, which includes zero). So when r0 = 0, the spec says to subtract 1.

But the current implementation does this:

if h && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h && r0.0 >= BaseField::Q - gamma2 {
    Elem::new((r1.0 + m - 1) % m)
}

The problem is r0.0 <= gamma2 includes zero. When r0 = 0, this condition is true (since 0 <= gamma2), so it adds 1. But according to the spec, r0 = 0 should fall into the r0 <= 0 case and subtract 1 instead.

The result is +1 when it should be -1, which is an off by two error mod m.

PoC

Take MLDSA 44 where γ2 = 95,232 and m = 44.

If use_hint(true, 0) is called:

• Decompose(0) gives (r1=0, r0=0)
• The condition r0.0 <= gamma2 is 0 <= 95232 which is true
• So it returns (0 + 1) % 44 = 1

But FIPS 204 says:

• r0 > 0 is 0 > 0 which is false
• r0 ≤ 0 is 0 ≤ 0 which is true
• So it should return (0 - 1) mod 44 = 43

The function returns 1 when it should return 43.

This can happen in real signatures whenever any coefficient of the w' vector happens to be a multiple of 2γ2, which makes its decomposed r0 equal zero. It's not super common but it's definitely possible, and when it hits, verification will fail for a completely valid signature.

Impact

This is a FIPS 204 compliance bug that affects signature verification. When the edge case triggers, valid signatures get rejected. Since MLDSA is supposed to be used for high security post quantum cryptography, having verification randomly fail isn't great. It's also theoretically possible that the mismatch between what signing expects and what verification does could be exploited somehow, though that would need more looking into.

The fix is straightforward, just change the condition to explicitly check for positive values:

if h && r0.0 > 0 && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h {
    Elem::new((r1.0 + m - 1) % m)
}

Affected Crate: ml-dsa
Affected Versions: v0.1.0-rc.2 (and commits since b01c3b7)
Severity: Medium
Reporter: Oren Yomtov (Fireblocks)

Summary

The ML-DSA signature verification implementation in the RustCrypto ml-dsa crate incorrectly accepts signatures with repeated (duplicate) hint indices. According to the ML-DSA specification (FIPS 204 / RFC 9881), hint indices within each polynomial must be strictly increasing. The current implementation uses a non-strict monotonic check (<= instead of <), allowing duplicate indices.

Note: This is a regression bug. The original implementation was correct, but commit b01c3b7 ("Make ML-DSA signature decoding follow the spec (#895)", fixing issue #894) inadvertently changed the strict < comparison to <=, introducing the vulnerability.

Vulnerability Details

Root Cause

The vulnerability is located in the monotonic helper function in ml-dsa/src/hint.rs:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] <= *x)
}

The comparison operator <= allows equal consecutive values, meaning duplicate hint indices are not rejected. The correct implementation should use strict less-than (<):

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Regression Analysis

• Original correct code (commit 1d3a1d1 - "Add support for ML-DSA (#877)"): Used < (strict)
• Bug introduced (commit b01c3b7 - "Make ML-DSA signature decoding follow the spec (#895)"): Changed to <=

The commit message suggests it was intended to fix issue #894 and make decoding follow the spec, but the change to the monotonic function was in the wrong direction. The other changes in that commit (to use_hint function) may have been correct, but this specific change introduced signature malleability.

Technical Impact

This vulnerability allows signature malleability - the same logical signature can have multiple valid byte-level encodings. An attacker can take a valid signature and create additional "valid" signatures by duplicating hint indices.

Per the ML-DSA specification (FIPS 204, Section 6.2 and Algorithm 26 HintBitUnpack), hint indices must be strictly increasing to ensure a unique, canonical encoding. Accepting non-canonical signatures can lead to:

1. Signature Malleability: Multiple distinct byte sequences verify as valid for the same message/key pair
2. Protocol-Level Vulnerabilities: Systems that rely on signature uniqueness (e.g., for transaction deduplication, replay protection, or signature-based identifiers) may be vulnerable
3. Interoperability Issues: Non-compliant signatures may be rejected by other conforming implementations

Affected Security Levels

All ML-DSA parameter sets are affected:

• ML-DSA-44 (NIST Security Level 2)
• ML-DSA-65 (NIST Security Level 3)
• ML-DSA-87 (NIST Security Level 5)

Proof of Concept

See the file poc_mldsa_repeated_hint.rs for a standalone proof of concept that demonstrates the vulnerability.

The PoC uses test vectors from the Wycheproof test suite that specifically test for this invalid encoding:

• Test Vector Source: Wycheproof ML-DSA Test Vectors
• Test Case ID 18: "signature with a repeated hint"
• Expected Result: invalid
• Actual Result: valid (BUG)

Remediation

Update the monotonic function in ml-dsa/src/hint.rs to use strict less-than comparison:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Design Intent: ML-DSA is NOT Intended to Allow Malleability

While some cryptographic libraries intentionally permit signature malleability for compatibility or performance reasons, ML-DSA is explicitly designed to prevent it:

1. FIPS 204 Specification: ML-DSA is designed to be strongly unforgeable under chosen message attacks (SUF-CMA). This security property explicitly prevents signature malleability.

2. NIST PQC Forum Discussion: In February 2024, there was a discussion on the NIST PQC forum about potential malleability in ML-DSA's hint unpacking. The consensus was that ML-DSA is intended to be SUF-CMA, meaning any malleability issues should be considered bugs and fixed.

3. No Documentation of Intentional Malleability: There is no documentation in the RustCrypto ml-dsa crate, FIPS 204, or RFC 9881 suggesting that signature malleability is an acceptable or intentional property.

4. Regression Bug: The fact that the original implementation had strict ordering (<) and this was changed to non-strict (<=) in a "fix" commit suggests this was an unintentional regression, not a design decision.

Summary

There's a bug in the use_hint function where it adds 1 instead of subtracting 1 when the decomposed low bits r0 equal exactly zero. FIPS 204 Algorithm 40 is pretty clear that r0 > 0 means strictly positive, but the current code treats zero as positive. This causes valid signatures to potentially fail verification when this edge case gets hit.

Details

The issue is in ml-dsa/src/hint.rs in the use_hint function. Here's what FIPS 204 Algorithm 40 says:

3: if h = 1 and r0 > 0  return (r1 + 1) mod m
4: if h = 1 and r0 <= 0  return (r1 − 1) mod m

Line 3 uses r0 > 0 (strictly greater than zero), and line 4 uses r0 <= 0 (less than or equal, which includes zero). So when r0 = 0, the spec says to subtract 1.

But the current implementation does this:

if h && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h && r0.0 >= BaseField::Q - gamma2 {
    Elem::new((r1.0 + m - 1) % m)
}

The problem is r0.0 <= gamma2 includes zero. When r0 = 0, this condition is true (since 0 <= gamma2), so it adds 1. But according to the spec, r0 = 0 should fall into the r0 <= 0 case and subtract 1 instead.

The result is +1 when it should be -1, which is an off by two error mod m.

PoC

Take MLDSA 44 where γ2 = 95,232 and m = 44.

If use_hint(true, 0) is called:

• Decompose(0) gives (r1=0, r0=0)
• The condition r0.0 <= gamma2 is 0 <= 95232 which is true
• So it returns (0 + 1) % 44 = 1

But FIPS 204 says:

• r0 > 0 is 0 > 0 which is false
• r0 ≤ 0 is 0 ≤ 0 which is true
• So it should return (0 - 1) mod 44 = 43

The function returns 1 when it should return 43.

This can happen in real signatures whenever any coefficient of the w' vector happens to be a multiple of 2γ2, which makes its decomposed r0 equal zero. It's not super common but it's definitely possible, and when it hits, verification will fail for a completely valid signature.

Impact

This is a FIPS 204 compliance bug that affects signature verification. When the edge case triggers, valid signatures get rejected. Since MLDSA is supposed to be used for high security post quantum cryptography, having verification randomly fail isn't great. It's also theoretically possible that the mismatch between what signing expects and what verification does could be exploited somehow, though that would need more looking into.

The fix is straightforward, just change the condition to explicitly check for positive values:

if h && r0.0 > 0 && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h {
    Elem::new((r1.0 + m - 1) % m)
}

Affected Crate: ml-dsa
Affected Versions: v0.1.0-rc.2 (and commits since b01c3b7)
Severity: Medium
Reporter: Oren Yomtov (Fireblocks)

Summary

The ML-DSA signature verification implementation in the RustCrypto ml-dsa crate incorrectly accepts signatures with repeated (duplicate) hint indices. According to the ML-DSA specification (FIPS 204 / RFC 9881), hint indices within each polynomial must be strictly increasing. The current implementation uses a non-strict monotonic check (<= instead of <), allowing duplicate indices.

Note: This is a regression bug. The original implementation was correct, but commit b01c3b7 ("Make ML-DSA signature decoding follow the spec (#895)", fixing issue #894) inadvertently changed the strict < comparison to <=, introducing the vulnerability.

Vulnerability Details

Root Cause

The vulnerability is located in the monotonic helper function in ml-dsa/src/hint.rs:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] <= *x)
}

The comparison operator <= allows equal consecutive values, meaning duplicate hint indices are not rejected. The correct implementation should use strict less-than (<):

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Regression Analysis

• Original correct code (commit 1d3a1d1 - "Add support for ML-DSA (#877)"): Used < (strict)
• Bug introduced (commit b01c3b7 - "Make ML-DSA signature decoding follow the spec (#895)"): Changed to <=

The commit message suggests it was intended to fix issue #894 and make decoding follow the spec, but the change to the monotonic function was in the wrong direction. The other changes in that commit (to use_hint function) may have been correct, but this specific change introduced signature malleability.

Technical Impact

This vulnerability allows signature malleability - the same logical signature can have multiple valid byte-level encodings. An attacker can take a valid signature and create additional "valid" signatures by duplicating hint indices.

Per the ML-DSA specification (FIPS 204, Section 6.2 and Algorithm 26 HintBitUnpack), hint indices must be strictly increasing to ensure a unique, canonical encoding. Accepting non-canonical signatures can lead to:

1. Signature Malleability: Multiple distinct byte sequences verify as valid for the same message/key pair
2. Protocol-Level Vulnerabilities: Systems that rely on signature uniqueness (e.g., for transaction deduplication, replay protection, or signature-based identifiers) may be vulnerable
3. Interoperability Issues: Non-compliant signatures may be rejected by other conforming implementations

Affected Security Levels

All ML-DSA parameter sets are affected:

• ML-DSA-44 (NIST Security Level 2)
• ML-DSA-65 (NIST Security Level 3)
• ML-DSA-87 (NIST Security Level 5)

Proof of Concept

See the file poc_mldsa_repeated_hint.rs for a standalone proof of concept that demonstrates the vulnerability.

The PoC uses test vectors from the Wycheproof test suite that specifically test for this invalid encoding:

• Test Vector Source: Wycheproof ML-DSA Test Vectors
• Test Case ID 18: "signature with a repeated hint"
• Expected Result: invalid
• Actual Result: valid (BUG)

Remediation

Update the monotonic function in ml-dsa/src/hint.rs to use strict less-than comparison:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Design Intent: ML-DSA is NOT Intended to Allow Malleability

While some cryptographic libraries intentionally permit signature malleability for compatibility or performance reasons, ML-DSA is explicitly designed to prevent it:

1. FIPS 204 Specification: ML-DSA is designed to be strongly unforgeable under chosen message attacks (SUF-CMA). This security property explicitly prevents signature malleability.

2. NIST PQC Forum Discussion: In February 2024, there was a discussion on the NIST PQC forum about potential malleability in ML-DSA's hint unpacking. The consensus was that ML-DSA is intended to be SUF-CMA, meaning any malleability issues should be considered bugs and fixed.

3. No Documentation of Intentional Malleability: There is no documentation in the RustCrypto ml-dsa crate, FIPS 204, or RFC 9881 suggesting that signature malleability is an acceptable or intentional property.

4. Regression Bug: The fact that the original implementation had strict ordering (<) and this was changed to non-strict (<=) in a "fix" commit suggests this was an unintentional regression, not a design decision.

Summary

A timing side-channel was discovered in the Decompose algorithm which is used during ML-DSA signing to generate hints for the signature.

Details

The analysis was performed using a constant-time analyzer that examines compiled assembly code for instructions with data-dependent timing behavior. The analyzer flags:

• UDIV/SDIV instructions: Hardware division instructions have early termination optimizations where execution time depends on operand values.

The decompose function used a hardware division instruction to compute r1.0 / TwoGamma2::U32. This function is called during signing through high_bits() and low_bits(), which process values derived from secret key components:

• (&w - &cs2).low_bits() where cs2 is derived from secret key component s2
• Hint::new() calls high_bits() on values derived from secret key component t0

Original Code:

fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
    // ...
    let mut r1 = r_plus - r0;
    r1.0 /= TwoGamma2::U32;  // Variable-time division on secret-derived data
    (r1, r0)
}

PoC

I do not have an exploit written for this, currently.

Impact

The dividend (r1.0) is derived from secret key material. An attacker with precise timing measurements could extract information about the signing key by observing timing variations in the division operation.

Mitigation

Replacing division with constant-time Barrett reduction mitigates this risk. Since TwoGamma2 is a compile-time constant, we precompute the multiplicative inverse:

diff --git a/ml-dsa/src/algebra.rs b/ml-dsa/src/algebra.rs
index 559b68a..bb126ce 100644
--- a/ml-dsa/src/algebra.rs
+++ b/ml-dsa/src/algebra.rs
@@ -54,8 +54,50 @@ pub(crate) trait Decompose {
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem);
 }
 
+/// Constant-time division by a compile-time constant divisor.
+///
+/// This trait provides a constant-time alternative to the hardware division
+/// instruction, which has variable timing based on operand values.
+/// Uses Barrett reduction to compute `x / M` where M is a compile-time constant.
+pub(crate) trait ConstantTimeDiv: Unsigned {
+    /// Bit shift for Barrett reduction, chosen to provide sufficient precision
+    const CT_DIV_SHIFT: usize;
+    /// Precomputed multiplier: ceil(2^SHIFT / M)
+    const CT_DIV_MULTIPLIER: u64;
+
+    /// Perform constant-time division of x by Self::U32
+    /// Requires: x < Q (the field modulus, ~2^23)
+    #[inline(always)]
+    fn ct_div(x: u32) -> u32 {
+        // Barrett reduction: q = (x * MULTIPLIER) >> SHIFT
+        // This gives us floor(x / M) for x < 2^SHIFT / MULTIPLIER * M
+        let x64 = u64::from(x);
+        let quotient = (x64 * Self::CT_DIV_MULTIPLIER) >> Self::CT_DIV_SHIFT;
+        quotient as u32
+    }
+}
+
+impl<M> ConstantTimeDiv for M
+where
+    M: Unsigned,
+{
+    // Use a shift that provides enough precision for the ML-DSA field (Q ~ 2^23)
+    // We need SHIFT > log2(Q) + log2(M) to ensure accuracy
+    // With Q < 2^24 and M < 2^20, SHIFT = 48 is sufficient
+    const CT_DIV_SHIFT: usize = 48;
+
+    // Precompute the multiplier at compile time
+    // We add (M-1) before dividing to get ceiling division, ensuring we never underestimate
+    #[allow(clippy::integer_division_remainder_used)]
+    const CT_DIV_MULTIPLIER: u64 = ((1u64 << Self::CT_DIV_SHIFT) + M::U64 - 1) / M::U64;
+}
+
 impl Decompose for Elem {
     // Algorithm 36 Decompose
+    //
+    // This implementation uses constant-time division to avoid timing side-channels.
+    // The original algorithm used hardware division which has variable timing based
+    // on operand values, potentially leaking secret information during signing.
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
         let r_plus = self.clone();
         let r0 = r_plus.mod_plus_minus::<TwoGamma2>();
@@ -63,8 +105,9 @@ impl Decompose for Elem {
         if r_plus - r0 == Elem::new(BaseField::Q - 1) {
             (Elem::new(0), r0 - Elem::new(1))
         } else {
-            let mut r1 = r_plus - r0;
-            r1.0 /= TwoGamma2::U32;
+            let diff = r_plus - r0;
+            // Use constant-time division instead of hardware division
+            let r1 = Elem::new(TwoGamma2::ct_div(diff.0));
             (r1, r0)
         }
     }

See our blog post on how we avoided side-channels in our Go implementation of ML-DSA for more information.

Summary

There's a bug in the use_hint function where it adds 1 instead of subtracting 1 when the decomposed low bits r0 equal exactly zero. FIPS 204 Algorithm 40 is pretty clear that r0 > 0 means strictly positive, but the current code treats zero as positive. This causes valid signatures to potentially fail verification when this edge case gets hit.

Details

The issue is in ml-dsa/src/hint.rs in the use_hint function. Here's what FIPS 204 Algorithm 40 says:

3: if h = 1 and r0 > 0  return (r1 + 1) mod m
4: if h = 1 and r0 <= 0  return (r1 − 1) mod m

Line 3 uses r0 > 0 (strictly greater than zero), and line 4 uses r0 <= 0 (less than or equal, which includes zero). So when r0 = 0, the spec says to subtract 1.

But the current implementation does this:

if h && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h && r0.0 >= BaseField::Q - gamma2 {
    Elem::new((r1.0 + m - 1) % m)
}

The problem is r0.0 <= gamma2 includes zero. When r0 = 0, this condition is true (since 0 <= gamma2), so it adds 1. But according to the spec, r0 = 0 should fall into the r0 <= 0 case and subtract 1 instead.

The result is +1 when it should be -1, which is an off by two error mod m.

PoC

Take MLDSA 44 where γ2 = 95,232 and m = 44.

If use_hint(true, 0) is called:

• Decompose(0) gives (r1=0, r0=0)
• The condition r0.0 <= gamma2 is 0 <= 95232 which is true
• So it returns (0 + 1) % 44 = 1

But FIPS 204 says:

• r0 > 0 is 0 > 0 which is false
• r0 ≤ 0 is 0 ≤ 0 which is true
• So it should return (0 - 1) mod 44 = 43

The function returns 1 when it should return 43.

This can happen in real signatures whenever any coefficient of the w' vector happens to be a multiple of 2γ2, which makes its decomposed r0 equal zero. It's not super common but it's definitely possible, and when it hits, verification will fail for a completely valid signature.

Impact

This is a FIPS 204 compliance bug that affects signature verification. When the edge case triggers, valid signatures get rejected. Since MLDSA is supposed to be used for high security post quantum cryptography, having verification randomly fail isn't great. It's also theoretically possible that the mismatch between what signing expects and what verification does could be exploited somehow, though that would need more looking into.

The fix is straightforward, just change the condition to explicitly check for positive values:

if h && r0.0 > 0 && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h {
    Elem::new((r1.0 + m - 1) % m)
}

Affected Crate: ml-dsa
Affected Versions: v0.1.0-rc.2 (and commits since b01c3b7)
Severity: Medium
Reporter: Oren Yomtov (Fireblocks)

Summary

The ML-DSA signature verification implementation in the RustCrypto ml-dsa crate incorrectly accepts signatures with repeated (duplicate) hint indices. According to the ML-DSA specification (FIPS 204 / RFC 9881), hint indices within each polynomial must be strictly increasing. The current implementation uses a non-strict monotonic check (<= instead of <), allowing duplicate indices.

Note: This is a regression bug. The original implementation was correct, but commit b01c3b7 ("Make ML-DSA signature decoding follow the spec (#895)", fixing issue #894) inadvertently changed the strict < comparison to <=, introducing the vulnerability.

Vulnerability Details

Root Cause

The vulnerability is located in the monotonic helper function in ml-dsa/src/hint.rs:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] <= *x)
}

The comparison operator <= allows equal consecutive values, meaning duplicate hint indices are not rejected. The correct implementation should use strict less-than (<):

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Regression Analysis

• Original correct code (commit 1d3a1d1 - "Add support for ML-DSA (#877)"): Used < (strict)
• Bug introduced (commit b01c3b7 - "Make ML-DSA signature decoding follow the spec (#895)"): Changed to <=

The commit message suggests it was intended to fix issue #894 and make decoding follow the spec, but the change to the monotonic function was in the wrong direction. The other changes in that commit (to use_hint function) may have been correct, but this specific change introduced signature malleability.

Technical Impact

This vulnerability allows signature malleability - the same logical signature can have multiple valid byte-level encodings. An attacker can take a valid signature and create additional "valid" signatures by duplicating hint indices.

Per the ML-DSA specification (FIPS 204, Section 6.2 and Algorithm 26 HintBitUnpack), hint indices must be strictly increasing to ensure a unique, canonical encoding. Accepting non-canonical signatures can lead to:

1. Signature Malleability: Multiple distinct byte sequences verify as valid for the same message/key pair
2. Protocol-Level Vulnerabilities: Systems that rely on signature uniqueness (e.g., for transaction deduplication, replay protection, or signature-based identifiers) may be vulnerable
3. Interoperability Issues: Non-compliant signatures may be rejected by other conforming implementations

Affected Security Levels

All ML-DSA parameter sets are affected:

• ML-DSA-44 (NIST Security Level 2)
• ML-DSA-65 (NIST Security Level 3)
• ML-DSA-87 (NIST Security Level 5)

Proof of Concept

See the file poc_mldsa_repeated_hint.rs for a standalone proof of concept that demonstrates the vulnerability.

The PoC uses test vectors from the Wycheproof test suite that specifically test for this invalid encoding:

• Test Vector Source: Wycheproof ML-DSA Test Vectors
• Test Case ID 18: "signature with a repeated hint"
• Expected Result: invalid
• Actual Result: valid (BUG)

Remediation

Update the monotonic function in ml-dsa/src/hint.rs to use strict less-than comparison:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Design Intent: ML-DSA is NOT Intended to Allow Malleability

While some cryptographic libraries intentionally permit signature malleability for compatibility or performance reasons, ML-DSA is explicitly designed to prevent it:

1. FIPS 204 Specification: ML-DSA is designed to be strongly unforgeable under chosen message attacks (SUF-CMA). This security property explicitly prevents signature malleability.

2. NIST PQC Forum Discussion: In February 2024, there was a discussion on the NIST PQC forum about potential malleability in ML-DSA's hint unpacking. The consensus was that ML-DSA is intended to be SUF-CMA, meaning any malleability issues should be considered bugs and fixed.

3. No Documentation of Intentional Malleability: There is no documentation in the RustCrypto ml-dsa crate, FIPS 204, or RFC 9881 suggesting that signature malleability is an acceptable or intentional property.

4. Regression Bug: The fact that the original implementation had strict ordering (<) and this was changed to non-strict (<=) in a "fix" commit suggests this was an unintentional regression, not a design decision.

Summary

A timing side-channel was discovered in the Decompose algorithm which is used during ML-DSA signing to generate hints for the signature.

Details

The analysis was performed using a constant-time analyzer that examines compiled assembly code for instructions with data-dependent timing behavior. The analyzer flags:

• UDIV/SDIV instructions: Hardware division instructions have early termination optimizations where execution time depends on operand values.

The decompose function used a hardware division instruction to compute r1.0 / TwoGamma2::U32. This function is called during signing through high_bits() and low_bits(), which process values derived from secret key components:

• (&w - &cs2).low_bits() where cs2 is derived from secret key component s2
• Hint::new() calls high_bits() on values derived from secret key component t0

Original Code:

fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
    // ...
    let mut r1 = r_plus - r0;
    r1.0 /= TwoGamma2::U32;  // Variable-time division on secret-derived data
    (r1, r0)
}

PoC

I do not have an exploit written for this, currently.

Impact

The dividend (r1.0) is derived from secret key material. An attacker with precise timing measurements could extract information about the signing key by observing timing variations in the division operation.

Mitigation

Replacing division with constant-time Barrett reduction mitigates this risk. Since TwoGamma2 is a compile-time constant, we precompute the multiplicative inverse:

diff --git a/ml-dsa/src/algebra.rs b/ml-dsa/src/algebra.rs
index 559b68a..bb126ce 100644
--- a/ml-dsa/src/algebra.rs
+++ b/ml-dsa/src/algebra.rs
@@ -54,8 +54,50 @@ pub(crate) trait Decompose {
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem);
 }
 
+/// Constant-time division by a compile-time constant divisor.
+///
+/// This trait provides a constant-time alternative to the hardware division
+/// instruction, which has variable timing based on operand values.
+/// Uses Barrett reduction to compute `x / M` where M is a compile-time constant.
+pub(crate) trait ConstantTimeDiv: Unsigned {
+    /// Bit shift for Barrett reduction, chosen to provide sufficient precision
+    const CT_DIV_SHIFT: usize;
+    /// Precomputed multiplier: ceil(2^SHIFT / M)
+    const CT_DIV_MULTIPLIER: u64;
+
+    /// Perform constant-time division of x by Self::U32
+    /// Requires: x < Q (the field modulus, ~2^23)
+    #[inline(always)]
+    fn ct_div(x: u32) -> u32 {
+        // Barrett reduction: q = (x * MULTIPLIER) >> SHIFT
+        // This gives us floor(x / M) for x < 2^SHIFT / MULTIPLIER * M
+        let x64 = u64::from(x);
+        let quotient = (x64 * Self::CT_DIV_MULTIPLIER) >> Self::CT_DIV_SHIFT;
+        quotient as u32
+    }
+}
+
+impl<M> ConstantTimeDiv for M
+where
+    M: Unsigned,
+{
+    // Use a shift that provides enough precision for the ML-DSA field (Q ~ 2^23)
+    // We need SHIFT > log2(Q) + log2(M) to ensure accuracy
+    // With Q < 2^24 and M < 2^20, SHIFT = 48 is sufficient
+    const CT_DIV_SHIFT: usize = 48;
+
+    // Precompute the multiplier at compile time
+    // We add (M-1) before dividing to get ceiling division, ensuring we never underestimate
+    #[allow(clippy::integer_division_remainder_used)]
+    const CT_DIV_MULTIPLIER: u64 = ((1u64 << Self::CT_DIV_SHIFT) + M::U64 - 1) / M::U64;
+}
+
 impl Decompose for Elem {
     // Algorithm 36 Decompose
+    //
+    // This implementation uses constant-time division to avoid timing side-channels.
+    // The original algorithm used hardware division which has variable timing based
+    // on operand values, potentially leaking secret information during signing.
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
         let r_plus = self.clone();
         let r0 = r_plus.mod_plus_minus::<TwoGamma2>();
@@ -63,8 +105,9 @@ impl Decompose for Elem {
         if r_plus - r0 == Elem::new(BaseField::Q - 1) {
             (Elem::new(0), r0 - Elem::new(1))
         } else {
-            let mut r1 = r_plus - r0;
-            r1.0 /= TwoGamma2::U32;
+            let diff = r_plus - r0;
+            // Use constant-time division instead of hardware division
+            let r1 = Elem::new(TwoGamma2::ct_div(diff.0));
             (r1, r0)
         }
     }

See our blog post on how we avoided side-channels in our Go implementation of ML-DSA for more information.

Summary

There's a bug in the use_hint function where it adds 1 instead of subtracting 1 when the decomposed low bits r0 equal exactly zero. FIPS 204 Algorithm 40 is pretty clear that r0 > 0 means strictly positive, but the current code treats zero as positive. This causes valid signatures to potentially fail verification when this edge case gets hit.

Details

The issue is in ml-dsa/src/hint.rs in the use_hint function. Here's what FIPS 204 Algorithm 40 says:

3: if h = 1 and r0 > 0  return (r1 + 1) mod m
4: if h = 1 and r0 <= 0  return (r1 − 1) mod m

Line 3 uses r0 > 0 (strictly greater than zero), and line 4 uses r0 <= 0 (less than or equal, which includes zero). So when r0 = 0, the spec says to subtract 1.

But the current implementation does this:

if h && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h && r0.0 >= BaseField::Q - gamma2 {
    Elem::new((r1.0 + m - 1) % m)
}

The problem is r0.0 <= gamma2 includes zero. When r0 = 0, this condition is true (since 0 <= gamma2), so it adds 1. But according to the spec, r0 = 0 should fall into the r0 <= 0 case and subtract 1 instead.

The result is +1 when it should be -1, which is an off by two error mod m.

PoC

Take MLDSA 44 where γ2 = 95,232 and m = 44.

If use_hint(true, 0) is called:

• Decompose(0) gives (r1=0, r0=0)
• The condition r0.0 <= gamma2 is 0 <= 95232 which is true
• So it returns (0 + 1) % 44 = 1

But FIPS 204 says:

• r0 > 0 is 0 > 0 which is false
• r0 ≤ 0 is 0 ≤ 0 which is true
• So it should return (0 - 1) mod 44 = 43

The function returns 1 when it should return 43.

This can happen in real signatures whenever any coefficient of the w' vector happens to be a multiple of 2γ2, which makes its decomposed r0 equal zero. It's not super common but it's definitely possible, and when it hits, verification will fail for a completely valid signature.

Impact

This is a FIPS 204 compliance bug that affects signature verification. When the edge case triggers, valid signatures get rejected. Since MLDSA is supposed to be used for high security post quantum cryptography, having verification randomly fail isn't great. It's also theoretically possible that the mismatch between what signing expects and what verification does could be exploited somehow, though that would need more looking into.

The fix is straightforward, just change the condition to explicitly check for positive values:

if h && r0.0 > 0 && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h {
    Elem::new((r1.0 + m - 1) % m)
}

Affected Crate: ml-dsa
Affected Versions: v0.1.0-rc.2 (and commits since b01c3b7)
Severity: Medium
Reporter: Oren Yomtov (Fireblocks)

Summary

The ML-DSA signature verification implementation in the RustCrypto ml-dsa crate incorrectly accepts signatures with repeated (duplicate) hint indices. According to the ML-DSA specification (FIPS 204 / RFC 9881), hint indices within each polynomial must be strictly increasing. The current implementation uses a non-strict monotonic check (<= instead of <), allowing duplicate indices.

Note: This is a regression bug. The original implementation was correct, but commit b01c3b7 ("Make ML-DSA signature decoding follow the spec (#895)", fixing issue #894) inadvertently changed the strict < comparison to <=, introducing the vulnerability.

Vulnerability Details

Root Cause

The vulnerability is located in the monotonic helper function in ml-dsa/src/hint.rs:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] <= *x)
}

The comparison operator <= allows equal consecutive values, meaning duplicate hint indices are not rejected. The correct implementation should use strict less-than (<):

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Regression Analysis

• Original correct code (commit 1d3a1d1 - "Add support for ML-DSA (#877)"): Used < (strict)
• Bug introduced (commit b01c3b7 - "Make ML-DSA signature decoding follow the spec (#895)"): Changed to <=

The commit message suggests it was intended to fix issue #894 and make decoding follow the spec, but the change to the monotonic function was in the wrong direction. The other changes in that commit (to use_hint function) may have been correct, but this specific change introduced signature malleability.

Technical Impact

This vulnerability allows signature malleability - the same logical signature can have multiple valid byte-level encodings. An attacker can take a valid signature and create additional "valid" signatures by duplicating hint indices.

Per the ML-DSA specification (FIPS 204, Section 6.2 and Algorithm 26 HintBitUnpack), hint indices must be strictly increasing to ensure a unique, canonical encoding. Accepting non-canonical signatures can lead to:

1. Signature Malleability: Multiple distinct byte sequences verify as valid for the same message/key pair
2. Protocol-Level Vulnerabilities: Systems that rely on signature uniqueness (e.g., for transaction deduplication, replay protection, or signature-based identifiers) may be vulnerable
3. Interoperability Issues: Non-compliant signatures may be rejected by other conforming implementations

Affected Security Levels

All ML-DSA parameter sets are affected:

• ML-DSA-44 (NIST Security Level 2)
• ML-DSA-65 (NIST Security Level 3)
• ML-DSA-87 (NIST Security Level 5)

Proof of Concept

See the file poc_mldsa_repeated_hint.rs for a standalone proof of concept that demonstrates the vulnerability.

The PoC uses test vectors from the Wycheproof test suite that specifically test for this invalid encoding:

• Test Vector Source: Wycheproof ML-DSA Test Vectors
• Test Case ID 18: "signature with a repeated hint"
• Expected Result: invalid
• Actual Result: valid (BUG)

Remediation

Update the monotonic function in ml-dsa/src/hint.rs to use strict less-than comparison:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Design Intent: ML-DSA is NOT Intended to Allow Malleability

While some cryptographic libraries intentionally permit signature malleability for compatibility or performance reasons, ML-DSA is explicitly designed to prevent it:

1. FIPS 204 Specification: ML-DSA is designed to be strongly unforgeable under chosen message attacks (SUF-CMA). This security property explicitly prevents signature malleability.

2. NIST PQC Forum Discussion: In February 2024, there was a discussion on the NIST PQC forum about potential malleability in ML-DSA's hint unpacking. The consensus was that ML-DSA is intended to be SUF-CMA, meaning any malleability issues should be considered bugs and fixed.

3. No Documentation of Intentional Malleability: There is no documentation in the RustCrypto ml-dsa crate, FIPS 204, or RFC 9881 suggesting that signature malleability is an acceptable or intentional property.

4. Regression Bug: The fact that the original implementation had strict ordering (<) and this was changed to non-strict (<=) in a "fix" commit suggests this was an unintentional regression, not a design decision.

Summary

A timing side-channel was discovered in the Decompose algorithm which is used during ML-DSA signing to generate hints for the signature.

Details

The analysis was performed using a constant-time analyzer that examines compiled assembly code for instructions with data-dependent timing behavior. The analyzer flags:

• UDIV/SDIV instructions: Hardware division instructions have early termination optimizations where execution time depends on operand values.

The decompose function used a hardware division instruction to compute r1.0 / TwoGamma2::U32. This function is called during signing through high_bits() and low_bits(), which process values derived from secret key components:

• (&w - &cs2).low_bits() where cs2 is derived from secret key component s2
• Hint::new() calls high_bits() on values derived from secret key component t0

Original Code:

fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
    // ...
    let mut r1 = r_plus - r0;
    r1.0 /= TwoGamma2::U32;  // Variable-time division on secret-derived data
    (r1, r0)
}

PoC

I do not have an exploit written for this, currently.

Impact

The dividend (r1.0) is derived from secret key material. An attacker with precise timing measurements could extract information about the signing key by observing timing variations in the division operation.

Mitigation

Replacing division with constant-time Barrett reduction mitigates this risk. Since TwoGamma2 is a compile-time constant, we precompute the multiplicative inverse:

diff --git a/ml-dsa/src/algebra.rs b/ml-dsa/src/algebra.rs
index 559b68a..bb126ce 100644
--- a/ml-dsa/src/algebra.rs
+++ b/ml-dsa/src/algebra.rs
@@ -54,8 +54,50 @@ pub(crate) trait Decompose {
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem);
 }
 
+/// Constant-time division by a compile-time constant divisor.
+///
+/// This trait provides a constant-time alternative to the hardware division
+/// instruction, which has variable timing based on operand values.
+/// Uses Barrett reduction to compute `x / M` where M is a compile-time constant.
+pub(crate) trait ConstantTimeDiv: Unsigned {
+    /// Bit shift for Barrett reduction, chosen to provide sufficient precision
+    const CT_DIV_SHIFT: usize;
+    /// Precomputed multiplier: ceil(2^SHIFT / M)
+    const CT_DIV_MULTIPLIER: u64;
+
+    /// Perform constant-time division of x by Self::U32
+    /// Requires: x < Q (the field modulus, ~2^23)
+    #[inline(always)]
+    fn ct_div(x: u32) -> u32 {
+        // Barrett reduction: q = (x * MULTIPLIER) >> SHIFT
+        // This gives us floor(x / M) for x < 2^SHIFT / MULTIPLIER * M
+        let x64 = u64::from(x);
+        let quotient = (x64 * Self::CT_DIV_MULTIPLIER) >> Self::CT_DIV_SHIFT;
+        quotient as u32
+    }
+}
+
+impl<M> ConstantTimeDiv for M
+where
+    M: Unsigned,
+{
+    // Use a shift that provides enough precision for the ML-DSA field (Q ~ 2^23)
+    // We need SHIFT > log2(Q) + log2(M) to ensure accuracy
+    // With Q < 2^24 and M < 2^20, SHIFT = 48 is sufficient
+    const CT_DIV_SHIFT: usize = 48;
+
+    // Precompute the multiplier at compile time
+    // We add (M-1) before dividing to get ceiling division, ensuring we never underestimate
+    #[allow(clippy::integer_division_remainder_used)]
+    const CT_DIV_MULTIPLIER: u64 = ((1u64 << Self::CT_DIV_SHIFT) + M::U64 - 1) / M::U64;
+}
+
 impl Decompose for Elem {
     // Algorithm 36 Decompose
+    //
+    // This implementation uses constant-time division to avoid timing side-channels.
+    // The original algorithm used hardware division which has variable timing based
+    // on operand values, potentially leaking secret information during signing.
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
         let r_plus = self.clone();
         let r0 = r_plus.mod_plus_minus::<TwoGamma2>();
@@ -63,8 +105,9 @@ impl Decompose for Elem {
         if r_plus - r0 == Elem::new(BaseField::Q - 1) {
             (Elem::new(0), r0 - Elem::new(1))
         } else {
-            let mut r1 = r_plus - r0;
-            r1.0 /= TwoGamma2::U32;
+            let diff = r_plus - r0;
+            // Use constant-time division instead of hardware division
+            let r1 = Elem::new(TwoGamma2::ct_div(diff.0));
             (r1, r0)
         }
     }

See our blog post on how we avoided side-channels in our Go implementation of ML-DSA for more information.

Summary

There's a bug in the use_hint function where it adds 1 instead of subtracting 1 when the decomposed low bits r0 equal exactly zero. FIPS 204 Algorithm 40 is pretty clear that r0 > 0 means strictly positive, but the current code treats zero as positive. This causes valid signatures to potentially fail verification when this edge case gets hit.

Details

The issue is in ml-dsa/src/hint.rs in the use_hint function. Here's what FIPS 204 Algorithm 40 says:

3: if h = 1 and r0 > 0  return (r1 + 1) mod m
4: if h = 1 and r0 <= 0  return (r1 − 1) mod m

Line 3 uses r0 > 0 (strictly greater than zero), and line 4 uses r0 <= 0 (less than or equal, which includes zero). So when r0 = 0, the spec says to subtract 1.

But the current implementation does this:

if h && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h && r0.0 >= BaseField::Q - gamma2 {
    Elem::new((r1.0 + m - 1) % m)
}

The problem is r0.0 <= gamma2 includes zero. When r0 = 0, this condition is true (since 0 <= gamma2), so it adds 1. But according to the spec, r0 = 0 should fall into the r0 <= 0 case and subtract 1 instead.

The result is +1 when it should be -1, which is an off by two error mod m.

PoC

Take MLDSA 44 where γ2 = 95,232 and m = 44.

If use_hint(true, 0) is called:

• Decompose(0) gives (r1=0, r0=0)
• The condition r0.0 <= gamma2 is 0 <= 95232 which is true
• So it returns (0 + 1) % 44 = 1

But FIPS 204 says:

• r0 > 0 is 0 > 0 which is false
• r0 ≤ 0 is 0 ≤ 0 which is true
• So it should return (0 - 1) mod 44 = 43

The function returns 1 when it should return 43.

This can happen in real signatures whenever any coefficient of the w' vector happens to be a multiple of 2γ2, which makes its decomposed r0 equal zero. It's not super common but it's definitely possible, and when it hits, verification will fail for a completely valid signature.

Impact

This is a FIPS 204 compliance bug that affects signature verification. When the edge case triggers, valid signatures get rejected. Since MLDSA is supposed to be used for high security post quantum cryptography, having verification randomly fail isn't great. It's also theoretically possible that the mismatch between what signing expects and what verification does could be exploited somehow, though that would need more looking into.

The fix is straightforward, just change the condition to explicitly check for positive values:

if h && r0.0 > 0 && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h {
    Elem::new((r1.0 + m - 1) % m)
}

Affected Crate: ml-dsa
Affected Versions: v0.1.0-rc.2 (and commits since b01c3b7)
Severity: Medium
Reporter: Oren Yomtov (Fireblocks)

Summary

The ML-DSA signature verification implementation in the RustCrypto ml-dsa crate incorrectly accepts signatures with repeated (duplicate) hint indices. According to the ML-DSA specification (FIPS 204 / RFC 9881), hint indices within each polynomial must be strictly increasing. The current implementation uses a non-strict monotonic check (<= instead of <), allowing duplicate indices.

Note: This is a regression bug. The original implementation was correct, but commit b01c3b7 ("Make ML-DSA signature decoding follow the spec (#895)", fixing issue #894) inadvertently changed the strict < comparison to <=, introducing the vulnerability.

Vulnerability Details

Root Cause

The vulnerability is located in the monotonic helper function in ml-dsa/src/hint.rs:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] <= *x)
}

The comparison operator <= allows equal consecutive values, meaning duplicate hint indices are not rejected. The correct implementation should use strict less-than (<):

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Regression Analysis

• Original correct code (commit 1d3a1d1 - "Add support for ML-DSA (#877)"): Used < (strict)
• Bug introduced (commit b01c3b7 - "Make ML-DSA signature decoding follow the spec (#895)"): Changed to <=

The commit message suggests it was intended to fix issue #894 and make decoding follow the spec, but the change to the monotonic function was in the wrong direction. The other changes in that commit (to use_hint function) may have been correct, but this specific change introduced signature malleability.

Technical Impact

This vulnerability allows signature malleability - the same logical signature can have multiple valid byte-level encodings. An attacker can take a valid signature and create additional "valid" signatures by duplicating hint indices.

Per the ML-DSA specification (FIPS 204, Section 6.2 and Algorithm 26 HintBitUnpack), hint indices must be strictly increasing to ensure a unique, canonical encoding. Accepting non-canonical signatures can lead to:

1. Signature Malleability: Multiple distinct byte sequences verify as valid for the same message/key pair
2. Protocol-Level Vulnerabilities: Systems that rely on signature uniqueness (e.g., for transaction deduplication, replay protection, or signature-based identifiers) may be vulnerable
3. Interoperability Issues: Non-compliant signatures may be rejected by other conforming implementations

Affected Security Levels

All ML-DSA parameter sets are affected:

• ML-DSA-44 (NIST Security Level 2)
• ML-DSA-65 (NIST Security Level 3)
• ML-DSA-87 (NIST Security Level 5)

Proof of Concept

See the file poc_mldsa_repeated_hint.rs for a standalone proof of concept that demonstrates the vulnerability.

The PoC uses test vectors from the Wycheproof test suite that specifically test for this invalid encoding:

• Test Vector Source: Wycheproof ML-DSA Test Vectors
• Test Case ID 18: "signature with a repeated hint"
• Expected Result: invalid
• Actual Result: valid (BUG)

Remediation

Update the monotonic function in ml-dsa/src/hint.rs to use strict less-than comparison:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Design Intent: ML-DSA is NOT Intended to Allow Malleability

While some cryptographic libraries intentionally permit signature malleability for compatibility or performance reasons, ML-DSA is explicitly designed to prevent it:

1. FIPS 204 Specification: ML-DSA is designed to be strongly unforgeable under chosen message attacks (SUF-CMA). This security property explicitly prevents signature malleability.

2. NIST PQC Forum Discussion: In February 2024, there was a discussion on the NIST PQC forum about potential malleability in ML-DSA's hint unpacking. The consensus was that ML-DSA is intended to be SUF-CMA, meaning any malleability issues should be considered bugs and fixed.

3. No Documentation of Intentional Malleability: There is no documentation in the RustCrypto ml-dsa crate, FIPS 204, or RFC 9881 suggesting that signature malleability is an acceptable or intentional property.

4. Regression Bug: The fact that the original implementation had strict ordering (<) and this was changed to non-strict (<=) in a "fix" commit suggests this was an unintentional regression, not a design decision.

Summary

A timing side-channel was discovered in the Decompose algorithm which is used during ML-DSA signing to generate hints for the signature.

Details

The analysis was performed using a constant-time analyzer that examines compiled assembly code for instructions with data-dependent timing behavior. The analyzer flags:

• UDIV/SDIV instructions: Hardware division instructions have early termination optimizations where execution time depends on operand values.

The decompose function used a hardware division instruction to compute r1.0 / TwoGamma2::U32. This function is called during signing through high_bits() and low_bits(), which process values derived from secret key components:

• (&w - &cs2).low_bits() where cs2 is derived from secret key component s2
• Hint::new() calls high_bits() on values derived from secret key component t0

Original Code:

fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
    // ...
    let mut r1 = r_plus - r0;
    r1.0 /= TwoGamma2::U32;  // Variable-time division on secret-derived data
    (r1, r0)
}

PoC

I do not have an exploit written for this, currently.

Impact

The dividend (r1.0) is derived from secret key material. An attacker with precise timing measurements could extract information about the signing key by observing timing variations in the division operation.

Mitigation

Replacing division with constant-time Barrett reduction mitigates this risk. Since TwoGamma2 is a compile-time constant, we precompute the multiplicative inverse:

diff --git a/ml-dsa/src/algebra.rs b/ml-dsa/src/algebra.rs
index 559b68a..bb126ce 100644
--- a/ml-dsa/src/algebra.rs
+++ b/ml-dsa/src/algebra.rs
@@ -54,8 +54,50 @@ pub(crate) trait Decompose {
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem);
 }
 
+/// Constant-time division by a compile-time constant divisor.
+///
+/// This trait provides a constant-time alternative to the hardware division
+/// instruction, which has variable timing based on operand values.
+/// Uses Barrett reduction to compute `x / M` where M is a compile-time constant.
+pub(crate) trait ConstantTimeDiv: Unsigned {
+    /// Bit shift for Barrett reduction, chosen to provide sufficient precision
+    const CT_DIV_SHIFT: usize;
+    /// Precomputed multiplier: ceil(2^SHIFT / M)
+    const CT_DIV_MULTIPLIER: u64;
+
+    /// Perform constant-time division of x by Self::U32
+    /// Requires: x < Q (the field modulus, ~2^23)
+    #[inline(always)]
+    fn ct_div(x: u32) -> u32 {
+        // Barrett reduction: q = (x * MULTIPLIER) >> SHIFT
+        // This gives us floor(x / M) for x < 2^SHIFT / MULTIPLIER * M
+        let x64 = u64::from(x);
+        let quotient = (x64 * Self::CT_DIV_MULTIPLIER) >> Self::CT_DIV_SHIFT;
+        quotient as u32
+    }
+}
+
+impl<M> ConstantTimeDiv for M
+where
+    M: Unsigned,
+{
+    // Use a shift that provides enough precision for the ML-DSA field (Q ~ 2^23)
+    // We need SHIFT > log2(Q) + log2(M) to ensure accuracy
+    // With Q < 2^24 and M < 2^20, SHIFT = 48 is sufficient
+    const CT_DIV_SHIFT: usize = 48;
+
+    // Precompute the multiplier at compile time
+    // We add (M-1) before dividing to get ceiling division, ensuring we never underestimate
+    #[allow(clippy::integer_division_remainder_used)]
+    const CT_DIV_MULTIPLIER: u64 = ((1u64 << Self::CT_DIV_SHIFT) + M::U64 - 1) / M::U64;
+}
+
 impl Decompose for Elem {
     // Algorithm 36 Decompose
+    //
+    // This implementation uses constant-time division to avoid timing side-channels.
+    // The original algorithm used hardware division which has variable timing based
+    // on operand values, potentially leaking secret information during signing.
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
         let r_plus = self.clone();
         let r0 = r_plus.mod_plus_minus::<TwoGamma2>();
@@ -63,8 +105,9 @@ impl Decompose for Elem {
         if r_plus - r0 == Elem::new(BaseField::Q - 1) {
             (Elem::new(0), r0 - Elem::new(1))
         } else {
-            let mut r1 = r_plus - r0;
-            r1.0 /= TwoGamma2::U32;
+            let diff = r_plus - r0;
+            // Use constant-time division instead of hardware division
+            let r1 = Elem::new(TwoGamma2::ct_div(diff.0));
             (r1, r0)
         }
     }

See our blog post on how we avoided side-channels in our Go implementation of ML-DSA for more information.

Summary

There's a bug in the use_hint function where it adds 1 instead of subtracting 1 when the decomposed low bits r0 equal exactly zero. FIPS 204 Algorithm 40 is pretty clear that r0 > 0 means strictly positive, but the current code treats zero as positive. This causes valid signatures to potentially fail verification when this edge case gets hit.

Details

The issue is in ml-dsa/src/hint.rs in the use_hint function. Here's what FIPS 204 Algorithm 40 says:

3: if h = 1 and r0 > 0  return (r1 + 1) mod m
4: if h = 1 and r0 <= 0  return (r1 − 1) mod m

Line 3 uses r0 > 0 (strictly greater than zero), and line 4 uses r0 <= 0 (less than or equal, which includes zero). So when r0 = 0, the spec says to subtract 1.

But the current implementation does this:

if h && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h && r0.0 >= BaseField::Q - gamma2 {
    Elem::new((r1.0 + m - 1) % m)
}

The problem is r0.0 <= gamma2 includes zero. When r0 = 0, this condition is true (since 0 <= gamma2), so it adds 1. But according to the spec, r0 = 0 should fall into the r0 <= 0 case and subtract 1 instead.

The result is +1 when it should be -1, which is an off by two error mod m.

PoC

Take MLDSA 44 where γ2 = 95,232 and m = 44.

If use_hint(true, 0) is called:

• Decompose(0) gives (r1=0, r0=0)
• The condition r0.0 <= gamma2 is 0 <= 95232 which is true
• So it returns (0 + 1) % 44 = 1

But FIPS 204 says:

• r0 > 0 is 0 > 0 which is false
• r0 ≤ 0 is 0 ≤ 0 which is true
• So it should return (0 - 1) mod 44 = 43

The function returns 1 when it should return 43.

This can happen in real signatures whenever any coefficient of the w' vector happens to be a multiple of 2γ2, which makes its decomposed r0 equal zero. It's not super common but it's definitely possible, and when it hits, verification will fail for a completely valid signature.

Impact

This is a FIPS 204 compliance bug that affects signature verification. When the edge case triggers, valid signatures get rejected. Since MLDSA is supposed to be used for high security post quantum cryptography, having verification randomly fail isn't great. It's also theoretically possible that the mismatch between what signing expects and what verification does could be exploited somehow, though that would need more looking into.

The fix is straightforward, just change the condition to explicitly check for positive values:

if h && r0.0 > 0 && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h {
    Elem::new((r1.0 + m - 1) % m)
}

Affected Crate: ml-dsa
Affected Versions: v0.1.0-rc.2 (and commits since b01c3b7)
Severity: Medium
Reporter: Oren Yomtov (Fireblocks)

Summary

The ML-DSA signature verification implementation in the RustCrypto ml-dsa crate incorrectly accepts signatures with repeated (duplicate) hint indices. According to the ML-DSA specification (FIPS 204 / RFC 9881), hint indices within each polynomial must be strictly increasing. The current implementation uses a non-strict monotonic check (<= instead of <), allowing duplicate indices.

Note: This is a regression bug. The original implementation was correct, but commit b01c3b7 ("Make ML-DSA signature decoding follow the spec (#895)", fixing issue #894) inadvertently changed the strict < comparison to <=, introducing the vulnerability.

Vulnerability Details

Root Cause

The vulnerability is located in the monotonic helper function in ml-dsa/src/hint.rs:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] <= *x)
}

The comparison operator <= allows equal consecutive values, meaning duplicate hint indices are not rejected. The correct implementation should use strict less-than (<):

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Regression Analysis

• Original correct code (commit 1d3a1d1 - "Add support for ML-DSA (#877)"): Used < (strict)
• Bug introduced (commit b01c3b7 - "Make ML-DSA signature decoding follow the spec (#895)"): Changed to <=

The commit message suggests it was intended to fix issue #894 and make decoding follow the spec, but the change to the monotonic function was in the wrong direction. The other changes in that commit (to use_hint function) may have been correct, but this specific change introduced signature malleability.

Technical Impact

This vulnerability allows signature malleability - the same logical signature can have multiple valid byte-level encodings. An attacker can take a valid signature and create additional "valid" signatures by duplicating hint indices.

Per the ML-DSA specification (FIPS 204, Section 6.2 and Algorithm 26 HintBitUnpack), hint indices must be strictly increasing to ensure a unique, canonical encoding. Accepting non-canonical signatures can lead to:

1. Signature Malleability: Multiple distinct byte sequences verify as valid for the same message/key pair
2. Protocol-Level Vulnerabilities: Systems that rely on signature uniqueness (e.g., for transaction deduplication, replay protection, or signature-based identifiers) may be vulnerable
3. Interoperability Issues: Non-compliant signatures may be rejected by other conforming implementations

Affected Security Levels

All ML-DSA parameter sets are affected:

• ML-DSA-44 (NIST Security Level 2)
• ML-DSA-65 (NIST Security Level 3)
• ML-DSA-87 (NIST Security Level 5)

Proof of Concept

See the file poc_mldsa_repeated_hint.rs for a standalone proof of concept that demonstrates the vulnerability.

The PoC uses test vectors from the Wycheproof test suite that specifically test for this invalid encoding:

• Test Vector Source: Wycheproof ML-DSA Test Vectors
• Test Case ID 18: "signature with a repeated hint"
• Expected Result: invalid
• Actual Result: valid (BUG)

Remediation

Update the monotonic function in ml-dsa/src/hint.rs to use strict less-than comparison:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Design Intent: ML-DSA is NOT Intended to Allow Malleability

While some cryptographic libraries intentionally permit signature malleability for compatibility or performance reasons, ML-DSA is explicitly designed to prevent it:

1. FIPS 204 Specification: ML-DSA is designed to be strongly unforgeable under chosen message attacks (SUF-CMA). This security property explicitly prevents signature malleability.

2. NIST PQC Forum Discussion: In February 2024, there was a discussion on the NIST PQC forum about potential malleability in ML-DSA's hint unpacking. The consensus was that ML-DSA is intended to be SUF-CMA, meaning any malleability issues should be considered bugs and fixed.

3. No Documentation of Intentional Malleability: There is no documentation in the RustCrypto ml-dsa crate, FIPS 204, or RFC 9881 suggesting that signature malleability is an acceptable or intentional property.

4. Regression Bug: The fact that the original implementation had strict ordering (<) and this was changed to non-strict (<=) in a "fix" commit suggests this was an unintentional regression, not a design decision.

Summary

A timing side-channel was discovered in the Decompose algorithm which is used during ML-DSA signing to generate hints for the signature.

Details

The analysis was performed using a constant-time analyzer that examines compiled assembly code for instructions with data-dependent timing behavior. The analyzer flags:

• UDIV/SDIV instructions: Hardware division instructions have early termination optimizations where execution time depends on operand values.

The decompose function used a hardware division instruction to compute r1.0 / TwoGamma2::U32. This function is called during signing through high_bits() and low_bits(), which process values derived from secret key components:

• (&w - &cs2).low_bits() where cs2 is derived from secret key component s2
• Hint::new() calls high_bits() on values derived from secret key component t0

Original Code:

fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
    // ...
    let mut r1 = r_plus - r0;
    r1.0 /= TwoGamma2::U32;  // Variable-time division on secret-derived data
    (r1, r0)
}

PoC

I do not have an exploit written for this, currently.

Impact

The dividend (r1.0) is derived from secret key material. An attacker with precise timing measurements could extract information about the signing key by observing timing variations in the division operation.

Mitigation

Replacing division with constant-time Barrett reduction mitigates this risk. Since TwoGamma2 is a compile-time constant, we precompute the multiplicative inverse:

diff --git a/ml-dsa/src/algebra.rs b/ml-dsa/src/algebra.rs
index 559b68a..bb126ce 100644
--- a/ml-dsa/src/algebra.rs
+++ b/ml-dsa/src/algebra.rs
@@ -54,8 +54,50 @@ pub(crate) trait Decompose {
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem);
 }
 
+/// Constant-time division by a compile-time constant divisor.
+///
+/// This trait provides a constant-time alternative to the hardware division
+/// instruction, which has variable timing based on operand values.
+/// Uses Barrett reduction to compute `x / M` where M is a compile-time constant.
+pub(crate) trait ConstantTimeDiv: Unsigned {
+    /// Bit shift for Barrett reduction, chosen to provide sufficient precision
+    const CT_DIV_SHIFT: usize;
+    /// Precomputed multiplier: ceil(2^SHIFT / M)
+    const CT_DIV_MULTIPLIER: u64;
+
+    /// Perform constant-time division of x by Self::U32
+    /// Requires: x < Q (the field modulus, ~2^23)
+    #[inline(always)]
+    fn ct_div(x: u32) -> u32 {
+        // Barrett reduction: q = (x * MULTIPLIER) >> SHIFT
+        // This gives us floor(x / M) for x < 2^SHIFT / MULTIPLIER * M
+        let x64 = u64::from(x);
+        let quotient = (x64 * Self::CT_DIV_MULTIPLIER) >> Self::CT_DIV_SHIFT;
+        quotient as u32
+    }
+}
+
+impl<M> ConstantTimeDiv for M
+where
+    M: Unsigned,
+{
+    // Use a shift that provides enough precision for the ML-DSA field (Q ~ 2^23)
+    // We need SHIFT > log2(Q) + log2(M) to ensure accuracy
+    // With Q < 2^24 and M < 2^20, SHIFT = 48 is sufficient
+    const CT_DIV_SHIFT: usize = 48;
+
+    // Precompute the multiplier at compile time
+    // We add (M-1) before dividing to get ceiling division, ensuring we never underestimate
+    #[allow(clippy::integer_division_remainder_used)]
+    const CT_DIV_MULTIPLIER: u64 = ((1u64 << Self::CT_DIV_SHIFT) + M::U64 - 1) / M::U64;
+}
+
 impl Decompose for Elem {
     // Algorithm 36 Decompose
+    //
+    // This implementation uses constant-time division to avoid timing side-channels.
+    // The original algorithm used hardware division which has variable timing based
+    // on operand values, potentially leaking secret information during signing.
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
         let r_plus = self.clone();
         let r0 = r_plus.mod_plus_minus::<TwoGamma2>();
@@ -63,8 +105,9 @@ impl Decompose for Elem {
         if r_plus - r0 == Elem::new(BaseField::Q - 1) {
             (Elem::new(0), r0 - Elem::new(1))
         } else {
-            let mut r1 = r_plus - r0;
-            r1.0 /= TwoGamma2::U32;
+            let diff = r_plus - r0;
+            // Use constant-time division instead of hardware division
+            let r1 = Elem::new(TwoGamma2::ct_div(diff.0));
             (r1, r0)
         }
     }

See our blog post on how we avoided side-channels in our Go implementation of ML-DSA for more information.

Summary

There's a bug in the use_hint function where it adds 1 instead of subtracting 1 when the decomposed low bits r0 equal exactly zero. FIPS 204 Algorithm 40 is pretty clear that r0 > 0 means strictly positive, but the current code treats zero as positive. This causes valid signatures to potentially fail verification when this edge case gets hit.

Details

The issue is in ml-dsa/src/hint.rs in the use_hint function. Here's what FIPS 204 Algorithm 40 says:

3: if h = 1 and r0 > 0  return (r1 + 1) mod m
4: if h = 1 and r0 <= 0  return (r1 − 1) mod m

Line 3 uses r0 > 0 (strictly greater than zero), and line 4 uses r0 <= 0 (less than or equal, which includes zero). So when r0 = 0, the spec says to subtract 1.

But the current implementation does this:

if h && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h && r0.0 >= BaseField::Q - gamma2 {
    Elem::new((r1.0 + m - 1) % m)
}

The problem is r0.0 <= gamma2 includes zero. When r0 = 0, this condition is true (since 0 <= gamma2), so it adds 1. But according to the spec, r0 = 0 should fall into the r0 <= 0 case and subtract 1 instead.

The result is +1 when it should be -1, which is an off by two error mod m.

PoC

Take MLDSA 44 where γ2 = 95,232 and m = 44.

If use_hint(true, 0) is called:

• Decompose(0) gives (r1=0, r0=0)
• The condition r0.0 <= gamma2 is 0 <= 95232 which is true
• So it returns (0 + 1) % 44 = 1

But FIPS 204 says:

• r0 > 0 is 0 > 0 which is false
• r0 ≤ 0 is 0 ≤ 0 which is true
• So it should return (0 - 1) mod 44 = 43

The function returns 1 when it should return 43.

This can happen in real signatures whenever any coefficient of the w' vector happens to be a multiple of 2γ2, which makes its decomposed r0 equal zero. It's not super common but it's definitely possible, and when it hits, verification will fail for a completely valid signature.

Impact

This is a FIPS 204 compliance bug that affects signature verification. When the edge case triggers, valid signatures get rejected. Since MLDSA is supposed to be used for high security post quantum cryptography, having verification randomly fail isn't great. It's also theoretically possible that the mismatch between what signing expects and what verification does could be exploited somehow, though that would need more looking into.

The fix is straightforward, just change the condition to explicitly check for positive values:

if h && r0.0 > 0 && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h {
    Elem::new((r1.0 + m - 1) % m)
}

Affected Crate: ml-dsa
Affected Versions: v0.1.0-rc.2 (and commits since b01c3b7)
Severity: Medium
Reporter: Oren Yomtov (Fireblocks)

Summary

The ML-DSA signature verification implementation in the RustCrypto ml-dsa crate incorrectly accepts signatures with repeated (duplicate) hint indices. According to the ML-DSA specification (FIPS 204 / RFC 9881), hint indices within each polynomial must be strictly increasing. The current implementation uses a non-strict monotonic check (<= instead of <), allowing duplicate indices.

Note: This is a regression bug. The original implementation was correct, but commit b01c3b7 ("Make ML-DSA signature decoding follow the spec (#895)", fixing issue #894) inadvertently changed the strict < comparison to <=, introducing the vulnerability.

Vulnerability Details

Root Cause

The vulnerability is located in the monotonic helper function in ml-dsa/src/hint.rs:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] <= *x)
}

The comparison operator <= allows equal consecutive values, meaning duplicate hint indices are not rejected. The correct implementation should use strict less-than (<):

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Regression Analysis

• Original correct code (commit 1d3a1d1 - "Add support for ML-DSA (#877)"): Used < (strict)
• Bug introduced (commit b01c3b7 - "Make ML-DSA signature decoding follow the spec (#895)"): Changed to <=

The commit message suggests it was intended to fix issue #894 and make decoding follow the spec, but the change to the monotonic function was in the wrong direction. The other changes in that commit (to use_hint function) may have been correct, but this specific change introduced signature malleability.

Technical Impact

This vulnerability allows signature malleability - the same logical signature can have multiple valid byte-level encodings. An attacker can take a valid signature and create additional "valid" signatures by duplicating hint indices.

Per the ML-DSA specification (FIPS 204, Section 6.2 and Algorithm 26 HintBitUnpack), hint indices must be strictly increasing to ensure a unique, canonical encoding. Accepting non-canonical signatures can lead to:

1. Signature Malleability: Multiple distinct byte sequences verify as valid for the same message/key pair
2. Protocol-Level Vulnerabilities: Systems that rely on signature uniqueness (e.g., for transaction deduplication, replay protection, or signature-based identifiers) may be vulnerable
3. Interoperability Issues: Non-compliant signatures may be rejected by other conforming implementations

Affected Security Levels

All ML-DSA parameter sets are affected:

• ML-DSA-44 (NIST Security Level 2)
• ML-DSA-65 (NIST Security Level 3)
• ML-DSA-87 (NIST Security Level 5)

Proof of Concept

See the file poc_mldsa_repeated_hint.rs for a standalone proof of concept that demonstrates the vulnerability.

The PoC uses test vectors from the Wycheproof test suite that specifically test for this invalid encoding:

• Test Vector Source: Wycheproof ML-DSA Test Vectors
• Test Case ID 18: "signature with a repeated hint"
• Expected Result: invalid
• Actual Result: valid (BUG)

Remediation

Update the monotonic function in ml-dsa/src/hint.rs to use strict less-than comparison:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Design Intent: ML-DSA is NOT Intended to Allow Malleability

While some cryptographic libraries intentionally permit signature malleability for compatibility or performance reasons, ML-DSA is explicitly designed to prevent it:

1. FIPS 204 Specification: ML-DSA is designed to be strongly unforgeable under chosen message attacks (SUF-CMA). This security property explicitly prevents signature malleability.

2. NIST PQC Forum Discussion: In February 2024, there was a discussion on the NIST PQC forum about potential malleability in ML-DSA's hint unpacking. The consensus was that ML-DSA is intended to be SUF-CMA, meaning any malleability issues should be considered bugs and fixed.

3. No Documentation of Intentional Malleability: There is no documentation in the RustCrypto ml-dsa crate, FIPS 204, or RFC 9881 suggesting that signature malleability is an acceptable or intentional property.

4. Regression Bug: The fact that the original implementation had strict ordering (<) and this was changed to non-strict (<=) in a "fix" commit suggests this was an unintentional regression, not a design decision.

Summary

A timing side-channel was discovered in the Decompose algorithm which is used during ML-DSA signing to generate hints for the signature.

Details

The analysis was performed using a constant-time analyzer that examines compiled assembly code for instructions with data-dependent timing behavior. The analyzer flags:

• UDIV/SDIV instructions: Hardware division instructions have early termination optimizations where execution time depends on operand values.

The decompose function used a hardware division instruction to compute r1.0 / TwoGamma2::U32. This function is called during signing through high_bits() and low_bits(), which process values derived from secret key components:

• (&w - &cs2).low_bits() where cs2 is derived from secret key component s2
• Hint::new() calls high_bits() on values derived from secret key component t0

Original Code:

fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
    // ...
    let mut r1 = r_plus - r0;
    r1.0 /= TwoGamma2::U32;  // Variable-time division on secret-derived data
    (r1, r0)
}

PoC

I do not have an exploit written for this, currently.

Impact

The dividend (r1.0) is derived from secret key material. An attacker with precise timing measurements could extract information about the signing key by observing timing variations in the division operation.

Mitigation

Replacing division with constant-time Barrett reduction mitigates this risk. Since TwoGamma2 is a compile-time constant, we precompute the multiplicative inverse:

diff --git a/ml-dsa/src/algebra.rs b/ml-dsa/src/algebra.rs
index 559b68a..bb126ce 100644
--- a/ml-dsa/src/algebra.rs
+++ b/ml-dsa/src/algebra.rs
@@ -54,8 +54,50 @@ pub(crate) trait Decompose {
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem);
 }
 
+/// Constant-time division by a compile-time constant divisor.
+///
+/// This trait provides a constant-time alternative to the hardware division
+/// instruction, which has variable timing based on operand values.
+/// Uses Barrett reduction to compute `x / M` where M is a compile-time constant.
+pub(crate) trait ConstantTimeDiv: Unsigned {
+    /// Bit shift for Barrett reduction, chosen to provide sufficient precision
+    const CT_DIV_SHIFT: usize;
+    /// Precomputed multiplier: ceil(2^SHIFT / M)
+    const CT_DIV_MULTIPLIER: u64;
+
+    /// Perform constant-time division of x by Self::U32
+    /// Requires: x < Q (the field modulus, ~2^23)
+    #[inline(always)]
+    fn ct_div(x: u32) -> u32 {
+        // Barrett reduction: q = (x * MULTIPLIER) >> SHIFT
+        // This gives us floor(x / M) for x < 2^SHIFT / MULTIPLIER * M
+        let x64 = u64::from(x);
+        let quotient = (x64 * Self::CT_DIV_MULTIPLIER) >> Self::CT_DIV_SHIFT;
+        quotient as u32
+    }
+}
+
+impl<M> ConstantTimeDiv for M
+where
+    M: Unsigned,
+{
+    // Use a shift that provides enough precision for the ML-DSA field (Q ~ 2^23)
+    // We need SHIFT > log2(Q) + log2(M) to ensure accuracy
+    // With Q < 2^24 and M < 2^20, SHIFT = 48 is sufficient
+    const CT_DIV_SHIFT: usize = 48;
+
+    // Precompute the multiplier at compile time
+    // We add (M-1) before dividing to get ceiling division, ensuring we never underestimate
+    #[allow(clippy::integer_division_remainder_used)]
+    const CT_DIV_MULTIPLIER: u64 = ((1u64 << Self::CT_DIV_SHIFT) + M::U64 - 1) / M::U64;
+}
+
 impl Decompose for Elem {
     // Algorithm 36 Decompose
+    //
+    // This implementation uses constant-time division to avoid timing side-channels.
+    // The original algorithm used hardware division which has variable timing based
+    // on operand values, potentially leaking secret information during signing.
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
         let r_plus = self.clone();
         let r0 = r_plus.mod_plus_minus::<TwoGamma2>();
@@ -63,8 +105,9 @@ impl Decompose for Elem {
         if r_plus - r0 == Elem::new(BaseField::Q - 1) {
             (Elem::new(0), r0 - Elem::new(1))
         } else {
-            let mut r1 = r_plus - r0;
-            r1.0 /= TwoGamma2::U32;
+            let diff = r_plus - r0;
+            // Use constant-time division instead of hardware division
+            let r1 = Elem::new(TwoGamma2::ct_div(diff.0));
             (r1, r0)
         }
     }

See our blog post on how we avoided side-channels in our Go implementation of ML-DSA for more information.

Summary

There's a bug in the use_hint function where it adds 1 instead of subtracting 1 when the decomposed low bits r0 equal exactly zero. FIPS 204 Algorithm 40 is pretty clear that r0 > 0 means strictly positive, but the current code treats zero as positive. This causes valid signatures to potentially fail verification when this edge case gets hit.

Details

The issue is in ml-dsa/src/hint.rs in the use_hint function. Here's what FIPS 204 Algorithm 40 says:

3: if h = 1 and r0 > 0  return (r1 + 1) mod m
4: if h = 1 and r0 <= 0  return (r1 − 1) mod m

Line 3 uses r0 > 0 (strictly greater than zero), and line 4 uses r0 <= 0 (less than or equal, which includes zero). So when r0 = 0, the spec says to subtract 1.

But the current implementation does this:

if h && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h && r0.0 >= BaseField::Q - gamma2 {
    Elem::new((r1.0 + m - 1) % m)
}

The problem is r0.0 <= gamma2 includes zero. When r0 = 0, this condition is true (since 0 <= gamma2), so it adds 1. But according to the spec, r0 = 0 should fall into the r0 <= 0 case and subtract 1 instead.

The result is +1 when it should be -1, which is an off by two error mod m.

PoC

Take MLDSA 44 where γ2 = 95,232 and m = 44.

If use_hint(true, 0) is called:

• Decompose(0) gives (r1=0, r0=0)
• The condition r0.0 <= gamma2 is 0 <= 95232 which is true
• So it returns (0 + 1) % 44 = 1

But FIPS 204 says:

• r0 > 0 is 0 > 0 which is false
• r0 ≤ 0 is 0 ≤ 0 which is true
• So it should return (0 - 1) mod 44 = 43

The function returns 1 when it should return 43.

This can happen in real signatures whenever any coefficient of the w' vector happens to be a multiple of 2γ2, which makes its decomposed r0 equal zero. It's not super common but it's definitely possible, and when it hits, verification will fail for a completely valid signature.

Impact

This is a FIPS 204 compliance bug that affects signature verification. When the edge case triggers, valid signatures get rejected. Since MLDSA is supposed to be used for high security post quantum cryptography, having verification randomly fail isn't great. It's also theoretically possible that the mismatch between what signing expects and what verification does could be exploited somehow, though that would need more looking into.

The fix is straightforward, just change the condition to explicitly check for positive values:

if h && r0.0 > 0 && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h {
    Elem::new((r1.0 + m - 1) % m)
}

Affected Crate: ml-dsa
Affected Versions: v0.1.0-rc.2 (and commits since b01c3b7)
Severity: Medium
Reporter: Oren Yomtov (Fireblocks)

Summary

The ML-DSA signature verification implementation in the RustCrypto ml-dsa crate incorrectly accepts signatures with repeated (duplicate) hint indices. According to the ML-DSA specification (FIPS 204 / RFC 9881), hint indices within each polynomial must be strictly increasing. The current implementation uses a non-strict monotonic check (<= instead of <), allowing duplicate indices.

Note: This is a regression bug. The original implementation was correct, but commit b01c3b7 ("Make ML-DSA signature decoding follow the spec (#895)", fixing issue #894) inadvertently changed the strict < comparison to <=, introducing the vulnerability.

Vulnerability Details

Root Cause

The vulnerability is located in the monotonic helper function in ml-dsa/src/hint.rs:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] <= *x)
}

The comparison operator <= allows equal consecutive values, meaning duplicate hint indices are not rejected. The correct implementation should use strict less-than (<):

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Regression Analysis

• Original correct code (commit 1d3a1d1 - "Add support for ML-DSA (#877)"): Used < (strict)
• Bug introduced (commit b01c3b7 - "Make ML-DSA signature decoding follow the spec (#895)"): Changed to <=

The commit message suggests it was intended to fix issue #894 and make decoding follow the spec, but the change to the monotonic function was in the wrong direction. The other changes in that commit (to use_hint function) may have been correct, but this specific change introduced signature malleability.

Technical Impact

This vulnerability allows signature malleability - the same logical signature can have multiple valid byte-level encodings. An attacker can take a valid signature and create additional "valid" signatures by duplicating hint indices.

Per the ML-DSA specification (FIPS 204, Section 6.2 and Algorithm 26 HintBitUnpack), hint indices must be strictly increasing to ensure a unique, canonical encoding. Accepting non-canonical signatures can lead to:

1. Signature Malleability: Multiple distinct byte sequences verify as valid for the same message/key pair
2. Protocol-Level Vulnerabilities: Systems that rely on signature uniqueness (e.g., for transaction deduplication, replay protection, or signature-based identifiers) may be vulnerable
3. Interoperability Issues: Non-compliant signatures may be rejected by other conforming implementations

Affected Security Levels

All ML-DSA parameter sets are affected:

• ML-DSA-44 (NIST Security Level 2)
• ML-DSA-65 (NIST Security Level 3)
• ML-DSA-87 (NIST Security Level 5)

Proof of Concept

See the file poc_mldsa_repeated_hint.rs for a standalone proof of concept that demonstrates the vulnerability.

The PoC uses test vectors from the Wycheproof test suite that specifically test for this invalid encoding:

• Test Vector Source: Wycheproof ML-DSA Test Vectors
• Test Case ID 18: "signature with a repeated hint"
• Expected Result: invalid
• Actual Result: valid (BUG)

Remediation

Update the monotonic function in ml-dsa/src/hint.rs to use strict less-than comparison:

fn monotonic(a: &[usize]) -> bool {
    a.iter().enumerate().all(|(i, x)| i == 0 || a[i - 1] < *x)
}

Design Intent: ML-DSA is NOT Intended to Allow Malleability

While some cryptographic libraries intentionally permit signature malleability for compatibility or performance reasons, ML-DSA is explicitly designed to prevent it:

1. FIPS 204 Specification: ML-DSA is designed to be strongly unforgeable under chosen message attacks (SUF-CMA). This security property explicitly prevents signature malleability.

2. NIST PQC Forum Discussion: In February 2024, there was a discussion on the NIST PQC forum about potential malleability in ML-DSA's hint unpacking. The consensus was that ML-DSA is intended to be SUF-CMA, meaning any malleability issues should be considered bugs and fixed.

3. No Documentation of Intentional Malleability: There is no documentation in the RustCrypto ml-dsa crate, FIPS 204, or RFC 9881 suggesting that signature malleability is an acceptable or intentional property.

4. Regression Bug: The fact that the original implementation had strict ordering (<) and this was changed to non-strict (<=) in a "fix" commit suggests this was an unintentional regression, not a design decision.

Summary

A timing side-channel was discovered in the Decompose algorithm which is used during ML-DSA signing to generate hints for the signature.

Details

The analysis was performed using a constant-time analyzer that examines compiled assembly code for instructions with data-dependent timing behavior. The analyzer flags:

• UDIV/SDIV instructions: Hardware division instructions have early termination optimizations where execution time depends on operand values.

The decompose function used a hardware division instruction to compute r1.0 / TwoGamma2::U32. This function is called during signing through high_bits() and low_bits(), which process values derived from secret key components:

• (&w - &cs2).low_bits() where cs2 is derived from secret key component s2
• Hint::new() calls high_bits() on values derived from secret key component t0

Original Code:

fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
    // ...
    let mut r1 = r_plus - r0;
    r1.0 /= TwoGamma2::U32;  // Variable-time division on secret-derived data
    (r1, r0)
}

PoC

I do not have an exploit written for this, currently.

Impact

The dividend (r1.0) is derived from secret key material. An attacker with precise timing measurements could extract information about the signing key by observing timing variations in the division operation.

Mitigation

Replacing division with constant-time Barrett reduction mitigates this risk. Since TwoGamma2 is a compile-time constant, we precompute the multiplicative inverse:

diff --git a/ml-dsa/src/algebra.rs b/ml-dsa/src/algebra.rs
index 559b68a..bb126ce 100644
--- a/ml-dsa/src/algebra.rs
+++ b/ml-dsa/src/algebra.rs
@@ -54,8 +54,50 @@ pub(crate) trait Decompose {
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem);
 }
 
+/// Constant-time division by a compile-time constant divisor.
+///
+/// This trait provides a constant-time alternative to the hardware division
+/// instruction, which has variable timing based on operand values.
+/// Uses Barrett reduction to compute `x / M` where M is a compile-time constant.
+pub(crate) trait ConstantTimeDiv: Unsigned {
+    /// Bit shift for Barrett reduction, chosen to provide sufficient precision
+    const CT_DIV_SHIFT: usize;
+    /// Precomputed multiplier: ceil(2^SHIFT / M)
+    const CT_DIV_MULTIPLIER: u64;
+
+    /// Perform constant-time division of x by Self::U32
+    /// Requires: x < Q (the field modulus, ~2^23)
+    #[inline(always)]
+    fn ct_div(x: u32) -> u32 {
+        // Barrett reduction: q = (x * MULTIPLIER) >> SHIFT
+        // This gives us floor(x / M) for x < 2^SHIFT / MULTIPLIER * M
+        let x64 = u64::from(x);
+        let quotient = (x64 * Self::CT_DIV_MULTIPLIER) >> Self::CT_DIV_SHIFT;
+        quotient as u32
+    }
+}
+
+impl<M> ConstantTimeDiv for M
+where
+    M: Unsigned,
+{
+    // Use a shift that provides enough precision for the ML-DSA field (Q ~ 2^23)
+    // We need SHIFT > log2(Q) + log2(M) to ensure accuracy
+    // With Q < 2^24 and M < 2^20, SHIFT = 48 is sufficient
+    const CT_DIV_SHIFT: usize = 48;
+
+    // Precompute the multiplier at compile time
+    // We add (M-1) before dividing to get ceiling division, ensuring we never underestimate
+    #[allow(clippy::integer_division_remainder_used)]
+    const CT_DIV_MULTIPLIER: u64 = ((1u64 << Self::CT_DIV_SHIFT) + M::U64 - 1) / M::U64;
+}
+
 impl Decompose for Elem {
     // Algorithm 36 Decompose
+    //
+    // This implementation uses constant-time division to avoid timing side-channels.
+    // The original algorithm used hardware division which has variable timing based
+    // on operand values, potentially leaking secret information during signing.
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
         let r_plus = self.clone();
         let r0 = r_plus.mod_plus_minus::<TwoGamma2>();
@@ -63,8 +105,9 @@ impl Decompose for Elem {
         if r_plus - r0 == Elem::new(BaseField::Q - 1) {
             (Elem::new(0), r0 - Elem::new(1))
         } else {
-            let mut r1 = r_plus - r0;
-            r1.0 /= TwoGamma2::U32;
+            let diff = r_plus - r0;
+            // Use constant-time division instead of hardware division
+            let r1 = Elem::new(TwoGamma2::ct_div(diff.0));
             (r1, r0)
         }
     }

See our blog post on how we avoided side-channels in our Go implementation of ML-DSA for more information.

Summary

There's a bug in the use_hint function where it adds 1 instead of subtracting 1 when the decomposed low bits r0 equal exactly zero. FIPS 204 Algorithm 40 is pretty clear that r0 > 0 means strictly positive, but the current code treats zero as positive. This causes valid signatures to potentially fail verification when this edge case gets hit.

Details

The issue is in ml-dsa/src/hint.rs in the use_hint function. Here's what FIPS 204 Algorithm 40 says:

3: if h = 1 and r0 > 0  return (r1 + 1) mod m
4: if h = 1 and r0 <= 0  return (r1 − 1) mod m

Line 3 uses r0 > 0 (strictly greater than zero), and line 4 uses r0 <= 0 (less than or equal, which includes zero). So when r0 = 0, the spec says to subtract 1.

But the current implementation does this:

if h && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h && r0.0 >= BaseField::Q - gamma2 {
    Elem::new((r1.0 + m - 1) % m)
}

The problem is r0.0 <= gamma2 includes zero. When r0 = 0, this condition is true (since 0 <= gamma2), so it adds 1. But according to the spec, r0 = 0 should fall into the r0 <= 0 case and subtract 1 instead.

The result is +1 when it should be -1, which is an off by two error mod m.

PoC

Take MLDSA 44 where γ2 = 95,232 and m = 44.

If use_hint(true, 0) is called:

• Decompose(0) gives (r1=0, r0=0)
• The condition r0.0 <= gamma2 is 0 <= 95232 which is true
• So it returns (0 + 1) % 44 = 1

But FIPS 204 says:

• r0 > 0 is 0 > 0 which is false
• r0 ≤ 0 is 0 ≤ 0 which is true
• So it should return (0 - 1) mod 44 = 43

The function returns 1 when it should return 43.

This can happen in real signatures whenever any coefficient of the w' vector happens to be a multiple of 2γ2, which makes its decomposed r0 equal zero. It's not super common but it's definitely possible, and when it hits, verification will fail for a completely valid signature.

Impact

This is a FIPS 204 compliance bug that affects signature verification. When the edge case triggers, valid signatures get rejected. Since MLDSA is supposed to be used for high security post quantum cryptography, having verification randomly fail isn't great. It's also theoretically possible that the mismatch between what signing expects and what verification does could be exploited somehow, though that would need more looking into.

The fix is straightforward, just change the condition to explicitly check for positive values:

if h && r0.0 > 0 && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h {
    Elem::new((r1.0 + m - 1) % m)
}

Summary

A timing side-channel was discovered in the Decompose algorithm which is used during ML-DSA signing to generate hints for the signature.

Details

The analysis was performed using a constant-time analyzer that examines compiled assembly code for instructions with data-dependent timing behavior. The analyzer flags:

• UDIV/SDIV instructions: Hardware division instructions have early termination optimizations where execution time depends on operand values.

The decompose function used a hardware division instruction to compute r1.0 / TwoGamma2::U32. This function is called during signing through high_bits() and low_bits(), which process values derived from secret key components:

• (&w - &cs2).low_bits() where cs2 is derived from secret key component s2
• Hint::new() calls high_bits() on values derived from secret key component t0

Original Code:

fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
    // ...
    let mut r1 = r_plus - r0;
    r1.0 /= TwoGamma2::U32;  // Variable-time division on secret-derived data
    (r1, r0)
}

PoC

I do not have an exploit written for this, currently.

Impact

The dividend (r1.0) is derived from secret key material. An attacker with precise timing measurements could extract information about the signing key by observing timing variations in the division operation.

Mitigation

Replacing division with constant-time Barrett reduction mitigates this risk. Since TwoGamma2 is a compile-time constant, we precompute the multiplicative inverse:

diff --git a/ml-dsa/src/algebra.rs b/ml-dsa/src/algebra.rs
index 559b68a..bb126ce 100644
--- a/ml-dsa/src/algebra.rs
+++ b/ml-dsa/src/algebra.rs
@@ -54,8 +54,50 @@ pub(crate) trait Decompose {
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem);
 }
 
+/// Constant-time division by a compile-time constant divisor.
+///
+/// This trait provides a constant-time alternative to the hardware division
+/// instruction, which has variable timing based on operand values.
+/// Uses Barrett reduction to compute `x / M` where M is a compile-time constant.
+pub(crate) trait ConstantTimeDiv: Unsigned {
+    /// Bit shift for Barrett reduction, chosen to provide sufficient precision
+    const CT_DIV_SHIFT: usize;
+    /// Precomputed multiplier: ceil(2^SHIFT / M)
+    const CT_DIV_MULTIPLIER: u64;
+
+    /// Perform constant-time division of x by Self::U32
+    /// Requires: x < Q (the field modulus, ~2^23)
+    #[inline(always)]
+    fn ct_div(x: u32) -> u32 {
+        // Barrett reduction: q = (x * MULTIPLIER) >> SHIFT
+        // This gives us floor(x / M) for x < 2^SHIFT / MULTIPLIER * M
+        let x64 = u64::from(x);
+        let quotient = (x64 * Self::CT_DIV_MULTIPLIER) >> Self::CT_DIV_SHIFT;
+        quotient as u32
+    }
+}
+
+impl<M> ConstantTimeDiv for M
+where
+    M: Unsigned,
+{
+    // Use a shift that provides enough precision for the ML-DSA field (Q ~ 2^23)
+    // We need SHIFT > log2(Q) + log2(M) to ensure accuracy
+    // With Q < 2^24 and M < 2^20, SHIFT = 48 is sufficient
+    const CT_DIV_SHIFT: usize = 48;
+
+    // Precompute the multiplier at compile time
+    // We add (M-1) before dividing to get ceiling division, ensuring we never underestimate
+    #[allow(clippy::integer_division_remainder_used)]
+    const CT_DIV_MULTIPLIER: u64 = ((1u64 << Self::CT_DIV_SHIFT) + M::U64 - 1) / M::U64;
+}
+
 impl Decompose for Elem {
     // Algorithm 36 Decompose
+    //
+    // This implementation uses constant-time division to avoid timing side-channels.
+    // The original algorithm used hardware division which has variable timing based
+    // on operand values, potentially leaking secret information during signing.
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
         let r_plus = self.clone();
         let r0 = r_plus.mod_plus_minus::<TwoGamma2>();
@@ -63,8 +105,9 @@ impl Decompose for Elem {
         if r_plus - r0 == Elem::new(BaseField::Q - 1) {
             (Elem::new(0), r0 - Elem::new(1))
         } else {
-            let mut r1 = r_plus - r0;
-            r1.0 /= TwoGamma2::U32;
+            let diff = r_plus - r0;
+            // Use constant-time division instead of hardware division
+            let r1 = Elem::new(TwoGamma2::ct_div(diff.0));
             (r1, r0)
         }
     }

See our blog post on how we avoided side-channels in our Go implementation of ML-DSA for more information.

Summary

There's a bug in the use_hint function where it adds 1 instead of subtracting 1 when the decomposed low bits r0 equal exactly zero. FIPS 204 Algorithm 40 is pretty clear that r0 > 0 means strictly positive, but the current code treats zero as positive. This causes valid signatures to potentially fail verification when this edge case gets hit.

Details

The issue is in ml-dsa/src/hint.rs in the use_hint function. Here's what FIPS 204 Algorithm 40 says:

3: if h = 1 and r0 > 0  return (r1 + 1) mod m
4: if h = 1 and r0 <= 0  return (r1 − 1) mod m

Line 3 uses r0 > 0 (strictly greater than zero), and line 4 uses r0 <= 0 (less than or equal, which includes zero). So when r0 = 0, the spec says to subtract 1.

But the current implementation does this:

if h && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h && r0.0 >= BaseField::Q - gamma2 {
    Elem::new((r1.0 + m - 1) % m)
}

The problem is r0.0 <= gamma2 includes zero. When r0 = 0, this condition is true (since 0 <= gamma2), so it adds 1. But according to the spec, r0 = 0 should fall into the r0 <= 0 case and subtract 1 instead.

The result is +1 when it should be -1, which is an off by two error mod m.

PoC

Take MLDSA 44 where γ2 = 95,232 and m = 44.

If use_hint(true, 0) is called:

• Decompose(0) gives (r1=0, r0=0)
• The condition r0.0 <= gamma2 is 0 <= 95232 which is true
• So it returns (0 + 1) % 44 = 1

But FIPS 204 says:

• r0 > 0 is 0 > 0 which is false
• r0 ≤ 0 is 0 ≤ 0 which is true
• So it should return (0 - 1) mod 44 = 43

The function returns 1 when it should return 43.

This can happen in real signatures whenever any coefficient of the w' vector happens to be a multiple of 2γ2, which makes its decomposed r0 equal zero. It's not super common but it's definitely possible, and when it hits, verification will fail for a completely valid signature.

Impact

This is a FIPS 204 compliance bug that affects signature verification. When the edge case triggers, valid signatures get rejected. Since MLDSA is supposed to be used for high security post quantum cryptography, having verification randomly fail isn't great. It's also theoretically possible that the mismatch between what signing expects and what verification does could be exploited somehow, though that would need more looking into.

The fix is straightforward, just change the condition to explicitly check for positive values:

if h && r0.0 > 0 && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h {
    Elem::new((r1.0 + m - 1) % m)
}

Summary

A timing side-channel was discovered in the Decompose algorithm which is used during ML-DSA signing to generate hints for the signature.

Details

The analysis was performed using a constant-time analyzer that examines compiled assembly code for instructions with data-dependent timing behavior. The analyzer flags:

• UDIV/SDIV instructions: Hardware division instructions have early termination optimizations where execution time depends on operand values.

The decompose function used a hardware division instruction to compute r1.0 / TwoGamma2::U32. This function is called during signing through high_bits() and low_bits(), which process values derived from secret key components:

• (&w - &cs2).low_bits() where cs2 is derived from secret key component s2
• Hint::new() calls high_bits() on values derived from secret key component t0

Original Code:

fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
    // ...
    let mut r1 = r_plus - r0;
    r1.0 /= TwoGamma2::U32;  // Variable-time division on secret-derived data
    (r1, r0)
}

PoC

I do not have an exploit written for this, currently.

Impact

The dividend (r1.0) is derived from secret key material. An attacker with precise timing measurements could extract information about the signing key by observing timing variations in the division operation.

Mitigation

Replacing division with constant-time Barrett reduction mitigates this risk. Since TwoGamma2 is a compile-time constant, we precompute the multiplicative inverse:

diff --git a/ml-dsa/src/algebra.rs b/ml-dsa/src/algebra.rs
index 559b68a..bb126ce 100644
--- a/ml-dsa/src/algebra.rs
+++ b/ml-dsa/src/algebra.rs
@@ -54,8 +54,50 @@ pub(crate) trait Decompose {
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem);
 }
 
+/// Constant-time division by a compile-time constant divisor.
+///
+/// This trait provides a constant-time alternative to the hardware division
+/// instruction, which has variable timing based on operand values.
+/// Uses Barrett reduction to compute `x / M` where M is a compile-time constant.
+pub(crate) trait ConstantTimeDiv: Unsigned {
+    /// Bit shift for Barrett reduction, chosen to provide sufficient precision
+    const CT_DIV_SHIFT: usize;
+    /// Precomputed multiplier: ceil(2^SHIFT / M)
+    const CT_DIV_MULTIPLIER: u64;
+
+    /// Perform constant-time division of x by Self::U32
+    /// Requires: x < Q (the field modulus, ~2^23)
+    #[inline(always)]
+    fn ct_div(x: u32) -> u32 {
+        // Barrett reduction: q = (x * MULTIPLIER) >> SHIFT
+        // This gives us floor(x / M) for x < 2^SHIFT / MULTIPLIER * M
+        let x64 = u64::from(x);
+        let quotient = (x64 * Self::CT_DIV_MULTIPLIER) >> Self::CT_DIV_SHIFT;
+        quotient as u32
+    }
+}
+
+impl<M> ConstantTimeDiv for M
+where
+    M: Unsigned,
+{
+    // Use a shift that provides enough precision for the ML-DSA field (Q ~ 2^23)
+    // We need SHIFT > log2(Q) + log2(M) to ensure accuracy
+    // With Q < 2^24 and M < 2^20, SHIFT = 48 is sufficient
+    const CT_DIV_SHIFT: usize = 48;
+
+    // Precompute the multiplier at compile time
+    // We add (M-1) before dividing to get ceiling division, ensuring we never underestimate
+    #[allow(clippy::integer_division_remainder_used)]
+    const CT_DIV_MULTIPLIER: u64 = ((1u64 << Self::CT_DIV_SHIFT) + M::U64 - 1) / M::U64;
+}
+
 impl Decompose for Elem {
     // Algorithm 36 Decompose
+    //
+    // This implementation uses constant-time division to avoid timing side-channels.
+    // The original algorithm used hardware division which has variable timing based
+    // on operand values, potentially leaking secret information during signing.
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
         let r_plus = self.clone();
         let r0 = r_plus.mod_plus_minus::<TwoGamma2>();
@@ -63,8 +105,9 @@ impl Decompose for Elem {
         if r_plus - r0 == Elem::new(BaseField::Q - 1) {
             (Elem::new(0), r0 - Elem::new(1))
         } else {
-            let mut r1 = r_plus - r0;
-            r1.0 /= TwoGamma2::U32;
+            let diff = r_plus - r0;
+            // Use constant-time division instead of hardware division
+            let r1 = Elem::new(TwoGamma2::ct_div(diff.0));
             (r1, r0)
         }
     }

See our blog post on how we avoided side-channels in our Go implementation of ML-DSA for more information.

Summary

There's a bug in the use_hint function where it adds 1 instead of subtracting 1 when the decomposed low bits r0 equal exactly zero. FIPS 204 Algorithm 40 is pretty clear that r0 > 0 means strictly positive, but the current code treats zero as positive. This causes valid signatures to potentially fail verification when this edge case gets hit.

Details

The issue is in ml-dsa/src/hint.rs in the use_hint function. Here's what FIPS 204 Algorithm 40 says:

3: if h = 1 and r0 > 0  return (r1 + 1) mod m
4: if h = 1 and r0 <= 0  return (r1 − 1) mod m

Line 3 uses r0 > 0 (strictly greater than zero), and line 4 uses r0 <= 0 (less than or equal, which includes zero). So when r0 = 0, the spec says to subtract 1.

But the current implementation does this:

if h && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h && r0.0 >= BaseField::Q - gamma2 {
    Elem::new((r1.0 + m - 1) % m)
}

The problem is r0.0 <= gamma2 includes zero. When r0 = 0, this condition is true (since 0 <= gamma2), so it adds 1. But according to the spec, r0 = 0 should fall into the r0 <= 0 case and subtract 1 instead.

The result is +1 when it should be -1, which is an off by two error mod m.

PoC

Take MLDSA 44 where γ2 = 95,232 and m = 44.

If use_hint(true, 0) is called:

• Decompose(0) gives (r1=0, r0=0)
• The condition r0.0 <= gamma2 is 0 <= 95232 which is true
• So it returns (0 + 1) % 44 = 1

But FIPS 204 says:

• r0 > 0 is 0 > 0 which is false
• r0 ≤ 0 is 0 ≤ 0 which is true
• So it should return (0 - 1) mod 44 = 43

The function returns 1 when it should return 43.

This can happen in real signatures whenever any coefficient of the w' vector happens to be a multiple of 2γ2, which makes its decomposed r0 equal zero. It's not super common but it's definitely possible, and when it hits, verification will fail for a completely valid signature.

Impact

This is a FIPS 204 compliance bug that affects signature verification. When the edge case triggers, valid signatures get rejected. Since MLDSA is supposed to be used for high security post quantum cryptography, having verification randomly fail isn't great. It's also theoretically possible that the mismatch between what signing expects and what verification does could be exploited somehow, though that would need more looking into.

The fix is straightforward, just change the condition to explicitly check for positive values:

if h && r0.0 > 0 && r0.0 <= gamma2 {
    Elem::new((r1.0 + 1) % m)
} else if h {
    Elem::new((r1.0 + m - 1) % m)
}

Summary

A timing side-channel was discovered in the Decompose algorithm which is used during ML-DSA signing to generate hints for the signature.

Details

The analysis was performed using a constant-time analyzer that examines compiled assembly code for instructions with data-dependent timing behavior. The analyzer flags:

• UDIV/SDIV instructions: Hardware division instructions have early termination optimizations where execution time depends on operand values.

The decompose function used a hardware division instruction to compute r1.0 / TwoGamma2::U32. This function is called during signing through high_bits() and low_bits(), which process values derived from secret key components:

• (&w - &cs2).low_bits() where cs2 is derived from secret key component s2
• Hint::new() calls high_bits() on values derived from secret key component t0

Original Code:

fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
    // ...
    let mut r1 = r_plus - r0;
    r1.0 /= TwoGamma2::U32;  // Variable-time division on secret-derived data
    (r1, r0)
}

PoC

I do not have an exploit written for this, currently.

Impact

The dividend (r1.0) is derived from secret key material. An attacker with precise timing measurements could extract information about the signing key by observing timing variations in the division operation.

Mitigation

Replacing division with constant-time Barrett reduction mitigates this risk. Since TwoGamma2 is a compile-time constant, we precompute the multiplicative inverse:

diff --git a/ml-dsa/src/algebra.rs b/ml-dsa/src/algebra.rs
index 559b68a..bb126ce 100644
--- a/ml-dsa/src/algebra.rs
+++ b/ml-dsa/src/algebra.rs
@@ -54,8 +54,50 @@ pub(crate) trait Decompose {
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem);
 }
 
+/// Constant-time division by a compile-time constant divisor.
+///
+/// This trait provides a constant-time alternative to the hardware division
+/// instruction, which has variable timing based on operand values.
+/// Uses Barrett reduction to compute `x / M` where M is a compile-time constant.
+pub(crate) trait ConstantTimeDiv: Unsigned {
+    /// Bit shift for Barrett reduction, chosen to provide sufficient precision
+    const CT_DIV_SHIFT: usize;
+    /// Precomputed multiplier: ceil(2^SHIFT / M)
+    const CT_DIV_MULTIPLIER: u64;
+
+    /// Perform constant-time division of x by Self::U32
+    /// Requires: x < Q (the field modulus, ~2^23)
+    #[inline(always)]
+    fn ct_div(x: u32) -> u32 {
+        // Barrett reduction: q = (x * MULTIPLIER) >> SHIFT
+        // This gives us floor(x / M) for x < 2^SHIFT / MULTIPLIER * M
+        let x64 = u64::from(x);
+        let quotient = (x64 * Self::CT_DIV_MULTIPLIER) >> Self::CT_DIV_SHIFT;
+        quotient as u32
+    }
+}
+
+impl<M> ConstantTimeDiv for M
+where
+    M: Unsigned,
+{
+    // Use a shift that provides enough precision for the ML-DSA field (Q ~ 2^23)
+    // We need SHIFT > log2(Q) + log2(M) to ensure accuracy
+    // With Q < 2^24 and M < 2^20, SHIFT = 48 is sufficient
+    const CT_DIV_SHIFT: usize = 48;
+
+    // Precompute the multiplier at compile time
+    // We add (M-1) before dividing to get ceiling division, ensuring we never underestimate
+    #[allow(clippy::integer_division_remainder_used)]
+    const CT_DIV_MULTIPLIER: u64 = ((1u64 << Self::CT_DIV_SHIFT) + M::U64 - 1) / M::U64;
+}
+
 impl Decompose for Elem {
     // Algorithm 36 Decompose
+    //
+    // This implementation uses constant-time division to avoid timing side-channels.
+    // The original algorithm used hardware division which has variable timing based
+    // on operand values, potentially leaking secret information during signing.
     fn decompose<TwoGamma2: Unsigned>(self) -> (Elem, Elem) {
         let r_plus = self.clone();
         let r0 = r_plus.mod_plus_minus::<TwoGamma2>();
@@ -63,8 +105,9 @@ impl Decompose for Elem {
         if r_plus - r0 == Elem::new(BaseField::Q - 1) {
             (Elem::new(0), r0 - Elem::new(1))
         } else {
-            let mut r1 = r_plus - r0;
-            r1.0 /= TwoGamma2::U32;
+            let diff = r_plus - r0;
+            // Use constant-time division instead of hardware division
+            let r1 = Elem::new(TwoGamma2::ct_div(diff.0));
             (r1, r0)
         }
     }

See our blog post on how we avoided side-channels in our Go implementation of ML-DSA for more information.