From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id BE882C0032 for ; Wed, 26 Jul 2023 14:09:14 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 9397381BCB for ; Wed, 26 Jul 2023 14:09:14 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 9397381BCB Authentication-Results: smtp1.osuosl.org; dkim=pass (2048-bit key) header.d=q32-com.20221208.gappssmtp.com header.i=@q32-com.20221208.gappssmtp.com header.a=rsa-sha256 header.s=20221208 header.b=xlL+Nq6d X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: 0.144 X-Spam-Level: X-Spam-Status: No, score=0.144 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DATE_IN_PAST_06_12=1.543, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FREEMAIL_FORGED_FROMDOMAIN=0.25, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=no autolearn_force=no Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id KTgGbHvX-gJ1 for ; Wed, 26 Jul 2023 14:09:12 +0000 (UTC) Received: from mail-yw1-x1129.google.com (mail-yw1-x1129.google.com [IPv6:2607:f8b0:4864:20::1129]) by smtp1.osuosl.org (Postfix) with ESMTPS id A3E7681A3B for ; Wed, 26 Jul 2023 14:09:12 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org A3E7681A3B Received: by mail-yw1-x1129.google.com with SMTP id 00721157ae682-57a8ec82ea6so8838967b3.1 for ; Wed, 26 Jul 2023 07:09:12 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=q32-com.20221208.gappssmtp.com; s=20221208; t=1690380551; x=1690985351; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=cm98l7/8SgDtj0rH+PKAXg59hT2ow5+VDq6UTmx+9X8=; b=xlL+Nq6d+n8kcWYFlUk4nkA73Dk2MJ+I0POvW/HK8vG5dGVqxRgECBjI6kh4z+GgYZ pmiWSQoqOBgY7kLWTNsryjHgzAE8E9BC9rMzgoZWWZow8BpGWsLyUgUIv3K9kRLf/U/N n4JzzipZlsE1r46D/zGjtk/+wpXr2BGtPvVBV1DkhH5u/XG5tjMpYFEMsWUg1ga/+icp 2RmF81hp8s29KLKnzCVtzPcdt3uJyu1WkWxgeoa0INXVfULWMgit01mVQYS4ms0B/wv3 QIZeVSlHjHh3XTlbHlVF0o9Cetke5sHaT8NQV+bZGiKc7NrMQmN0jj+rFZTuLMIiQrji IBZw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20221208; t=1690380551; x=1690985351; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=cm98l7/8SgDtj0rH+PKAXg59hT2ow5+VDq6UTmx+9X8=; b=io4WBIMqBMuLPpwrsAPE7Kef9lujo4/IK4b0wMXpxSCwIcz2a4scC2jMx3otTuEvQY tnb8IEPMOj8yjrNWVWOSp/leS+G+Ppc+Jyy/6SfUrHhuenm9lrEeU95L8i4ZRX+suNtV s40JGfp1+5OWlr9SiBsFgkqJ/4mIXlDEEtFEJFp8jETyXOQWmEltm8whqI1VyK/rXQ4i /OfeSO761QcIUPfo3koZXUUKcOluJjFKgW4NwdxiELvCeWfNBqaHwBcr/p8MjSU0SXPF J50h9aqPOkGCoG+ixNYAeZzEnCtEkI/ItLN0p/qxczKfEQKQNqdnj0R0m5qJKyDDYkEr qiMg== X-Gm-Message-State: ABy/qLb/Gkr17NzDD4Lv6rl/1RNKPEdPdQ48xNQi5YdWxy83CMPUmj4H NHVZlgw+iRHMNJOlwEFhnJqp27eLa6RGP9DT6tQhjKlQRSPrRbk= X-Google-Smtp-Source: APBJJlGB6mwn0kenoiTLMTL2zot8VLyArzCymE4XYuaresgOqKUJX9+n1XDJEDHy8aj7N2bPU1witRMBQGq0IQ7gRiM= X-Received: by 2002:a0d:cb52:0:b0:583:adc6:10b8 with SMTP id n79-20020a0dcb52000000b00583adc610b8mr1066429ywd.3.1690380551180; Wed, 26 Jul 2023 07:09:11 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Erik Aronesty Date: Wed, 26 Jul 2023 00:09:41 -0400 Message-ID: To: Tom Trevethan , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="00000000000049f08706016464cb" X-Mailman-Approved-At: Wed, 26 Jul 2023 14:32:50 +0000 Subject: Re: [bitcoin-dev] Blinded 2-party Musig2 X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 26 Jul 2023 14:09:14 -0000 --00000000000049f08706016464cb Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable personally, i think *any* time a public key is transmitted, it should come with a "proof of secret key". it should be baked-in to low level protocols so that people don't accidentally create vulns. alt discussion link: https://gist.github.com/RubenSomsen/be7a4760dd4596d06963d67baf140406 On Tue, Jul 25, 2023 at 5:18=E2=80=AFPM Tom Trevethan via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Thanks for the replies. As I understand it, the v=3D2 nonces signing > protocol of musig2 prevents the Wagner attack. Also, that the challenge > value c must be blinded from the server to prevent the server from being > able to determine the signature from the on-chain state. > > In addition, in order to update the server (party 1) keyshare when a > statecoin is transferred between users, the key aggregation coefficient > must be set to 1 for each key. The purpose of this coefficient in the > Musig2 protocol is to prevent 'rogue key attacks' where one party can > choose a public key derived from both their own secret key and the invers= e > of the other party's public key giving them the ability to unilaterally > produce a valid signature over the aggregate key. However this can be > prevented by the party producing a proof of knowledge of the private key > corresponding to their supplied public key. This can be a signature, whic= h > is produced in any case by signing the statechain state in the mercury > protocol. This signature must be verified by the receiver of a coin (who > must also verify the server pubkey combines with the sender pubkey to get > the coin address) which proves that the server is required to co-sign to > generate any signature for this address. > > Here is a modified protocol: > > Keygen: > > Server generates private key x1 and public key X1 =3D x1.G and sends X1 t= o > user (party 2) > User generates private key x2 and public key X2 =3D x2.G and (random) > blinding nonce z and computes the aggregate public key X =3D z.(X1 + X2) > (server never learns of X, X2 or z). > > Signing: > > Server generates nonces r11 and r12 and R11 =3D r11.G and R12 =3D r12.G a= nd > sends R11 and R12 to the user. > User generates nonces r21 and r22 and R21 =3D r21.G and R22 =3D r22.G > User computes R1 =3D R11 + R21 and R2 =3D R12 + R22 and b =3D H(X,(R1,R2)= ,m) and > R =3D R1 + b.R2 and c =3D (X,R,m) > User sends the values y =3D cz and b to the server. > Server computes s1 =3D yx1 + r11 + br12 and sends it to the user. > User computes s2 =3D yx2 + r21 + br22 and s =3D s1 + s2 and signature (s,= R) > > Transfer: > > In a statecoin transfer, when receiving a statecoin, in order to verify > that the coin address (i.e. aggregate public key) is shared correctly > between the previous owner and the server, the client must verify the > following: > > Retrieve the CURRENT public key from the server for this coin X1. > Retrieve the public key X2 and the blinding nonce z from the sender. > Verify that z.X1 + X2 =3D P the address of the statecoin. > Verify that the sender has the private key used to generate X2: this is > done by verifying the statechain signature over the receiver public key X= 3 > from X2. > This proves that the address P was generated (aggregated) with the server > and can only be signed with cooperation with the server, i.e. no previous > owner can hold the full key. > > In order to update the key shares on transfer, the following protocol can > be used: > > Server (party 1) generates a random blinding nonce e and sends it to user= . > User adds their private key to the nonce: t1 =3D e + x2 > Client sends t1 and z to the reciever as part of transfer_msg (encrypted > with the receiver public key X3 =3D x3.G). > Receiver client decrypts t1 and then subtracts their private key x3: t2 = =3D > e + x2 - x3. > Receiver client sends t2 to the server as part of transfer_receiver. > Server the updates the private key share x1_2 =3D x1 + t2 - e =3D x1 + e = + x2 > - x3 - e =3D x1 + x2 - x3 > So now, x1_2 + x3 (the aggregation of the new server key share with the > new client key share) is equal to x1 + x2 (the aggregation of the old > server key share with the old client key share). > The server deletes x1. > > On Tue, Jul 25, 2023 at 3:12=E2=80=AFPM Erik Aronesty wrot= e: > >> posk is "proof of secret key". so you cannot use wagner to select R >> >> On Mon, Jul 24, 2023 at 1:59=E2=80=AFPM AdamISZ via bitcoin-dev < >> bitcoin-dev@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. th= e >>> 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 =3D c * a1 * x1 + r1, you expressed the idea that the challenge c >>> could be given to the server, to construct s1, but since a1 =3D H(L, X1= ) and >>> L is the serialization of all (in this case, 2) keys, that wouldn't wor= k >>> 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 a1= X1 + >>> 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 serv= er >>> sees? >>> >>> But I agree with Jonas that this is just the start, i.e. the fundamenta= l >>> 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 p= roof >>> 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 t= he >>> 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" (i= irc >>> 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@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] :=3D R1[i] + R2[i] for all i <=3D K-1 >>> > R[K] :=3D R1[0] + ... + R1[K-1] >>> > c[i] :=3D H(X, R[i], m[i]) for all i <=3D K. >>> > Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that >>> > c[0] + ... + c[K-1] =3D c[K]. >>> > - Send c[0], ..., c[K-1] to the server to obtain s[0], ..., s[K-1]. >>> > - Let >>> > s[K] =3D s[0] + ... + s[K-1]. >>> > Then (s[K], R[K]) is a valid signature from the server, since >>> > s[K]G =3D 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 =3D k1G >>> > - Client sends c to the server and proves in zero knowledge that c = =3D >>> > SHA256(X1 + X2, R1 + R2, m). >>> > - Server replies with s1 =3D 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@lists.linuxfoundation.org >>> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >>> _______________________________________________ >>> bitcoin-dev mailing list >>> bitcoin-dev@lists.linuxfoundation.org >>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >>> >> _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > --00000000000049f08706016464cb Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
personally, i think *any* time a public key is transmitted= , it should come with a "proof of secret key".=C2=A0 =C2=A0it sho= uld be baked-in to low level protocols so that people don't accidentall= y create vulns.=C2=A0 alt discussion link:=C2=A0 https://gist.github.= com/RubenSomsen/be7a4760dd4596d06963d67baf140406

