Skip to content

Instantly share code, notes, and snippets.

@AdamISZ
Last active April 3, 2023 20:01
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save AdamISZ/ca974ed67889cedc738c4a1f65ff620b to your computer and use it in GitHub Desktop.
Save AdamISZ/ca974ed67889cedc738c4a1f65ff620b to your computer and use it in GitHub Desktop.
Forgery with a fake key in MuSig2

As per footnote 2 in the draft BIP here, it is possible in MuSig2 to create a partial signature which verifies correctly to the other participants, even though the adversary does not know the secret key corresponding to the given public key, but only by the adversary taking the role of at least one other participant, and in that case it is not possible to create a partial signature for that other public key, even if the corresponding private key is known.

The purpose of this gist is to work through the mathematical details of the above statement, as it isn't, probably, obvious to most readers (although it may be at least somewhat intuitive - think about 'free variables').

Setup: keyset $L = X_1 , X_2 , X_3 , X_4 , X_5$. The adversary will take the roles of indices 4 and 5, and will forge a partial signature on key $X_4$, not knowing the corresponding secret $x_4$, on a given message $m$. Assume the adversary does know the secret key for $X_5$.

Being the last two entries in the list, the adversary will receive the set of nonces from the earlier participants: $(R_{1,1}, R_{1,2}), (R_{2, 1}, R_{2, 2}), (R_{3, 1}, R_{3,2})$.

The adversary sets aggregate partial nonces $R_1, R_2$ at random, without yet choose the individual pairs of partial nonces for indices 4 and 5. This is the 'cheat', which allows him to precalculate:

Calculate $\tilde{X} = \sum \mathbb{H}(L,X_i)X_{i}$

Calculate $b = \mathbb{H}(\tilde{X}, R_1, R_2, m)$

Calculate $\tilde{R} = R_1 + b \cdot R_2$

Calculate $R_{1}^{*} = R_1 - \Sigma_{k=1}^3 R_{k,1}$

Calculate $R_{2}^{*} = R_2 - \Sigma_{k=1}^3 R_{k,2}$

The last two values $R_{i}^{*}$ are 'what is left over' to be filled in by the adversary's nonce values.

To create nonces such that the forgery on $X_4$ verifies, the adversary does this:

Choose $s_4$ at random.

Calculate $Q = s_{4} \cdot G - \mathbb{H}\left(\tilde{X}, \tilde{R}, m\right)\mathbb{H}\left(L, X_4\right)X_4$

Choose $R_{4,1}$ at random.

Calculate $R_{4,2} = b^{-1} \cdot \left (Q - R_{4,1}\right)$

Then $s_4$ will verify as a valid partial signature on message $m$ for keyset $L$ and specific key $X_4$, but only if:

$R_{5,1} = R_{1}^{*} - R_{4,1}$ and $R_{5,2} = R_{2}^{*} - R_{4,2}$

So, as a completion of the first stage of the signing protocol, the adversary must pass over the values $R_{4,1},R_{4,2},R_{5,1},R_{5,2}$ as calculated/selected above. Only then can the adversary pass over to other counterparties the value $s_4$, and at this point, he is not able to create a valid $s_5$, which can be seen by examining the partial signature verification equation for index 5:

$$s_{5} \cdot G = R_{5,1} + b \cdot R_{5,2} + \mathbb{H}\left(\tilde{X}, \tilde{R}, m\right)\mathbb{H}\left(L,X_5\right)X_5$$

The RHS is entirely fixed by the previous steps, and thus the LHS is a point whose discrete log cannot be extracted (another way of saying it - the values $R_{5,1},R_{5,2}$ were determined by the choices of the nonces at the other indices, and their secret values cannot be determined (in contrast to honest signing, where they are chosen in advance by the signer). So even if the adversary knows the private key of $X_5$ , they still cannot achieve a complete MuSig2 protocol execution.

@jonasnick
Copy link

jonasnick commented May 24, 2022

Thanks for the detailed writeup.

There's some chance that this attack wouldn't be possible (so that partial signatures are actual signatures) if we'd remove the ability to do third party nonce aggregation, i.e., hash all individual $R_{i,j}$ into $b$. But on the other hand it's difficult to imagine a scenario where this attack would have a considerable impact.

Should be $s_4$ in step 4 "Calculate $Q = ...$". Perhaps slightly simpler to demonstrate this attack with just three signers. You'd be able to shorten the last paragraph by saying "and at this point, he is not able to create a valid $s_5$ because this would imply a real MuSig2 forgery" :)

@AdamISZ
Copy link
Author

AdamISZ commented May 24, 2022

@jonasnick thanks.

"and at this point, he is not able to create a valid because this would imply a real MuSig2 forgery" :)

Well true, but only a rare kind of person would find that more intellectually satisfying :)

Perhaps slightly simpler to demonstrate this attack with just three signers.

Probably. Not sure what made me go that way, perhaps unconsciously I preferred it to have the adversary controlling less than a majority of keys (although I'm well aware that's not relevant).

There's some chance that this attack wouldn't be possible (so that partial signatures are actual signatures) if we'd remove the ability to do third party nonce aggregation, i.e., hash all individual into . But on the other hand it's difficult to imagine a scenario where this attack would have a considerable impact.

Interesting point; I remember in my blog post write up I wrote it like that, i.e. write every single sub-nonce into the hash. I was a bit surprised that the paper chose the sums, and it's an example of a general pattern I've noticed in this field - choice of slightly less simple or slight less 'unquestionable' design choices because it shaves off a bit on performance. In general I'm not a fan of that though of course, in many cases, I'm not qualified to judge, and anyway it's a tricky judgement call.

Should be in step 4 "Calculate ".

Thanks, will fix.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment