Chapter 18: Hash-based signature cryptanalysis

Every hash-based signature in Part III reduces to three hash properties. Preimage resistance: given $y$, find $x$ with $H(x) = y$. Second-preimage resistance: given $x$, find $x' \neq x$ with $H(x') = H(x)$. Collision resistance: find any distinct $x, x'$ with $H(x) = H(x')$. Formally, the SPHINCS+/SLH-DSA proof packages these intuitions into stronger properties: pseudorandom-function security, distinct-function multi-target second-preimage resistance for the WOTS+, FORS, and Merkle hash calls, and interleaved target subset resilience for the FORS message mapping (Aumasson et al., 2020).

Each scheme in Part III reduces forgery to one of those properties, on a target population of its own:

Scheme	What a forgery reduces to
Lamport (Chapter 14)	finding unrevealed preimages for the digest positions a message selects
WOTS+ (Chapter 15)	moving backward in at least one hash chain, a preimage problem for the chain function
FORS (Chapter 16)	obtaining the secret values for all $k$ leaf indices a new message digest selects
SLH-DSA (Chapter 17)	any of the above, on a hypertree whose every hash call is bound to a position by ADRS

The question is: how many hash targets does a signature expose, what does an adversary gain from attacking any one of them, and do the FIPS 205 parameter sets absorb the resulting security reduction? The numbers below answer all three.

Multi-target preimage on SLH-DSA-128s

A single SLH-DSA-SHA2-128s signature is a sequence of $n$-byte strings. They are not all hash outputs. FORS contributes $k = 14$ secret values (PRF outputs) and $k \cdot a = 168$ authentication-path Merkle nodes, a total of $k(1+a) = 182$ strings. The hypertree contributes $d = 7$ WOTS+ signatures of $\ell = 35$ chain values each, for $d \cdot \ell = 245$ strings. Here $\ell = \ell_1 + \ell_2$ with $\ell_1 = 32$ message-digit chains and $\ell_2 = 3$ checksum chains. The checksum forces at least one chain backward, so a forged digest cannot shorten every chain (Chapter 15).

The signature also carries the XMSS authentication paths above the WOTS+ leaves: $h = 63$ Merkle nodes in total, since each of the $d$ XMSS signatures contributes $h/d = 9$ nodes. With the $n$-byte randomizer $R$, the full signature is $1 + 182 + 245 + 63 = 491$ $n$-byte strings. That is $491 \times 16 = 7{,}856$ bytes, the FIPS 205 signature size for SLH-DSA-SHA2-128s (National Institute of Standards and Technology, 2024).

The preimage-style attack surface is not the same as the signature-component list. WOTS+ signature elements are chain values. Forging one means moving backward in a chain, a preimage problem for the chain function. A FORS forgery either reuses an already-revealed FORS secret value or, for an unrevealed index, attacks the corresponding leaf hash $F(\text{sk})$ (the verifier recomputes that leaf from the revealed secret, and the leaf hash is never transmitted). The FORS and XMSS authentication-path nodes are not preimage targets. They belong to the Merkle second-preimage surface, analyzed separately under attack-by-attack cost analysis. The $k \cdot a$ FORS and $h$ XMSS authentication nodes therefore count toward signature size but not toward the preimage-target population below.

As an intuition model, count the FORS leaf hashes inside one FORS instance’s position space, $k \cdot t$, plus the WOTS+ revealed chain values the corresponding hypertree layer produces, $d \cdot \ell$. For 128s that is $57{,}344 + 245 = 57{,}589$ preimage-style targets.

What this count is and is not

This is not what the SPHINCS+/SLH-DSA security proof literally counts. The full parameter search also accounts for signing queries, position reuse, FORS few-time degradation, and construction-specific terms (Aumasson et al., 2020). Position randomization keeps the expected per-position signature count at $Q / 2^h$ after $Q$ total signatures, so the figure above is a position-scoped intuition model: not a per-signature exposure, and not the key-level proof term. Every “no ADRS” figure in this chapter inherits that scope.

Without ADRS domain separation, the multi-target preimage advantage against this intuition-model population is $\log_2(57{,}589) \approx 15.8$ bits, which drops the effective preimage security from 128 bits to $128 - 15.8 = 112.2$ bits. With ADRS, each hash call uses a distinct tweaked function, so inverting one target provides no information about any other, and the multi-target term returns to the single-target preimage bound of 128 bits (Aumasson et al., 2020).

import math

n_bytes = 16
n_bits = 8 * n_bytes
k, a = 14, 12
t = 2**a
w = 16

lg_w = int(math.log2(w))
ell_1 = math.ceil(8 * n_bytes / lg_w)
mc = ell_1 * (w - 1)
ell_2 = math.ceil((math.floor(math.log2(mc)) + 1) / lg_w)
ell = ell_1 + ell_2
d = 7

revealed_fors = k * (1 + a)
revealed_wots = d * ell
h = 63
randomizer = 1
sig_elements = randomizer + revealed_fors + revealed_wots + h
sig_bytes = sig_elements * n_bytes
fors_wots_elems = revealed_fors + revealed_wots

fors_instance_targets = k * t
wots_layer_targets = d * ell
per_instance_total = fors_instance_targets + wots_layer_targets

adv = math.log2(per_instance_total)
eff_no_adrs = n_bits - adv

print(f"FORS signature values (n-byte): {revealed_fors}")
# ==> FORS signature values (n-byte): 182
print(f"WOTS+ chain values (n-byte)   : {revealed_wots}")
# ==> WOTS+ chain values (n-byte)   : 245
print(f"XMSS auth-path nodes (n-byte) : {h}")
# ==> XMSS auth-path nodes (n-byte) : 63
print(f"randomizer R (n-byte)         : {randomizer}")
# ==> randomizer R (n-byte)         : 1
print(f"signature n-byte strings      : {sig_elements}")
# ==> signature n-byte strings      : 491
print(f"signature size (bytes)        : {sig_bytes:,}")
# ==> signature size (bytes)        : 7,856
print(f"FORS+WOTS+ signature elems    : {fors_wots_elems}")
# ==> FORS+WOTS+ signature elems    : 427
print(f"FORS targets per instance     : {fors_instance_targets:,}")
# ==> FORS targets per instance     : 57,344
print(f"WOTS+ targets per instance    : {wots_layer_targets}")
# ==> WOTS+ targets per instance    : 245
print(f"per-instance total            : {per_instance_total:,}")
# ==> per-instance total            : 57,589
print(f"multi-target advantage        : {adv:.1f} bits")
# ==> multi-target advantage        : 15.8 bits
print(f"effective security (no ADRS)  : {eff_no_adrs:.1f} bits")
# ==> effective security (no ADRS)  : 112.2 bits
print(f"single-target preimage bound  : {n_bits} bits")
# ==> single-target preimage bound  : 128 bits