On Tue, Jul 25, 2023 at= 5:18=E2=80=AFPM Tom Trevethan via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org&= gt; wrote:
Thanks for the replies. As I understand it, the v=3D2 nonces si= gning protocol of musig2 prevents the Wagner attack. Also, that the challen= ge value c must be blinded from the server to prevent the server from being= able to determine the signature from the on-chain state.

In additi= on, in order to update the server (party 1) keyshare when a statecoin is tr= ansferred between users, the key aggregation coefficient must be set to 1 f= or each key. The purpose of this coefficient in the Musig2 protocol is to p= revent 'rogue key attacks' where one party can choose a public key = derived from both their own secret key and the inverse of the other party&#= 39;s public key giving them the ability to unilaterally produce a valid sig= nature over the aggregate key. However this can be prevented by the party p= roducing a proof of knowledge of the private key corresponding to their sup= plied public key. This can be a signature, which is produced in any case by= signing the statechain state in the mercury protocol. This signature must = be verified by the receiver of a coin (who must also verify the server pubk= ey combines with the sender pubkey to get the coin address) which proves th= at the server is required to co-sign to generate any signature for this add= ress.

Here is a modified protocol:

Keygen:

Server gen= erates private key x1 and public key X1 =3D x1.G and sends X1 to user (part= y 2)
User generates private key x2 and public key X2 =3D x2.G and (rando= m) blinding nonce z and computes the aggregate public key X =3D z.(X1 + X2)= (server never learns of X, X2 or z).

