PDF Run this chapter's code LaTeX source Comments

Chapter 21SLH-DSA (SPHINCS⁺, FIPS 205): Algorithm Walkthrough

21.1What is SPHINCS⁺?#

SPHINCS⁺ is the hash-based signature scheme that NIST standardized as SLH-DSA in FIPS 205 [1, 2], and it is the most conservative of all the post-quantum standards. Where the lattice signatures of the previous part rest on the presumed hardness of lattice problems, SPHINCS⁺ rests on nothing but the security of a hash function – the single best-understood assumption in cryptography. If every lattice and code assumption fell tomorrow, a secure hash function would still yield a secure signature; that is exactly why the family is kept in the standard portfolio as a hedge.

The scheme is the endpoint of a short lineage: the stateless design SPHINCS appeared in 2015, was hardened into SPHINCS⁺ for the NIST competition through 2017–2019 [2], and was finalized as SLH-DSA in FIPS 205 in 2024. The three names denote essentially the same construction; this book uses SLH-DSA for the standardized algorithm and SPHINCS⁺ for the scheme it came from. In one sentence, it is a giant hypertree of one-time and few-time hash-based signatures, arranged so that no signing state need ever be kept.

Why “stateless” is the hard part.#

The “SL” in SLH-DSA stands for stateless, and that is the property the design fights for. Earlier hash-based schemes such as XMSS and LMS are stateful: each one-time key may be used exactly once, so the signer must remember which leaves are already spent, and a single slip – a restored virtual-machine snapshot, a copied key file – reuses a one-time key and can be catastrophic. SPHINCS⁺ removes the state entirely. It uses message randomization and a hypertree address space so large that accidental address collisions are negligible. This is not permission to reuse addresses: WOTS leaves must remain unique, while FORS security degrades with the finite signature count and any accidental collisions. The price of statelessness is size: SPHINCS⁺ signatures are the largest of the standards, several kilobytes each. The scheme is instantiated over either SHA-2 or SHAKE, in a simple or robust mode, and in the size-versus-speed s and f families detailed in the parameter section below.

21.2Learning objectives#

The two previous chapters built the pieces of hash-based signing from the ground up: one-time and few-time signatures (Chapter 19) and the Merkle-tree and hypertree machinery that makes them stateless and many-time (Chapter 20). This chapter assembles those pieces exactly as the standard specifies them. After finishing this chapter, you should be able to:

• explain why SPHINCS⁺ is the most conservative standard and what “stateless” buys and costs;

• recall how WOTS⁺, FORS, Merkle trees, and the hypertree fit together;

• explain how every secret is derived deterministically from a few seeds and an address;

• follow the SLH-DSA key generation, signing, and verification algorithms;

• read off the parameter families and their size–speed trade-off.

21.3Review: the pieces, assembled#

It is worth restating the ladder in one place, since SLH-DSA is precisely its assembly:

• WOTS⁺ (Chapter 19) signs one value with hash chains and a checksum;

• a Merkle tree (Chapter 20) binds \(2^h\) WOTS⁺ keys under one root, authenticated by a path – one such tree is an XMSS instance;

• a hypertree stacks \(d\) layers of these trees so that each root is signed by the layer above, exposing only the top root as the public key;

• FORS signs the actual message digest as a few-time signature, and its public key is what the bottom hypertree layer signs.

Figure 21.1 draws a complete SLH-DSA signature: the whole chain of one-time and few-time signatures from the message at the bottom up to the published root (the block-level view of the same hypertree is Figure 20.2). What remains is to specify where every secret comes from and to write down the three algorithms.

21.4The real input: seeds and addresses#

Like ML-KEM and ML-DSA, SLH-DSA is deterministic once its seeds are fixed. Everything is derived from three \(n\)-byte values:

• SK.seed – secret; every WOTS⁺ and FORS secret value is generated from it by a PRF;

• SK.prf – secret; a PRF key used to derive the per-signature randomizer \(R\);

• PK.seed – public; tweaks every hash so that structurally identical nodes differ.

The device that keeps the many hashes distinct is the address (ADRS): a structured label identifying exactly which tree, which layer, which leaf, and which position within a chain a given hash belongs to. Every hash call takes the public seed and an address, so no two structurally identical computations in different places produce the same value. This is what defeats multi-target attacks, and it is why PK.seed, though public, is essential.

21.5Key generation#

