Fault Attacks on SLH-DSA: Tree Grafting, Why Verify-After-Sign Misses It, and the Countermeasures That Hold

The security argument for SLH-DSA assumes something so obvious that it is rarely stated: the signer computes correctly. Every one of the scheme's thousands of hash evaluations per signature must produce the value the specification says it produces, every time. Under that assumption the hypertree is safe even though each of its one-time keys signs over and over, because it always signs the same thing. Break the assumption once, through a glitch on a power line, a laser pulse, a marginal transistor or a stray particle, and a one-time key may sign a second, different value. For a stateful scheme that would be a recognisable error; for SLH-DSA it can be a universal forgery, produced from a signature that looks perfectly valid. Fault attacks are therefore not a footnote to hash-based signatures. They are the place where the scheme's elegant statelessness depends most heavily on the physical machine.

The invariant faults break

In one sentence, the construction is a hypertree of d layers of Merkle trees whose leaves are Winternitz one-time keys, each upper-layer key signing the root of a tree below it and each bottom-layer key signing the public key of a few-time FORS instance. Every value a hypertree key signs, a subtree root or a FORS public key, is fixed by the secret seed. The same upper-layer key is used by every signature whose path runs through it, and it produces byte-identical signatures each time, so reuse reveals nothing.

This is the invariant: within one SLH-DSA key, every one-time key only ever signs one value. The security proof relies on it implicitly, because it treats the hypertree as a collection of one-time keys each used on a single message. FIPS 205 recognises the physical dimension in Section 3.2, noting that care must be taken to protect implementations against side-channel and fault attacks and citing the literature on both.

A fault that changes any value on the way to a signed root, or the signing computation itself, can produce a Winternitz signature on a value other than the one the key always signs. From that moment the key has signed two different messages, and a Winternitz key that has signed two different messages is no longer a one-time key in any useful sense.

From one faulty signature to a grafted tree

Castelnovi, Martinelli and Prest described the consequence in 2018 as tree grafting, the first fault attack on the framework shared by SPHINCS, Gravity-SPHINCS and SPHINCS+. Their summary is stark: the attack allows forging a signature on any message at the cost of a single faulted message, under a reasonable fault model, and it does not depend on which hash function is used.

The mechanism, described here conceptually, follows from how Winternitz signatures work. Each signature reveals one intermediate point on each of a key's hash chains, and anyone can hash forward from a revealed point. With two signatures on different values under the same key, an attacker knows, for every chain, the earlier of the two revealed points, and can therefore produce valid chain values for any digit at or after it. That is not enough to sign arbitrary values, because the Winternitz checksum pushes some digits the other way, but it is enough to sign some values. The attacker then constructs subtrees of their own, with their own one-time and few-time keys, until one has a root the compromised Winternitz key can now sign. Grafted under the genuine upper layers, that subtree carries a valid authentication path to the genuine public root.

Turning a grafted branch into signatures on chosen messages uses a freedom that SLH-DSA gives every signer: the randomiser R is not checked by the verifier, so a forger can try values of R until a message's digest routes through the grafted branch. The cost of that search falls as the graft moves up the hypertree, and the published attack includes a trade-off in which a few more faulty signatures reduce the computation further. None of this needs the secret seed. The attacker never learns the key; they acquire a branch of it.

Where a fault does the most damage, and what caching can afford

Not every fault is equally valuable to an attacker, and the structure of the hypertree says which ones matter most. A grafted branch is only useful for messages whose digest routes through it, and the forger searches over randomisers until one does. A graft just below the top layer covers a large fraction of the key: in SLH-DSA-128s the top tree has 512 leaves, so a branch under one of them covers one part in 512 of all bottom leaves, and a forger needs on the order of 512 randomiser trials to route a chosen message into it. A graft one layer lower covers one part in 2 to the power 18, and each further layer divides the coverage by another 512. This arithmetic, our own reading of the published construction, explains why the published attack includes a trade-off between faults and computation, and why faults affecting the upper layers are the ones to fear most.

The same structure sets the price of caching. Each Winternitz signature in a 128s key is 35 chain values of 16 bytes, 560 bytes in all. Caching every top-layer signature means storing 512 of them, about 287 kilobytes, a trivial cost for a signing service. Caching the next layer down means 2 to the power 18 signatures, about 147 megabytes; the layer below that would need roughly 75 gigabytes, and the bottom layers are beyond any storage. Caching therefore protects exactly the layers where a graft is cheapest to exploit and stops long before the bottom.