Every Python block this chapter prints is also a standalone file in the companion repository, under chapter-code/ch18/, one file per block. Appendix C covers the clone and the environment they run on.

The 15.8-bit reduction would, if every target were reachable through one untweaked hash function, drop category 1 below its 128-bit reference. ADRS removes that simple $N$-target amplification: each tree node, chain step, and secret-value derivation carries the position it occupies, so an evaluation against one target is not also an evaluation against the others. The address names a position in the structure rather than counting calls, so a verifier recomputing a node uses the same address the signer did. At the algorithm level the address is 32 bytes. The SHA-2 parameter sets compress it to a 22-byte $\text{ADRS}^c$ before it enters the hash functions (National Institute of Standards and Technology, 2024). This does not zero the full SPHINCS+/SLH-DSA proof loss. It removes the dominant shared-function multi-target term. The remaining signing-query and construction loss is carried by the SPHINCS+ parameter search, whose sets FIPS 205 approves (Aumasson et al., 2020, sec. 7.1.2; National Institute of Standards and Technology, 2024).

The diagram below labels three attack surfaces on a stylized SLH-DSA hypertree: multi-target preimage on FORS leaf hashes (bottom), second-preimage on internal Merkle nodes (middle), and WOTS+ chain endpoint inversion (at each layer boundary).

Figure 18.1. Three attack regions on an SLH-DSA hypertree. Bottom (red): FORS multi-target preimage, the without-ADRS model, which ADRS collapses to single-target. Middle (amber): Merkle second-preimage. Top (teal): WOTS+ revealed-chain-value preimage. ADRS binds each hash call to a position (32-byte ADRS, 22-byte ADRS^c for SHA-2), removing the simple shared-function multi-target amplification.

Multi-target advantage, birthday bound, and quantum cost formulas

Convention: in the formulas below, $n$ denotes the hash output length in bits. FIPS 205 uses $n$ for the security parameter in bytes. The relationship is $n_{\text{bits}} = 8 \times n_{\text{bytes}}$. The code blocks use n_bytes and n_bits to distinguish the two.

A second convention: the “128-bit”, “192-bit”, and “256-bit” figures here are exponent shorthand. FIPS 205 does not claim a single-number bit security. Its category claim is comparative. Breaking a category 1, 3, or 5 set is claimed to need resources at least comparable to breaking a generic block cipher with a 128-, 192-, or 256-bit key, under realistic models of computation (National Institute of Standards and Technology, 2024).

Multi-target preimage advantage

Model $H : \{0,1\}^* \to \{0,1\}^n$ as an ideal $n$-bit hash. That is the random-function heuristic Boneh and Shoup make explicit, and one-wayness is a property the model supplies rather than a consequence of the output width (Sections 8.10.2 and 8.11.1 in Boneh & Shoup, 2023). Given one target $y$, a fresh query hits it with probability $1/2^n$, so preimage search takes $2^n$ evaluations in expectation. When the adversary holds $N$ distinct target digests $(y_1, \ldots, y_N)$ under the same function, a fresh query hits one of them with probability $N / 2^n$, so generic preimage search takes $2^n / N$ evaluations in expectation. The effective bit security drops from $n$ to $n - \log_2 N$.

$$\text{effective preimage security} = n - \log_2 N \text{ bits}$$

For preimage-style attacks in this chapter, $N$ counts FORS leaf hashes and WOTS+ revealed-chain-value targets. Internal Merkle nodes form a related but distinct second-preimage target surface, treated separately below.

FORS forgery probability

FORS forgery does not require inverting a hash. The adversary who has observed $q$ signatures on the same FORS instance has seen $q$ index sets, each containing $k$ indices from $\{0, \ldots, t-1\}$. Forgery succeeds if the adversary finds a message $m^*$ whose $k$ FORS indices are all covered by previously revealed leaves. A given index in one tree is missed by all $q$ signatures with probability $(1 - 1/t)^q$, so it is covered with probability $1 - (1 - 1/t)^q$. All $k$ trees are covered with probability $\left(1 - (1 - 1/t)^q\right)^k$, which reduces to $(q/t)^k$ only when $q \ll t$ (Aumasson et al., 2020). The approximation is loose for the “f” parameter sets, where $t$ is as small as 64.

This is the conditional coverage probability for a single fixed FORS instance reused $q$ times, against a fresh random candidate digest. It is not the full SLH-DSA key-level forgery probability. The SPHINCS+ interleaved-target-subset-resilience bound also weights the chance the digest selects that same instance out of $2^h$, sums over how many of the $q$ prior signatures landed on it, and charges the adversary’s offline $\text{H}_{msg}$ trials (Aumasson et al., 2020).

$$P_{\text{forgery}} = \left(1 - \left(1 - \tfrac{1}{t}\right)^{q}\right)^{k} \approx \left(\frac{q}{t}\right)^k \quad (q \ll t)$$

In SLH-DSA the hypertree leaf space is at least $2^{63}$ positions, and each position derives its own FORS instance. The birthday-paradox estimate $q^2 / 2^{64}$ for the expected number of FORS-instance collisions after $q$ signatures is intuition, not the FIPS lifetime limit. FIPS 205 designs its parameter sets to stay EUF-CMA secure for up to $2^{64}$ signatures per key (National Institute of Standards and Technology, 2024). At $h = 63$ that design limit averages about two signatures per position. Position reuse is real and is absorbed by the FORS few-time bound (Chapter 16), not assumed away. The formula above bounds the worst case for a single instance: if one FORS instance were reused $q$ times, how large can $q$ grow before forgery becomes feasible?

Grover’s algorithm and hash preimage

