Tweakable Hashes and Multi-Target Attacks: What SLH-DSA's Addresses, Public Seed and Proof Actually Buy

Ask most engineers what SLH-DSA assumes and the answer is quick: nothing but a good hash function. That answer is right and incomplete. A hash function with a 128-bit output resists a second-preimage search on one given value for roughly 2 to the power 128 guesses, but a single SLH-DSA key does not present one value to an attacker. Over its permitted lifetime it reveals tens of sextillions of them, and the generic search does not care which one it hits. If nothing in the design separated those values from each other, the scheme's own scale would quietly subtract seventy bits from the security its parameter name promises. The 32-byte address and the public seed that appear in every call to F, H and T in FIPS 205 are the engineering that prevents this, and the security proof leans on them in a precise and auditable way. This piece follows that mechanism from the counting argument, through the proof's assumptions, to the practical rules it imposes on anyone shipping or reviewing an implementation.

Many targets make a generic attack cheaper

Start with the attacker that hash-based signatures must survive: one that treats the hash function as a black box and simply evaluates it on fresh inputs, hoping to land on a useful output. Two properties matter. Preimage resistance says that given an output, finding any input that produces it is hard. Second-preimage resistance says that given an input, finding a different input with the same output is hard. For an ideal function with an n-byte output, each evaluation succeeds against one specified target with probability about one in 2 to the power 8n, so 128-bit outputs cost roughly 2 to the power 128 evaluations per target.

The arithmetic changes as soon as the attacker is satisfied by any one of many targets. If T distinct outputs are on the table and success against any of them is enough, every evaluation is a lottery ticket against all T at once, and the expected work falls by a factor of T. Hulsing, Rijneveld and Song called this the multi-target problem and showed that earlier hash-based signature schemes paid for it with a security loss that grew with performance parameters such as total tree height. Their remedy, developed for a stateful scheme they called XMSS-T, is the ancestor of what FIPS 205 does on every call.

Why would one success be enough? Because a hash-based signature is a web of commitments: a chain value commits to the secret beneath it, a tree node commits to its two children, a public key commits to everything below. A second preimage for any committed value is a place where the attacker can substitute material of their own choosing while the commitments above still check out. The security reduction treats every such value as a potential failure point, so the number of values exposed is, quite literally, the number of lottery tickets the generic attacker is holding.

Quantum search changes the exponent but not the structure. Grover-style search finds a preimage of one target in roughly the square root of the classical work, and multi-target quantum search gains from many targets in a related way. The generic bounds that SPHINCS+ relies on are stated for both classical and quantum adversaries, which is why the parameter sets aim at security categories defined against both.

Counting the targets one FIPS 205 key exposes

To see the size of the problem, count what one key reveals when it is used to its full budget. Take SLH-DSA-SHA2-128s from Table 2 of FIPS 205: 16-byte hash outputs, a hypertree of 7 layers with trees of height 9, and a forest of 14 FORS trees of height 12 at the bottom. Section 3 of the standard notes that a key of this family conceptually contains 2 to the power 63 FORS key pairs, and the standard sizes every parameter set for at most 2 to the power 64 signatures per key.

Each signature carries, among other things, 7 Winternitz one-time signatures of 35 chain values each, 7 authentication paths of 9 nodes, 14 revealed FORS secret values and 14 FORS authentication paths of 12 nodes. That is roughly five hundred hash-derived values per signature. Upper-layer values repeat across signatures because the same upper trees certify many lower ones, but the bottom layer and the FORS forest are spread across 2 to the power 63 instances and are mostly fresh. A careful but deliberately rough count, which is our own order-of-magnitude analysis rather than a figure from the standard, puts the distinct hash outputs exposed by one key over its full budget somewhere between 2 to the power 68 and 2 to the power 72, depending on how one treats repeated and internal values.

Now apply the multi-target arithmetic. If every one of those outputs were produced by the same unkeyed 128-bit function, a classical attacker satisfied by any of them would need on the order of 2 to the power 56 to 2 to the power 60 evaluations, nowhere near the category-1 target of resisting attacks that cost as much as recovering an AES-128 key. The scheme would be undone by its own statelessness: the very abundance of one-time and few-time keys that removes the need to remember state would also hand the attacker an enormous target list.