Signing:

Server genera= tes nonces r11 and r12 and R11 =3D r11.G and R12 =3D r12.G and sends R11 an= d R12 to the user.
User generates nonces r21 and r22 and R21 =3D r21.G = and R22 =3D r22.G
User computes R1 =3D R11 + R21 and R2 =3D R12 + R22 an= d b =3D H(X,(R1,R2),m) and R =3D R1 + b.R2 and c =3D (X,R,m)
User sends = the values y =3D cz and b to the server.
Server computes s1 =3D yx1 + r= 11 + br12 and sends it to the user.
User computes s2 =3D yx2 + r21 + br= 22 and s =3D s1 + s2 and signature (s,R)

Transfer:

In a state= coin transfer, when receiving a statecoin, in order to verify that the coin= address (i.e. aggregate public key) is shared correctly between the previo= us owner and the server, the client must verify the following:

Retri= eve the CURRENT public key from the server for this coin X1.
Retrieve th= e public key X2 and the blinding nonce z from the sender.
Verify that z= .X1 + X2 =3D P the address of the statecoin.
Verify that the sender has = the private key used to generate X2: this is done by verifying the statecha= in signature over the receiver public key X3 from X2.
This proves that t= he address P was generated (aggregated) with the server and can only be sig= ned with cooperation with the server, i.e. no previous owner can hold the f= ull key.

