{ "cells": [ { "cell_type": "markdown", "id": "ch47-000", "metadata": {}, "source": [ "# Chapter 47: Hash-Based Signatures — From Lamport to SLH-DSA\n" ] }, { "cell_type": "markdown", "id": "ch47-001", "metadata": {}, "source": [ "## 47.1 Why Hash-Based Signatures Are Special\n", "\n", "Every other public-key signature scheme — RSA, DSA, ECDSA, Ed25519, ML-DSA,\n", "Falcon, multivariate, isogeny — rests on an *algebraic* hardness assumption:\n", "factoring, discrete logarithm, Module-LWE, MQ, isogeny walks. These assumptions\n", "are *believed* hard, but their hardness is not proven, and a single mathematical\n", "breakthrough could collapse them.\n", "\n", "Hash-based signatures rest on a much weaker assumption:\n", "\n", "```{admonition} The hash-based security premise\n", ":class: important\n", "The hash function $H \\colon \\{0,1\\}^* \\to \\{0,1\\}^n$ is **collision-resistant**\n", "(no adversary can find $x \\ne y$ with $H(x) = H(y)$ within their resource\n", "budget) and, for some constructions, **second-preimage resistant** (given $x$,\n", "no adversary can find $y \\ne x$ with $H(x) = H(y)$).\n", "```\n", "\n", "That is it. No number theory. No algebra. If SHA-256 (or SHA-3, or SHAKE)\n", "remains second-preimage resistant against your adversary, then your\n", "hash-based signature is secure against that adversary — period. This makes\n", "hash-based signatures the **most conservatively-secure post-quantum primitive\n", "we have**. They were the first PQC scheme NIST standardised (SLH-DSA, FIPS 205,\n", "2024) precisely because the security argument is as close to bullet-proof as\n", "cryptography allows.\n", "\n", "The price is **size**. SLH-DSA signatures are 8–50 KB (compare to Ed25519's 64\n", "bytes, or ML-DSA's 2.5–4.6 KB). For long-term signatures on rare events\n", "(software releases, root-of-trust certificates, code-signing keys), this is\n", "acceptable. For high-volume protocols (TLS), it is generally not, and ML-DSA\n", "is preferred.\n", "\n", "This chapter builds hash-based signatures from the ground up: from the\n", "**Lamport one-time signature** (1979) → **Winternitz OTS** (signature size\n", "trade-off) → **Merkle trees** (one key, many signatures) → **stateful XMSS/LMS**\n", "(Internet RFCs) → **stateless SPHINCS+** (FIPS 205).\n" ] }, { "cell_type": "markdown", "id": "ch47-002", "metadata": {}, "source": [ "## 47.2 Lamport One-Time Signatures (1979)\n", "\n", "```{admonition} Lamport OTS\n", ":class: important\n", "Let $H \\colon \\{0,1\\}^* \\to \\{0,1\\}^n$ be a one-way hash function.\n", "\n", "**Key generation.** Pick $2n$ random secret strings\n", "$s_{i,b} \\in \\{0,1\\}^n$ for $i = 0, \\ldots, n-1$ and $b \\in \\{0,1\\}$.\n", "The **secret key** is the array $\\{s_{i,b}\\}_{i, b}$. The **public key** is\n", "$\\{H(s_{i,b})\\}_{i, b}$ — also $2n$ values, each $n$ bits.\n", "\n", "**Signing** a message $m$. Compute $h = H(m) = h_0 h_1 \\ldots h_{n-1}$. The\n", "signature is $\\sigma = (s_{0, h_0}, s_{1, h_1}, \\ldots, s_{n-1, h_{n-1}})$ —\n", "*one* secret string per bit of the message hash.\n", "\n", "**Verification.** Given $\\sigma = (\\sigma_0, \\ldots, \\sigma_{n-1})$ and message\n", "$m$, compute $h = H(m)$ and check that $H(\\sigma_i) = \\mathrm{pk}_{i, h_i}$ for\n", "every $i$.\n", "```\n", "\n", "Two properties stand out:\n", "\n", "- **One-time only.** Each signature reveals $n$ secret strings, one per bit\n", " of the message hash. After two signatures of *different* messages, the\n", " attacker knows on average $1.5n$ of the $2n$ secret strings: at the $\\approx n/2$\n", " positions where the two hashes differ, *both* secrets are revealed; at the\n", " remaining positions only *one*. Each bit of a freshly chosen target hash\n", " then lands on a known secret with probability $\\approx 3/4$ — but a valid\n", " forgery requires *every* one of the $n$ bits to land on a known secret, so\n", " the brute-force forger must search for a target hash whose every position\n", " is \"covered\" (Exercise 47.E5 in the practical sheet).\n", "- **Quantum security.** Both the security argument (one-wayness of $H$) and\n", " the Grover-quantum attack against second-preimages are well-understood. To\n", " reach 128 quantum-bits of security against Grover, take $n \\ge 256$.\n", "\n", "For the rest of the chapter, set $n = 256$ bits ($= 32$ bytes) and use SHA-256.\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "ch47-003", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:14.405283Z", "iopub.status.busy": "2026-05-12T08:46:14.405183Z", "iopub.status.idle": "2026-05-12T08:46:14.412213Z", "shell.execute_reply": "2026-05-12T08:46:14.411757Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Signature length : 256 strings of 32 bytes = 8192 bytes total\n", "Verifies : True\n", "Verifies (tamper): False\n" ] } ], "source": [ "import hashlib, os\n", "from typing import Tuple, List\n", "\n", "N = 32 # 256-bit security level (quantum-128)\n", "\n", "def H(x: bytes) -> bytes:\n", " return hashlib.sha256(x).digest()\n", "\n", "def lamport_keygen() -> Tuple[List[List[bytes]], List[List[bytes]]]:\n", " '''Return (sk, pk). Each is a list of 256 pairs of N-byte strings.'''\n", " sk = [[os.urandom(N), os.urandom(N)] for _ in range(8 * N)]\n", " pk = [[H(sk_i_b) for sk_i_b in pair] for pair in sk]\n", " return sk, pk\n", "\n", "def bits(x: bytes) -> List[int]:\n", " out = []\n", " for byte in x:\n", " for j in range(8):\n", " out.append((byte >> (7 - j)) & 1)\n", " return out\n", "\n", "def lamport_sign(sk, message: bytes) -> List[bytes]:\n", " h = H(message)\n", " return [sk[i][b] for i, b in enumerate(bits(h))]\n", "\n", "def lamport_verify(pk, message: bytes, sig: List[bytes]) -> bool:\n", " h = H(message)\n", " for i, b in enumerate(bits(h)):\n", " if H(sig[i]) != pk[i][b]:\n", " return False\n", " return True\n", "\n", "\n", "sk, pk = lamport_keygen()\n", "msg = b'Lamport-attacks-can-be-fixed-by-Merkle'\n", "sig = lamport_sign(sk, msg)\n", "print('Signature length :', len(sig), 'strings of', N, 'bytes =',\n", " len(sig) * N, 'bytes total')\n", "print('Verifies :', lamport_verify(pk, msg, sig))\n", "print('Verifies (tamper):', lamport_verify(pk, msg + b'.', sig))\n" ] }, { "cell_type": "markdown", "id": "ch47-004", "metadata": {}, "source": [ "## 47.3 Winternitz One-Time Signatures (WOTS+)\n", "\n", "Lamport signatures are large: $\\tfrac{n^2}{4}$ bytes of public key plus\n", "$\\tfrac{n^2}{8}$ bytes of signature for an $n$-bit hash. For $n = 256$ that\n", "is 16 KB of public key and 8 KB of signature *per signature*.\n", "\n", "The **Winternitz** construction trades signature time for size by chaining\n", "hashes. Instead of representing each *bit* of the message hash by one chain,\n", "we represent each $\\log_2(w)$-bit *digit* by one chain.\n", "\n", "```{admonition} WOTS+ at a glance\n", ":class: important\n", "We follow the FIPS 205 convention: $w$ is the **alphabet size** (typically\n", "$w = 16$, i.e. $\\log_2 w = 4$ bits per digit). Split the $n$-bit message hash\n", "into\n", "\n", "$$\\ell_1 = \\left\\lceil \\frac{n}{\\log_2 w} \\right\\rceil \\;\\;\\text{digits in}\\;\\; \\{0, \\ldots, w-1\\},$$\n", "\n", "and append $\\ell_2$ checksum digits computed so that any *increase* of a\n", "message digit forces a *decrease* of a checksum digit.\n", "\n", "For each of the $\\ell = \\ell_1 + \\ell_2$ digit positions, derive a chain\n", "$x \\to H(x) \\to H(H(x)) \\to \\cdots$ of length $w - 1$. The secret key is the\n", "$\\ell$ chain starts; the public key is the $\\ell$ chain ends.\n", "\n", "To sign digit $d_i$, publish $H^{d_i}(\\mathrm{sk}_i)$ — the chain truncated\n", "$d_i$ steps in. To verify, the verifier hashes the published value $w - 1 - d_i$\n", "further times and checks against $\\mathrm{pk}_i$.\n", "\n", "The checksum prevents an attacker from forging by *increasing* one digit\n", "(which would cost only further hashing) without triggering a *decrease*\n", "elsewhere — and decreases require inverting the chain, which is\n", "preimage-resistant.\n", "```\n", "\n", "For $n = 256$ bits and $w = 16$ we get $\\ell_1 = 64$ and $\\ell_2 = 3$, hence\n", "$\\ell = 67$. With per-chain output of $32$ bytes, the WOTS+ signature is\n", "$\\ell \\cdot 32 = 2144$ bytes ≈ **2.1 KB** (vs Lamport's 8 KB). The verifier\n", "performs up to $\\ell \\cdot (w - 1) = 67 \\cdot 15 = 1005$ hash evaluations.\n", "\n", "```{admonition} Why WOTS+, not WOTS?\n", ":class: tip\n", "The \"+\" in WOTS+ refers to a 2011 improvement by Hülsing that replaces the\n", "naive iterated-hash chain with a *masked* iteration $H_{r_i}(x) := H(x \\xor r_i)$\n", "using public per-step bitmasks $r_i$. This eliminates a multi-target attack on\n", "plain WOTS and brings the security back to $n$ bits classically (and $n/2$\n", "quantum-bits via Grover).\n", "```\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "ch47-005", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:14.413391Z", "iopub.status.busy": "2026-05-12T08:46:14.413314Z", "iopub.status.idle": "2026-05-12T08:46:14.418317Z", "shell.execute_reply": "2026-05-12T08:46:14.417927Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "WOTS parameters : w=16 (so 4 bits/digit), len = 64 + 3 = 67 chains\n", "WOTS signature size: 2144 bytes (Lamport had 2048 bytes for same hash size)\n", "WOTS verifies : True\n", "WOTS verifies tamp.: False\n" ] } ], "source": [ "# A toy WOTS implementation (without the \"+\" bitmasks; production code uses\n", "# masks per Hülsing 2013). This is enough to see the size/time trade-off.\n", "import math, struct\n", "\n", "W = 16 # Winternitz parameter\n", "WBITS = W.bit_length() - 1 # bits per digit (4 for w=16)\n", "LEN1 = (8 * N + WBITS - 1) // WBITS # digits in message hash -> 64\n", "LEN2 = (math.floor(math.log2(LEN1 * (W - 1))) // WBITS) + 1 # checksum digits\n", "LEN = LEN1 + LEN2\n", "\n", "def H_chain(x: bytes, steps: int) -> bytes:\n", " for _ in range(steps):\n", " x = H(x)\n", " return x\n", "\n", "def to_digits(msg_hash: bytes):\n", " out = []\n", " bit_buf, bits_in_buf = 0, 0\n", " for byte in msg_hash:\n", " bit_buf = (bit_buf << 8) | byte\n", " bits_in_buf += 8\n", " while bits_in_buf >= WBITS:\n", " bits_in_buf -= WBITS\n", " out.append((bit_buf >> bits_in_buf) & (W - 1))\n", " return out\n", "\n", "def base_w(msg: bytes):\n", " digits = to_digits(H(msg))[:LEN1]\n", " csum = sum(W - 1 - d for d in digits)\n", " csum_bytes = csum.to_bytes((LEN2 * WBITS + 7) // 8, 'big')\n", " digits += to_digits(csum_bytes)[:LEN2]\n", " return digits\n", "\n", "def wots_keygen():\n", " sk = [os.urandom(N) for _ in range(LEN)]\n", " pk = [H_chain(s, W - 1) for s in sk]\n", " return sk, pk\n", "\n", "def wots_sign(sk, msg):\n", " return [H_chain(sk[i], d) for i, d in enumerate(base_w(msg))]\n", "\n", "def wots_verify(pk, msg, sig):\n", " return all(H_chain(sig[i], W - 1 - d) == pk[i]\n", " for i, d in enumerate(base_w(msg)))\n", "\n", "\n", "sk_w, pk_w = wots_keygen()\n", "msg_w = b'WOTS-can-sign-once'\n", "sig_w = wots_sign(sk_w, msg_w)\n", "print(f'WOTS parameters : w={W} (so {WBITS} bits/digit), '\n", " f'len = {LEN1} + {LEN2} = {LEN} chains')\n", "print(f'WOTS signature size: {LEN * N} bytes '\n", " f'(Lamport had {2 * 8 * N * N // 8} bytes for same hash size)')\n", "print(f'WOTS verifies : {wots_verify(pk_w, msg_w, sig_w)}')\n", "print(f'WOTS verifies tamp.: {wots_verify(pk_w, msg_w + b\"x\", sig_w)}')\n" ] }, { "cell_type": "markdown", "id": "ch47-006", "metadata": {}, "source": [ "## 47.4 Merkle Trees: One Public Key, Many Signatures\n", "\n", "The Merkle one-time-signature schemes above bind one Lamport (or WOTS+) key\n", "pair to one signature. To sign $2^h$ messages with one **published** public\n", "key, **Ralph Merkle (1979)** introduced what we now call the **Merkle tree**.\n", "\n", "Generate $2^h$ independent OTS key pairs $(\\mathrm{sk}^{(j)}, \\mathrm{pk}^{(j)})$\n", "for $j = 0, \\ldots, 2^h - 1$. Compute leaf hashes\n", "$\\ell_j = H(\\mathrm{pk}^{(j)})$ and build a binary tree by hashing pairs:\n", "\n", "$$\n", "\\mathrm{node}(v) = H\\bigl(\\mathrm{node}(\\mathrm{left}(v)) \\,\\|\\, \\mathrm{node}(\\mathrm{right}(v))\\bigr).\n", "$$\n", "\n", "The **public key** is just the **root** $r$ of the tree — *one* hash, $n$ bytes.\n", "A signature on the $j$-th message consists of:\n", "\n", "- the OTS signature $\\sigma^{(j)}$ produced from $\\mathrm{sk}^{(j)}$;\n", "- the OTS public key $\\mathrm{pk}^{(j)}$;\n", "- the **authentication path** — the $h$ sibling hashes along the path from\n", " leaf $j$ to the root.\n", "\n", "To verify, recompute the leaf hash $H(\\mathrm{pk}^{(j)})$, walk up the tree\n", "combining with the authentication path, and check that the result equals the\n", "public root.\n", "\n", "```{admonition} Why this works\n", ":class: tip\n", "The security of Merkle's construction reduces to (i) the OTS being\n", "unforgeable, and (ii) the hash function being collision-resistant. No\n", "new assumptions, no new mathematics. It is the most boring and the most\n", "robust signature scheme on the planet.\n", "```\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "ch47-007", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:14.419387Z", "iopub.status.busy": "2026-05-12T08:46:14.419308Z", "iopub.status.idle": "2026-05-12T08:46:14.480223Z", "shell.execute_reply": "2026-05-12T08:46:14.479884Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Public root (32 bytes): 5c8c75ab2d33dab586b5964eba03d01076292d8f07d4a3e484150afd02e76274\n", "Sig consists of: 1 OTS sig + 1 OTS pk + h auth-path nodes; total bytes = 24672\n", "OTS verifies: True Path verifies: True\n", "\n", " h | leaves | keygen(s) | sig bytes | of which auth-path bytes\n", "---+--------+-----------+-----------+-------------------------\n", " 2 | 4 | 0.00 | 24640 | 64\n", " 4 | 16 | 0.01 | 24704 | 128\n", " 6 | 64 | 0.04 | 24768 | 192\n", "\n", "The auth-path overhead (32*h bytes) is negligible compared with the OTS\n", "payload — so once you fix the OTS, taller trees buy you many more\n", "signatures essentially for free. This is why WOTS+ replaces Lamport in\n", "XMSS / LMS / SPHINCS+: cutting OTS bytes by ~4x makes huge trees viable.\n" ] } ], "source": [ "def merkle_build(leaf_pks: List[List[List[bytes]]]) -> List[List[bytes]]:\n", " '''Build a binary Merkle tree from leaf OTS public keys. Return all levels.'''\n", " leaves = [H(b''.join(b''.join(pair) for pair in pk)) for pk in leaf_pks]\n", " levels = [leaves]\n", " cur = leaves\n", " while len(cur) > 1:\n", " nxt = []\n", " for i in range(0, len(cur), 2):\n", " nxt.append(H(cur[i] + cur[i + 1]))\n", " levels.append(nxt)\n", " cur = nxt\n", " return levels # levels[0] = leaves; levels[-1] = [root]\n", "\n", "def merkle_auth_path(levels: List[List[bytes]], j: int) -> List[bytes]:\n", " path = []\n", " for lvl in levels[:-1]:\n", " sibling_idx = j ^ 1 # flip last bit -> sibling\n", " path.append(lvl[sibling_idx])\n", " j //= 2\n", " return path\n", "\n", "def merkle_verify(root: bytes, leaf_pk_hash: bytes, j: int,\n", " path: List[bytes]) -> bool:\n", " cur = leaf_pk_hash\n", " for sib in path:\n", " if j % 2 == 0:\n", " cur = H(cur + sib)\n", " else:\n", " cur = H(sib + cur)\n", " j //= 2\n", " return cur == root\n", "\n", "\n", "# Build a height-3 Merkle MSS over 2^3 = 8 Lamport keys.\n", "H_HEIGHT = 3\n", "N_LEAVES = 1 << H_HEIGHT\n", "all_sk, all_pk = [], []\n", "for _ in range(N_LEAVES):\n", " sk_j, pk_j = lamport_keygen()\n", " all_sk.append(sk_j)\n", " all_pk.append(pk_j)\n", "\n", "levels = merkle_build(all_pk)\n", "public_root = levels[-1][0]\n", "print('Public root (32 bytes):', public_root.hex())\n", "\n", "# Sign message #5 in the tree.\n", "J = 5\n", "msg = b'Five fish in five seas.'\n", "ots_sig = lamport_sign(all_sk[J], msg)\n", "auth_path = merkle_auth_path(levels, J)\n", "print('Sig consists of: 1 OTS sig + 1 OTS pk + h auth-path nodes;',\n", " ' total bytes =', len(ots_sig) * N + sum(len(b''.join(p)) for p in all_pk[J])\n", " + len(auth_path) * N)\n", "\n", "leaf_hash = H(b''.join(b''.join(pair) for pair in all_pk[J]))\n", "ok_ots = lamport_verify(all_pk[J], msg, ots_sig)\n", "ok_path = merkle_verify(public_root, leaf_hash, J, auth_path)\n", "print('OTS verifies:', ok_ots, ' Path verifies:', ok_path)\n", "\n", "# How does signature size scale with tree height? Each Merkle MSS signature\n", "# carries (one OTS sig + one OTS pk + h auth-path nodes). The OTS payload\n", "# dominates; the auth path adds 32*h bytes for SHA-256. Measure on Lamport\n", "# (worst case) to make the trend visible.\n", "import time as _time\n", "print()\n", "print(' h | leaves | keygen(s) | sig bytes | of which auth-path bytes')\n", "print('---+--------+-----------+-----------+-------------------------')\n", "for h_test in (2, 4, 6):\n", " n_leaves = 1 << h_test\n", " t0 = _time.time()\n", " sks_t, pks_t = zip(*(lamport_keygen() for _ in range(n_leaves)))\n", " levels_t = merkle_build(list(pks_t))\n", " keygen_t = _time.time() - t0\n", " auth_path_bytes = h_test * N\n", " ots_sig_bytes = 8 * N * N # 256 secret strings * 32 bytes\n", " ots_pk_bytes = 2 * 8 * N * N\n", " sig_bytes = ots_sig_bytes + ots_pk_bytes + auth_path_bytes\n", " print(f' {h_test} | {n_leaves:6d} | {keygen_t:8.2f} | {sig_bytes:9d} | {auth_path_bytes:5d}')\n", "print()\n", "print('The auth-path overhead (32*h bytes) is negligible compared with the OTS')\n", "print(\"payload — so once you fix the OTS, taller trees buy you many more\")\n", "print('signatures essentially for free. This is why WOTS+ replaces Lamport in')\n", "print('XMSS / LMS / SPHINCS+: cutting OTS bytes by ~4x makes huge trees viable.')\n" ] }, { "cell_type": "markdown", "id": "ch47-008", "metadata": {}, "source": [ "## 47.5 XMSS and LMS — Stateful Hash-Based Standards\n", "\n", "The Merkle MSS above has one painful flaw: the signer **must remember** which\n", "leaves they have already used. Reusing a Lamport leaf reveals its secrets;\n", "reusing a WOTS+ leaf permits trivial forgery via the standard Winternitz\n", "multi-signature attack. This is the **state requirement**.\n", "\n", "In the 2010s, two stateful hash-based signature schemes were standardised:\n", "\n", "- **XMSS** — *eXtended Merkle Signature Scheme*. Buchmann, Dahmen, Hülsing\n", " (2011). Standardised in **RFC 8391** (May 2018). Uses WOTS+ leaves, masked\n", " Merkle hashing.\n", "- **LMS** — *Leighton–Micali Signatures*. Standardised in **RFC 8554**\n", " (April 2019). Uses LM-OTS (a Winternitz variant) and HSS hyper-trees for\n", " scaling.\n", "\n", "NIST recommends both in **SP 800-208** (2020) for **specific narrow use cases**\n", "where the signer can guarantee that no leaf is ever signed twice. Typical\n", "example: signing firmware releases from an HSM in a tightly-controlled\n", "deployment pipeline.\n", "\n", "```{admonition} Why state is dangerous in practice\n", ":class: warning\n", "Imagine a signer hosted in a VM. The hypervisor takes a snapshot, then later\n", "restores the VM from the snapshot. Without a hardware monotonic counter, the\n", "*restored* signer happily re-uses leaves it already used in the *original*\n", "timeline — and silently breaks the signature scheme. This is not a hypothetical:\n", "it is the reason NIST issued SP 800-208 with explicit, narrow deployment\n", "guidance, and the reason SPHINCS+ exists.\n", "```\n" ] }, { "cell_type": "markdown", "id": "ch47-009", "metadata": {}, "source": [ "## 47.6 SPHINCS+ / SLH-DSA — Going Stateless\n", "\n", "SPHINCS+ is a hash-based signature scheme that **eliminates the state\n", "requirement** at a modest cost in signature size. It is now standardised as\n", "**SLH-DSA** in **FIPS 205** (August 2024). The scheme is by Bernstein, Hülsing,\n", "Kölbl, Niederhagen, Rijneveld, and Schwabe (CCS 2019).\n", "\n", "The key idea is a **hyper-tree** of fixed height $h$ together with **few-time\n", "signatures (FORS)** at the leaves, plus a *deterministic but pseudorandom* leaf\n", "selector driven by the message itself. Concretely:\n", "\n", "1. Build a Merkle hyper-tree of total height $h$ (FIPS 205 uses\n", " $h \\in \\{63, 64, 66, 68\\}$ across its six parameter sets). Each layer of the\n", " hyper-tree has its own subtree height $h' = h / d$.\n", "2. At each subtree node, use a WOTS+ key pair to sign the root of the subtree\n", " below.\n", "3. At the leaves of the hyper-tree, place **FORS** (Forest Of Random Subsets)\n", " few-time signatures — these can sign a small number of messages without\n", " catastrophic key reuse.\n", "4. To sign a message, derive a leaf index *pseudorandomly* from the message.\n", " Sign the message hash with that leaf's FORS instance, then publish the\n", " chain of WOTS+ subtree-root signatures up to the public root.\n", "\n", "Because the leaf index is derived from the message, **two distinct messages\n", "almost certainly hit different FORS leaves**, so the few-time-signature property\n", "never fires. Even if (by birthday luck) two messages collide on the same FORS\n", "leaf, FORS is designed to remain secure for several messages per leaf.\n", "\n", "```{admonition} Parameter sets you should know\n", ":class: tip\n", "FIPS 205 names the parameter sets *SLH-DSA-{SHA2,SHAKE}-128/192/256{f,s}*,\n", "where the trailing `f` is \"fast\" (larger signatures) and `s` is \"small\"\n", "(slower). Levels 128/192/256 match NIST security categories 1/3/5,\n", "i.e. ML-KEM-512/768/1024. Sample sizes:\n", "\n", "| Parameter set | Public key | Signature |\n", "|---|---|---|\n", "| SLH-DSA-SHA2-128f (fast) | 32 B | 17 088 B (~16.7 KB) |\n", "| SLH-DSA-SHA2-128s (small)| 32 B | 7 856 B (~7.7 KB) |\n", "| SLH-DSA-SHA2-256s | 64 B | 29 792 B (~29 KB) |\n", "\n", "For the highest level, signatures push 50 KB. ML-DSA, by contrast, is 2.5–4.6 KB.\n", "```\n" ] }, { "cell_type": "markdown", "id": "ch47-010", "metadata": {}, "source": [ "## 47.7 The State-Reuse Catastrophe — Demonstrated\n", "\n", "If the signer of an XMSS / LMS instance accidentally signs *two* distinct\n", "messages with the same WOTS+ leaf, the consequences are catastrophic. Let us\n", "build the cleanest possible demonstration: a Lamport leaf signed twice on\n", "distinct messages.\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "ch47-011", "metadata": { "execution": { "iopub.execute_input": "2026-05-12T08:46:14.481398Z", "iopub.status.busy": "2026-05-12T08:46:14.481327Z", "iopub.status.idle": "2026-05-12T08:46:14.485526Z", "shell.execute_reply": "2026-05-12T08:46:14.485193Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Hash size for demo : 16 bits\n", "Differing positions : 10/16\n", "Secrets known : 26/32\n", "Forged signature for 'Send 1000 PLN to Mallory. salt=132' after 132 tries\n", "Forged sig verifies: True\n" ] } ], "source": [ "# For demonstration only, we use a truncated 16-bit hash so the forgery search\n", "# completes in seconds. With a real 256-bit hash, the attacker still acquires the\n", "# same fraction of secrets, but locating a third message whose hash lands only on\n", "# already-known positions becomes a hash-preimage problem (chosen-prefix\n", "# collisions or NIST hash-inversion records). The vulnerability is identical\n", "# in shape; only the brute-force budget changes.\n", "\n", "DEMO_HASH_BITS = 16\n", "\n", "def H_demo(x: bytes) -> bytes:\n", " return hashlib.sha256(x).digest()[: DEMO_HASH_BITS // 8]\n", "\n", "def lamport_keygen_demo():\n", " sk = [[os.urandom(N), os.urandom(N)] for _ in range(DEMO_HASH_BITS)]\n", " pk = [[H(s) for s in pair] for pair in sk]\n", " return sk, pk\n", "\n", "def bits_demo(x: bytes):\n", " out = []\n", " for byte in x:\n", " for j in range(8):\n", " out.append((byte >> (7 - j)) & 1)\n", " return out\n", "\n", "def lamport_sign_demo(sk, message):\n", " return [sk[i][b] for i, b in enumerate(bits_demo(H_demo(message)))]\n", "\n", "def lamport_verify_demo(pk, message, sig):\n", " return all(H(sig[i]) == pk[i][b]\n", " for i, b in enumerate(bits_demo(H_demo(message))))\n", "\n", "\n", "sk_leaf, pk_leaf = lamport_keygen_demo()\n", "msg1 = b'Send 100 PLN to Alice.'\n", "msg2 = b'Send 999 PLN to Bob.'\n", "\n", "sig1 = lamport_sign_demo(sk_leaf, msg1)\n", "sig2 = lamport_sign_demo(sk_leaf, msg2)\n", "assert lamport_verify_demo(pk_leaf, msg1, sig1)\n", "assert lamport_verify_demo(pk_leaf, msg2, sig2)\n", "\n", "# Attacker observes both (msg, sig) pairs. The two signatures together reveal\n", "# sk[i][h1[i]] AND sk[i][h2[i]] at every position i. At positions where\n", "# h1[i] != h2[i] the attacker now knows BOTH secrets at that position.\n", "h1 = bits_demo(H_demo(msg1))\n", "h2 = bits_demo(H_demo(msg2))\n", "known = {}\n", "for i, (b1, b2) in enumerate(zip(h1, h2)):\n", " known[(i, b1)] = sig1[i]\n", " known[(i, b2)] = sig2[i]\n", "\n", "print(f'Hash size for demo : {DEMO_HASH_BITS} bits')\n", "print(f'Differing positions : {sum(a != b for a, b in zip(h1, h2))}/{DEMO_HASH_BITS}')\n", "print(f'Secrets known : {len(known)}/{2 * DEMO_HASH_BITS}')\n", "\n", "def forge(msg, known):\n", " h = bits_demo(H_demo(msg))\n", " out = []\n", " for i, b in enumerate(h):\n", " if (i, b) not in known:\n", " return None\n", " out.append(known[(i, b)])\n", " return out\n", "\n", "# Brute force a third message whose hash lands entirely on known positions.\n", "for trial in range(200_000):\n", " msg3 = f'Send 1000 PLN to Mallory. salt={trial}'.encode()\n", " forged = forge(msg3, known)\n", " if forged is not None:\n", " print(f'Forged signature for {msg3.decode()!r} after {trial:,} tries')\n", " print('Forged sig verifies:', lamport_verify_demo(pk_leaf, msg3, forged))\n", " break\n", "else:\n", " print('No forgeable message found — try again or grow the budget.')\n" ] }, { "cell_type": "markdown", "id": "ch47-012", "metadata": {}, "source": [ "When you run the cell above, the attacker should land a forgery within a few\n", "thousand random trials (the success probability per trial is roughly\n", "$(3/4)^{16} \\approx 1\\%$ — when half of the hash positions differ between the\n", "two signed messages, the attacker has both secrets at those positions and one\n", "secret at the rest).\n", "\n", "Scale the same logic to the real 256-bit hash and the per-trial probability\n", "falls to $(3/4)^{256} \\approx 2^{-106}$. So in production the attacker cannot\n", "brute-force *random* third messages — they need to **invert the hash function\n", "onto a chosen target set of bit positions**, which is the hash-preimage problem.\n", "Whether or not that is feasible depends on the hash function and the target,\n", "but the point stands: **two signatures from the same Lamport leaf irrevocably\n", "weaken the scheme**, and the consequences range from \"near-total compromise\"\n", "(weak hash) to \"tractable preimage attack\" (real hash). SPHINCS+/SLH-DSA\n", "exists specifically to remove this failure mode.\n" ] }, { "cell_type": "markdown", "id": "ch47-013", "metadata": {}, "source": [ "## 47.8 Exercises\n", "\n", "---\n", "\n", "**Exercise 47.1 — WOTS+ from scratch.**\n", "\n", "Implement WOTS+ for $n = 32$, $w = 16$. Verify that key generation, signing,\n", "and verification work for a 256-bit message hash. Measure the actual signature\n", "size in bytes and compare with the prediction $\\ell \\cdot n$ where\n", "$\\ell = \\ell_1 + \\ell_2$ is computed from $w$.\n", "\n", "---\n", "\n", "**Exercise 47.2 — Merkle tree timing.**\n", "\n", "Build Merkle trees of height $h = 4, 8, 12, 16$ over WOTS+ leaves. For each,\n", "measure (a) the keygen time, (b) the per-signature time, (c) the verifier\n", "time, and (d) the public-key and signature byte-counts. Plot $h$ vs each\n", "metric on a log–log axis.\n", "\n", "---\n", "\n", "**Exercise 47.3 — FORS sketch.**\n", "\n", "A FORS instance for $k$-out-of-$2^t$ leaves works as follows: split the message\n", "hash into $k$ chunks of $t$ bits; for each chunk $i$, publish the leaf at index\n", "$\\mathrm{chunk}_i$ in the $i$-th of $k$ Merkle trees of height $t$, together\n", "with its authentication path. Implement FORS for $k = 14$, $t = 12$ and verify\n", "that two distinct messages hash to *almost-never* the same leaf set.\n", "\n", "---\n", "\n", "**Exercise 47.4 — Reproduce the catastrophe at scale.**\n", "\n", "Modify the demonstration in §47.7 so that the attacker, given $r$ signatures\n", "under one leaf, computes the *expected* fraction of forgeable messages\n", "(closed form). Plot this fraction as a function of $r$ for $r = 2, 3, \\ldots, 8$.\n", "\n", "---\n", "\n", "**Exercise 47.5 (project candidate) — SLH-DSA reference.**\n", "\n", "Pick the SLH-DSA-SHA2-128s parameter set. Read FIPS 205 Algorithm 17 (`slh_sign`)\n", "and Algorithm 18 (`slh_verify`). Using only `hashlib` and the WOTS+, FORS, and\n", "Merkle tree primitives you built in earlier exercises, implement the full\n", "SLH-DSA signing and verification. Verify on a sample message. Compare the\n", "signature size you obtain with the FIPS 205 specification (7 856 bytes).\n" ] }, { "cell_type": "markdown", "id": "ch47-014", "metadata": {}, "source": [ "## 47.9 Summary\n", "\n", "1. Hash-based signatures are the most conservatively-secure post-quantum\n", " signature primitive — their security reduces to one-wayness and\n", " collision-resistance of a hash function, no algebra required.\n", "2. Lamport (1979) is the simplest one-time signature: 2 secret strings per\n", " message-hash bit, signing reveals one of each pair.\n", "3. Winternitz / WOTS+ trades signing time for signature size by chaining\n", " hashes; reduces signature size by ~4× at $w = 16$.\n", "4. Merkle trees (1979) bind $2^h$ OTS keys to a single $n$-byte public root,\n", " at the cost of authentication-path overhead.\n", "5. XMSS (RFC 8391) and LMS (RFC 8554) standardise stateful hash-based\n", " signatures for narrow deployments where state can be guaranteed.\n", "6. SPHINCS+ / SLH-DSA (FIPS 205) eliminates state via FORS leaves and a\n", " pseudorandom leaf selector, at the cost of 8–50 KB signatures.\n", "7. The state-reuse catastrophe demonstrates *why* statelessness matters in\n", " practice, and *why* FIPS 205 was the first NIST PQC signature standard\n", " to publish.\n" ] }, { "cell_type": "markdown", "id": "ch47-015", "metadata": {}, "source": [ "## 47.10 References\n", "\n", "1. **Lamport, L.** (1979). *Constructing Digital Signatures from a One-Way\n", " Function.* SRI Technical Report CSL-98.\n", "2. **Merkle, R. C.** (1979). *Secrecy, Authentication and Public Key Systems.*\n", " Stanford PhD thesis.\n", "3. **Hülsing, A.** (2013). *W-OTS+ — Shorter Signatures for Hash-Based\n", " Signature Schemes.* AFRICACRYPT 2013.\n", "4. **Buchmann, J., Dahmen, E., Hülsing, A.** (2011). *XMSS — A Practical\n", " Forward Secure Signature Scheme based on Minimal Security Assumptions.*\n", " PQCrypto 2011.\n", "5. **IETF RFC 8391** (May 2018). *XMSS: eXtended Merkle Signature Scheme.*\n", "6. **IETF RFC 8554** (April 2019). *Leighton–Micali Hash-Based Signatures.*\n", "7. **NIST SP 800-208** (October 2020). *Recommendation for Stateful\n", " Hash-Based Signature Schemes.*\n", "8. **Bernstein, D. J., Hülsing, A., Kölbl, S., Niederhagen, R., Rijneveld, J.,\n", " Schwabe, P.** (2019). *The SPHINCS⁺ Signature Framework.* CCS '19.\n", "9. **NIST FIPS 205** (August 2024). *Stateless Hash-Based Digital Signature\n", " Standard.* \n", "10. **Aumasson, J.-P., Bernstein, D. J., et al.** (2020). *SPHINCS+ submission\n", " package, round 3.* \n" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.14.2" } }, "nbformat": 4, "nbformat_minor": 5 }