That is why caching is worth doing and why it is not enough. It removes the most valuable fault targets for a few hundred kilobytes, which makes it a sensible first layer for any long-lived signing key. But Genet's 2023 analysis is explicit that a single random bit flip anywhere in signing can damage the guarantees and that caching intermediate Winternitz signatures is circumvented in an active attack with a tolerable number of queries. Faults below the cached layers, and faults in the computation of FORS public keys that the bottom Winternitz keys sign, remain open unless the computation itself is checked.

Why the faulty signature still verifies

A natural first defence is to verify every signature before releasing it. The evidence says this does not work against grafting. Amiet, Leuenberger, Curiger and Zbinden, reporting the first FPGA implementation of SPHINCS+ in 2020, found that a sign-then-verify operation does not detect a faulty signature, and that only a full replication of the hardware might make detection possible. Genet's 2023 analysis states the same conclusion in general form: the faulty signature produced by a single random bit flip cannot be detected by the verification procedure. Castelnovi and co-authors had already noted that faulted signatures remain valid, which makes the attack stealthy.

The intuition is that verification checks consistency, not correctness. A signature carries the authentication paths the verifier uses to recompute each subtree root. If a fault corrupts part of the lower tree whose values are also carried in the signature, the verifier recomputes the same corrupted root the signer computed, checks the Winternitz signature on that corrupted root, finds it genuine, and continues upward to the true public root. Every step is consistent. The signature is valid; it is simply a valid signature that should never have existed, because it exposes a one-time key on a second value.

This is a recurring lesson in fault analysis and it is sharper here than for most schemes. A post-signing verification catches faults that produce garbage; it cannot catch faults that produce a different, internally consistent object. The useful check is not whether the output verifies, but whether it equals what an independent computation of the same inputs would have produced.

The evidence: from a glitch on a microcontroller to a random bit flip

The attack moved from theory to practice quickly. Genet, Kannwischer, Pelletier and McLauchlan mounted it in 2018 against the original SPHINCS on an Arduino Due board with an ARM Cortex-M3 microcontroller, using a simple voltage glitch, and collected enough faulty signatures to build a universal forgery within seconds. They noted that the attack applies to all the hash-based candidates of the time, stateful and stateless alike, including XMSS, LMS, SPHINCS+ and Gravity-SPHINCS.

Amiet and co-authors then found the same class of weakness in hardware they had built for speed: their FPGA design of SPHINCS+ was about a hundred times faster than the reference software, and a fault-injection attack broke it completely, collecting enough private information to forge a signature in seconds on their setup. Speed and exposure went together; the faster the implementation, the quicker an attacker could gather the faulty outputs they needed.

Genet's 2023 study in IACR Transactions on Cryptographic Hardware and Embedded Systems made the most consequential point for operators who do not face a deliberate attacker at all. It adapted the original attack to SPHINCS+ with randomised signing, extended it to any combination of faulty and valid signatures, and showed that with high probability the security guarantees of SPHINCS+ drop significantly when a single random bit flip occurs anywhere in the signing procedure. A fault does not have to be aimed to be useful to an attacker; it only has to happen and be published.

Countermeasures that do not hold

Three intuitive defences fail or fall short, and each failure teaches something. Verify-after-sign fails for the reason above: consistent faults produce valid signatures. Randomised signing, the hedged mode that FIPS 205 makes the default and recommends where side channels are a concern, also does not stop grafting; Genet's 2023 paper explicitly adapts the attack to SPHINCS+ reinforced with randomised signing. Randomisation changes which FORS instance a message uses, but the upper layers of the hypertree are shared by vast numbers of signatures regardless of R, and they are where grafting does its damage.

The third defence, caching, is the instructive one. Genet and co-authors showed in 2018 that caching one-time signatures entirely prevents the attack for stateful schemes such as XMSS and LMS: if each upper-layer Winternitz signature is computed once, stored and reused, no later fault can make that key sign anything else. The same idea applies to SLH-DSA only partly. The top layer has a single tree and its signatures can be cached, but each lower layer has exponentially more trees, and storing every Winternitz signature in the hypertree is out of the question. Genet's 2023 analysis found that caching intermediate Winternitz signatures offers only marginally greater protection against unintentional faults and is circumvented with a tolerable number of queries in an active attack.