In order to update the key shares on transfer, the followin= g protocol can be used:

Server (party 1) generates a random blinding= nonce e and sends it to user.
User adds their private key to the nonce:= t1 =3D e + x2
Client sends t1 and z to the reciever as part of transfer= _msg (encrypted with the receiver public key X3 =3D x3.G).
Receiver clie= nt decrypts t1 and then subtracts their private key x3: t2 =3D e + x2 - x3.=
Receiver client sends t2 to the server as part of transfer_receiver.Server the updates the private key share x1_2 =3D x1 + t2 - e =3D x1 + e += x2 - x3 - e =3D x1 + x2 - x3
So now, x1_2 + x3 (the aggregation of the = new server key share with the new client key share) is equal to x1 + x2 (th= e aggregation of the old server key share with the old client key share).The server deletes x1.

On Tue, Jul 25, 2023 at 3:12=E2=80=AFPM Erik = Aronesty <erik@q32.com= > wrote:
=
posk is "proof of secret key".=C2=A0 =C2=A0so yo= u cannot use wagner to select R

On Mon, Jul 24, 2023 at 1:59=E2=80=AFPM Adam= ISZ via bitcoin-dev <bitcoin-dev@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 want= ed to mention (using your notation):

in s1 =3D c * a1 * x1 + r1, you expressed the idea that the challenge c cou= ld be given to the server, to construct s1, but since a1 =3D 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 the= ir "pure" key x1), then perhaps it avoids the issue? Given what&#= 39;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 there= fore 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 re= quirement 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 i= t 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 &quo= t;KOSK" (iirc they used it in FROST for example). It isn't clear t= o 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@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 preven= t is that
> the server signs K times, but the client ends up with K+1 Schnorr sign= atures 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 sendin= g 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] :=3D R1[i] + R2[i] for all i <=3D K-1
> R[K] :=3D R1[0] + ... + R1[K-1]
> c[i] :=3D H(X, R[i], m[i]) for all i <=3D K.
> Using Wagner's algorithm, choose R2[0], ..., R2[K-1] such that
> c[0] + ... + c[K-1] =3D c[K].
> - Send c[0], ..., c[K-1] to the server to obtain s[0], ..., s[K-1]. > - Let
> s[K] =3D s[0] + ... + s[K-1].
> Then (s[K], R[K]) is a valid signature from the server, since
> s[K]G =3D 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 =3D k1G
> - Client sends c to the server and proves in zero knowledge that c =3D=
> SHA256(X1 + X2, R1 + R2, m).
> - Server replies with s1 =3D k1 + c*x1
>
> However, this is just some quick intuition and I'm not sure if thi= s actually
> works, but maybe worth exploring.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--00000000000049f08706016464cb--