Appendix D: Solutions for Chapter 18

This page collects solutions and editorial notes for the exercises in Chapter 18: Hash-based signature cryptanalysis. Compute and derivation exercises have worked solutions; open-ended exercises have an editorial note describing what a strong answer addresses.

Exercise 1

WOTS+ at $n = 20, w = 16$: $\ell_1 = \lceil 160/4 \rceil = 40$. The largest checksum $40 \cdot 15 = 600$ needs $\lfloor \log_2 600 \rfloor + 1 = 10$ bits, so $\ell_2 = \lceil 10/4 \rceil = 3$ and $\ell = 43$.

The target counts follow the chapter’s model: $k \cdot t$ FORS leaf hashes inside one instance’s position space, plus the $d \cdot \ell$ WOTS+ chain values the corresponding hypertree layer reveals. That is $10 \cdot 1024 = 10{,}240$ FORS targets and $5 \cdot 43 = 215$ WOTS+ targets, so $10{,}455$ in total. The multi-target advantage is $\log_2 10{,}455 = 13.4$ bits, subtracted from the $8n = 160$-bit hash output, leaving $146.6$ bits classical. The quantum figure halves what is left rather than subtracting the advantage from $80$: Grover over $N$ marked items in a space of $2^{160}$ costs about $2^{(160 - 13.4)/2}$, so $73.3$ bits.

So this set still clears a 128-bit classical preimage-query target without ADRS, and the reason is headroom rather than a small target population. A 160-bit output against a 128-bit target starts 32 bits clear, and a 13.4-bit reduction does not close that gap. SLH-DSA-SHA2-128s starts with no headroom at all: its output is 128 bits against the same target, so the 15.8-bit reduction in the chapter’s table drops it to 112.2 and it falls short.

A NIST category verdict is a different claim and this arithmetic does not reach it. NIST prices a category as the computational resources an attack needs against a reference problem, under a depth limit and in gate counts, so placing a hypothetical scheme in a category takes the whole construction and a cost analysis of the attack on it, not an idealized query count against one hash (National Institute of Standards and Technology, 2016). What the numbers above establish is the query target, which is what the exercise asks for.

That is not an argument that ADRS is unnecessary here. With ADRS every hash call uses a domain-separating address, so the shared-function amplification disappears whatever the headroom. What remains is the explicit reduction loss carried by the SPHINCS+ parameter search behind the approved sets, not a target count (Aumasson et al., 2020, sec. 7.1.2).

import math
n_bytes, k, t, d, w = 20, 10, 1024, 5, 16
# Integers only, as FIPS 205 requires of SLH-DSA. bit_length() is floor(log2) + 1.
lg_w = w.bit_length() - 1
l1 = (8 * n_bytes + lg_w - 1) // lg_w
l2 = ((l1 * (w - 1)).bit_length() + lg_w - 1) // lg_w
ell = l1 + l2
fors_targets = k * t
wots_targets = d * ell
total = fors_targets + wots_targets
adv = math.log2(total)
print(l1, l2, ell, fors_targets, wots_targets, total)
# ==> 40 3 43 10240 215 10455
print(round(adv, 1), round(160 - adv, 1), round((160 - adv) / 2, 1))
# ==> 13.4 146.6 73.3

Exercise 2

The chapter’s exact-threshold table answers this directly. The first $q$ whose forgery probability reaches $2^{-64}$ is $q = 20$ for SLH-DSA-128f and $q = 176$ for SLH-DSA-128s, so the ‘s’ set tolerates $176 / 20 = 8.8$ times more reuses.

Working it from the quoted approximation instead is worth doing, because it fails here in exactly the way the chapter warns about. Setting $(q/t)^k = 2^{-64}$ gives $q = t \cdot 2^{-64/k}$, so $64 \cdot 2^{-64/33} = 16.7$ for 128f and $4096 \cdot 2^{-64/14} = 172.3$ for 128s. The 128s figure lands within about 2% of the exact 176. The 128f figure is 17% low, because $(q/t)^k$ assumes $q \ll t$ and 128f has $t = 64$, so $q = 20$ is already a third of the tree. The approximation over-estimates coverage at every $q$, which is why it reaches any threshold sooner and reports the smaller $q$.