Key generation samples the three seeds and computes the one value that summarizes the entire hypertree: the root of its top-layer Merkle tree.

21.6Signing and verification#

Signing hashes the message (with a randomizer) to a digest, splits it into a FORS message and a pair of indices selecting a bottom-layer tree and leaf, signs the digest with FORS, and then signs the FORS public key up the hypertree.

Verification is nothing but a chain of hash recomputations: rebuild the FORS public key from the message, fold it up the hypertree using the supplied authentication paths, and accept only if the final value equals the published root. There is no arithmetic to protect and no secret-dependent branch, which makes SLH-DSA unusually easy to implement in constant time (Chapter 26).

21.7Parameter sets#

SLH-DSA comes in two flavours at each security level: s (small signatures, slower signing) and f (fast signing, larger signatures), instantiated with either SHA2 or SHAKE.

Signatures are large – roughly \(8\) to \(50\) kilobytes – which is the price of relying on hashing alone. In return, the security argument is the simplest and most conservative of any post-quantum scheme.

21.8SageMath experiment: addressed Merkle authentication#

This small hash-only example checks the part of SLH-DSA verification that folds an authentication path back to a public root. It uses eight leaves and a SHA-256-based toy hash; it is not a FORS, WOTS⁺, or full SLH-DSA implementation.

from hashlib import sha256
from operator import xor

n = 16
pk_seed = b"public seed for a toy tree"

def H(label, address, data=b""):
    return sha256(pk_seed + label + address + data).digest()[:n]

def leaf(index):
    return H(b"leaf", int(index).to_bytes(4, "big"))

def parent(left, right, level, index):
    address = (int(level).to_bytes(1, "big") +
               int(index).to_bytes(4, "big"))
    return H(b"node", address, left + right)

