# Why are WOTS and WOTS+ one-time schemes?

I've been doing some reading on hash based signature schemes, specifically XMSS and thus the underlying Winternitz scheme (WOTS+ to be precise).

As their names suggests, WOTS and WOTS+ are one time schemes, so signing multiple messages with the same key should leak some info. I have however not been able to come up with a way to abuse this and was hoping someone can point me in the right direction. Specifically, the way I see it, the checksum prevents me from forging a signature even if two different messages were signed with the same key. Why is this not the case?

## 1 Answer

I have however not been able to come up with a way to abuse this and was hoping someone can point me in the right direction. Specifically, the way I see it, the checksum prevents me from forging a signature even if two different messages were signed with the same key. Why is this not the case?

Let us take a rather simplified example; consider the case where there is a single WOTS digit used to express the hash (and therefore a single WOTS digit to express the checksum); for this example, we'll have $$W=16$$.

The first message we sign is the hash value 2; that means that we publish $$H^2(x)$$ (where $$x$$ is from the private key), along with the checksum 14, which we publish as $$H^{14}(y)$$ (where $$y$$ is also from the private key)

Now, we sign (with the same private key) the hash value 13; that means we publish $$H^{13}(x)$$ and the checksum $$H^3(y)$$.

At this point, the attacker has enough information to generate a forgery for (say) the hash value 7. To do that, he'd take the $$H^2(x)$$ value from the first signature (which we'll call $$a$$) and compute $$H^5(a)$$; he'd take the $$H^3(y)$$ from the second signature (which we'll call $$b$$) and compute $$H^6(b)$$. The pair $$H^5(a), H^6(b)$$ is equal to $$H^7(x), H^9(y)$$, and so is a valid signature for 7, even though the attacker has no idea what the values for $$x$$ and $$y$$ are.

This attack extends easily to the real WOTS system (where a message is expressed in multiple digits), and the modification of WOTS+ (which stirs in a unique value for each hash invocation) doesn't actually make the attacker's job any harder.

• Thanks very much, that's exactly the type of explanation I was looking for! Mar 31, 2022 at 7:34