Strong Unforgeability and the Hint: Why a Byte-Exact Signature Matters for Logs, Tokens and Ledgers

In 2016 two Bitcoin developers specified a rule to stop relay nodes from flipping a number inside other people's signatures. Nobody was forging anything; the flipped signatures were still made by the rightful key holders and still valid. The trouble was that the transaction identifier was computed over those signature bytes, so any stranger could change it, and software that tracked payments by identifier lost track of them. That episode is the clearest way into a property most engineers never think about until it breaks: whether a valid signature can be reshaped into a different valid signature without the key. ML-DSA is designed so that it cannot. The interesting questions are where that guarantee comes from, how close the standard came to losing it, and where systems built around agents still lose it on their own.

A signature is also an identifier

A digital signature exists to prove authenticity and integrity, but systems quietly give it a second job. A replay cache remembers the hashes of signed requests it has seen so that a captured request cannot be submitted twice. A deduplicating log drops entries whose signature it already stored. A content-addressed store names an object by a hash that includes its signature. A ledger derives a transaction identifier from bytes that include the signatures. In each case the system is using the signature as an identifier, and it is assuming that the only way to obtain a different valid signature is to ask the key holder.

Cryptography has a name for that assumption. A scheme is existentially unforgeable under chosen-message attack, EUF-CMA, if an adversary who may request signatures on messages of its choice cannot produce a valid signature on any message it never requested. It is strongly unforgeable, SUF-CMA, if the adversary also cannot produce a new valid signature on a message it did request. The difference is exactly the reshaping problem. Under EUF alone, an attacker holding one valid signature may be able to turn it into a different valid signature for the same message, a property called malleability, without learning anything about the key and without counting as a forger in the weaker game.

FIPS 204 Section 3.1 states that ML-DSA is designed to be SUF-CMA, and the abstract of the standard spells out what that is for: detecting unauthorized modification and authenticating the signer. This article asks the two questions that matter for anyone building on that sentence. Where, concretely, does ML-DSA get uniqueness, so that a verifier knows what it must enforce? And where do real systems lose uniqueness even when the algorithm keeps it?

The precedent: a free second signature in ECDSA

Bitcoin Improvement Proposal 146, by Lau and Wuille, describes the problem in its motivation. An ECDSA signature is a pair of numbers, and negating the second number modulo the curve order yields another signature that also verifies. Any relay node could therefore take a transaction in transit, replace each signature with its mirror image, and pass it on. The transaction still spent the same coins to the same recipients under the same keys, but for transactions created before segregated witness the identifier changed, which, in the words of the proposal, invalidates any unconfirmed child transactions that referred to the original identifier.

The fixes are instructive because none of them changed the underlying hard problem. BIP 66 first required strict DER encoding, removing malleability that came purely from alternative byte encodings of the same pair. BIP 146 then specified that the second number must lie in the lower half of its range, so that exactly one of each mirror-image pair is accepted. Segregated witness, specified in BIP 141, removed signatures from the input of the transaction identifier altogether. EdDSA, as specified in RFC 8032, builds the equivalent of the range rule into verification by rejecting signatures whose scalar is not fully reduced.

The general lesson is that malleability is a property of the verifier's acceptance set, not only of the mathematics. A scheme can rest on a hard problem and still accept several byte strings for one message if its encoding admits alternatives or its verification equation is symmetric. Strong unforgeability is achieved when both layers are pinned down: the mathematical objects that pass verification are unique for the signer's output, and the bytes that decode to those objects are unique too.

Where ML-DSA's uniqueness comes from

An ML-DSA signature has three parts: a short commitment hash, a response vector of polynomials, and a hint. Verification recomputes the signer's rounded commitment from the response, the challenge derived from the commitment hash, and the compressed public key, using the hint to correct carries that the compression of the public key would otherwise introduce. It then checks that the recomputed commitment hashes, together with the message representative, to the commitment hash in the signature, that every coefficient of the response is below a fixed bound, and that the hint has no more than a fixed number of nonzero positions. FIPS 204 explains that the hint is needed because the public key drops low-order bits, and that a second round of rejection in signing keeps the hint within its budget.