Grover’s algorithm reduces brute-force search from $O(2^n)$ classical evaluations to $O(2^{n/2})$ quantum evaluations (Grover, 1996). For an $n$-bit hash, quantum preimage search costs approximately $2^{n/2}$ quantum hash calls. NIST defines post-quantum security categories relative to the cost of breaking specific symmetric primitives: category 1 requires resources comparable to AES-128 key search, category 3 to AES-192, and category 5 to AES-256. The $2^{n/2}$ Grover bound is a first-order approximation. The actual quantum gate cost of each Grover iteration depends on the circuit depth of the hash or cipher evaluation (National Institute of Standards and Technology, 2024).

BHT quantum collision finding

The Brassard-Hoyer-Tapp (BHT) algorithm finds collisions in $O(2^{n/3})$ quantum evaluations using $O(2^{n/3})$ entries of quantum-accessible RAM (QRAM) (Brassard et al., 1998). For $n = 128$, this is approximately $2^{42.7}$ quantum evaluations, below the naive Grover exponent of $2^{64}$. That does not directly set the NIST category: the categories compare full attack resources against reference primitives under realistic models of computation, not naive quantum query exponents.

The $2^{n/3}$ figure is a query-complexity result in an idealized black-box model with substantial quantum-accessible memory. It is not a gate-cost estimate. NIST-style category comparisons do not simply replace the collision exponent $n/2$ by $n/3$ from that query count alone. Circuit depth, memory access, and the cost of fault-tolerant quantum memory all matter (National Institute of Standards and Technology, 2016). BHT is worth explaining, but it is not the category-setting bottleneck for SLH-DSA in the simplified model used here. That bottleneck is preimage resistance under Grover, not collision resistance (National Institute of Standards and Technology, 2024).

ADRS domain separation

Without address binding, one hash evaluation can be read as an attempt against a large population of structurally identical targets, and for $N$ targets the generic preimage exponent drops by about $\log_2 N$. SLH-DSA’s tweakable hash construction $\text{Tw}(\text{PK.seed}, \text{ADRS}, M)$, from the SPHINCS+ framework, feeds the public seed and a position address into every WOTS+, FORS, and Merkle-node hash call (Aumasson et al., 2020). The address encodes the hypertree layer, subtree index, key position, chain index, and step within the chain: 32 bytes at the algorithm level, a compressed 22-byte $\text{ADRS}^c$ in the SHA-2 instantiation (National Institute of Standards and Technology, 2024). A query for one address is not a query against every other target, so the simple $N$-target amplification does not apply.

This does not mean the proof has zero loss. Theorem 9.1 of the round-3 specification, stated in Section 9 and proved in Section 9.2, is the tight reduction that specification attempted, and it is not a statement about single-target hash security. The proof it came with did not survive, which the paragraph after the list takes up. The theorem assumes five things (Aumasson et al., 2020):

• $F$, $H$ and $T$ meet the post-quantum distinct-function multi-target second-preimage notion.
• $F$ satisfies the specification’s equation (14): every image value has at least two preimages.
• $\text{PRF}$ and $\text{PRF}_{\text{msg}}$ are post-quantum pseudorandom function families.
• The bitmask generator $\text{PRF}_{\text{BM}}$ is modelled as a quantum-accessible random oracle.
• $H_{\text{msg}}$ is post-quantum interleaved-target-subset resilient.

That proof was flawed. Kudinov, Kiktenko and Fedorov found the defect in 2020, in the security argument for the Winternitz one-time signature the construction is built on. It was never turned into an attack on SPHINCS+ (Hülsing & Kudinov, 2022). What survived was a non-tight reduction, which does not support the parameter sets the specification claims. Hülsing and Kudinov recovered a tight proof in 2022 without changing the scheme, at a loss of a factor $w$ against the originally claimed bound. It rests on a different hypothesis set. Theorem 3 of the paper keeps the two pseudorandom-function assumptions on $\text{PRF}$ and $\text{PRF}_{\text{msg}}$ and interleaved-target-subset resilience for message compression, and asks the tweakable hash functions for target-collision resistance, decisional second-preimage resistance, preimage resistance and undetectability in the paper’s single-function multi-target form: the adversary’s targets carry distinct tweaks, each function is a member of the collection that shares its public seed, and the target counts are set by the tree and chain parameters. Their results cover both the simple and the robust tweakable-hash constructions, with the preimage bound for the simple one resting on a conjecture carried over from the round-3 submission (Hülsing & Kudinov, 2022). So the five hypotheses above are what the round-3 theorem asserted it needed, and not the assumptions a current tight bound for SLH-DSA rests on.

The first is the formal counterpart of the paragraph above. ADRS is what makes a distinct-tweak multi-target assumption the right one to state, and it is what removes the dominant shared-function multi-target term. Two steps then separate the theorem from a claim about deployed SLH-DSA. Reading its bound as a security estimate against a single-target hash instantiation is one. Carrying it across to the final construction is the other, and the fourth hypothesis is where that bites: bitmasks belong to the robust variant, and FIPS 205 approves only the simple instances (Appendix A in National Institute of Standards and Technology, 2024). The remaining construction loss is absorbed by the parameter search behind those approved sets rather than by enlarging $n$ beyond the NIST category target (Aumasson et al., 2020, sec. 7.1.2).

Attack-by-attack cost analysis

Second-preimage attacks on Merkle trees

A Merkle tree internal node $v = H(\text{left} \| \text{right})$ is vulnerable to second-preimage attack: find a different pair $(\text{left}', \text{right}')$ with $H(\text{left}' \| \text{right}') = v$. If the adversary succeeds at any internal node, the adversary can substitute an entire subtree without invalidating the root.

Without domain separation, the same untweaked compression function is reused across tree levels. A candidate child pair that matches a node value is not syntactically tied to one level, so a second preimage found for a node is not bound to where it sits. With ADRS, the position address is part of the function input, so the same child pair is a different hash query at a different level, and a match at one level does not transfer.

import hashlib
import struct

left  = hashlib.sha256(b"node-left").digest()[:16]
right = hashlib.sha256(b"node-right").digest()[:16]

h_level1 = hashlib.sha256(left + right).hexdigest()[:16]
h_level2 = hashlib.sha256(left + right).hexdigest()[:16]
print(f"without ADRS: level 1 == level 2 ? {h_level1 == h_level2}")
# ==> without ADRS: level 1 == level 2 ? True

