Score:0

Why are WOTS and WOTS+ one-time schemes?

ru flag

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?

Score:2
my flag

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.

ru flag
Thanks very much, that's exactly the type of explanation I was looking for!
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.