To reshape a valid signature into a different valid one for the same message, an attacker must change at least one part and still pass all checks. Changing the commitment hash while keeping the response forces the recomputed commitment to hash to a new value, which the idealized hash makes infeasible to aim. Keeping the commitment hash and changing the response is the interesting case. Two different responses that verify for the same message and the same challenge recompute the same rounded commitment, so their difference is a short vector that the public matrix sends to something very small, after the hint and rounding are accounted for. The Dilithium 3.1 specification states that this is exactly where MSIS enters its bound: the MSIS term, with a larger coefficient bound than the forgery terms, is needed only for strong unforgeability, and its parameter table reports the strong variant's MSIS hardness separately.

That is the mathematical layer. It says that the set of response, hint and commitment-hash triples that verify for a given message cannot be extended by anyone without solving a lattice problem. It does not, by itself, say that each such triple has only one byte encoding. That is the job of the decoding rules, and it is where the standard nearly slipped.

The check that went missing

The hint is stored compactly. Rather than writing every coefficient, the encoder lists the positions of the nonzero coefficients for each polynomial in turn and then records, for each polynomial, a running count of how many positions have been written so far. Algorithm 21 in FIPS 204, the hint decoder, therefore has to defend against byte strings that the honest encoder would never produce. It rejects a running count that decreases or exceeds the maximum, it rejects positions within a polynomial that are not strictly increasing, and it rejects any nonzero byte in the unused part of the position list. Each of these rules removes a way to write the same hint in more than one form.

Appendix D of FIPS 204 records that the draft standard included pseudocode that unintentionally omitted a check for malformed input while unpacking the hint, cites forum posts by Hamburg and by Mattsson on behalf of Jendral from 2024, and states plainly that failure to perform this check results in a signature scheme that is not strongly existentially unforgeable. The final standard restored the check. Whatever the exact rule that was missing, the mechanism is easy to see from the encoding: if a decoder does not insist that positions be strictly increasing, the same set of hint positions can be written in a different order, and a decoder that reconstructs the hint by setting those coefficients produces the same hint from a different byte string. The mathematics is untouched; the signature is still authentic and still verifies; but anyone can mint a second valid encoding, which is precisely what SUF-CMA forbids.

Two related rules close neighbouring gaps. Section 3.6.2 requires that an implementation accepting keys or signatures of arbitrary length shall reject any whose length differs from the specified one, and warns that failing to check lengths may interfere with strong unforgeability. Appendix D.3 also notes that the final standard uses all bits of the commitment hash when deriving the challenge, where the draft used only the first 256 bits; under the draft rule, bits beyond that prefix did not influence the challenge at all.

For implementers the practical consequence is about testing. A library can pass every positive test vector, signing and verifying correctly, and still accept malformed encodings, because a positive vector never presents a malformed hint. Strong unforgeability can only be tested with negative cases: signatures whose hint positions have been permuted within a polynomial, whose unused position bytes are nonzero, whose running counts decrease, or whose length is off by one. A verifier that accepts any of them is EUF-secure at best.

What strong unforgeability does not give you

The most common misreading of SUF-CMA is that each message has one signature. It does not mean that. It means that only the key holder can produce valid signatures. FIPS 204 signs in hedged mode by default, mixing a fresh random value into the derivation of the mask, so the honest signer produces a different valid signature every time it signs the same message. An agent that times out and retries a signed tool call has created two valid signatures for one call. A replay cache keyed on signature bytes will treat them as two requests. Nothing about this is an attack on ML-DSA; it is an application assuming a property the scheme never offered.

The second gap sits above the signature bytes, in text encodings. RFC 4648 Section 3.5 notes that base64 has pad bits in its final symbol that conforming encoders must set to zero, that if they are not checked multiple encoded strings can decode to the same binary data, and that decoders may choose to reject such encodings. A JSON Web Signature carries its signature in base64url. A gateway that indexes requests by the encoded string, while its decoder tolerates nonzero pad bits, has reintroduced malleability above a scheme that carefully removed it. The same is true of any signed payload that is re-serialized, for example JSON with reordered keys or changed whitespace, if identity is computed over the re-serialized form.

The third gap is composition. The IETF composite ML-DSA draft, which pairs ML-DSA with a classical signature, states that composite signatures are not SUF-CMA against a quantum adversary and that applications where SUF-CMA is critical should not use them. Two reasons are given: a malleable classical component such as ECDSA passes its malleability through, and even when both components are strongly unforgeable, an attacker holding two composite signatures on the same message can swap halves to build a third valid one. The fourth gap is the verifier itself: a lenient implementation that ignores length or hint checks quietly downgrades the whole system to EUF.