adrs1 = struct.pack(">I", 1) + b"\x00" * 28
adrs2 = struct.pack(">I", 2) + b"\x00" * 28
h_adrs1 = hashlib.sha256(adrs1 + left + right).hexdigest()[:16]
h_adrs2 = hashlib.sha256(adrs2 + left + right).hexdigest()[:16]
print(f"with ADRS:    level 1 == level 2 ? {h_adrs1 == h_adrs2}")
# ==> with ADRS:    level 1 == level 2 ? False

The block is a toy demonstration of cross-position separation, not a second-preimage attack simulation. Without ADRS, identical inputs at different tree levels produce identical hashes, so a second preimage found at one level transfers to any other. With ADRS, the level byte makes the inputs distinct, and the outputs differ.

Multi-target preimage across all FIPS 205 parameter sets

The table below computes the multi-target preimage advantage for all six FIPS 205 SHA-2 parameter sets. For each set, the per-FORS-instance target count is $k \cdot t$ (FORS leaf hashes) plus $d \cdot \ell$ (WOTS+ revealed chain values). The “no_adrs” column shows the effective preimage security if all targets were attackable simultaneously. The “adrs” column shows the ADRS-defended security (single-target). The “cat” column is the NIST security category.

import math

def wots_ell(n_bytes, w):
    lg_w = int(math.log2(w))
    ell_1 = math.ceil(8 * n_bytes / lg_w)
    mc = ell_1 * (w - 1)
    ell_2 = math.ceil((math.floor(math.log2(mc)) + 1) / lg_w)
    return ell_1 + ell_2

params = [
    ("SLH-DSA-SHA2-128s", 16, 63, 7, 12, 14, 16),
    ("SLH-DSA-SHA2-128f", 16, 66, 22, 6, 33, 16),
    ("SLH-DSA-SHA2-192s", 24, 63, 7, 14, 17, 16),
    ("SLH-DSA-SHA2-192f", 24, 66, 22, 8, 33, 16),
    ("SLH-DSA-SHA2-256s", 32, 64, 8, 14, 22, 16),
    ("SLH-DSA-SHA2-256f", 32, 68, 17, 9, 35, 16),
]

header = f"{'name':<22} {'n':>3} {'targets':>10} {'adv':>6} {'no_adrs':>8} {'adrs':>5} {'cat':>4}"
print(header)
for nm, n, h, d, a, k, w in params:
    t = 2**a
    ell = wots_ell(n, w)
    targets = k * t + d * ell
    adv = math.log2(targets)
    n_bits = 8 * n
    eff_no_adrs = n_bits - adv
    eff_adrs = n_bits
    cat_num = {128: 1, 192: 3, 256: 5}[n_bits]
    print(f"{nm:<22} {n_bits:>3} {targets:>10,} {adv:>6.1f} {eff_no_adrs:>8.1f} {eff_adrs:>5} {cat_num:>4}")
# ==> name                     n    targets    adv  no_adrs  adrs  cat
# ==> SLH-DSA-SHA2-128s      128     57,589   15.8    112.2   128    1
# ==> SLH-DSA-SHA2-128f      128      2,882   11.5    116.5   128    1
# ==> SLH-DSA-SHA2-192s      192    278,885   18.1    173.9   192    3
# ==> SLH-DSA-SHA2-192f      192      9,570   13.2    178.8   192    3
# ==> SLH-DSA-SHA2-256s      256    360,984   18.5    237.5   256    5
# ==> SLH-DSA-SHA2-256f      256     19,059   14.2    241.8   256    5

The “s” (small signature) variants expose more FORS targets than the “f” (fast) variants, but not because they use more trees. The “s” variants use larger FORS trees ($a = 12$ to $14$, so $t = 2^a$ from $4{,}096$ to $16{,}384$) and fewer of them ($k = 14$ to $22$). The “f” variants use small trees ($a = 6$ to $9$, $t = 64$ to $512$) and more of them ($k = 33$ to $35$). The per-instance target count $k \cdot t$ is larger for the “s” sets because $t = 2^a$ grows faster than $k$ shrinks.

If every target were attackable through one untweaked hash function, every parameter set would fall below the preimage-query count its category is named for: the 128-bit sets to 112 or 116 bits, the 256-bit sets to 237 or 241 bits. Those are query counts on one hash rather than category verdicts, which NIST prices as attack costs under a depth limit against its reference problems (National Institute of Standards and Technology, 2016). ADRS removes this shared-function multi-target term, so each set returns to its single-target preimage bound. The residual SPHINCS+/SLH-DSA proof loss is then carried by the SPHINCS+ parameter search behind the approved sets, not by enlarging $n$ (Aumasson et al., 2020, sec. 7.1.2).

Grover and BHT quantum cost estimates

The table below reports the classical and quantum attack costs for each hash output size used in FIPS 205. Classical preimage is $2^n$. Quantum preimage (Grover) is $2^{n/2}$. Classical collision (birthday) is $2^{n/2}$. BHT quantum collision is $2^{n/3}$ (with large quantum memory) (Brassard et al., 1998; Grover, 1996).

import math

header = f"{'n_bits':>10} {'class_pre':>10} {'quant_pre':>10} {'class_coll':>11} {'bht_coll':>10} {'nist_cat':>9}"
print(header)
for n_bits, cat in [(128, 1), (192, 3), (256, 5)]:
    cp = n_bits
    qp = n_bits // 2
    cc = n_bits // 2
    bht = n_bits / 3
    print(f"{n_bits:>10} {cp:>10} {qp:>10} {cc:>11} {bht:>10.1f} {cat:>9}")
# ==>     n_bits  class_pre  quant_pre  class_coll   bht_coll  nist_cat
# ==>        128        128         64          64       42.7         1
# ==>        192        192         96          96       64.0         3
# ==>        256        256        128         128       85.3         5