The pattern across all three is that a defence must compare the computation against an independent source of truth. Verification uses the computation's own outputs as truth; randomisation changes inputs but not the invariant; caching supplies independent truth but only for the few keys it can store.

Countermeasures that hold

Genet's 2023 recommendation for real-world deployments of SPHINCS+ is to implement redundancy checks, and the SPHINCS+ specification makes the matching statement from the designers' side: implementations without dedicated protection against fault injection should be expected to be vulnerable, and deployments where an attacker can inject faults require specially protected implementations, typically with countermeasures at the hardware level. Redundancy means computing the values that a one-time key will sign, subtree roots and FORS public keys, more than once, independently, and releasing the signature only if the computations agree. Amiet and co-authors' observation that full hardware replication might detect the fault is the same idea taken to its physical extreme.

Redundancy is not free. Duplicating a computation roughly doubles the cost of whatever is duplicated, and tree building dominates signing time, so a fully redundant signer is roughly half as fast. That is usually an acceptable price for the keys where fault resistance matters most, which sign rarely: model-release roots, firmware and tool-registry keys. Implementers can also target the redundancy, for example by recomputing each subtree root that is about to be signed rather than every intermediate value, accepting that the residual risk must then be argued carefully.

Physical and operational controls complete the picture. Signing should happen inside hardware with fault sensors and tamper response where an attacker might reach the device; rate limiting and refusal to sign attacker-chosen messages in bulk reduce how many faulty outputs an attacker can harvest; and side-channel protection deserves separate attention. Kannwischer and co-authors showed in 2018 that differential power analysis could recover at least a 32-bit chunk of the secret key of a hardware SPHINCS-256 implementation because of its stateless construction, and the SPHINCS+ specification notes that deterministic signing lets an attacker collect repeated traces of the same computation, which is why hedged signing helps against power analysis even though it does not help against grafting.

Whatever the countermeasure, it must be tested, and fault protection is unusually easy to get wrong silently: a redundancy check that compares a value with itself, or that the compiler optimises away, passes every functional test. The practical remedy is fault simulation in software. A test build of the signer injects a single bit flip into a chosen intermediate value, a chain step, a tree node or a FORS leaf, and the test asserts that the signer refuses to release the signature. Running that test across every class of intermediate value, and across optimisation levels, is the closest a software team can get to the evidence a hardware fault-injection laboratory would produce, and it costs nothing at release time.

A detection idea: auditing what a key has already signed

The invariant that faults break is also checkable from the outside, which suggests a detection control we have not seen proposed in the cited work and offer here as our own synthesis. Because every one-time key in the hypertree signs exactly one value, any two valid signatures from the same SLH-DSA key whose paths pass through the same upper-layer key must contain byte-identical Winternitz signatures at that layer. The tree and leaf indices are recomputed by any verifier from the message digest, so an auditor holding a log of a key's issued signatures can group them by layer and position and check that every group is identical.

A mismatch is proof that the key signed two different values with one one-time key: exactly the event grafting needs. Coverage is best where it matters most. The top layer has only one tree, so with enough signatures its keys recur constantly; lower layers recur less often, and the audit says nothing about a fault whose output was never logged. The control therefore complements prevention rather than replacing it, but it turns a stealthy failure into a detectable one for any organisation that already records its signatures, for example in a transparency log of model or package releases.

The audit is cheap: it parses signatures and compares bytes, with no secret material and no extra signing. A mismatch should be treated as a key compromise, because once a faulty signature is public, anyone may hold the material to graft.

groups = map from (layer, tree_index, leaf_index) to wots_signature_bytes
for each (message, signature) in signature_log(public_key):
    require slh_verify(message, signature, public_key)
    path = recompute_indices_from_digest(message, signature.R, public_key)
    for layer in 0 .. d - 1:
        position = path.position_at(layer)
        wots = signature.hypertree_layer(layer).wots_bytes
        if position in groups and groups[position] != wots:
            alert('one-time key signed two values at layer', layer, position)
            treat_as_key_compromise(public_key)
        groups[position] = wots

Why this matters for agents and AI infrastructure