Three ways an agent platform loses uniqueness without breaking ML-DSA

It helps to make the gaps concrete. Consider an agent platform in which every agent holds an ML-DSA key, signs each tool call it sends to a gateway, and the gateway, the audit log and a provenance ledger all consume those signatures. None of the three failures below requires breaking the lattice problem, recovering a key or forging anything. Each comes from an identity decision made one layer above the signature, and each is this article's own analysis of a pattern rather than a reported incident.

The first is the retry storm. An agent sends a signed request to transfer data, the network stalls, and the agent's client library retries by re-signing the same request. Under hedged signing the second signature is different and valid. If the gateway's replay cache is keyed on a hash of the signature, both requests pass, and a tool with side effects runs twice. The damage scales with exactly the property that makes agents useful: they retry automatically, quickly and often. The fix is an idempotency identifier inside the signed payload, chosen once by the agent and reused across retries, so that the second request is recognized as the first.

The second is the split audit trail. An incident team later asks which agent asked for what, and the audit store deduplicated entries by signature. The two retried requests appear as two distinct actions, or, if the store instead deduplicated by encoded token text and a proxy re-encoded one copy with different base64 padding, the same action appears under two names that do not match the gateway's records. Either way the evidence no longer lines up across systems. The fix is a log entry identifier computed over the canonical payload, with every signature that was presented stored alongside it as evidence.

The third is the forked ledger reference. A provenance ledger anchors each model-release attestation by a hash that includes the signature bytes, and later records reference earlier ones by that hash. A verifier somewhere in the ecosystem is lenient about lengths or about the hint encoding, so a third party can submit a re-encoded copy of a genuine attestation that this verifier accepts. Two ledger entries now claim to be the same attestation under different references, and anything that chains from one of them can be orphaned. This is the ECDSA identifier problem reproduced on top of a scheme designed to prevent it, and the fix is the same: strict verification everywhere, and identifiers that do not depend on signature bytes at all.

Beyond unforgeability: what hashing the public key buys

Strong unforgeability is a statement about one honestly generated key. Several real protocol failures have involved a different question: what an adversary can do with keys it generates itself. Cremers, Duzlu, Fiedler, Fischlin and Janson (2021) collected these under the name beyond unforgeability features. Exclusive ownership asks that nobody can produce a second public key under which an existing signature also verifies. Message-bound signatures asks that a signature cannot be valid for two different messages, even under a maliciously chosen key. Non-resignability asks that an adversary who sees a signature on an unknown message cannot produce its own signature on that same message. Their analysis of third-round post-quantum candidates found that many did not offer these properties, and that generic transformations based on hashing could add them efficiently.

FIPS 204 adopts that approach. The message representative that ML-DSA actually signs is a hash of the hash of the public key together with the formatted message, so every signature is bound to one specific key. Appendix D.2 records that the standard lengthened the public-key hash to 512 bits and the commitment hash to 384 and 512 bits for the two larger parameter sets in order to ensure these properties, and a footnote ties the length of the commitment hash to the message-bound property. RFC 9881's security considerations summarize the result: ML-DSA has exclusive ownership, message-bound signatures and non-resignability, based tightly on the collision resistance of SHAKE256.

For agent systems these properties close attacks that unforgeability leaves open. An agent registry that maps a signature to the key that made it can be confused if a second key also verifies that signature; an attacker could then claim authorship of another agent's signed output by registering a crafted key. Exclusive ownership rules that out for ML-DSA. A provenance system that stores a signature and later re-fetches the message from elsewhere relies on the signature being valid for only one message; message binding provides that. These guarantees rest on hash collision resistance rather than on the lattice bound, which is a reason to treat them as robust, and a reason not to strip the public-key hash out of the signing input when integrating ML-DSA into custom protocols.

Logs, tokens and ledgers: designing for byte-exact identity

The design rule that follows is simple to state and easy to violate: verify signatures strictly, but never use them as identifiers. Identity belongs to the signed payload, and the payload should carry an explicit identifier that the signer chose, such as a request nonce, a monotonic sequence number or an idempotency key, together with the audience and an expiry. The signature then proves that the identifier and everything around it came from the key holder. Two signatures over the same payload are, correctly, one request.