The count matters for a second reason. It explains why SLH-DSA can use n equal to 16 bytes at category 1 at all. SPHINCS, the 2015 predecessor, was already designed to be collision-resilient: it rests on second-preimage resistance and pseudorandomness rather than collision resistance, which the SPHINCS+ specification credits with allowing a shorter output at the same security level and with relying on a far weaker assumption. Targeted properties are cheaper per byte, but the same specification names their price, multi-target attacks, and the next section shows how the design pays it.

Tweakable hash functions: one name, many independent functions

The remedy, formalised by Bernstein, Hulsing, Kolbl, Niederhagen, Rijneveld and Schwabe in the SPHINCS+ framework paper, is the tweakable hash function: a hash that takes, besides its message, a public parameter and a tweak, and behaves as a different function for every distinct tweak. In FIPS 205 the public parameter is PK.seed, the random n-byte value stored in every public key, and the tweak is ADRS, a 32-byte address. The three functions that build chains and trees, F, H and T, all take both, and Section 4.2 of the standard states plainly that the address is used in these functions to mitigate multi-target attacks.

The address is a coordinate, not a counter. It names the layer of the hypertree, the tree within that layer, the type of computation (a chain step, a chain compression, a tree node, a FORS tree, a FORS root compression, or one of two secret-generation types), and then the position inside that structure: which key pair, which chain, which step of the chain, or which height and index in a tree. The standard requires a different address for every call to every function within the structure, so no two positions in a key ever evaluate the same function.

The effect on the attacker is exactly what the counting argument needs. A guess evaluated at one address says nothing about any other address, because each address selects what is, for the purposes of the analysis, an independent function. In the SPHINCS+ specification's generic analysis, the success probability of a classical attacker making q queries against distinct-function multi-target second-preimage resistance is about q plus one over 2 to the power 8n, and the quantum version is about the square of that numerator over the same denominator, independent of the number of targets. The 2 to the power 70 lottery tickets collapse into a single ticket.

There is a subtle assumption buried here that the SPHINCS+ specification spells out. SLH-DSA does not derive a fresh pseudorandom key for every call; it simply prefixes the message with PK.seed and the address. For that to act like independent keying, there must be no exponentially large subset of inputs, defined by the prefix, on which finding second preimages is easy. The designers argue this holds for any Merkle-Damgard or sponge hash whose compression function or permutation behaves like a random function, which is the same kind of belief that justifies using the hash at all.

The public seed: from many targets in one key to many keys

Addresses separate positions inside one key. They do nothing, on their own, to separate two different keys, because two key pairs have identical address spaces: layer 3, tree 17, chain 5, step 9 exists in every SLH-DSA key of the same parameter set. If two keys used the same function at the same address, an attacker who wanted to forge for any key in a large population could pool targets across keys and recover the multi-target factor that the address was supposed to remove. Section 3 of FIPS 205 gives PK.seed exactly this job: it provides domain separation between different SLH-DSA key pairs.

The standard then went one step further than the round-three SPHINCS+ submission. Appendix A of FIPS 205 lists the change: PK.seed was added as an input to PRF, the function that expands the secret seed into every WOTS+ and FORS secret value, in order to mitigate multi-key attacks, and two new address types, WOTS_PRF and FORS_PRF, were defined so secret-value generation has its own coordinates. The interpretation, ours rather than the standard's wording, is that without the public seed a guess at a secret seed could be checked against every key in a population at once, because the derived values would depend only on the guess and the address. With the public seed mixed in, a guess is tied to one key, and the work of attacking a million keys is a million times the work of attacking one.

This multi-key setting is not hypothetical for anyone building agent infrastructure. A model hub, a tool marketplace or a plug-in registry is precisely a large population of independently generated signing keys, and the attacker's goal is often any one of them, the weakest publisher rather than a specific one. The public seed is what makes the security of each publisher's key independent of how many other publishers exist.