The BHT collision column shows that quantum collision finding would be cheaper than quantum preimage search ($2^{42.7}$ versus $2^{64}$ at $n = 128$) under an unrestricted black-box memory model. BHT’s query exponent alone does not determine a NIST category: NIST measures an attack against several resource metrics rather than one, and a comparison needs a concrete circuit and memory cost model, which the $2^{42.7}$ figure does not supply (National Institute of Standards and Technology, 2016). SLH-DSA’s security argument reduces to preimage resistance of the individual hash calls, not collision resistance. Collision resistance matters only for the internal Merkle nodes, where the adversary must find a second preimage (not a free collision) to substitute a subtree. The binding constraint is quantum preimage at $2^{n/2}$, which is the query count each category’s reference is named for. FIPS 205 assigns the categories themselves, on the full scheme rather than on this exponent (National Institute of Standards and Technology, 2024).

Chapter 36 (threat model) and Chapter 37 (signature surface) extend this analysis to L1 blockchain scale. ADRS removes the multi-target amplification inside a single signer’s keypair; a population of many independent signers adds a separate multi-key effect. FIPS 205 blunts it by adding PK.seed to PRF, a separate Appendix A change from adding $R$ and PK.seed to the SHA-2 $\text{H}_{msg}$ input against long-message multi-target second-preimage attacks (National Institute of Standards and Technology, 2024). Those chapters treat per-signer ADRS and the multi-key population effect as distinct, not as one analysis carried over unchanged.

SHA-256/SHA-512 split rationale

This split belongs to the SHA2 family alone. Within it, FIPS 205 uses SHA-256 for the F and PRF functions at every category, and moves H and $\text{T}_\ell$ to SHA-512 when $n \geq 24$ (security categories 3 and 5). The two message-hashing roles move as well, though not to a bare hash call: $\text{PRF}_{msg}$ becomes a truncated HMAC-SHA-512, and $\text{H}_{msg}$ an MGF1-SHA-512 expansion over a SHA-512 digest. The six SHAKE parameter sets do not split at all, instantiating all six roles with SHAKE256 at every category (National Institute of Standards and Technology, 2024).

A major reason is the chaining-value width. SHA-256 has a 256-bit internal state (chaining value). The H function in SLH-DSA hashes two $n$-byte inputs (the left and right children of a Merkle node), which for $n = 32$ is 64 bytes of payload. The tweakable hash construction prepends PK.seed and the compressed ADRS, so the total input spans multiple SHA-256 compression blocks. An adversary who targets the chaining value rather than the final hash output faces a multi-target second-preimage problem against the 256-bit chaining value, not the $8n$-bit hash output. For category 5 ($n = 32$, targeting 256-bit security), 256-bit chaining-value width provides zero margin.

FIPS 205 Appendix A records the SHA-512 substitution as a deliberate change from the SPHINCS+ submission, made after weaknesses were found in reaching category-5 security with SHA-256. A separate Appendix A change adds $R$ and PK.seed to the SHA-2 $\text{H}_{msg}$ input, to blunt multi-target long-message second-preimage attacks (National Institute of Standards and Technology, 2024).

SHA-512 has a 512-bit chaining value. For $n = 32$, the chaining-value width (512 bits) exceeds the security target (256 bits) by 256 bits, which absorbs the multi-target reduction comfortably. The F function still uses SHA-256 at every security category. Its SHA-256 input is PK.seed padded with zeros to a full 64-byte block, then the 22-byte compressed ADRS and one $n$-byte value. For $n \leq 32$ that message-dependent part fits in one further SHA-256 block, so the multi-block chaining-value concern that pushes H and $\text{T}_\ell$ to SHA-512 does not bite F.

FORS forgery and implementation attacks

FORS reuse thresholds across the parameter sets

FORS forgery does not require breaking the hash function. The adversary exploits index coverage: after observing enough signatures, the adversary may have seen every index in every FORS tree and can forge for any message. The probability depends on $k$ (number of trees), $t$ (leaves per tree), and $q$ (number of signatures on the same FORS instance).

At $q = 1$ (a single signature), the forgery probability is $(1/t)^k = 2^{-ak}$. The table below shows this probability for all six SHA-2 parameter sets. It then gives the exact first reuse count $q$ at which $P_{\text{forgery}}$ reaches $2^{-128}$ and $2^{-64}$, found by binary search on the exact coverage formula, not the $q \ll t$ approximation.

import math

params_fors = [
    ("SLH-DSA-128s", 14, 12),
    ("SLH-DSA-128f", 33, 6),
    ("SLH-DSA-192s", 17, 14),
    ("SLH-DSA-192f", 33, 8),
    ("SLH-DSA-256s", 22, 14),
    ("SLH-DSA-256f", 35, 9),
]

def log2_fors_forgery(q, k, t):
    if q == 0:
        return float("-inf")
    log_miss = q * math.log1p(-1.0 / t)   # ln (1 - 1/t)^q
    covered = -math.expm1(log_miss)        # 1 - (1 - 1/t)^q
    return k * math.log2(covered)

def first_q_at_or_above(k, t, threshold_bits):
    lo, hi = 0, 1
    while log2_fors_forgery(hi, k, t) < -threshold_bits:
        hi *= 2
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if log2_fors_forgery(mid, k, t) < -threshold_bits:
            lo = mid
        else:
            hi = mid
    return hi

print("single-signature forgery: log2(P) = -a*k")
header = f"{'name':<16} {'k':>3} {'a':>3} {'t':>6} {'log2_P':>8}"
print(header)
for nm, k, a in params_fors:
    t = 2**a
    print(f"{nm:<16} {k:>3} {a:>3} {t:>6} {-a*k:>8}")
print()
print("exact first q with P >= 2^-128 and >= 2^-64")
header2 = f"{'name':<16} {'k':>3} {'t':>6} {'q@2^-128':>9} {'q@2^-64':>9}"
print(header2)
for nm, k, a in params_fors:
    t = 2**a
    q128 = first_q_at_or_above(k, t, 128)
    q64 = first_q_at_or_above(k, t, 64)
    print(f"{nm:<16} {k:>3} {t:>6} {q128:>9} {q64:>9}")
# ==> single-signature forgery: log2(P) = -a*k
# ==> name               k   a      t   log2_P
# ==> SLH-DSA-128s      14  12   4096     -168
# ==> SLH-DSA-128f      33   6     64     -198
# ==> SLH-DSA-192s      17  14  16384     -238
# ==> SLH-DSA-192f      33   8    256     -264
# ==> SLH-DSA-256s      22  14  16384     -308
# ==> SLH-DSA-256f      35   9    512     -315
# ==>
# ==> exact first q with P >= 2^-128 and >= 2^-64
# ==> name               k      t  q@2^-128   q@2^-64
# ==> SLH-DSA-128s      14   4096         8       176
# ==> SLH-DSA-128f      33     64         5        20
# ==> SLH-DSA-192s      17  16384        89      1253
# ==> SLH-DSA-192f      33    256        18        78
# ==> SLH-DSA-256s      22  16384       293      2341
# ==> SLH-DSA-256f      35    512        43       170

