Chapter 18: Hash-based signature cryptanalysis

Hülsing and Kudinov’s 2022 proof for SPHINCS+, which FIPS 205 cites for SLH-DSA’s security (National Institute of Standards and Technology, 2024, sec. 11), asks for specific properties of each function. Their Theorem 3 bounds a forger’s success probability by a sum of terms, each the insecurity of one function under one property, and the table gives each function the properties it is asked for (Theorem 3 in Hülsing & Kudinov, 2022).

Function	What it computes	What Theorem 3 asks of it
$\text{PRF}$	the WOTS+ and FORS secret values	pseudorandom-function security
$\text{PRF}_{\text{msg}}$	the randomizer $R$	pseudorandom-function security
$\text{H}_{msg}$	the message digest, which selects the FORS indices and the signing position	interleaved target subset resilience
$F$	each WOTS+ chain step and each FORS leaf	undetectability, target-collision resistance, preimage resistance and decisional second-preimage resistance
$H$	each Merkle node, from its two children	target-collision resistance
$\text{T}_\ell$	one value from the WOTS+ chain ends or from the FORS roots	target-collision resistance

The properties asked of $F$ , $H$ and $\text{T}_\ell$ are single-function multi-target ones: every target carries its own tweak, and the three functions share one public seed (Hülsing & Kudinov, 2022).

Each multi-target property is a game over many targets, each under its own tweak (Definitions 2 to 7 in Hülsing & Kudinov, 2022). Target-collision resistance: the adversary fixes its targets, an input under each tweak, before it learns the public seed, and must then find a different input with the same output as one of them under that target’s tweak. That asks for a second preimage of a target fixed in advance, not a free collision. Preimage resistance: the targets are the outputs on hidden random inputs, and the adversary must find an input that maps to one of them under its tweak. Undetectability: the adversary cannot tell the outputs on hidden random inputs from uniformly random strings. Decisional second-preimage resistance: the adversary must say whether one of its target inputs has a second preimage under that target’s tweak, and its advantage is measured against the trivial strategy of always answering yes (Definition 6 in Hülsing & Kudinov, 2022).

Interleaved target subset resilience is asked of $\text{H}_{msg}$ , which maps a message and its randomizer to a FORS instance and one index in each of that instance’s $k$ trees. After seeing the selections of many signed messages, the adversary cannot find a new message and randomizer that select an instance in which each of the $k$ indices they select was already selected by some earlier message (Aumasson et al., 2022, sec. 9.1). Where Theorem 3 asks $F$ , $H$ and $\text{T}_\ell$ for the properties above, the round-3 theorem later in this chapter asks them for distinct-function multi-target second-preimage resistance. Its targets are random inputs to distinct, predefined members of a function family, and the adversary cannot find a second preimage of any one of them under its own member (Aumasson et al., 2022, sec. 9.1).

FIPS 205 approves only the simple instances (Appendix A in National Institute of Standards and Technology, 2024). For them, the properties in the table can be derived from the assumption that the hash function behaves like a random oracle even to a quantum adversary that queries it in superposition (Aumasson et al., 2022, sec. 9). That is the quantum random-oracle model (QROM), which Chapter 5’s note on the random-oracle model introduces and Chapter 33 defines, and Hülsing and Kudinov analyze the simple construction in it (Hülsing & Kudinov, 2022, p. 6). The model is an idealization, not a proof about SHA-2 or SHAKE. The tight estimates also keep stated conjectures, among them three that Hülsing and Kudinov’s Table 1 marks. Its generic bounds for decisional second-preimage resistance and interleaved target subset resilience are conjectured, and the one for preimage resistance rests on a conjecture (Table 1 in Hülsing & Kudinov, 2022). The robust instances, which FIPS 205 does not approve, assume a random oracle only for the function that generates their bitmasks (Aumasson et al., 2022, sec. 9).

The round-3 specification’s earlier theorem, and the flaw in its proof, come later in this chapter. The attacks this chapter prices are stated in three simpler terms. 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')$ .

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, finds a preimage of the corresponding leaf hash $F(\text{sk})$ , since the verifier accepts any preimage of that leaf hash in place of the secret. The first node of each FORS authentication path is such a leaf hash, the sibling of the revealed index. The other FORS authentication-path nodes and the XMSS ones belong to the Merkle second-preimage surface, analyzed separately under attack-by-attack cost analysis. All $k \cdot a$ FORS and $h$ XMSS authentication nodes count toward signature size. The $k$ FORS sibling leaf hashes are already included in the $k \cdot t$ preimage targets below. The remaining authentication nodes add no targets to that model.

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.

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 = w.bit_length() - 1                 # log2(w), since w is a power of two
ell_1 = (8 * n_bytes + lg_w - 1) // lg_w  # ceil(8 * n_bytes / lg_w)
mc = ell_1 * (w - 1)
ell_2 = (mc.bit_length() + lg_w - 1) // lg_w  # bit_length() is floor(log2) + 1
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 indices whose secret values earlier signatures revealed in the corresponding tree. 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 gives the average fresh-target coverage for one fixed FORS instance, conditioned on $q$ uses and averaged over independent uniform index selections. It does not describe the total key lifetime or the worst realized exposure history. It answers one question: 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. NIST’s preliminary guidance caps circuit depth and prices quantum attacks in gates. Under the cap, Grover’s long serial computation has to run as many smaller parallel instances, which makes the speedup less dramatic (National Institute of Standards and Technology, 2016).