Key generation carries the matching obligation. FIPS 205 requires the three seeds, PK.seed, SK.seed and SK.prf, to be fresh outputs of an approved random bit generator with security strength at least 8n bits. A fleet that derives seeds from a shared value, or clones a template key, gives up the separation the public seed exists to provide.

Simple versus robust: the variant the standard kept

SPHINCS+ originally offered two ways to build each tweakable hash. The robust instances generate pseudorandom bitmasks from the public seed and the address and XOR them into the message before hashing. The simple instances, added in the round-two update and modelled on the approach of the LMS stateful scheme, omit the bitmasks and hash the public seed, the address and the message directly. Combined with six parameter shapes and three hash families, SHA-2, SHAKE and Haraka, the submission defined 36 instances.

The two variants differ in what the proof has to assume. For robust instances, the required properties follow from standard-model properties of the hash, plus a random-oracle assumption limited to the function that generates bitmasks; the specification notes that if all bitmasks were stored in the public key, the proof would hold in the standard model. For simple instances, the properties are derived from modelling the whole hash as a random oracle that even a quantum adversary can query in superposition, the quantum-accessible random oracle model.

FIPS 205 approves only 12 of the 36 instances: the six parameter shapes in SHA-2 and SHAKE form, and only the simple variants. The trade is speed for idealisation. Simple instances skip the bitmask generation that robust instances perform on every call, and the SHA-2 simple instances additionally benefit from a precomputation trick that reduces most chain steps to a single compression-function call. The cost is that the formal argument now relies on the hash behaving like a random function in the strongest sense.

How uncomfortable should that be? The SPHINCS+ designers answer in their discussion of SHAKE: cryptanalysts hunt for any feasibly detectable non-random behaviour, not only for the textbook properties, and a faster-than-generic attack on the properties SLH-DSA needs would itself be a major advance in hash cryptanalysis. That is an argument from the state of the art, not a proof, and a careful reader should file it as such.

What the proof needs, property by property

The tight reduction for SPHINCS+, as presented in the version 3.1 specification and the Hulsing and Kudinov paper it cites, bounds a forger's success by a sum of advantages against a short list of properties. Each item names one function and one job, which makes the list useful as an audit map: if a property fails, you know which part of the construction is exposed.

Two pseudorandomness assumptions cover the secrets. PRF must be a pseudorandom function so that every WOTS+ and FORS secret derived from SK.seed is indistinguishable from fresh randomness; PRF_msg must be pseudorandom so the per-message randomiser R hides nothing about SK.prf. One property covers message hashing: H_msg must be interleaved target subset resilient, meaning an attacker cannot efficiently find a message whose digest selects FORS positions entirely covered by positions already revealed in earlier signatures.

The remaining properties concern the chain and tree functions, and the vocabulary is worth defining precisely. Single-function multi-target means one function family, many targets, attacker chooses which to attack. Target-collision resistance asks the attacker to commit to an input before learning the tweak or key and then find a colliding input. Decisional second-preimage resistance, introduced by Bernstein and Hulsing in 2019, asks whether the attacker can even decide if a given input has a second preimage, which is the bridge that lets second-preimage resistance imply preimage resistance for length-preserving functions such as F. Undetectability says the image of a random input looks like a random element of the range. F needs all three multi-target forms: undetectability, target-collision resistance and decisional second-preimage resistance. H and T need multi-target target-collision resistance.

Two things about this list are easy to miss. First, collision resistance does not appear: no part of the reduction asks for a collision-resistant F, H or T, which is why 16-byte outputs can reach category 1. Second, the single place where the number of signatures enters the bound is the H_msg property, which is why the signature budget is a FORS question and not a tree question.

Reading the bound as an engineer

A sum of advantages can feel abstract, but it reads naturally as a failure map. Each term is a way the real system could fall short of the idealised one, and each points at something an implementer or reviewer controls. The pseudorandomness terms are about how secrets are made, so they implicate seed generation and any deviation from the standard PRF. The subset-resilience term is about how many signatures one key produces, so it implicates the signing volume and the number of replicas sharing a key. The multi-target terms are about the chain and tree hashing itself, so they implicate the address discipline and the choice of hash family.