levels = [[leaf(i) for i in range(8)]]
for level in range(3):
    previous = levels[-1]
    levels.append([parent(previous[2*i], previous[2*i + 1], level, i)
                   for i in range(len(previous)//2)])
root = levels[-1][0]

leaf_index = 5
auth = [levels[level][xor(int(leaf_index >> level), 1)]
        for level in range(3)]

def root_from_path(node, index, path):
    for level, sibling in enumerate(path):
        parent_index = index >> 1
        node = (parent(node, sibling, level, parent_index)
                if index % 2 == 0 else
                parent(sibling, node, level, parent_index))
        index >>= 1
    return node

assert root_from_path(leaf(leaf_index), leaf_index, auth) == root
bad_auth = list(auth)
bad_auth[0] = bytes([xor(bad_auth[0][0], 1)]) + bad_auth[0][1:]
assert root_from_path(leaf(leaf_index), leaf_index, bad_auth) != root
print("addressed Merkle path accepts intact data and rejects a tampered path")

The address is included in every hash call, so the same byte strings at a different layer or node index are domain-separated. That is the small-scale version of the address discipline used throughout SLH-DSA.

21.9A complete SageMath implementation#

The Merkle experiment above is a toy in one respect that matters: it uses a made-up address format. The companion file sage/fips205_slhdsa.sage implements the real thing – all twenty-five numbered algorithms of FIPS 205, each as its own function annotated with its algorithm number, for all twelve approved parameter sets. That means both hash families (SHA2 and SHAKE) at all three security levels in both the s and f variants, together with the WOTS⁺ chains, the XMSS trees, the hypertree, FORS, the pure and pre-hash top-level algorithms, and the 32-byte address structure with its 22-byte compressed form.

Run it in a browser: the f parameter sets end to end, and the s sets — whose signing takes minutes — verified against NIST’s ACVP signatures. See appliedpqc.io/playground.html — nothing to install.

The address is a small class carrying the member functions of Table 1 of the standard, so the recursive tree walk of Algorithm 9 reads exactly as specified:

def xmss_node(self, skseed, i, z, pkseed, adrs):
    """Algorithm 9. Root of a Merkle subtree of WOTS+ public keys."""
    if z == 0:
        adrs.setTypeAndClear(WOTS_HASH)
        adrs.setKeyPairAddress(i)
        return self.wots_pkGen(skseed, pkseed, adrs)
    lnode = self.xmss_node(skseed, 2*i,     z - 1, pkseed, adrs)
    rnode = self.xmss_node(skseed, 2*i + 1, z - 1, pkseed, adrs)
    adrs.setTypeAndClear(TREE)
    adrs.setTreeHeight(z)
    adrs.setTreeIndex(i)
    return self._H(pkseed, adrs, lnode + rnode)

The hypertree is then just that tree, stacked \(d\) deep, with each layer signing the root of the layer below:

def ht_sign(self, M, skseed, pkseed, idxtree, idxleaf):
    """Algorithm 12. A hypertree signature: d chained XMSS signatures."""
    adrs = ADRS()
    adrs.setTreeAddress(idxtree)
    SIGtmp = self.xmss_sign(M, skseed, idxleaf, pkseed, adrs)
    SIG_HT = SIGtmp
    root   = self.xmss_pkFromSig(idxleaf, SIGtmp, M, pkseed, adrs)
    for j in range(1, self.d):
        idxleaf = idxtree % (1 << self.hp)   # low h' bits
        idxtree = idxtree >> self.hp
        adrs.setLayerAddress(j)
        adrs.setTreeAddress(idxtree)
        SIGtmp  = self.xmss_sign(root, skseed, idxleaf, pkseed, adrs)
        SIG_HT += SIGtmp
        if j < self.d - 1:
            root = self.xmss_pkFromSig(idxleaf, SIGtmp, root, pkseed, adrs)
    return SIG_HT

What Sage contributes to a scheme with no algebra.#

SLH-DSA is built from hash functions alone, so unlike ML-KEM and ML-DSA there is no ring here for a computer-algebra system to check the code against. What Sage supplies instead is exact integer reasoning about the combinatorics. The function verify_parameter_consistency() at the end of sage/fips205_slhdsa.sage re-derives Table 2 from the defining equations for all twelve parameter sets: that \(h = d\cdot h'\), so the hypertree really has \(2^{h}\) leaves; that the checksum length \(len_2\) produced by Algorithm 1 agrees with the closed form \(\lfloor \log_w(len_1(w-1)) \rfloor + 1\), computed with Sage’s exact integer logarithm; that the digest length \(m\) is large enough to supply the FORS message and both tree indices; and that the published key and signature sizes match \(2n\) and \((1 + k(1+a) + h + d\cdot len)\,n\) respectively. A parameter table is exactly the kind of thing that is easy to transcribe wrongly and hard to notice, and this turns it into a test.

Validation.#

The implementation is checked against NIST’s ACVP vectors [3] for FIPS 205 – key generation, signature generation, and signature verification, across all twelve parameter sets in both the pure and pre-hash forms – and reproduces them byte for byte.

One practical caveat is a property of the scheme rather than of this implementation. Signing with an s parameter set requires rebuilding whole XMSS trees: SLH-DSA-128s traverses on the order of a million hash calls per signature, which in Sage takes about sixteen seconds, and the 256-bit variants about twice that. The quick test run therefore covers signature generation only for the f sets, and reports how many groups it left out; make kat-full includes them. Verification is cheap for every parameter set and is always checked in full. This asymmetry is the same one that gives the two variants their names.

21.10Pitfalls#

Pitfall 1: reusing a one-time (WOTS⁺) leaf.#

Signing two different messages with the same WOTS⁺ chain reveals enough chain points to forge (Chapter 19). The address mechanism and message randomization make accidental collisions extremely unlikely; neither WOTS nor FORS addresses may be intentionally reused.

Pitfall 2: thinking SLH-DSA needs state.#

Earlier hash-based schemes (XMSS, LMS) are stateful: the signer must remember which leaves are spent, and a single reuse is catastrophic. SLH-DSA is stateless – the message hash selects the path – which is why it was chosen for standardization despite larger signatures.

Pitfall 3: forgetting the public seed’s role.#

PK.seed tweaks every hash call through the address mechanism. Without it, structurally identical nodes in different trees would hash identically, enabling multi-target attacks. It is public but essential.

21.11Summary#

SLH-DSA is the assembly of the hash-based ladder into a single stateless standard:

• every secret is derived deterministically from SK.seed and an address; PK.seed keeps all hashes distinct;

• a signature is a FORS signature on the message digest, carried up a hypertree of Merkle-tree (XMSS) instances to the one published root;

• verification is pure hashing, so the scheme is conservative in assumption and easy to make constant-time.

Its security depends on nothing but the hash function, making it the backstop among post-quantum signatures. This completes the two signature families – lattice-based (ML-DSA, FN-DSA) and hash-based (SLH-DSA). The next part turns to a third and independent foundation: code-based cryptography.

References