The single-signature forgery probabilities are far below the security targets: $2^{-168}$ for SLH-DSA-128s versus the $2^{-128}$ target. The exact-threshold columns give the first integer $q$ for which $P_{\text{forgery}}$ is at or above the stated threshold. For SLH-DSA-128s, $q = 7$ is still below $2^{-128}$ while $q = 8$ is already above it, and $q = 176$ is the first to reach $2^{-64}$. The small-$t$ “f” sets cross sooner: $q = 5$ for SLH-DSA-128f at $2^{-128}$.

These $q$ are reuses of one fixed FORS instance, a local reuse intuition, not a key lifetime bound. The key-level forgery probability is the SPHINCS+ interleaved-target-subset-resilience bound, not this single-instance figure (Aumasson et al., 2020). What separates the two is the position distribution set out where this chapter first derived the coverage formula. Randomized message hashing spreads signatures across $2^h \geq 2^{63}$ positions, so the $2^{64}$-signature design limit averages about two per position rather than concentrating them on one.

(k, t) parameter tradeoffs

Larger $t$ (more leaves per FORS tree) exponentially reduces forgery probability at a given $q$, because each tree has more slots the adversary must cover. Larger $k$ (more trees) also exponentially reduces forgery probability, because the adversary must match all $k$ trees simultaneously. Both increase signature size: each FORS tree contributes $(1 + a) \cdot n$ bytes (one leaf value plus $a = \log_2 t$ authentication-path nodes), and there are $k$ trees. The tradeoff is visible in the “s” versus “f” split: the “s” variants use large $t$ and moderate $k$ for smaller signatures; the “f” variants use small $t$ and large $k$ for faster tree construction (fewer authentication-path nodes per tree).

Fault injection and timing side channels

Fault injection during WOTS+ chain computation can expose an earlier chain value. A chain runs to step $w - 1$ during key-generation and public-key recomputation, and to the message digit $d_i$ during signing. If a fault returns the value at step $j$ instead, the adversary hashes forward from it to reach any later step $j, \ldots, w - 1$. That forges a signature for any message whose digit at that position lies in the range. The countermeasure is verify-after-sign: after computing the WOTS+ signature, re-derive the public key from the signature using the verification algorithm and compare it against the stored public key. Any fault changes the intermediate value, which propagates to a different public key, and the check fails.

Fault attacks fall outside the ordinary EUF-CMA model. They are an implementation concern, and FIPS 205 explicitly directs implementers to protect SLH-DSA against side-channel and fault attacks (National Institute of Standards and Technology, 2024). Verify-after-sign catches simple local computation faults only when the recomputation is independent and covers the public-root path. It is not a complete defence: in the grafting attack below a faulted signature still verifies, so a real implementation also needs redundancy, duplicated or independently recomputed tree computations, or fault sensors.

Timing side channels arise because WOTS+ signing hashes chain $i$ exactly $d_i$ times, where $d_i$ is the $i$-th digit of the message encoding, including the checksum digits. The number of hash evaluations varies with the message digest and checksum, not with SK.seed, so the leak is about message-digest structure rather than the private key. In many signature APIs the message is already public, which limits the impact. It still matters when the signing input is confidential, when timing composes with a fault attack, or on shared hardware, so hardened implementations hash every chain $w - 1$ times regardless and select the correct intermediate value. The cost is $(w - 1) \cdot \ell$ hash evaluations per signature instead of the sum of the message digits, roughly doubling the signing time at $w = 16$.

Grafting: fault attacks on the deterministic randomizer

The fault attack above targets one WOTS+ chain. A grafting attack targets the hypertree. SLH-DSA derives the signing position from $\text{H}_{msg}(R, \text{PK.seed}, \text{PK.root}, M)$, where $R$ is a per-message randomizer. FIPS 205 sets $R$ in one of two ways (FIPS 205 §9.2) (National Institute of Standards and Technology, 2024). The hedged variant makes $R$ also depend on fresh per-signature randomness. The deterministic variant makes $R$ a pseudorandom function of the message and the secret key alone.

Castelnovi, Martinelli, and Prest showed the deterministic variant is fragile under fault injection (Castelnovi et al., 2018). The adversary requests two signatures on the same message. Determinism forces the same hypertree path each time, so one WOTS+ key signs the same subtree root on both runs. A fault injected into the upper-tree computation of the second run makes that key sign a different root. Two WOTS+ signatures on different roots under one key expose enough chain material to partially compromise that WOTS+ key, the same WOTS+ reuse weakness as Chapter 15. That gives the adversary WOTS+ signing capacity for a non-negligible fraction of candidate roots. Searching over attacker-built subtree roots turns that partial capacity into a universal forgery, and what it costs depends on the parameter set and on where the fault lands. Genêt’s analysis of SPHINCS+ prices the grafting search between $2^{30}$ and $2^{55}$ hash evaluations when the adversary holds one faulted signature alongside one valid one (Genêt, 2023). It falls to between $2^{13}$ and $2^{22}$ once thirty-two signatures under that key are available, which is the trade the original attack already offered.

SLH-DSA’s randomized index derivation does not by itself stop the attack. The hedged variant removes the simplest deterministic precondition: signing the same message twice no longer intentionally reuses one hypertree path, which makes the original deterministic attack path harder to stage. It is not a complete countermeasure. Genêt adapts the attack to SPHINCS+ with randomized signing, shows the faulty signatures can still verify (so the forgery is stealthy), and shows caching-based WOTS+ countermeasures can be bypassed with a feasible number of faulted queries (Genêt, 2023).