This reading also explains why some well-intentioned optimisations are dangerous. Caching or reusing a hash state across calls is harmless when the prefix truly is identical, which is what the SHA-2 instances exploit with the public seed padded to a full block. Shortening or merging address fields to save bytes, or reusing an address for two different inputs because the code path looked equivalent, silently merges two functions into one and reintroduces a multi-target factor that no test vector will reveal, because test vectors check outputs, not the independence of functions.

The map is equally useful for prioritising review time. A defect in seed generation compromises every key from that generator; a defect in addressing weakens every key from that library; an excess of signatures weakens one key at a time and degrades gradually. Those are different blast radii, and an assurance plan for long-lived keys should spend its effort in that order.

A proof that broke, and what its repair cost

Hash-based signatures are often called the scheme with the cleanest security story, so it is instructive that its tight proof has a repair history. The version 3.1 specification is candid about it: several attempts at proving tight security were shown to be flawed after publication, and the hard part was always the Winternitz one-time signature used inside the scheme, analysed across many instances at once.

There were two issues. An earlier version of the reduction assumed that every possible input to F has at least one other input with the same output, a sibling, which does not hold for a random function and therefore should not hold for a good hash. A later flaw, pointed out in 2020 by Kudinov, Kiktenko and Fedorov, concerned the argument that if an output has two preimages the attacker cannot tell which one the signer used. That argument works for uniformly random inputs without side information, but inside a Winternitz chain the input to one step is the output of the previous step, which is side information.

Hulsing and Kudinov's 2022 paper restored a tight proof by describing the Winternitz variant on its own, as WOTS-TW, and proving it secure against non-adaptive chosen-message attacks in which the attacker learns the public key only after its signature query, which turns out to be enough for the full scheme. The new bound is almost the old one, with a loss of a factor of w, the Winternitz parameter, which is 16 in every FIPS 205 parameter set. A factor of 16 is 4 bits of proven margin. In 2024 Barbosa and co-authors reconstructed that proof in the EasyCrypt proof assistant, so the tight bound is now machine-checked.

Three lessons follow. None of the flaws ever became an attack; the specification stresses that the actual security of the scheme was never challenged and that a non-tight Winternitz proof still applied. Tightness is a parameter-selection input: a loose proof forces either larger parameters or a stated reliance on the absence of better attacks. And idealised assumptions such as the random-oracle model are only as reassuring as the reduction that uses them, which is why the formal verification step is worth more than its modest headline.

Why this matters for agents, model releases and their implementers

For an AI-agent ecosystem the multi-target and multi-key arguments map onto concrete objects. A model-release key may sign for a decade; a tool or plug-in registry may hold thousands of publisher keys; an agent runtime may verify signatures from all of them. The address and the public seed are what let each of those keys keep its stated category regardless of how long it has signed and how many neighbours it has. They are also invisible in normal operation, which is exactly why they are at risk from well-meant shortcuts.

The practical rules come straight from the standard. Section 3.2 tells module designers not to expose WOTS+, XMSS, FORS or hypertree components as stand-alone interfaces, because they are not approved for that use and their security depends on the surrounding address discipline. Section 3.1 requires public-key validation to check the 2n-byte length and requires that assurance of private-key possession by regeneration recompute PK.root from SK.seed and PK.seed. A fleet should treat PK.seed generation with the same care as SK.seed, since a duplicated public seed across keys reintroduces exactly the pooling the seed exists to prevent.

One compatibility trap is specific to keys made before the standard. Appendix A of FIPS 205 records that the method for extracting FORS indices from the message digest was changed and is not compatible with the round-three reference implementation, besides the PRF and hash-function changes already described. Artefacts signed with a pre-standard SPHINCS+ library, which some early post-quantum pilots used for model and package signing, will not verify under a conforming FIPS 205 verifier and should be re-signed rather than accommodated with a compatibility switch.

Finally, the proof says nothing about physical leakage. Multi-target hygiene protects against generic computation; it does not stop a fault or a power trace from exposing secrets during signing. Those are separate threat models with separate countermeasures, and a review that checks addresses has not thereby checked the signer's hardware.

