SLH-DSA / FIPS 205 and Hash-Based Signatures

Hash-based signatures trade larger signatures and substantial hashing work for a different, independent security foundation from every lattice-based scheme in this course. The interesting engineering question is where that trade is actually useful, and which operational assumptions must remain true throughout the key's entire lifetime. This chapter builds from Lamport one-time signatures, through Winternitz chains and Merkle trees, to FORS and the full SLH-DSA hypertree — deriving the exact signature-size formula (\(7{,}856\) bytes for one parameter set, checked by hand) and closing with a reproducible OpenSSL lab verifying two real parameter sets on real hardware.

1. Learning objectives and current status

This chapter starts with one-time signatures and builds toward the stateless hash-based signature algorithm in FIPS 205. You need the hash-function and signature concepts from Part 2, but no lattice algebra at all. By the end, you should understand the role of hash chains, authentication paths, FORS, and multiple tree layers, and be able to select a benchmark that reflects your actual workload rather than a vendor's headline number.

FIPS 205 was finalized August 13, 2024, with twelve parameter sets standardized. As checked for this chapter, SP 800-230 — proposing additional limited-signature-use sets — remains an initial public draft published April 2026. Its closed comment period does not make it final. Keep these two status claims separate; they're easy to conflate in casual conversation.

SLH-DSA descends from SPHINCS+, whose research paper explains the design's development in depth. Historical SPHINCS+ parameter names and implementations are useful research context, but production interoperability must name the final SLH-DSA parameter set and encoding explicitly — "hash-based" describes a family, not a universal wire format. See the SPHINCS+ research paper.

2. Lamport: reveal one secret per message bit

A simple one-time signature makes the basic idea visible. For each message bit position, generate two independent secret strings. Publish the hash of each string. To sign a bit, reveal the secret corresponding to its value. A verifier hashes each revealed secret and compares it against the appropriate published hash.

For a three-bit educational message, the private pairs are \((x_{0,0},x_{0,1})\), \((x_{1,0},x_{1,1})\), and \((x_{2,0},x_{2,1})\). Signing "101" reveals \(x_{0,1}\), \(x_{1,0}\), and \(x_{2,1}\). Verification needs no secret information beyond these disclosed values — the one-way property of the hash prevents a verifier from easily recovering the unrevealed alternatives.

Now sign "010" with the same key. Every previously unrevealed alternative becomes public. An observer can now assemble a signature for any of the eight possible three-bit messages. Reuse is therefore a structural, total failure — not a minor decrease in confidence. Real schemes hash long messages into fixed-size representations and use much larger secret values, but those changes do not remove the fundamental one-time restriction.

This example also shows why "collision resistance" alone is an incomplete description of what a hash-based construction needs. Different parts of the construction need properties like preimage resistance, second-preimage resistance, and appropriate pseudorandomness or domain separation — a real security analysis accounts for the exact functions used and how many targets an attacker can attack simultaneously.

3. Winternitz chains: compress the one-time signature

Lamport's representation is large because it exposes one independent secret for every digest bit. A Winternitz scheme groups bits into base-\(w\) digits and represents each digit by a position along a hash chain. The public endpoint of a chain is obtained by hashing repeatedly; the signature reveals an intermediate point from which the verifier finishes the chain themselves.

In a toy base-4 chain \(x \to H(x) \to H^2(x) \to H^3(x)\), digit "1" can be represented by \(H(x)\). The verifier hashes twice more to reach the public endpoint. Revealing \(H(x)\) also lets an observer move forward to \(H^2(x)\), which corresponds to another digit — a checksum across the message digits prevents this simple forward-only manipulation from producing a valid signature on an arbitrary new message.

The checksum is not optional redundancy — it couples the digits so that changing them in the direction available to an attacker forces an unavailable change elsewhere. Real WOTS+ additionally uses carefully defined keyed/addressed hash operations; replacing those operations with repeated calls to an undifferentiated hash function discards the construction's essential domain-separation rules.

The Winternitz parameter controls a tradeoff between the number of chains and work per chain. Fewer, longer chains can reduce transmitted elements while increasing total hashing work. This illustrates a recurring theme throughout this course: a compact signature can require substantially more work to produce or verify — byte count and CPU cost are genuinely distinct design axes.

4. Merkle trees authenticate many one-time keys

