Claimed attacks cut up to 100 bits from SHA-2 LMS and XMSS
Two concurrent papers say a herding-style second-preimage attack defeats the multi-target countermeasure in deployed SHA-256 parameter sets.
Two concurrent papers claim that SHA-2 parameter sets of the stateful hash-based signature schemes HSS/LMS and XMSS lose far more EUF-CMA security than their designs assume. Falko Strenzke told the NIST post-quantum cryptography list that the claims are serious enough that the IETF Crypto Forum Research Group should not wait for peer review before judging them.
Both works describe the same multi-target second-preimage attack on the message digest, a variant of the Kelsey-Kohno herding, or diamond, attack. In the standard resource model the attacker is given 2^64 signatures. The attack searches for collisions among internal SHA-256 chaining states during digest computation. That, the authors say, defeats the schemes' multi-target countermeasure: prefixing each signed message with a key identifier and the one-time signature leaf index.
Strenzke's paper covers both HSS/LMS and XMSS. Combined with the older Kelsey-Schneier long-message attack, it claims a loss of up to 100 bits for SHA-256 parameter sets, with cost counted in compression-function calls, and up to 39 bits for SHA-256/192 sets. A paper by Chun Guo, Hongrui Cheng, Bart Preneel, and Meiqin Wang addresses only HSS/LMS. It also describes a fixed-point attack that needs no diamond structure and still applies when signed and forged messages are very short, and it derives security bounds in the ideal-cipher model.
Strenzke wrote that, because the claims concern deployed parameter sets, "it may not be advisable to wait until they have undergone peer review." He asked CFRG to decide whether the results are refuted, need correction in their numbers, or stand, and to consider consequences for the RFCs that define the schemes and parameter sets: RFC 8554, RFC 9858, and RFC 8391.