1
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks very much, that's exactly the type of explanation I was looking for! $\endgroup$
    – Dennis8
    Commented Mar 31, 2022 at 7:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.