A verifier cannot efficiently retain a separate trusted public key for every signature. A Merkle tree compresses many leaf commitments into one trusted root. A signature includes the relevant one-time signature and the sibling hashes needed to reconstruct the root from that specific leaf.

Fig. 1 — To authenticate L2, provide L3 and H(L0,L1) — the verifier recomputes upward, preserving left/right ordering at each step, and checks the result against the already-trusted root.

For a full binary tree of height \(h\), the authentication path contains \(h\) sibling nodes. A tree with \(2^{20}\) leaves needs only 20 siblings to authenticate one leaf, rather than transmitting every other leaf. With 32-byte nodes, the path alone occupies 640 bytes — this is arithmetic for the example, not the total signature size of any named scheme.

The root authenticates membership only when it is already trusted. Fetching both the leaf and its claimed root from an attacker proves nothing about identity. In a signature system, the trusted root is part of an authenticated public key; the tree path then binds one particular one-time or few-time signing component to that key. Node position and function type must be encoded consistently — a hash value representing a leaf must never be accidentally interpreted as a pair of internal nodes, or reused at another address. Standards define these details precisely because a diagram alone doesn't express the domain boundaries a real proof requires.

5. Stateful signatures and the rollback problem

XMSS, described in RFC 8391, combines one-time signatures with Merkle trees and carefully managed state. The signer tracks which leaf index has already been used. NIST's SP 800-208 profiles stateful hash-based signatures for approved use under specified operational conditions.

The challenge is operational atomicity. If a signer issues a signature and crashes before persisting the updated index, restoring the old state can reuse a one-time key — a catastrophic failure for the whole scheme. Two cloned virtual machines can independently use the same next index. A backup restored without monotonic state protection can recreate an already-consumed signing capability. A correct stateful deployment needs stronger guarantees than an application counter in a mutable file — it must account for concurrent requests, failover, recovery, backup restoration, and the cryptographic module's own requirements. This may be entirely feasible in a tightly controlled firmware-signing appliance, while being genuinely difficult in a horizontally scaled service with ordinary snapshot semantics.

The XMSS and WOTS+ components inside SLH-DSA are not byte-for-byte the same schemes as the standalone constructions in RFC 8391 or SP 800-208 — they share architecture and terminology, but FIPS 205 defines its own actual internal functions. Treating the older RFC as a substitute implementation specification would be a real interoperability mistake.

6. FORS: a forest for a message digest

SLH-DSA uses FORS (Forest Of Random Subsets), a few-time signature component, to sign a message digest. Think of the digest as selecting one leaf in each of several small trees. The signature reveals the selected secret leaf values and their authentication paths; reconstructing each tree root and combining those roots yields the FORS public key.

A tiny forest with three trees of four leaves each would consume three two-bit indices. A digest fragment "01 11 00" selects leaf 1 in the first tree, leaf 3 in the second, and leaf 0 in the third. The verifier reconstructs each root from the supplied path. Real parameter sets use far larger forests and precise hash addressing than this toy example.

FORS is few-time rather than unrestricted-use. Security analysis accounts for the probability of repeated leaf selections and how much information multiple signatures expose over time — this is exactly why the number of signatures under a top-level key, and the distribution of selected addresses, appear directly in the analysis. Statelessness does not mean unlimited use has zero effect on security bounds (§9).

The digest and tree indices are derived from message-dependent hashing that includes public-key-related inputs and a signature randomizer. The randomizer is carried inside the signature itself. Its job is part of the construction's message processing — it is not an application nonce that developers can casually reuse or replace with their own request identifier.

7. The hypertree connects FORS to one public root

A FORS signature authenticates the message at a selected address. A layered tree structure — the hypertree — then authenticates that FORS public key all the way up to the SLH-DSA public root. At each layer, a WOTS+ signature authenticates the value from below, and an authentication path identifies the appropriate root for the next layer up.

message + signature randomizer
              ↓
      digest and tree indices
              ↓
     FORS signature → FORS public key
              ↓
     WOTS+ signature + authentication path
              ↓
        next subtree root
              ↓
         repeat by layer
              ↓
      compare with public root

Layering makes an enormous virtual tree manageable in practice. The signer derives required secret values from seeds and computes only the paths it actually needs, instead of ever materializing every possible leaf. The public key contains a public seed and root; the private representation contains secret seeds plus public components. Small keys therefore coexist with large signatures and substantial hashing work — that's the entire tradeoff SLH-DSA makes.

