k trustees contribute PRF shares across two rounds. No individual seed is sufficient to reconstruct the signing key — the aggregator holds a CRV-masked copy, and each trustee's share masks one row of the chain matrix. AggregatorVerify is standard OTS verification: the verifier is unaware of the distributed protocol.
Two kinds of numbers appear on this page. LIVE means your click just ran real SHA-256 via crypto.subtle.digest in this browser tab — different every time. MEASURED means a number recorded from an actual run of the Python implementation (benchmark.py, attacks.py) on real hardware, shown as a static reference point next to the live JS equivalent. Neither is a mockup.
| # | Section | What it does | Kind |
|---|---|---|---|
| 01 | Winternitz OTS | Keygen → sign → verify → forge one Winternitz one-time key, step by step | LIVE |
| 02 | Key Reuse Attack | Sign twice under one key; watch chain exposure computed live | LIVE |
| 03 | Security Properties | The four properties the constructions above establish | reference |
| 04 | Threshold Signing | k-of-n trustees; mark trustees compromised and watch signing get blocked | LIVE |
| 05 | Merkle Tree | Build a 4-leaf authentication tree; click a leaf to see its path | LIVE |
| 06 | Weak Seed Recovery | Brute-force a narrowed-entropy PRF seed against its real public round-1 value | LIVE |
| 07 | Timing Side Channel | Measure whether chain-walk time correlates with the secret digit, live | LIVE |
| 08 | Benchmarks | Measured timings for every primitive, plus a live JS vs. Python race | MEASURED + LIVE |
hash_lms(tweak, *data) = SHA-256(tweak₀_be32 ‖ tweak₁_be32 ‖ … ‖ data)[:N_BYTES].
Keygen walks 18 chains of 255 steps each (4,590 calls). Sign looks up chain position b_all[i] — O(A+C) total.
Verify continues from Z[i] for CHAIN_LEN−1−b_all[i] more steps, reconstructing the public key tip.
The checksum digits prevent digit-increment forgery: increasing any message digit forces the checksum to decrease, requiring the adversary to also advance a checksum chain beyond the signed position.
| N_BYTES | 16 |
| W | 8 |
| CHAIN_LEN (2^W) | 256 |
| A = N_BYTES (msg digits) | 16 |
| C = ⌈log₂(A·(2^W−1))/W⌉ | 2 |
| A+C (chains per key) | 18 |
| keyId (this run) | — |
After observing Z1[i] at digit position b1[i] and Z2[i] at position b2[i], an adversary can compute every chain element from position min(b1[i], b2[i]) upward by forward-hashing from whichever Z has the lower index — using the same absolute step indices the keygen used. Only positions 0 … min(b1[i], b2[i])−1 remain preimage-hard. With two uniformly random messages, the expected minimum is ≈ 85, so ≈ 67% of each chain is exposed. The defence is used_keys tracking in KK_Sign1(): a trustee refuses to contribute to a second signing under the same keyId.
Security reduces to second-preimage resistance of SHA-256 under the hash-based OTS proof of Buchmann et al., extended by Kelsey, Lang & Lucks to the distributed setting. No number-theoretic assumptions.
Signing at digit position b[i] exposes chain elements 0 … b[i]−1 of chain i (they are derivable from Z[i] by forward hashing). A second message with a smaller digit d' < b[i] at position i would require the adversary to produce Z'[i] at position d', which is a preimage of Z[i] under the chain function — computationally equivalent to SHA-256 second preimage.
Each trustee's PRF contribution PRF_Chain(seed_t, keyId, i, j) acts as a one-time pad over the aggregator's masked key CRV.SK[i][j]. A coalition of k−1 trustees observes a set of PRF images that are jointly uniform over the output space — the unmasked key SK[i][j] has negligible mutual information with their joint view.
The Winternitz checksum is csum = A×(CHAIN_LEN−1) − Σb[i]. Incrementing any message digit by δ decreases csum by δ, requiring the adversary to produce a chain element at a lower position for the checksum chains. That is a SHA-256 preimage — the Forge & Fail demo above demonstrates this directly: flipping one bit in Z[0] yields a reconstructed PK that does not match the stored value.
The verifier receives (R, Z, PATH) and calls lamport.Verify(R, Z, M, KeyID) followed by a Merkle path check — the same function used for non-distributed stateful HBS. The number of signing trustees k, the CRV structure, and the PRF contributions are invisible to the verifier. Verification cost is O(OTS verify + log D), independent of k.
Round 1: each active trustee t computes Rt = PRF_R(seed_t, keyId) and CHKt = PRF_Chk(seed_t, keyId), sends both to the aggregator.
Aggregator derives CRV.R = XOR(R_base, R₀, … Rₙ) and per-trustee integrity tokens CRV.CHK[t] = XOR(PRF_Auth(seed_t, R), CHK₀, CHK₁, …).
Round 2: trustee t receives R', verifies it against CHK_Prime (MAC check via KK_Auth), then contributes Zt[i] = WINTER(h, SK_share_t).
Aggregator XOR-combines contributions: Z[i] = XOR(CRV.SK[i][b], Zt₀[i], Zt₁[i], …).
Leaf i = Winternitz OTS public key for slot i, computed as hash_lms([0, i], *tips_i).
Internal node at level ℓ, position p: hash_lms([3, ℓ, p], left, right).
MT_MakePath(i) extracts the log₂(D) = 2 siblings needed to recompute the root.
Verifier reconstructs: h₀₁ = hash_lms([3,0,0], leaf[0], leaf[1]), then root = hash_lms([3,1,0], h₀₁, h₂₃) — two SHA-256 calls regardless of which leaf signed. Click a leaf after building to see its authentication path highlighted.
Target: Rt = PRF_R(seed, keyId, N_BYTES) — not a secret. It's the real value a trustee sends the aggregator in round 1 of KK_Aggregator_Sign() (see KK_SetupContribution() / KK_GenSig1() in distributed_signing.py). If a seed's true entropy is only seed_bits instead of the full 128 (a broken RNG, a password-derived seed), an adversary who intercepts one round-1 message can search the narrowed space directly against it. At 128 bits this exact search is infeasible — the numbers below are measured on this CPU, then extrapolated.
THREAT_MODEL.md lists timing side channels as out of scope: hash_lms gives no constant-time guarantee. SignLazy() walks each of 18 chains live from its seed for exactly b_all[i] hash calls — unlike eager Sign(), whose per-chain cost is a single O(1) table lookup regardless of the digit. Below: sign many random messages with both, and correlate elapsed time against the digit value that determined the work. This mirrors timing_analysis.py's measure_signlazy_timing() exactly, run against this browser's crypto.subtle.digest instead of Python's hashlib.
AggregatorSign cost is O(k × (A+C) × CHAIN_LEN + k log D) — dominated by the k OTS signing operations, not the tree depth. AggregatorVerify cost is O(OTS verify + log D), independent of k: a verifier processing a distributed signature runs the same code as for a non-distributed stateful HBS signature.
| Operation | Inputs | Time complexity |
|---|---|---|
| Gen | single OTS key | O(A × CHAIN_LEN) |
| Sign | single OTS key | O(A + C) |
| Verify | single OTS key | O((A+C) × CHAIN_LEN) |
| MT_Construct | D leaves | O(D) |
| MT_MakePath | D leaves | O(D + log D) |
| MT_Verify | D leaves | O(log D) |
| StatefulSign | D leaves | O(OTS sign + log D) |
| AggregatorSign | D leaves, k trustees | O(k × (A+C) × CHAIN_LEN + k log D) |
| AggregatorVerify | D leaves | O(OTS verify + log D) |
In CPython, int.from_bytes(v, 'big') ^ acc is a single bytecode instruction dispatched to C regardless of byte length. A byte-loop over 16 bytes dispatches 16 times. The JS equivalent: reinterpret the Uint8Array as a Uint32Array (same buffer, no copy) and XOR 4 words instead of 16 bytes. Click below to measure the actual ratio on this CPU.
# int XOR: single C dispatch regardless of byte width def _xor_many(values): if not values: return b"" n = len(values[0]) acc = int.from_bytes(values[0], "big") for v in values[1:]: if len(v) != n: raise ValueError("length mismatch") acc ^= int.from_bytes(v, "big") return acc.to_bytes(n, "big") # JS: view same buffer as Uint32Array — no allocation # const out = new Uint32Array(N_BYTES / 4); # for (const a of inputs) { # const v = new Uint32Array(a.buffer, a.byteOffset); # for (let i = 0; i < 4; i++) out[i] ^= v[i]; # }
Replaces a per-byte ^ loop with int.from_bytes + ^. CPython's integer XOR is a single C-level operation — bitwidth does not change dispatch cost. Measured over 20,000 runs with 10 × 16-byte inputs per call.
Single-line change: HASH_BACKEND = "blake2b". BLAKE2b has lower per-call overhead on 16-byte inputs due to a smaller internal state and faster finalization on short messages. Security reduces to collision resistance — the hash-based OTS proof is hash-agnostic.
Gen() precomputes all 18 × 256 chain positions at keygen, storing a 73 KB key matrix. GenLazy() stores only the 18 × 16-byte seeds (288 bytes) and walks each chain at sign time, shifting the 4,590-call cost from keygen to sign. Same PK, same signature format, same verify path.
def hash_lms(tweak, *data): h = hashlib.sha256() for t in tweak: if isinstance(t, int): h.update(t.to_bytes(4, "big")) # tweak ints → big-endian 4-byte prefix else: h.update(t) for d in data: h.update(d) return h.digest() # 32 B; callers slice [:N_BYTES]
def KK_SetupContribution(seed, KeyID, R, path_lens, sk_shape): rows, cols = sk_shape return { "Rt": PRF_R(seed, KeyID, N_BYTES), # tweak (30, keyId) — masks R_base "CHKt": PRF_Chk(seed, KeyID, N_BYTES), # tweak (31, keyId) — round-2 integrity "Auth": PRF_Auth(seed, KeyID, R), # tweak (32, keyId) — binds R to seed "PATHt": [PRF_Path(seed, KeyID, idx, n) for idx, n in enumerate(path_lens)], "SKt": [[PRF_Chain(seed, KeyID, i, j, N_BYTES) for j in range(cols)] # one-time pad over CRV.SK[i][j] for i in range(rows)], }