For an agent tool-call gateway this means four steps in order. Decode the transport encoding strictly and reject non-canonical forms. Verify the ML-DSA signature with a library that enforces exact lengths and the hint decoding rules. Parse the payload into a canonical form. Only then consult the replay cache, keyed on the payload's identifier and audience rather than on any bytes of the signature or of the encoded token. Retries by an honest agent then collapse to one execution, and an attacker who re-encodes a captured request gains nothing.

Audit logs that must be tamper-evident can and should store signatures, but should chain and deduplicate entries by a hash of the canonical payload. If a log also wants to prove which signature was presented, it can record the signature alongside, while treating it as evidence rather than as the entry's name. Ledgers face the strongest version of the problem because identifiers are referenced by later records; the elliptic-curve history shows that removing signatures from the identifier, as segregated witness did, is more robust than relying on any single verification rule, and that lesson carries over unchanged to ML-DSA-signed ledgers even though ML-DSA itself is designed to be strongly unforgeable.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

setup: generate a test key pair; sign a canary message 'uniqueness-canary-001'
assert verify(pk, msg, sig) == true

mutations = [
  permute_two_hint_positions_within_one_polynomial(sig),
  set_one_unused_hint_position_byte_nonzero(sig),
  make_hint_running_count_decrease(sig),
  append_one_byte(sig),
  truncate_one_byte(sig),
]
for m in mutations:
  if m is not None:
    assert verify(pk, msg, m) == false   # any acceptance = encoding malleability

text = base64url(sig)
assert decoder_rejects(set_nonzero_pad_bits(text))  # transport layer
report: count of accepted mutations (must be zero)

signed_tool_calls:
  algorithm: ML-DSA-65
  verification: strict          # exact lengths, hint rules, canonical base64url
  payload_required_fields: [request_id, audience, issued_at, expires_at]
  replay_cache:
    key: [audience, request_id]  # never the signature or the encoded token
    ttl: until_expires_at
  duplicate_request_id: return_original_result
  log_entry_id: hash(canonical_payload)
  signature_stored_as: evidence  # not as the entry's identifier

Glossary

EUF-CMA

Existential unforgeability under chosen-message attack: an adversary with a signing oracle cannot produce a valid signature on any message it never queried.

SUF-CMA

Strong unforgeability under chosen-message attack: the adversary cannot produce any valid message-signature pair that the signing oracle did not output, including a new signature on a queried message.

Signature malleability

The ability to transform a valid signature into a different valid signature on the same message without the private key.

Hint (ML-DSA)

A sparse binary vector in the signature that lets the verifier correct carries caused by the dropped low-order bits of the public key.

Commitment hash

The short hash in an ML-DSA signature of the signer's rounded commitment and the message representative, from which the challenge is derived.

Exclusive ownership

The property that no one can produce a different public key under which an existing signature also verifies.

Message-bound signature

The property that a signature cannot verify for two different messages, even under a maliciously generated key.

Non-resignability

The property that seeing a signature on an unknown message does not let an adversary produce its own signature on that message.

Canonical encoding

An encoding rule under which each value has exactly one valid representation, so equal values always have equal bytes.

References

1. NIST FIPS 204, Module-Lattice-Based Digital Signature Standard (2024), Sections 3.1, 3.6.2, Algorithm 21 and Appendix D
2. Ducas et al., CRYSTALS-Dilithium Algorithm Specifications and Supporting Documentation, Version 3.1 (2021), Section 6
3. Cremers, Duzlu, Fiedler, Fischlin and Janson, BUFFing Signature Schemes Beyond Unforgeability and the Case of Post-Quantum Signatures (IEEE S&P 2021), IACR ePrint 2020/1525
4. RFC 9881, Algorithm Identifiers for ML-DSA in the Internet X.509 PKI (2025), Security Considerations
5. Ounsworth et al., Composite ML-DSA for use in X.509 PKI, draft-ietf-lamps-pq-composite-sigs, Section 9.2
6. RFC 4648, The Base16, Base32, and Base64 Data Encodings, Section 3.5 Canonical Encoding
7. RFC 8032, Edwards-Curve Digital Signature Algorithm (EdDSA)
8. Lau and Wuille, BIP 146: Dealing with Signature Encoding Malleability (2016)