Hash-based signature scheme XMSS/LMS susceptible to preimage/second preimage attack?

Question

Are the quantum secure hash based signatures (XMSS/LMS) susceptible to preimage/second preimage attack?

Answer 1

I'll first recall the security notions used for signatures and those used for hashes, and then try to answer your question.

The building blocks

For signature schemes, we try to have "existential unforgeability", where an adversary tries to forge the signature of a message that was not yet signed.
We also try to have the harder "strong unforgeability", where an adversary tries to propose another signature for a message that was already signed.

For hash functions, we have the notion of "first-preimage-resistance", also known as "being one-way", that is, it must be hard to retrieve a preimage.
Next we have "second-preimage-resistance", when it is hard to find a distinct preimage, knowing one existing preimage.
Finally we have the "collision-resistance", which is an harder property stating that it must be hard to find a pair of messages that hashes to the same value.

Now, LMS uses the Winternitz one-time signature (WOTS) as its one-time signature scheme (OTS), while XMSS is based on a variant of WOTS called WOTS+.

To XMSS' advantage, WOTS+ does not require its underlying hash function to be collision-resistant, so second-preimage resistance is enough.

Against classical adversaries it lessens the burden of birthday attacks, and is good for performance, because then smaller parameters will offer the same level of security.

LMS on the other-hand, being based on WOTS requires a collision-resistant hash function.

Now, if we can break the underlying hash functions, the proofs of security of signature schemes based on it would collapse with it, as mentioned by Poncho in this related answer. But this does not necessarily mean the signature scheme is completely broken in that case... (Even if it actually does in this specific case, see below.)

Quantum stuff

While we are at it, we should distinguish the Quantum world from the Classical one, because the "complexity" of the generic attacks against hash functions' properties will depend on the world we consider:

$$ \begin{array} {r|r|r|} & \text{Classical} & \text{Quantum}\\ \hline \text{Preimage} & \Theta(2^{n})& \Theta(2^{n/2})\\ \text{Second-preimage} & \Theta(2^{n})& \Theta(2^{n/2}) \\ \text{Collision} & \Theta(2^{n/2}) & \Theta(2^{n/2})\\ \end{array} $$

This is so because Grover’s algorithm allows us to find preimages with a complexity of $\Theta(2^{n/2})$ in a quantum world, however the birthday paradox bounds the complexity of the collision-resistance in the classical world already. (And we don't know a better way to go around it in the quantum world. See [Be09].)

So in a post-quantum world, it appears that WOTS based scheme are as good as WOTS+ based schemes. In the classical world, WOTS+ has a slight advantage...

The signature schemes

Let's now take a look at the signature scheme themselves, not their building blocks.

For both LMS and XMSS, a second preimage attack on their hash function would allow for a single forgery.

More importantly, a preimage attack would allow the attacker to derive his own Merkle tree from a public key, thus allowing him to sign as many messages as he wants. This being the consequence of the way the keypairs are created.

Finally, it is worth mentioning that Winternitz-based schemes are all vulnerable to two chosen messages attacks: if an adversary know the signatures of the all-0 and of the all-1 messages, then she can forge the signatures of all possible messages.
However, this does not compromise the asymptotic security of the schemes (see [BH16]) if we consider that we are signing message digests, since the all-zero message and the all-one message are no easily "found". (And other signature schemes are trivially insecure against the all zero message.)
But notice this can become a serious problem if we are considering "fault attacks" in our threat model. (Which can be the case with signature schemes.)

References

[Be09] Bernstein, D. J. (2009). Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete. SHARCS, 9, 105.

[BH16] Bruinderink, L. G., & Hülsing, A. (2017, August). “Oops, I did it again”–Security of One-Time Signatures under Two-Message Attacks. In International Conference on Selected Areas in Cryptography (pp. 299-322). Springer, Cham.