📅 Original date posted:2023-07-25
🗒️ Summary of this message: The discussion is about the security of the blind MuSig scheme and the potential vulnerabilities it may have.
📝 Original message:
posk is "proof of secret key". so you cannot use wagner to select R
On Mon, Jul 24, 2023 at 1:59 PM AdamISZ via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> @ZmnSCPxj:
>
> yes, Wagner is the attack you were thinking of.
>
> And yeah, to avoid it, you should have the 3rd round of MuSig1, i.e. the R
> commitments.
>
> @Tom:
> As per above it seems you were more considering MuSig1 here, not MuSig2.
> At least in this version. So you need the initial commitments to R.
>
> Jonas' reply clearly has covered a lot of what matters here, but I wanted
> to mention (using your notation):
>
> in s1 = c * a1 * x1 + r1, you expressed the idea that the challenge c
> could be given to the server, to construct s1, but since a1 = H(L, X1) and
> L is the serialization of all (in this case, 2) keys, that wouldn't work
> for blinding the final key, right?
> But, is it possible that this addresses the other problem?
> If the server is given c1*a1 instead as the challenge for signing (with
> their "pure" key x1), then perhaps it avoids the issue? Given what's on the
> blockchain ends up allowing calculation of 'c' and the aggregate key a1X1 +
> a2X2, is it the case that you cannot find a1 and therefore you cannot
> correlate the transaction with just the quantity 'c1*a1' which the server
> sees?
>
> But I agree with Jonas that this is just the start, i.e. the fundamental
> requirement of a blind signing scheme is there has to be some guarantee of
> no 'one more forgery' possibility, so presumably there has to be some proof
> that the signing request is 'well formed' (Jonas expresses it below as a
> ZKP of a SHA2 preimage .. it does not seem pretty but I agree that on the
> face of it, that is what's needed).
>
> @Jonas, Erik:
> 'posk' is probably meant as 'proof of secret key' which may(?) be a mixup
> with what is sometimes referred to in the literature as "KOSK" (iirc they
> used it in FROST for example). It isn't clear to me yet how that factors
> into this scenario, although ofc it is for sure a potential building block
> of these constructions.
>
> Sent with Proton Mail secure email.
>
> ------- Original Message -------
> On Monday, July 24th, 2023 at 08:12, Jonas Nick via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org> wrote:
>
>
> > Hi Tom,
> >
> > I'm not convinced that this works. As far as I know blind musig is still
> an open
> > research problem. What the scheme you propose appears to try to prevent
> is that
> > the server signs K times, but the client ends up with K+1 Schnorr
> signatures for
> > the aggregate of the server's and the clients key. I think it's possible
> to
> > apply a variant of the attack that makes MuSig1 insecure if the nonce
> commitment
> > round was skipped or if the message isn't determined before sending the
> nonce.
> > Here's how a malicious client would do that:
> >
> > - Obtain K R-values R1[0], ..., R1[K-1] from the server
> > - Let
> > R[i] := R1[i] + R2[i] for all i <= K-1
> > R[K] := R1[0] + ... + R1[K-1]
> > c[i] := H(X, R[i], m[i]) for all i <= K.
> > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that
> > c[0] + ... + c[K-1] = c[K].
> > - Send c[0], ..., c[K-1] to the server to obtain s[0], ..., s[K-1].
> > - Let
> > s[K] = s[0] + ... + s[K-1].
> > Then (s[K], R[K]) is a valid signature from the server, since
> > s[K]G = R[K] + c[K]a1X1,
> > which the client can complete to a signature for public key X.
> >
> > What may work in your case is the following scheme:
> > - Client sends commitment to the public key X2, nonce R2 and message m
> to the
> > server.
> > - Server replies with nonce R1 = k1G
> > - Client sends c to the server and proves in zero knowledge that c =
> > SHA256(X1 + X2, R1 + R2, m).
> > - Server replies with s1 = k1 + c*x1
> >
> > However, this is just some quick intuition and I'm not sure if this
> actually
> > works, but maybe worth exploring.
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev at lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230725/717e4669/attachment-0001.html>;
Erik Aronesty [ARCHIVE] /
npub1y2…5taj0
2023-07-27 00:26:33
in reply to nevent1q…psc7
Author Public Key
npub1y22yec0znyzw8qndy5qn5c2wgejkj0k9zsqra7kvrd6cd6896z4qm5taj0Seen on
wss://nos.lolPublished at
2023-07-27 00:26:33Event JSON
{
"id": "4524ce93f503de14a51edd83b917721832617ba5e34417c8148ce9196d1c49d8",
"pubkey": "22944ce1e29904e3826d25013a614e4665693ec514003efacc1b7586e8e5d0aa",
"created_at": 1690417593,
"kind": 1,
"tags": [
[
"e",
"86a87258a295f0e8a6ce06957ce368a6146cf45a73137d0af6fcc0729ce599a0",
"",
"root"
],
[
"e",
"58cf29fe2ecbc6bfff982ebd8f5e11343c765fd590d8fe85ab2861c84486fae6",
"",
"reply"
],
[
"p",
"9b3cb9066a41d6c59c090531827defe6138e14f8b94a7802a8a183aa309a4e2b"
]
],
"content": "📅 Original date posted:2023-07-25\n🗒️ Summary of this message: The discussion is about the security of the blind MuSig scheme and the potential vulnerabilities it may have.\n📝 Original message:\nposk is \"proof of secret key\". so you cannot use wagner to select R\n\nOn Mon, Jul 24, 2023 at 1:59 PM AdamISZ via bitcoin-dev \u003c\nbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\n\u003e @ZmnSCPxj:\n\u003e\n\u003e yes, Wagner is the attack you were thinking of.\n\u003e\n\u003e And yeah, to avoid it, you should have the 3rd round of MuSig1, i.e. the R\n\u003e commitments.\n\u003e\n\u003e @Tom:\n\u003e As per above it seems you were more considering MuSig1 here, not MuSig2.\n\u003e At least in this version. So you need the initial commitments to R.\n\u003e\n\u003e Jonas' reply clearly has covered a lot of what matters here, but I wanted\n\u003e to mention (using your notation):\n\u003e\n\u003e in s1 = c * a1 * x1 + r1, you expressed the idea that the challenge c\n\u003e could be given to the server, to construct s1, but since a1 = H(L, X1) and\n\u003e L is the serialization of all (in this case, 2) keys, that wouldn't work\n\u003e for blinding the final key, right?\n\u003e But, is it possible that this addresses the other problem?\n\u003e If the server is given c1*a1 instead as the challenge for signing (with\n\u003e their \"pure\" key x1), then perhaps it avoids the issue? Given what's on the\n\u003e blockchain ends up allowing calculation of 'c' and the aggregate key a1X1 +\n\u003e a2X2, is it the case that you cannot find a1 and therefore you cannot\n\u003e correlate the transaction with just the quantity 'c1*a1' which the server\n\u003e sees?\n\u003e\n\u003e But I agree with Jonas that this is just the start, i.e. the fundamental\n\u003e requirement of a blind signing scheme is there has to be some guarantee of\n\u003e no 'one more forgery' possibility, so presumably there has to be some proof\n\u003e that the signing request is 'well formed' (Jonas expresses it below as a\n\u003e ZKP of a SHA2 preimage .. it does not seem pretty but I agree that on the\n\u003e face of it, that is what's needed).\n\u003e\n\u003e @Jonas, Erik:\n\u003e 'posk' is probably meant as 'proof of secret key' which may(?) be a mixup\n\u003e with what is sometimes referred to in the literature as \"KOSK\" (iirc they\n\u003e used it in FROST for example). It isn't clear to me yet how that factors\n\u003e into this scenario, although ofc it is for sure a potential building block\n\u003e of these constructions.\n\u003e\n\u003e Sent with Proton Mail secure email.\n\u003e\n\u003e ------- Original Message -------\n\u003e On Monday, July 24th, 2023 at 08:12, Jonas Nick via bitcoin-dev \u003c\n\u003e bitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\n\u003e\n\u003e \u003e Hi Tom,\n\u003e \u003e\n\u003e \u003e I'm not convinced that this works. As far as I know blind musig is still\n\u003e an open\n\u003e \u003e research problem. What the scheme you propose appears to try to prevent\n\u003e is that\n\u003e \u003e the server signs K times, but the client ends up with K+1 Schnorr\n\u003e signatures for\n\u003e \u003e the aggregate of the server's and the clients key. I think it's possible\n\u003e to\n\u003e \u003e apply a variant of the attack that makes MuSig1 insecure if the nonce\n\u003e commitment\n\u003e \u003e round was skipped or if the message isn't determined before sending the\n\u003e nonce.\n\u003e \u003e Here's how a malicious client would do that:\n\u003e \u003e\n\u003e \u003e - Obtain K R-values R1[0], ..., R1[K-1] from the server\n\u003e \u003e - Let\n\u003e \u003e R[i] := R1[i] + R2[i] for all i \u003c= K-1\n\u003e \u003e R[K] := R1[0] + ... + R1[K-1]\n\u003e \u003e c[i] := H(X, R[i], m[i]) for all i \u003c= K.\n\u003e \u003e Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that\n\u003e \u003e c[0] + ... + c[K-1] = c[K].\n\u003e \u003e - Send c[0], ..., c[K-1] to the server to obtain s[0], ..., s[K-1].\n\u003e \u003e - Let\n\u003e \u003e s[K] = s[0] + ... + s[K-1].\n\u003e \u003e Then (s[K], R[K]) is a valid signature from the server, since\n\u003e \u003e s[K]G = R[K] + c[K]a1X1,\n\u003e \u003e which the client can complete to a signature for public key X.\n\u003e \u003e\n\u003e \u003e What may work in your case is the following scheme:\n\u003e \u003e - Client sends commitment to the public key X2, nonce R2 and message m\n\u003e to the\n\u003e \u003e server.\n\u003e \u003e - Server replies with nonce R1 = k1G\n\u003e \u003e - Client sends c to the server and proves in zero knowledge that c =\n\u003e \u003e SHA256(X1 + X2, R1 + R2, m).\n\u003e \u003e - Server replies with s1 = k1 + c*x1\n\u003e \u003e\n\u003e \u003e However, this is just some quick intuition and I'm not sure if this\n\u003e actually\n\u003e \u003e works, but maybe worth exploring.\n\u003e \u003e _______________________________________________\n\u003e \u003e bitcoin-dev mailing list\n\u003e \u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e \u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20230725/717e4669/attachment-0001.html\u003e",
"sig": "fdb402684c622bdc577081439c946f4b146f9a817b8196090c00d5d43e34895b287ed5be277366374e7211e16c746b01ea44ff7b6a31e54d8cefe14d7ea88a73"
}