BHT quantum collision finding

The Brassard-Høyer-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. NIST measures an attack against every resource metric it deems relevant to practical security, with circuit depth capped (National Institute of Standards and Technology, 2016), and a query count leaves out the cost of the $2^{n/3}$ entries BHT reads in superposition. 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, as the discussion of the Grover and BHT cost estimates below explains.

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, and this subsection closes on its flaw and its repair. 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 modeled as a quantum-accessible random oracle.
$H_{\text{msg}}$ is post-quantum interleaved-target-subset resilient.

The round-3 list’s distinct-function multi-target second-preimage hypothesis is the formal counterpart of the address binding that opens this subsection. 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 bitmask 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).

The round-3 theorem’s 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.

Hülsing and Kudinov’s Theorem 3 rests on the hypotheses the table at the top of this chapter lists, with target counts set by the tree and chain parameters. Their results cover both the simple and the robust tweakable-hash constructions, with the tight preimage bound for the simple one resting on a conjecture about multi-target decisional second-preimage resistance from the 2019 paper that set out the SPHINCS+ framework (Hülsing & Kudinov, 2022). So the five hypotheses above are what the round-3 theorem asserted it needed, and not the assumptions Hülsing and Kudinov’s 2022 tight bound rests on.

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 = w.bit_length() - 1                 # log2(w), since w is a power of two
    ell_1 = (8 * n_bytes + lg_w - 1) // lg_w  # ceil(8 * n_bytes / lg_w)
    mc = ell_1 * (w - 1)
    ell_2 = (mc.bit_length() + lg_w - 1) // lg_w  # bit_length() is floor(log2) + 1
    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 does not rest on collision resistance. It uses the properties Hülsing and Kudinov’s proof asks for, listed at the top of this chapter. FIPS 205 says that collisions on SLH-DSA’s internal hash functions are believed to have no adverse effect on its security (National Institute of Standards and Technology, 2024, sec. 10.2). Substituting a subtree is no exception: the forged computation must reconnect to a node the fixed public root authenticates, which means matching an existing hash target with a different input rather than finding a free collision. 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).

