Score:0

How does not tagging hashes result in leaking the secret key if a nonce is re-used in a different scheme?

ar flag

I'm reading through BIP340 and I'm having trouble understanding this part:

For example, without tagged hashing a BIP340 signature could also be valid for a signature scheme where the only difference is that the arguments to the hash function are reordered. Worse, if the BIP340 nonce derivation function was copied or independently created, then the nonce could be accidentally reused in the other scheme leaking the secret key.

I'm assuming the first sentence is only valid in the case where the arguments happen to share values, is this correct? For instance the hash used by BIP340 is $\text{hash}(R||P||m)$. If a different scheme used $\text{hash}(R||m||P)$, then these two schemes would result in a collision if the message $m$ being signed happened to be equal to the public key $P$, causing a signature in one scheme to be valid in the other scheme.

My main question deals with the second sentence. How exactly would not tagging hashes cause re-using a nonce in a separate scheme to leak the private key? I'm trying to work through the math to see how this would work.

Suppose we have two Schnorr schemes which create their hashes as follows:

Scheme 1: $e_1=\text{hash}(R||P||m)$
Scheme 2: $e_2=\text{hash}(R||m||P)$

I could see how re-using a nonce would leak the private key if the same key were used in both schemes and the hashes were difference. For a nonce $k$, private key $d$, and signatures $s_1$ and $s_2$ we have:

\begin{align} s_1 &= k + e_1 \cdot d \\ s_2 &= k + e_2 \cdot d \\ s_1 - s_2 &= d (e_1 - e_2) \\ d &= (s_1 - s_2) (e_1 - e_2) ^ {-1} \end{align}

However if the hashes were already different, then altering the hash arguments with a scheme-specific tag would make no difference.

The other approach I could see is if the private keys were different and the hashes were the same, as I'm guessing is implied by the first sentence in the BIP quote. If the private keys were $d_1$ and $d_2$, and the hashes had a collision and were both $e$, then the difference in the private keys could be leaked as follows:

\begin{align} s_1 &= k + e \cdot d_1 \\ s_2 &= k + e \cdot d_2 \\ s_1 - s_2 &= e \cdot (d_1 - d_2) \\ d_1 - d_2 &= (s_1 - s_2) \cdot e^{-1} \end{align}

Although this leaks the difference in the private keys, which is probably not ideal, I don't see how the private keys themselves get leaked.

Maybe I'm going about this the wrong way. How does the math work in terms of leaking the private key as a result of both re-using a nonce and not tagging the hashes?

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.