Week 11

Digital Signatures & Zero-Knowledge Proofs (ECDSA Signature Malleability)

Security & Cryptography · Nutthakorn Chalaemwongwan

Today

• Signatures vs. MACs; a signature as a non-interactive ZKP
• RSA vs. ECDSA vs. EdDSA — sound math, fragile implementations
• ECDSA signature malleability: (r, s) has a valid twin (r, n−s)
• The fix: low-S / BIP-62 normalization
• 🔓 Game: Double-Spend the Bank

Recap — Week 10

• Asymmetric crypto (RSA/ECC) solves key-distribution — but is slow
• Hybrid encryption: use asymmetric to wrap a fast symmetric key (KEM/DEM)
• Same spine as always: textbook-sound primitive, real systems still misuse it

Signatures vs. MACs

Why this matters for PKI: a signature lets a stranger who never met you verify your claim — a MAC can't, because verifying it requires the same secret that created it.

A signature is a zero-knowledge proof

Schnorr identification protocol — Peggy proves she knows secret x (her private key) without revealing it:

1. Peggy sends a commitment (a random value derived from a fresh secret)
2. Victor sends a random challenge
3. Peggy answers with a response that only the holder of x could compute correctly

Victor is convinced Peggy knows x — but learns nothing about x itself, and a recorded transcript is useless to replay (next time the challenge is different).

Fiat–Shamir: turning the proof into a signature

• Problem: Schnorr needs Victor live, sending a fresh challenge
• Fiat–Shamir trick: replace Victor's random challenge with hash(commitment, message)
• Now Peggy can compute the whole proof alone, offline, and attach it to a message

Result: a digital signature is a non-interactive zero-knowledge proof of knowledge of the private key. EdDSA (Ed25519) is literally this — a Fiat–Shamir transform of Schnorr. ECDSA (DSA family) is also a NIZK proof of knowledge of the private key, but not a literal Fiat–Shamir/Schnorr construction (its hash covers only the message, not the commitment).

RSA vs. ECDSA vs. EdDSA

Why EdDSA is recommended today: it removes the human/implementation decision points (k generation, encoding) that make RSA and ECDSA go wrong in practice.

Inside an ECDSA signature

• Signer picks a fresh random nonce k, computes point R = k·G, and lets r = R.x mod n
• Computes s = k⁻¹ (hash(msg) + r·privkey) mod n
• Signature = the pair (r, s); n = the curve's group order (SECP256k1 here)
• Verification checks an equation built from r, s, the message hash, and the public key

This math is textbook-sound: nobody can forge (r, s) without the private key. But nothing here says (r, s) is the only valid pair for this message.

The break: signature malleability

Every valid ECDSA signature (r, s) has a valid twin (r, n − s) — same message, same key, verifies True, but different bytes.

• CWE-347 — Improper Verification of Cryptographic Signature
• CWE-345 — Insufficient Verification of Data Authenticity
• Textbook-secure primitive: unforgeable. Real-system failure: not unique.

n = ecdsa.SECP256k1.order
s_twin = n - s      # a second, different, still-valid signature

Where it bites: dedup by signature hash

A bank authorizes one withdrawal, signed with ECDSA. To stop double-processing, it computes a transaction id from the signature:

txid = sha256(str(r) + str(s))          # vulnerable_app.py
if txid in seen: reject()
seen.add(txid); process(withdrawal)

(r, s) and (r, n−s) are the same authorization mathematically — but hash to two different txids. Submit both → the bank processes it twice.

Case study: MtGox

• 2014: the largest Bitcoin exchange at the time collapsed, citing ~850,000 BTC "missing"
• Part of the claimed mechanism: attackers mutated transaction signatures so a transaction's id changed, making it look like a withdrawal hadn't gone through
• Exchange software that tracked transactions by a malleable id reissued/duplicated payouts
• Bitcoin's own response: BIP-62 / BIP-146 — standardize a single canonical (low-S) signature per transaction

SUF-CMA vs. EUF-CMA

• EUF-CMA (existential unforgeability): attacker cannot produce a valid signature on any new message. ECDSA satisfies this.
• SUF-CMA (strong unforgeability): attacker cannot produce any new valid signature either — not even a different encoding of an already-signed message.
• Malleability is exactly an EUF-CMA-safe, SUF-CMA-violating scheme: same message, new valid signature bytes.

Lesson: if your system's security depends on signatures being unique, you need SUF-CMA — EUF-CMA alone is not enough.

The fix: low-S / BIP-62

fixed_app.py adds one check before dedup:

def is_low_s(s, n):
    return s <= n // 2

if not is_low_s(sig_s, n):
    return 403  # "non-canonical signature: s must be <= n/2"
# ...only now compute txid and dedup

Exactly one of {s, n−s} is ≤ n/2 — reject the other. Now there is one canonical signature per (message, key), so the twin has nowhere to hide.

🔓 Game — Double-Spend the Bank

Two identical Flask banks, one rule apart:

1. GET /sign → a valid (r, s) for "withdraw 100 to attacker"
2. POST /withdraw with (r, s) → processed, total=100
3. Compute the twin (r, n−s) → POST again → processed again, total=200 → flag on :8102
4. Same sequence on :8103 → first accepted, twin 403 → no flag (PASS = not both-rejected)

Lab today — Worksheet 11

📋 Worksheet 11 — labs/week11-signatures-zkp/worksheet.md · kickoff: docker compose up -d

• Part 1 (essays): signatures vs. MACs, Schnorr/Fiat–Shamir as ZKP, RSA/ECDSA/EdDSA, substitution attacks, malleability + MtGox + SUF-CMA
• Part 2 (lab): capture the flag on :8102, confirm the 403 rejection on :8103
• 🤖 Audit the AI: critique a plausible-looking process() that dedups by signature hash — same bug, live in front of you
• 🧠 EiPE + Prompt Problem: explain ZKP in plain English; probe an AI on why ECDSA is malleable and EdDSA isn't

Key takeaways

• ECDSA's math is sound — unforgeable (EUF-CMA) — but not unique (not SUF-CMA)
• Textbook-secure primitive, real-system failure: the bug was trusting sha256(r,s) as an identity, not the signature check itself
• The fix is a canonicalization rule (low-S/BIP-62), not "verify harder"

Questions?

Next week: (see course roadmap)