Address separation within a keypair and attacks involving many keypairs are distinct issues. FIPS 205 Appendix A lists adding PK.seed to PRF, to mitigate multi-key attacks, among its differences from the round-3 specification, separately from adding $R$ and PK.seed to the MGF1 input of the SHA-2 $\text{H}_{msg}$ against long-message multi-target second-preimage attacks (National Institute of Standards and Technology, 2024).

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 MGF1 input of the SHA-2 $\text{H}_{msg}$ , 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) reduces forgery probability at a given $q$ , because each tree has more slots the adversary must cover. With $q$ much smaller than $t$ the probability is about $(q/t)^k$ , so it falls polynomially in $t$ and exponentially in $a = \log_2 t$ . Larger $k$ (more trees) reduces it exponentially, because the adversary must match all $k$ trees simultaneously. Both increase signature size: each FORS tree contributes $(1 + a) \cdot n$ bytes (one secret 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 defense: 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-induced WOTS+ reuse in the hypertree

The defense against grafting is redundancy: duplicated or independently recomputed tree computations, compared before the signature is released and covering each subtree root the signature commits to (Castelnovi et al., 2018, sec. 3.4). Hedged signing, FIPS 205’s default, mixes fresh randomness into each signature’s randomizer $R$ (National Institute of Standards and Technology, 2024, sec. 9.2), and it does not stop the attack on its own. Nor does verify-after-sign, since the faulted signature usually verifies. Genêt still recommends verifying, because a signature that fails to verify shows that a fault occurred (Genêt, 2023, sec. 7).

Genêt calls redundancy the current best solution. Of randomized signing he writes: “Unless an adversary can query the signature for any message, randomized signing may be disabled as such measure is not a reliable way to prevent the fault attack” (Genêt, 2023, sec. 7). His judgment concerns hedging as a fault countermeasure only, and FIPS 205 says it should be used on platforms where side-channel attacks are a concern (National Institute of Standards and Technology, 2024, sec. 9.2). Like the chain fault above, grafting is an implementation attack outside the EUF-CMA model, and FIPS 205 directs implementers to protect SLH-DSA against fault attacks (National Institute of Standards and Technology, 2024).

Each WOTS+ key in the hypertree signs the value computed below it, an XMSS root or, at the bottom layer, a FORS public key. It always signs the same value, so an intact signer’s reuse reveals nothing new (Chapter 16). A fault in that computation makes the key sign a second value: the chain reuse Chapter 15’s “Leaf reuse” block prints on its toy key. The adversary can then sign a non-negligible fraction of candidate roots, and a search over subtrees it builds yields a universal forgery (Castelnovi et al., 2018, sec. 3). The original attack drew the reuse from deterministic signing, where $R$ , and so the signing position, depends only on the message and the secret key. A fault in the second of two signatures on one message then changes the value signed. Hedging removes that precondition but not the attack, since upper-layer WOTS+ keys lie on many signing paths (Genêt, 2023).

Three results take the attack from a fault model to software running beside the signer:

Year and work	Fault source	Signing mode	Result
2018, Castelnovi, Martinelli and Prest (Castelnovi et al., 2018)	One fault in the computation of a subtree, as a model	Deterministic	Universal forgery against SPHINCS, Gravity-SPHINCS and the 2017 SPHINCS+ submission. The faulted signatures always verify (Remark 2 in Castelnovi et al., 2018, sec. 3.2)
2023, Genêt (Genêt, 2023)	One random fault per signing, in a hash call chosen uniformly, from clock glitches in his experiments (Sections 3, 4.1 and 6.1 in Genêt, 2023)	Randomized	The attack survives randomized signing, at the costs below. A random fault leaves a verifiable signature 86 to 95 percent of the time (Table 4 in Genêt, 2023, sec. 4.1)
2026, Boy, Purnal, Pätschke, Wilke and Eisenbarth (Boy et al., 2026)	Rowhammer, from user-level code on the signer’s logical CPU core (Boy et al., 2026, sec. 3)	Deterministic and randomized	End-to-end universal forgery against OpenSSL 3.5.1 on a commodity desktop (Table 2 in Boy et al., 2026)

Genêt gives average costs for a fault in a FORS tree or in an XMSS tree below the top layer. The grafting step costs $2^{30}$ to $2^{55}$ hash evaluations with two different WOTS+ signatures from the compromised key, and $2^{13}$ to $2^{22}$ with thirty-two. Steering each forged message onto the grafted subtree costs a further $2^{3}$ to $2^{68}$ (Table 2 in Genêt, 2023). Only two of his six parameter sets, 192f and 256s, are FIPS 205’s (Tables 2 and 3 in Genêt, 2023; Table 2 in National Institute of Standards and Technology, 2024, sec. 11).

The Rowhammer attack forged SHAKE-128f signatures in deterministic mode after a one-hour campaign, and SHA2-128s and SHAKE-192f signatures in randomized mode after eight-hour ones (Table 2 in Boy et al., 2026). Its authors ran one campaign length per mode, so the gap does not measure how much hedging slows the attack (Boy et al., 2026, sec. 8). It assumes a replica of the target system to prepare on, DDR4 memory, high-resolution timers and a way to influence when the signer allocates the memory under attack (Boy et al., 2026, sec. 3). The authors leave open how it fares on newer hardware and newer software (Boy et al., 2026, sec. 8.1). OpenSSL answered their disclosure by placing fault attacks outside its threat model (Boy et al., 2026, sec. 1.2).

Caching is the other countermeasure studied. A signer that reads a WOTS+ signature back from memory instead of recomputing it cannot be faulted into making that key sign a second root, and it signs faster for it (Genêt, 2023, sec. 5). Memory confines caching to the top few layers, and Genêt finds that neither form he studies protects SPHINCS+ properly (Sections 5 and 5.1 in Genêt, 2023). Compressed caching, from a 2026 preprint motivated by physical faults, stores a short hash of each cached WOTS+ signature and checks the freshly computed signature against it. It detects a fault rather than ruling one out, and it outperforms standard caching below about 256 kB of caching memory (Sections 1, 3.2 and 7 in Azouaoui et al., 2026).

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 fixed public root makes a substituted subtree reconnect to the authenticated computation, so an attack on an internal node needs a second preimage of an existing node rather than a free collision. Second-preimage resistance matches preimage resistance at $2^n$ classical and $2^{n/2}$ quantum. ADRS separates positions, so one hash evaluation cannot be tested unchanged against every position’s target, though the formal security statement remains a distinct-tweak multi-target one. 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, and the top of this chapter lists the ones Hülsing and Kudinov’s 2022 proof asks of the last of them, SLH-DSA. 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, and exponential for generic decoding without it, though an adversary may also attack the hidden structure itself. Chapter 20 builds McEliece, proposed in 1978, the same year as RSA. No practical attack has broken its binary-Goppa line at suitable parameters since, but the structural analyses of 2026 call for a fresh assessment of the submitted parameters, and Chapter 20’s status notes report those analyses. 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, or for one circulant block of a quasi-cyclic code, whereas Part III wrote it for the hash output length. Chapter 24 resets $n$ 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

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?
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?
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 why NIST does not reduce the category 1 floor to $2^{42.7}$ . Start from what category 1 and an SLH-DSA forgery each require, then address the quantum-memory (QRAM) model, circuit depth, and gate complexity.
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

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. (2022). SPHINCS+: Submission to the NIST Post-Quantum Project, v.3.1. SPHINCS+ specification v3.1, 10 June 2022. https://sphincs.org/data/sphincs+-r3.1-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

Last updated: Oct 21, 2026