Both attacks above assume the adversary can reach the device. Boy, Purnal, Pätschke, Wilke, and Eisenbarth remove that assumption. Their SLasH-DSA paper, published in the proceedings of the second Microarchitecture Security Conference (uASC 2026) on 3 February 2026, stages the grafting attack entirely in software: Rowhammer-induced bit flips corrupt the signer’s internal state (Boy et al., 2026). The demonstration ran against OpenSSL 3.5.1 on a commodity desktop with a single DDR4-2133 DIMM, and the authors leave the attack’s effect on newer memory and its Rowhammer defences open. They report end-to-end universal forgery for SHAKE-128f in deterministic mode after about one hour of hammering and 151 seconds of post-processing, and for SHA2-128s and SHAKE-192f in randomized mode after about eight hours. Most of the remaining parameter sets get complexity estimates, and three set-and-mode combinations yielded too few faulted signatures to attack at all.

Two limits are worth stating plainly. This is an implementation-fault result, not a break of SLH-DSA’s EUF-CMA claim. OpenSSL’s answer to the disclosure was that fault attacks sit outside its threat model. And the forgeries under randomized signing are what the paragraph above predicts: hedging raised the cost of staging the fault from about one hour to about eight, and did not remove the attack. What changes is who the attacker has to be, from someone holding the device to someone running code on the same machine.

FIPS 205 makes the hedged variant the default and directs implementers to protect SLH-DSA against side-channel and fault attacks (National Institute of Standards and Technology, 2024). The practical lesson is stronger than hedging alone: pair the hedged variant with fault-detection redundancy or recomputation around the tree computations. Verify-after-sign helps only if it recomputes and compares the whole hypertree, not a single WOTS+ public key. Hedging is necessary hardening, not a full fault-attack defence (Genêt, 2023).

Caching is the redundancy that avoids recomputing the top layers at all, and the bypass above does not rule it out. Genêt’s bypass targets fixed-size branch caching, where cache misses force WOTS+ recomputation anyway. Caching whole layers is more effective the more layers it holds, and the binding cost is memory (Boy et al., 2026; Genêt, 2023). Azouaoui, Schneider, and Verbakel (preprint, April 2026) shrink that cost. Instead of storing each cached WOTS+ signature, they store a $g$-byte truncated hash of it and recompute-and-compare at signing time (Azouaoui et al., 2026). That trades certain detection for a probability tunable in $g$, and buys back enough memory to cache more layers, outperforming standard caching below roughly 256 kB of caching memory. Note the scope: this targets physical fault models on constrained devices, not the software-only threat above.

Security comparison across Part III

header = f"{'scheme':<24} {'pre_cl':>7} {'pre_qu':>7} {'coll_cl':>8} {'coll_qu':>8} {'state':>10}"
print(header)
rows = [
    ("Lamport+Merkle (n=32)", 256, 128, 128, 85, "stateful"),
    ("WOTS+/XMSS (n=32)",    256, 128, 128, 85, "stateful"),
    ("SLH-DSA-128s",          128,  64,  64, 42, "stateless"),
    ("SLH-DSA-192s",          192,  96,  96, 64, "stateless"),
    ("SLH-DSA-256s",          256, 128, 128, 85, "stateless"),
]
for nm, pc, pq, cc, cq, st in rows:
    print(f"{nm:<24} {pc:>7} {pq:>7} {cc:>8} {cq:>8} {st:>10}")
# ==> scheme                    pre_cl  pre_qu  coll_cl  coll_qu      state
# ==> Lamport+Merkle (n=32)        256     128      128       85   stateful
# ==> WOTS+/XMSS (n=32)            256     128      128       85   stateful
# ==> SLH-DSA-128s                 128      64       64       42  stateless
# ==> SLH-DSA-192s                 192      96       96       64  stateless
# ==> SLH-DSA-256s                 256     128      128       85  stateless

Lamport+Merkle and WOTS+/XMSS use $n = 32$ bytes (256 bits) and are stateful. Their preimage security is 256 bits classical and 128 bits quantum. SLH-DSA trades smaller $n$ values (as low as 16 bytes for category 1) and larger signatures for statelessness.

The quantum column is uniformly half the classical preimage column (Grover’s square-root speedup). This is simpler than the lattice case, where the gap between classical and quantum sieving costs is narrower and depends on the specific sieving algorithm. In the generic query model, Grover search halves the preimage-security exponent. No sub-exponential quantum algorithm is known for hash inversion.

Collision resistance is not the bottleneck. The ADRS construction ensures that collision attacks on internal nodes require second-preimage (not free collision), and second-preimage resistance matches preimage resistance at $2^n$ classical and $2^{n/2}$ quantum. In the simplified generic-attack model used in this chapter, the dominant category intuition is quantum preimage cost. The full SLH-DSA category claim also depends on the FORS few-time analysis, the hypertree position space, signing-query limits, and the concrete parameter search (Aumasson et al., 2020, sec. 7.1.2).

Where Part III ends and Part IV picks up

Part III built one family end to end and then attacked it. Chapter 14 started from Lamport’s one-time signature. Chapter 15 reached WOTS+ and XMSS, trading chain length against signature size, and then paid the state-management cost. Chapter 16 removed the state with FORS and a hypertree. Chapter 17 assembled the result as FIPS 205’s SLH-DSA, and this chapter priced the attacks against it. Every construction in those five chapters rests on hash-function properties and on nothing algebraic: the preimage resistance this chapter priced, plus the pseudorandom-function, multi-target second-preimage, and interleaved-target-subset-resilience properties named at the top of the chapter. There is no number-theoretic structure for an adversary to exploit, which is why the quantum column above is a clean square root rather than an open question.

Part IV asks what other assumptions buy. Chapter 19 introduces coding theory and the decoding problem behind it: easy with the code’s structure, exponential without it. Chapter 20 builds McEliece, proposed in 1978, the same year as RSA, and unbroken in its binary-Goppa line at suitable parameters ever since. Chapter 21 builds HQC, which NIST selected in March 2025 as an additional code-based KEM. The two spend the same budget in opposite directions: McEliece takes a 261 KB public key in exchange for a 96-byte ciphertext. Chapters 22 and 23 turn to isogenies, first the mathematics and then SQIsign, whose round-3 specification pairs an 83-byte public key with a 200-byte signature. Chapter 24 closes the survey with multivariate signatures. One warning crosses the boundary: the coding chapters, 19 through 21, write $n$ for the code length, where Part III wrote it for the hash output length, and Chapter 24 resets it again to the total number of variables in a multivariate system.

