Score:3

MuSig: could the rogue key attack be mitigated by using commitments instead of key transformations?

eg flag

Background

MuSig is an extension of/derivation from Schnorr signatures using cyclic groups on elliptic curves. In the original paper, the authors point out that naive multi-Schnorr is vulnerable to a rogue key attack:

Given $\Bbb G$ is a cyclic group of prime order; $g$ is the generator point; $H$ is a hash function; $m$ is the message to sign; and there are $n$ participants:

Let $L = \{ X_1 = g^{x_1},..., X_n = g^{x_n} \}$ be the multiset of participant keys.

Let each nonce share be $R_i = g^{r_i}$.

Compute the aggregate nonce: $R = \prod_{i=1}^nR_i$

Compute the aggregate key: $\tilde X = \prod_{i=1}^nX_i$

Compute the challenge: $c = H(\tilde X, R, m)$

Compute each partial signature: $s_i = r_i + cx_i$

Compute the aggregate signature: $s = \sum_{i=1}^ns_i$

The signature for aggregate key $\tilde X$ and message $m$ is now $(R, s)$ and can be verified: $g^s = R\tilde X^c$

If one participant is a bad actor and waits to gather all other participant keys before sending his own, he can compute a key pair that allows him to sign for the group by inverting the partial product: $X_1 = g^{x_1} * {(\prod_{i=2}^nX_i)}^{-1}$

The primary contribution of the MuSig paper is a scheme that prevents the rogue key attack by transforming each participant key after key exchange in a way that allows for key aggregation in the plain public-key model:

Let $\langle L \rangle$ be a deterministic ordering of $L$.

Let $a_i = H(\langle L \rangle, X_i)$

Compute $\tilde X = \prod_{i=1}^n{X_i}^{a_i}$

One well-known problem with exchanging nonces is that under concurrent sessions with pre-shared nonces, an attacker can use Wagner's generalized birthday attack to bias the hash output and thus efficiently forge a signature. The solution to this problem is to have all participants commit to a nonce value and pre-share the commitment rather than the nonce; when the time comes to create a group signature, nonces are exchanged, and the protocol aborts if a received nonce does not map to a commitment.

Question

Can the rogue key attack be solved by committing to a public key before exchanging those keys? This would allow all participants to detect if any other participant is attempting to manipulate his public key to allow single signatures for the group. The session could then be discarded and the fraudulent aggregate key ignored.

Is this adequate to mitigate the rogue key attack, or does it lack security assurances in certain circumstances?

Aman Grewal avatar
gb flag
It's difficult to read large code blocks for things that aren't code. This site also supports $\LaTeX$ markup. Could you edit your question to make it more readable?
Jonathan Voss avatar
eg flag
@AmanGrewal I was unaware of latex markup and was wondering how other posts accomplished it. I will update posthaste.
Score:5
hu flag

Yes, the rogue key attack can be prevented by committing to a public key before exchanging the keys. But this requires that you never use a public key with more than one group of signers. If you use it with a second group of signers, the attacker knows your public key already and can use a rogue key. This requirement would be very limiting in practice.

If you want to avoid using MuSig-style key aggregation, you can also require every signer to provide a proof of possession of the secret key corresponding to their claimed public key. This proof can take the form of a Schnorr signature and does not have the same restriction as a simple public key commitment. For example, the "SpeedyMuSig" scheme makes use of this idea. However, the advantage of MuSig-style key aggregation is that it does not require extra steps and is therefore compatible with existing protocols that only handle regular public keys.

Erik Aronesty avatar
br flag
proof of secret key is easy, and simple to use in practice and opens up a wide-range of use-cases with schnorr signatures.
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.