Signature Malleability — a valid (r,s) becomes another valid (r,s) without the key

A scheme is malleable when a valid signature (r,s) on a message can be transformed into a *different* valid signature (r,s') on the *same* message, without the private key — dangerous whenever the signature itself is used as an identity (transaction ID, replay-dedup key, blocklist entry).

The signal that gives it away

- The challenge treats a signature as a unique ID: a dedup/replay check keyed on the raw (r,s) pair, a "you can't resubmit the same signature" rule, or a blocklist of forbidden signatures rather than forbidden messages. - The verifier accepts "any signature that verifies" for a fixed message, and the win condition is producing a second, different valid signature — not recovering the key. - Verification code that checks (r,s) mathematically valid but never canonicalizes s (no s <= n/2 check) or that parses signatures with a lax/manual ASN.1 decoder instead of a strict DER parser. - For RSA "signatures" specifically, the same *category* of bug (a valid signature turns into another valid one) comes from the multiplicative homomorphism of RSA, not from an s-flip — see RSA Signature Forgery — homomorphic combination and lax padding checks forge signatures without the private key. Malleability is about producing a *new* valid signature; it does not by itself recover the private key.

Core algebraic trick (ECDSA/DSA)

in the signing equation, r is derived from R.x (the x-coordinate of k*G), which is sign-independent, while s is linear in the nonce k and flips sign with it. Concretely, if (r,s) verifies, then (r, n-s) verifies too, for the same message and same public key:

``python def malleate_ecdsa(r, s, n): return (r, (n - s) % n) # both (r,s) and (r,n-s) verify for the same message/pubkey ``

Operational steps: 1. Confirm the target checks equality/membership on the raw (r,s) tuple (or its serialization) rather than re-deriving from the message + pubkey each time. 2. Take any valid (r,s) you can obtain (your own signing request, or one observed on the wire) and compute (r, n-s). 3. Submit the flipped signature where the original is now rejected (already "used", already in a blocklist, etc.) — it verifies against the same message and key, so the check that treats signatures as unique IDs is bypassed. 4. If the target enforces canonical low-S (s <= n/2, reject otherwise), the pure algebraic flip is closed — pivot to encoding-level malleability instead: many verifiers use lax ASN.1/DER parsers that accept non-canonical re-encodings of the *same* mathematical (r,s) — extra leading zero bytes, alternate BER length encodings, superfluous padding outside the DER structure — producing a byte-different signature blob that still verifies. Real-world precedent: this exact gap forced Bitcoin's BIP-62 (mandate low-S) and is documented as a recurring issue in ECDSA libraries with permissive DER decoders (e.g. indutny/elliptic issue #226). 5. Distinguish "which variant applies" before choosing tooling: if the dedup check compares the decoded (r,s) integers, only the n-s flip helps; if it compares the raw bytes/serialization, encoding-level re-padding also works and is strictly weaker to defend against (it requires strict canonical-encoding enforcement, not just a low-S check).

What does NOT work

- Trying the n-s flip after the target already enforces low-S (s <= n/2, replacing s with n-s at signing time whenever it lands high) — this closes the algebraic malleability completely; wasting time re-deriving flipped signatures here is a dead end, go straight to encoding-level tricks or abandon the malleability angle. - Confusing malleability with key recovery: flipping s never yields the private key or lets you sign an *arbitrary new message* — it only produces a second valid signature for the SAME message you already had a valid signature for. If the goal is forging a signature on a message you were never given a valid signature for, this is the wrong technique (look at ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra or RSA Signature Forgery — homomorphic combination and lax padding checks forge signatures without the private key instead). - Assuming malleability applies to RSA the same way: RSA has no s ↔ n-s symmetry from a nonce, because there is no per-signature nonce in textbook RSA signing. RSA's analogous weakness is multiplicative: sig(m1)*sig(m2) = sig(m1*m2), a different mechanism entirely — see RSA Signature Forgery — homomorphic combination and lax padding checks forge signatures without the private key. - Treating a strict DER-only, s-canonicalized verifier as still vulnerable — once both checks are in place (canonical low-S encoding + strict DER decoding, no BER/alternate-length tolerance), the malleability class documented here is closed and the challenge is asking for something else.

Related

ECDSA Fundamentals — the s*k = h + d*r identity that routes every nonce attack DSA Fundamentals — the linear signing equation every DSA attack exploits RSA Signature Forgery — homomorphic combination and lax padding checks forge signatures without the private key ECDSA/DSA Nonce Reuse — identical r collapses the private key to closed-form algebra Cryptanalysis Methodology — classify the family before you reach for an attack RSA Blinding Attack — bypass a signing/decryption oracle's blocklist with the multiplicative homomorphism