Read the two Parts as ends of a spectrum rather than as alternatives. Part III offers the most conservative assumption in the book at the largest signature sizes. Part IV offers sizes that hash-based constructions cannot reach, on assumptions with narrower deployment or shorter cryptanalytic exposure. Neither Part settles what to deploy. Part V does that work, taking SLH-DSA alongside ML-KEM and ML-DSA as given primitives and fitting them into inventories, protocols, and migration programs. The hash-based thread then resurfaces twice: Chapter 32 builds Merkle commitments as one of four commitment families for the zero-knowledge systems in Part VI, and Chapter 37 weighs SLH-DSA-128s against ML-DSA-65 for Layer-1 transaction signatures in Part VII.

Exercises

1. Multi-target advantage at custom parameters. Consider a hypothetical SLH-DSA-like scheme with $n = 20$ bytes, $k = 10$, $t = 1{,}024$ ($a = 10$), $d = 5$, and $w = 16$. Compute $\ell_1$, $\ell_2$, $\ell$, the FORS target count, the WOTS+ target count, the total multi-target advantage in bits, and the effective preimage security without ADRS. Would this parameter set still clear a 128-bit classical preimage-query target without ADRS, and what would a NIST category verdict need beyond that arithmetic?

2. FORS forgery threshold. For SLH-DSA-SHA2-128f ($k = 33$, $t = 64$), compute the number of FORS-instance reuses $q$ at which the forgery probability exceeds $2^{-64}$. Compare against SLH-DSA-SHA2-128s ($k = 14$, $t = 4{,}096$). Which parameter set tolerates more reuses before the $2^{-64}$ threshold, and by how much?

3. BHT collision and NIST categories. The BHT quantum collision-finding algorithm costs $O(2^{n/3})$ quantum evaluations for an $n$-bit hash. For $n = 128$, this is $2^{42.7}$, well below the $2^{64}$ idealized Grover query count for category 1. Explain in one paragraph why NIST does not reduce the category 1 floor to $2^{42.7}$. Your answer should address the quantum-memory (QRAM) model, circuit depth, and gate complexity.

4. Verify-after-sign cost. A WOTS+ implementation at $w = 16$ and $\ell = 35$ signs a message, then verifies the signature by hashing each chain value forward to the public key endpoint. If the message digits are $d_0, d_1, \ldots, d_{\ell-1}$, signing costs $\sum_i d_i$ hash evaluations and verification costs $\sum_i (w - 1 - d_i) = \ell(w-1) - \sum_i d_i$ evaluations. Show that verify-after-sign always costs exactly $\ell(w-1) = 525$ hash evaluations regardless of the message. Explain why this makes the combined sign-then-verify hash-call count constant with respect to the message. Note why a constant hash-call count is not full constant-time on its own: the implementation must also avoid releasing intermediate values or timing and must do the selection and comparison without data-dependent leakage.

Worked solutions and editorial notes for these exercises are in Appendix D, Chapter 18. A separate track, for rebuilding rather than reading. The package exercises/ch18-hash-cryptanalysis implements every number this chapter prints, because the chapter prints it. What it stubs is the five results stated in prose and never coded: the $q \ll t$ approximation to FORS coverage, the birthday estimate for repeated positions, the quantum form of the multi-target reduction, and Exercise 4’s two component costs. Run PQC_IMPL=exercises pytest tests/ch18 to grade your version against the suite that proves the reference one.

References

Aumasson, J.-P., Bernstein, D. J., Beullens, W., Dobraunig, C., Eichlseder, M., Fluhrer, S., Gazdag, S.-L., Hülsing, A., Kampanakis, P., Kölbl, S., Lange, T., Lauridsen, M. M., Mendel, F., Niederhagen, R., Rechberger, C., Rijneveld, J., Schwabe, P., & Westerbaan, B. (2020). SPHINCS+: Submission to the NIST Post-Quantum Cryptography Standardization Process. NIST PQC Round 3 submission; SPHINCS+ specification v3, 1 October 2020. https://sphincs.org/data/sphincs+-round3-specification.pdf

Azouaoui, M., Schneider, T., & Verbakel, D. (2026). A Scalable Fault Countermeasure for SLH-DSA: Trade-offs Between Memory, Performance, and Fault Resilience. Cryptology ePrint Archive, Paper 2026/759. https://eprint.iacr.org/2026/759

Boneh, D., & Shoup, V. (2023). A Graduate Course in Applied Cryptography (v0.6). Free online textbook. https://toc.cryptobook.us/

Boy, J., Purnal, A., Pätschke, A., Wilke, L., & Eisenbarth, T. (2026, February). SLasH-DSA: Breaking SLH-DSA Using an Extensible End-To-End Rowhammer Framework. Proceedings of the 2nd Microarchitecture Security Conference (uASC 2026). https://doi.org/10.46586/uasc.2026.009

Brassard, G., Høyer, P., & Tapp, A. (1998). Quantum Cryptanalysis of Hash and Claw-Free Functions. LATIN ’98: Theoretical Informatics, 1380, 163–169. https://doi.org/10.1007/bfb0054319

Castelnovi, L., Martinelli, A., & Prest, T. (2018). Grafting Trees: a Fault Attack against the SPHINCS Framework. Post-Quantum Cryptography – PQCrypto 2018, 10786, 165–184. https://doi.org/10.1007/978-3-319-79063-3_8

Genêt, A. (2023). On Protecting SPHINCS+ Against Fault Attacks. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2023(2), 80–114. https://doi.org/10.46586/tches.v2023.i2.80-114

Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), 212–219. https://doi.org/10.1145/237814.237866

Hülsing, A., & Kudinov, M. (2022). Recovering the Tight Security Proof of SPHINCS+. In S. Agrawal & D. Lin (Eds.), Advances in Cryptology – ASIACRYPT 2022, Part IV (Vol. 13794, pp. 3–33). Springer. https://doi.org/10.1007/978-3-031-22972-5_1

National Institute of Standards and Technology. (2016). Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. Call for Proposals, Section 4.A.5 (Security Strength Categories). https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf

National Institute of Standards and Technology. (2024). FIPS 205: Stateless Hash-Based Digital Signature Standard. Federal Information Processing Standards Publication. https://doi.org/10.6028/NIST.FIPS.205