The ‘s’ design buys that reuse tolerance with a larger $t$: 4,096 leaves per FORS tree against 128f’s 64. The extra depth is cheap, because the FORS contribution to a signature is $k(a + 1)n$ bytes and $a$ grows only as $\log_2 t$. The ‘f’ design gives the tolerance up for signing speed, spreading its hypertree over 22 layers of height 3 rather than 7 of height 9. It pays for that speed in signature size: 17,088 bytes against 7,856 (National Institute of Standards and Technology, 2024).

import math

def log2_p(q, k, t):
    return k * math.log2(-math.expm1(q * math.log1p(-1.0 / t)))

for name, k, t in (("128f", 33, 64), ("128s", 14, 4096)):
    approx = t * 2 ** (-64 / k)
    exact = next(q for q in range(1, 10_000) if log2_p(q, k, t) >= -64)
    print(f"{name}: exact {exact}, approx {approx:.1f}")
# ==> 128f: exact 20, approx 16.7
# ==> 128s: exact 176, approx 172.3

Exercise 3

The floor does not move, first, because a free collision is not the task either side of the comparison asks for. Category 1 is defined by key search on a 128-bit block cipher such as AES-128: any attack on a category 1 scheme must need resources comparable to or greater than that search (National Institute of Standards and Technology, 2016). A collision on SLH-DSA’s internal hash functions is not a forgery either. FIPS 205 says that even if collisions on the functions that instantiate them are feasible, there is believed to be no adverse effect on SLH-DSA’s security (National Institute of Standards and Technology, 2024, sec. 10.2). SLH-DSA’s security argument rests on the properties the chapter’s opening table lists, not on collision resistance. So even in BHT’s query model, $2^{42.7}$ queries for a collision would neither forge an SLH-DSA signature nor search AES-128’s key space.

The exception FIPS 205 names for forgery is pre-hashing: when the signer signs a digest of the content, a collision on the digest function can forge messages. That is why it requires the digest function to give at least 128 bits of classical security against collisions at category 1 (National Institute of Standards and Technology, 2024, sec. 10.2).

The resource models are a separate, second point. BHT’s $2^{n/3}$ counts queries, and it assumes about $2^{n/3}$ classically computed images that the algorithm reads in superposition (Brassard et al., 1998). At $n = 128$ that is $2^{42.7}$ entries of 128 bits, roughly 110 terabytes of quantum-accessible classical memory, which the query count does not charge for. NIST’s preliminary guidance prices quantum attacks in gates, with the circuit depth capped at a value MAXDEPTH between $2^{40}$ and $2^{96}$, and its estimate for the category 1 reference is $2^{170}/\text{MAXDEPTH}$ quantum gates or $2^{143}$ classical gates (National Institute of Standards and Technology, 2016). It notes that the categories give substantially more quantum security than a naive analysis suggests, because Grover’s long serial computation has to be split into many smaller parallel runs (National Institute of Standards and Technology, 2016).

For collision search, NIST’s table gives a classical figure only, $2^{146}$ gates for SHA3-256 (National Institute of Standards and Technology, 2016). A BHT query count cannot be set against those figures until its gates, depth and memory accesses are priced the same way, and pricing them would still not turn a collision into an AES-128 key search.

Exercise 4

Total cost is $\sum_i d_i + \sum_i (w - 1 - d_i) = \sum_i (d_i + w - 1 - d_i) = \sum_i (w - 1) = \ell (w - 1)$. The $d_i$ terms cancel exactly. At $w = 16, \ell = 35$: $35 \cdot 15 = 525$ hash evaluations regardless of which digits the message produces.

The cancellation is worth separating from what it buys. Verify-after-sign is a fault countermeasure: it re-derives the public key from the signature it just produced and compares, so a fault that moved a chain value fails the check. The constant total is a property of its cost, not its purpose.

It is not by itself a timing countermeasure. An observer who can separate the signing half from the verification half still sees $\sum_i d_i$, and those digits come from the message digest. The chapter’s timing defense is the other one: walk every chain the full $w - 1$ steps and select the value needed, which pays the same $\ell(w - 1)$ but pays it inside signing. Even that is not full constant-time on its own, as the exercise notes, because the selection and the comparison must also run without data-dependent branching or memory access.

Running the code

The fuller versions of these routines are in the hash_cryptanalysis package under solutions/ch18-hash-cryptanalysis. It carries the parameter table, the signature accounting, the FORS coverage formulas, the generic quantum cost model, and the countermeasure pricing, each as a function rather than as a script. From a clone of the companion repository, pytest tests/ch18 runs its suite. Appendix C has the setup.

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

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

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