Agent ecosystems put SLH-DSA keys in two kinds of place, and fault risk looks different in each. Release and registry keys for models and tools live in data-centre signing services and hardware security modules. There, deliberate glitching is unlikely, but accidental faults are not: engineers at Facebook, now Meta, reported in 2021 that testing across hundreds of thousands of machines found hundreds of CPUs that silently corrupted computation without raising hardware errors. Genet's result means that a single such corruption during an SLH-DSA signing, published as an ordinary signature, can weaken the release key for everyone who verifies it. Redundant computation in the signing service and a consistency audit over the release log are proportionate responses for keys that are meant to last a decade.

Keys on devices are the second place: robots, edge agents and embedded controllers that sign their own telemetry, attestations or actions. There, physical access is part of the threat model, and the published attacks were demonstrated on exactly that class of hardware. For such devices the choice is between protected hardware with redundancy and fault sensors, or a different signature for the high-volume device role and SLH-DSA kept for rarely used, well-protected keys elsewhere.

A word on the limits of this analysis. Claims about the published attacks are drawn from their abstracts and from FIPS 205 and the SPHINCS+ specification, not from re-running the attacks; the explanation of why faulty signatures verify is our reading of the mechanism consistent with those sources; the consistency audit is our proposal and its coverage depends on how many signatures a log contains. The article deliberately omits fault-injection parameters and any step-by-step procedure.

Practitioner Toolkit

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

test_key = keygen(test_seeds)
for value_class in [wots_chain_step, xmss_tree_node, fors_leaf, fors_root, subtree_root]:
    for trial in 1 .. 50:
        signer = build_signer(test_key, redundancy = on, fault_hook = flip_one_bit(value_class, random_position()))
        result = signer.sign(random_test_message(), hedged = true)
        assert result == REFUSED_FAULT_DETECTED, 'redundancy missed a fault in ' + value_class
# repeat for every optimisation level the release build may use
assert build_signer(test_key, redundancy = on).sign(m) verifies   # no false positives

slh_dsa_consistency_audit:
  schedule: on_every_new_signature_and_daily_full_scan
  on_mismatch:
    classify: key_compromise
    actions:
      - stop_signing_with_key
      - publish_revocation
      - rotate_to_successor_key
      - re_sign_artefacts_since_last_clean_audit
      - inspect_signer_hardware_for_faults
  rationale: one-time-key reuse in the hypertree enables grafting by anyone holding the signatures

Glossary

Fault attack

An attack that induces computation errors, by glitching power or clock, lasers or other means, and exploits the faulty outputs.

Tree grafting

Exploiting a faulty hypertree signature to attach an attacker-built subtree under a genuine upper-layer key, enabling forgeries.

One-time-key reuse

A Winternitz key signing two different values, which reveals enough chain values to sign some further values.

Winternitz checksum

Extra digits signed with every Winternitz signature so that increasing one digit forces another to decrease, limiting forgery.

Verify-after-sign

Checking a freshly produced signature before release; it catches inconsistent outputs but not consistent faulty ones.

Redundancy check

Computing security-critical values more than once, independently, and releasing output only if the results agree.

Hedged signing

Mixing fresh randomness into the signing randomiser; the FIPS 205 default, helpful against power analysis.

Differential power analysis

A side-channel attack that statistically correlates power consumption with hypotheses about secret data.

Silent data corruption

A hardware computation error that produces wrong results without any error being reported.

References

1. Castelnovi, Martinelli and Prest, Grafting Trees: a Fault Attack against the SPHINCS framework (PQCrypto 2018)
2. Genet, Kannwischer, Pelletier and McLauchlan, Practical Fault Injection Attacks on SPHINCS (2018)
3. Genet, On Protecting SPHINCS+ Against Fault Attacks (IACR TCHES 2023)
4. Amiet, Leuenberger, Curiger and Zbinden, FPGA-based SPHINCS+ Implementations: Mind the Glitch (DSD 2020)
5. Kannwischer, Genet, Butin, Kramer and Buchmann, Differential Power Analysis of XMSS and SPHINCS (COSADE 2018)
6. NIST FIPS 205, Stateless Hash-Based Digital Signature Standard (2024), Sections 3.2 and 9.2
7. SPHINCS+ Submission to the NIST post-quantum project, specification v3.1 (2022), Sections 8.1.5 and 9.4
8. Dixit et al., Silent Data Corruptions at Scale (2021)