A word on the limits of this argument. The target count in this article is an order-of-magnitude estimate built from the structure in Table 2 of FIPS 205; a different but reasonable counting convention moves it by a few powers of two without changing the conclusion. The generic bounds quoted are those stated in the SPHINCS+ version 3.1 specification for idealised functions; they describe what is achievable when the hash behaves randomly, not a guarantee about any concrete hash. The simple instances' reliance on the quantum-accessible random oracle model is an idealisation that the community accepts on cryptanalytic evidence rather than on reduction to a standard assumption. The formally verified proof certifies the reduction, not the implementation; conformance testing, side-channel protection and fault protection are separate obligations.

Practitioner Toolkit

Copy-paste, strictly defensive artifacts you can use today. Nothing here attacks a real system.

seen = empty map from (function_name, address_bytes) to input_bytes
wrap F, H, T_l, PRF with recorder:
    on call(name, pk_seed, adrs, data):
        key = (name, adrs)
        if key in seen and seen[key] != data:
            fail('address reused for a different input at ' + name)
        seen[key] = data
keypair = test_keygen(fresh_random_seeds)
signature = slh_sign(test_message, keypair.private, hedged = true)
assert slh_verify(test_message, signature, keypair.public)
report count(seen) as distinct addressed calls
# Expectation: zero failures; repeated identical recomputation is allowed

slh_dsa_publisher_keys:
  standard: FIPS 205
  accepted_parameter_sets: [SLH-DSA-SHA2-128s, SLH-DSA-SHAKE-128s, SLH-DSA-SHA2-192s, SLH-DSA-SHAKE-192s]
  reject:
    - duplicate_pk_seed_across_publishers
    - pre_standard_sphincs_plus_signatures
    - public_key_length_not_2n
  onboarding_checks:
    pk_seed_uniqueness: registry_wide
    conformance_statement: required
  rationale: per-key security must not depend on the size of the publisher population

Glossary

Multi-target attack

A generic attack that succeeds if it breaks any one of many targets, reducing the work by roughly the number of targets.

Tweakable hash function

A hash that takes a public parameter and a tweak besides its message and acts as an independent function for each distinct tweak.

PK.seed

The random public n-byte seed in every SLH-DSA public key, used to separate the hash functions of one key pair from every other.

ADRS (address)

The 32-byte coordinate passed to SLH-DSA's hash functions naming the layer, tree, computation type and position of each call.

Second-preimage resistance

The property that, given an input, it is hard to find a different input with the same hash output.

Target-collision resistance

The property that an attacker who commits to an input before learning the key or tweak cannot then find another input colliding with it.

Decisional second-preimage resistance

The property that an attacker cannot efficiently decide whether a given input has a second preimage; it links second-preimage and preimage resistance.

Interleaved target subset resilience

The property of H_msg that no efficient attacker finds a message whose FORS positions are all already revealed by earlier signatures.

Quantum-accessible random oracle model

An idealisation in which a hash is a random function that quantum adversaries may query in superposition.

Tight reduction

A security proof whose bound loses little or nothing relative to the underlying assumptions, so parameters need no extra margin for proof loss.

References

1. NIST FIPS 205, Stateless Hash-Based Digital Signature Standard (2024)
2. SPHINCS+ Submission to the NIST post-quantum project, specification v3.1 (2022)
3. Bernstein, Hulsing, Kolbl, Niederhagen, Rijneveld and Schwabe, The SPHINCS+ Signature Framework (ACM CCS 2019)
4. Hulsing, Rijneveld and Song, Mitigating Multi-Target Attacks in Hash-based Signatures (PKC 2016)
5. Bernstein and Hulsing, Decisional second-preimage resistance: When does SPR imply PRE? (ASIACRYPT 2019)
6. Kudinov, Kiktenko and Fedorov, Security analysis of the W-OTS+ signature scheme: Updating security bounds (2020)
7. Hulsing and Kudinov, Recovering the Tight Security Proof of SPHINCS+ (ASIACRYPT 2022)
8. Barbosa et al., A Tight Security Proof for SPHINCS+, Formally Verified (2024)