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.

References

• FIPS 204 (ML-DSA Standard): https://csrc.nist.gov/pubs/fips/204/final
• RFC 9881: https://datatracker.ietf.org/doc/html/rfc9881
• Wycheproof Test Suite: https://github.com/C2SP/wycheproof
• Relevant Wycheproof Test Files:
  • https://github.com/C2SP/wycheproof/blob/master/testvectors_v1/mldsa_44_verify_test.json (tcId: 18)
  • https://github.com/C2SP/wycheproof/blob/master/testvectors_v1/mldsa_65_verify_test.json (tcId: 19)
  • https://github.com/C2SP/wycheproof/blob/master/testvectors_v1/mldsa_87_verify_test.json (tcId: 21)
• Introducing PR:: #895
  • Introducing Commit: b01c3b7
• Related Issue: #894