The signature includes the randomizer, FORS material, and all required hypertree authentication material. The verifier reconstructs the whole chain of commitments and checks the final root. No persistent next-leaf counter needs to be synchronized across signing requests, unlike a stateful XMSS deployment (§5) — this is the entire point of "stateless" in the name.

8. Exact FIPS 205 parameter tradeoffs

Each row below applies to both the SHA2 and SHAKE hash-function family with the shown suffix — for example, "128s" denotes either SLH-DSA-SHA2-128s or SLH-DSA-SHAKE-128s. Public keys occupy \(2n\) bytes and the standard private representation \(4n\) bytes.

Suffix	Category	Public key	Private key	Signature
128s	1	32 bytes	64 bytes	7,856 bytes
128f	1	32 bytes	64 bytes	17,088 bytes
192s	3	48 bytes	96 bytes	16,224 bytes
192f	3	48 bytes	96 bytes	35,664 bytes
256s	5	64 bytes	128 bytes	29,792 bytes
256f	5	64 bytes	128 bytes	49,856 bytes

The s variants favor smaller signatures; f variants favor faster signature generation. The label does not promise every operation is faster on every platform. SHA2 versus SHAKE also depends on available implementations and hardware acceleration — measure the operation and device that actually matter to you rather than selecting a family purely from its name.

As a worked size check: 128s uses \(n=16\), FORS parameters \(k=14\) and \(a=12\), seven hypertree layers, WOTS+ length 35, and total tree height 63. The signature-size formula \(n[1 + k(a+1) + d \cdot \text{len} + h]\) gives \(16[1 + 14{\cdot}13 + 7{\cdot}35 + 63] = 7{,}856\) bytes — matching the table exactly. Each term corresponds to a visible, named component of the architecture above: the randomizer, FORS, the hypertree's WOTS+ signatures, and the authentication paths.

For a firmware image measured in megabytes, this overhead may be entirely acceptable. For millions of small authenticated messages, it may dominate transport and storage costs outright. A certificate chain containing several large signatures can amplify handshake size even if each public key is tiny — always evaluate the complete object and delivery path, not one component in isolation.

9. Statelessness and lifetime limits

The twelve FIPS 205 sets are designed for their claimed categories with at most \(2^{64}\) signatures per key. That very large bound is still a bound in the formal security analysis — it should never be generalized into a claim that every stateless hash-based parameter choice supports truly unlimited signatures.

The initial public draft SP 800-230 proposes six additional sets for limited-use applications, with a strict \(2^{24}\) signatures-per-key limit in exchange for improved size or verification characteristics (Part 1 §8). These are draft proposals, not general-purpose replacements for the final table above. A \(2^{24}\) budget equals 16,777,216 signatures — at an assumed constant 10 signatures per second, that budget lasts about 19.4 days; at one signature per day it lasts vastly longer. These are illustrative workload calculations, not recommendations. A fleet-wide key shared by many signers consumes one combined budget, including retries and otherwise-unused signatures — applications must evaluate whether they can enforce this lifetime limit across every signer and every copy of a key.

Tracking a lifetime budget differs mechanically from maintaining a unique one-time-key index (§5), but it still requires real operational controls. Restoring a backup must not silently reset the accounting. Test and production use of the same key would share the same limit. Separate keys, explicit ownership, and conservative retirement thresholds all make this requirement much easier to reason about correctly.

10. Native OpenSSL experiment

The OpenSSL SLH-DSA manual documents the native interface. The script below was executed with OpenSSL 3.5.8 on macOS ARM64. It verifies both SHA2 category-1 variants, checks exact signature sizes against §8's table, and rejects a changed message. It's a functional experiment, not a timing benchmark.

#!/usr/bin/env bash
set -euo pipefail
OPENSSL=${OPENSSL:-openssl}
LAB=$(mktemp -d)
trap 'rm -rf "$LAB"' EXIT
umask 077
cd "$LAB"
"$OPENSSL" version
printf '%s\n' 'firmware manifest: demonstration only' > message.txt
for variant in SLH-DSA-SHA2-128s SLH-DSA-SHA2-128f; do
 "$OPENSSL" genpkey -algorithm "$variant" -out private.pem
 "$OPENSSL" pkey -in private.pem -pubout -out public.pem
 "$OPENSSL" pkeyutl -sign -rawin -inkey private.pem -in message.txt -out signature.bin
 "$OPENSSL" pkeyutl -verify -rawin -pubin -inkey public.pem -in message.txt -sigfile signature.bin
 python3 - "$variant" <<'PY'
