A Kelsey–Kohno Attack Variant against SHA-2 Message Digests in HSS/LMS and XMSS

What it is

Falko Strenzke's ePrint 2026/2635 (received 25 October 2026, approved 26 October 2026, preprint) describes a multi-target second-preimage attack on the message hashing step of HSS/LMS and XMSS. It applies to parameter sets using SHA-256 and the truncated SHA-256/192. It adapts the Kelsey–Kohno herding technique.

How it works

Both schemes put the key identifier and the one-time-signature leaf index at the start of the hash input, so that one search cannot serve many signatures. The attack removes that protection.

1. The attacker collects many signatures and takes the SHA-256 chaining state after each signature's prefix.
2. Those states are merged, level by level through state collisions, into a single chaining state.
3. One search from that state then serves every collected signature at once.

The search can end in one of two ways. It can match final digests, which is the better choice against SHA-256/192. Or, after appending a Kelsey–Schneier expandable message, it can match the internal chaining states of long signed messages, which works against full SHA-256.

Preconditions / Affected

The attacker needs a large pool of signatures. NIST's bound of 2^64 signatures is used, and the signatures may be spread over any number of keys. Because the pool crosses keys, even the first signature of a single key adds to the overall exposure of an ecosystem.

Costs are in compression-function calls:

The 90-bit figure is derived from the stated numbers. SHA-256/192 uses digest matching, so message length does not matter.

The paper attributes the weakness to the SHA-256 chaining state being narrower than twice the targeted security level. SHAKE256 parameter sets are not affected.

What to do

The abstract gives no patch or configuration change. Its only stated boundary is that SHAKE256 parameter sets are unaffected. An engineer choosing parameters for HSS/LMS or XMSS can read that as a reason to prefer SHAKE256 sets over SHA-256 and SHA-256/192 ones. The paper's own recommendations may be in the full text, which the abstract page does not show.

Caveats

The 2^166 and 2^156 figures are attack costs, not demonstrated runs. They also assume the attacker has gathered signatures near NIST's 2^64 limit. The abstract states no practical attack parameters below that. This is a preprint and the page does not mention peer review.