Skip to main content

All weeks · Worksheet · Overview

Week 15 · Lecture slides

Week 15

Contents17 sections

Post-Quantum Cryptography (Lamport one-time signatures, key reuse)

Security & Cryptography · Nutthakorn Chalaemwongwan

Today

  • The quantum threat: Shor vs. Grover
  • Harvest now, decrypt later
  • The four PQC families + NIST's ML-KEM / ML-DSA
  • Hash-based signatures: Lamport OTS — and its one-time-only rule
  • 🔓 Signature game: Forge the Admin Signature (key reuse → private-key recovery)

Recap — Week 14

  • Authentication proved who you're talking to (passwords, MFA, sessions)
  • A signature proves what was said and that it wasn't tampered with — integrity + non-repudiation
  • This week: the primitive behind signatures is itself under threat — from quantum computers

Why quantum breaks (some) crypto

  • Shor's algorithm — solves factoring / discrete log efficiently → breaks RSA and ECC outright
  • Grover's algorithm — quadratic speedup on search → only halves symmetric/hash security
  • Grover's mitigation: double the key/output length (AES-256 stays ~AES-128-strength — still fine)

Harvest now, decrypt later

  • Adversary records ciphertext today, decrypts it once a quantum computer exists
  • Makes PQC migration urgent now — even though no large quantum computer exists yet
  • Real today for anything with a long confidentiality lifetime: health records, state secrets, long-lived credentials

The four PQC families

  • Lattice-based — NIST's ML-KEM (Kyber, a KEM) and ML-DSA (Dilithium, a signature)
  • Hash-based — Lamport, SPHINCS+, XMSS ← this week
  • Code-based
  • Multivariate
  • NIST standards (2024): FIPS 203 (ML-KEM) · FIPS 204 (ML-DSA) · FIPS 205 (SLH-DSA / SPHINCS+)

Lamport one-time signatures — the construction

  • Private key: two random preimages per message bit — sk[i] = (a_i, b_i)
  • Public key: hashes of both — pk[i] = (H(a_i), H(b_i))
  • To sign bit i: reveal a_i if that bit is 0, b_i if it's 1
  • Security rests on one assumption — hash preimage resistance. No exotic math, quantum-resistant

What one signature reveals

  • Signing message M reveals exactly one preimage per bit — the one matching M's bit value
  • The other preimage for each bit position stays secret
  • Lab check (bit 0, message 0x00000000): SHA256(sig[0]) == pk[0][0], but SHA256(sig[0]) != pk[0][1]
  • One signature ⇒ attacker learns half the private key — never enough to forge a different message

The break: sign twice and the key falls out

  • Sign M = 0x00000000 and its bitwise complement ~M = 0xFFFFFFFF
  • They differ in every bit → together the two signatures reveal both preimages, every position
  • That is the complete private key — no brute force, just algebra
  • CWE-323 — Reusing a Nonce/Key Pair in Encryption (the vulnerable app's exact flaw)

Worked example: forging the admin signature

# vulnerable_app.py — ONE Lamport keypair reused on every /sign call
sig0 = sign(0x00000000)   # reveals the "bit=0" preimage for every position
sig1 = sign(0xFFFFFFFF)   # reveals the "bit=1" preimage for every position
# assemble ANY message OFFLINE now -- including 0xA5A5C3C3, the admin message
forged = [sig0[i] if bit(admin_msg, i) == 0 else sig1[i] for i in range(32)]
# POST /admin {forged}  ->  {"flag": FLAG_PQC}

The fix — operational, not mathematical

  • fixed_app.py: the key signs at most once; any 2nd /sign call → 403
  • No new math, no bigger keys — just refuse reuse
  • Rule is "one signature, period" — not "one distinct message" (a 2nd request for the same message is refused too)
  • A client retrying a dropped response must cache the first signature, never re-sign
  • CWE-347 — Improper Verification of Cryptographic Signature (the class this closes)

Scaling past "one signature ever"

  • Stateful (XMSS, LMS) — a tree of one-time keys; must track which leaf was used — lose the state, reuse a key, break everything
  • Stateless (SPHINCS+ / SLH-DSA, FIPS 205) — huge tree + pseudorandom key selection; reuse becomes cryptographically negligible, no state to lose
  • Real deployed hash-based schemes are Lamport's exact discipline, engineered around

🔓 Signature game — Forge the Admin Signature

  • Two identical Flask targets, same Lamport scheme: :8100 reuses its key, :8101 allows only one signature
  • POST /sign two messages → recover the private key → forge 0xA5A5C3C3 → POST /admin → flag
  • Win condition: flag captured on :8100 and the identical attack correctly defeated on :8101
docker compose up -d
python exploit.py   # PASS on :8100 (flag captured), PASS on :8101 (attack defeated)

Crypto-agility — the real engineering lesson

  • Algorithms keep changing (MD5→SHA-2, RSA→PQC) — systems must swap primitives without a rewrite
  • Practical pattern: hybrid classical + ML-KEM channels (see companion hndl/ lab) — safe even if one side is later broken
  • The Lamport lesson generalizes: correct usage discipline matters as much as the underlying math

Lab today

📋 Worksheet 15 — labs/week15-pqc/worksheet.md (Part 2 written + Part 3 hands-on) · kickoff: docker compose up -d

  • Recover the Lamport private key from two signatures, forge the admin signature, capture the flag
  • Confirm one-time enforcement defeats the identical attack on :8101
  • + Audit the AI (a hashing-first Lamport signer that still reuses its key) + EiPE / Prompt Problem

Key takeaways

  • Shor breaks RSA/ECC outright; Grover only dents AES/SHA — mitigated by longer keys
  • Hash-based signatures are textbook-secure on one assumption — if used strictly one-time
  • Real-system failure: reuse the key once and the entire private key falls out — no math needed
  • The fix is a usage rule, not a bigger algorithm — "textbook-secure primitive, real-system failure"

Questions?

Next week: Capstone studio — composing the term into CryptoVault

All weeks in Security & Cryptography