import sys
from pathlib import Path
expected = 7856 if sys.argv[1].endswith('128s') else 17088
assert Path('signature.bin').stat().st_size == expected
print(sys.argv[1], 'signature bytes:', expected)
PY
 printf 'altered' > changed.txt
 if "$OPENSSL" pkeyutl -verify -rawin -pubin -inkey public.pem -in changed.txt -sigfile signature.bin > /dev/null 2>&1; then exit 1; fi
done
printf '%s\n' 'PASS: both variants verify and reject changed messages'

Both variants passed, producing exactly 7,856 and 17,088 bytes respectively — matching §8's table precisely. A command-line timer around this script would include key generation, filesystem work, process startup, signing, and verification all mixed together. To compare real signing performance, isolate that one operation with a maintained benchmark interface and report the environment and sample distribution (Part 14).

11. Implementation risks and appropriate uses

Hash-based foundations do not eliminate implementation attacks. Secret-seed derivation, address handling, memory safety, fault behavior, and randomizer generation all matter just as much as in any other algorithm family. A fault that changes an address or releases unintended secret material can violate the construction's assumptions even when the underlying hash function itself remains perfectly strong. Constant-time and physical-attack requirements depend on the actual threat model and implementation, not the algorithm family alone.

The diversity value here is substantial: SLH-DSA does not depend on the same lattice problems as ML-DSA at all (Part 5 §10). An organization can consider it for a carefully selected trust role where large signatures and higher signing cost are acceptable in exchange for that independence. Diversity should be evaluated across implementation dependencies too — two algorithms sharing one compromised signing service do not provide independent operational protection, no matter how different their math is.

A useful design exercise is an offline firmware authority. Specify how often it signs, how many devices verify, the smallest verifier's memory budget, update-package overhead, and expected key lifetime. Compare an s variant against an f variant under those exact constraints. Include recovery, trust-anchor rotation, and emergency revocation in the comparison — not just the signature byte count in isolation.

Why is reusing a Lamport key catastrophic rather than just weaker?

Every previously unrevealed secret alternative becomes public after a second signature (§2). An observer can then assemble a valid signature for any possible message the scheme could sign — it's a total structural break, not a gradual confidence decrease.

Does SLH-DSA need the same state-management discipline as XMSS?

No (§7). The hypertree derives everything it needs from seeds at signing time rather than tracking a persistent next-leaf index — that's the entire point of "stateless" in the name, and it removes the rollback/cloning failure mode described in §5.

Does "stateless" mean SLH-DSA keys can sign truly unlimited messages?

No (§9). The standardized sets support up to \(2^{64}\) signatures per key — an enormous but still finite bound baked into the security analysis. The draft limited-use parameters propose a much smaller \(2^{24}\) bound in exchange for better size/verification characteristics.

Takeaways

SLH-DSA layers four ideas: Lamport-style one-time signatures, Winternitz chains to compress them, Merkle trees to authenticate many of them, and FORS to sign a message digest few-time — all connected by a hypertree up to one public root.
Reusing a one-time signing key is a total break, not a weakening — this is why WOTS+/Lamport components need the tree structure wrapped around them at all.
SLH-DSA is stateless by design — no persistent next-leaf counter to synchronize across signers, cloned VMs, or backup restores, unlike stateful XMSS (SP 800-208).
The signature-size formula is fully derivable by hand: \(n[1+k(a{+}1)+d{\cdot}\text{len}+h]\) gives exactly 7,856 bytes for SLH-DSA-*-128s, matching both the standard's table and the reproducible lab's measured output.
Small keys, large signatures, heavy hashing — the right tradeoff for a firmware authority signing rarely and verified widely; likely wrong for high-volume small-message signing.
SLH-DSA's independence from lattice assumptions is its main diversity value against ML-DSA — but shared implementation or operational dependencies can still erase that independence in practice.

References & further reading

FIPS 205 (SLH-DSA) — the primary standard for this entire chapter.
SPHINCS+ research paper — §1, design history and development.
RFC 8391 (XMSS) · SP 800-208 — §5, stateful hash-based signatures.
Draft SP 800-230 — §9, limited-use parameter proposal.
OpenSSL SLH-DSA manual — §10, the lab commands.

SLH-DSA / FIPS 205 and hash-based signatures.