From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 6CDE1DB5 for ; Tue, 11 Sep 2018 17:20:20 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wm0-f43.google.com (mail-wm0-f43.google.com [74.125.82.43]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 906FE7D3 for ; Tue, 11 Sep 2018 17:20:19 +0000 (UTC) Received: by mail-wm0-f43.google.com with SMTP id y139-v6so1818794wmc.2 for ; Tue, 11 Sep 2018 10:20:19 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=q32-com.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=mdsTcfMugvJFX+aqQgQ1zwJMvFDhkrA8j3l25BBxcPc=; b=yhR23sKovsM0w1ME7O1hguSelrv/iShavqxjOLYgSantD6n7s0g9d5Q59S5n7U3TTT Zeig4c7zjcJX2HZqjJy+X25MrDVnl4LBMeNFmlqUI4MrSZtyFkLXwPGaHhrmVnY0kzjs 7yD7k3eNAzOk+2lk0XGsCWSdqqFf6SbLGnAb4dyhDaZ2T/RcwehSTS0X26vAyXQVIjnQ JgjLsiuoiR98/qNu91C/kR5/ADLBXGQSyY6odYRgt3a3ldof4c5X9jzOWc7+yNPOBBoS 8Ewq2aBiqZYlD0bhQ21yVEWptDtb079kPcpkln4v1o65sDnc9fEBnTCZ5bUqyWVmmF2G aK5A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=mdsTcfMugvJFX+aqQgQ1zwJMvFDhkrA8j3l25BBxcPc=; b=UddGFqiOyPSDHauGM4aEYZRRfsyWwKxZx/stCxxQ4tgixBUY21Ssu1pCwriCPOnpYm oJdM0ngUNaHRvrxLF96kMQO73BmY6luAQPlJG/9uSlwdgEeDDmvOkhBwxMIK4a+T09/L oiyHqQANMhlPQULWXMBm2eIeLcpaWDgZUEalxaVbVdFydvcSbtn46vOO6jrKYVOD+BGO /+Iy/RomAbwV5TzAAo5wDLle2JXABpb670d6DOySsctC0iTaGE8AnhtzGh0UQTZUIEiF lmOlKxemGv3iLg+5dnhAHFt0TiR1GIIxa7bJn+8Zdh8GKlM5F4/oJ4L4NFoIiPrzDG5t G34A== X-Gm-Message-State: APzg51AZy/opBhrLY6689ILQR6D4ks2jbs/yFC6NqkmQH9eFk1pExVuv bZloxogNHezYcKkGCSFLNZqs7tVzyKRwFZUrw1fORkaNjsze X-Google-Smtp-Source: ANB0Vdb0N14ymvMalEJGSLPaKJbi+AGjHE5Bx4i9Sfh7fZzucuKncADNuyogm7jafK+bKeYm66KmVB6FwFYQTjXK0+E= X-Received: by 2002:a1c:70b:: with SMTP id 11-v6mr2018201wmh.151.1536686417926; Tue, 11 Sep 2018 10:20:17 -0700 (PDT) MIME-Version: 1.0 References: <2e620d305c86f65cbff44b5fba548dc85c118f84.camel@timruffing.de> <20180812163734.GV499@boulet.lan> <20180903000518.GB18522@boulet.lan> In-Reply-To: From: Erik Aronesty Date: Tue, 11 Sep 2018 13:20:01 -0400 Message-ID: To: Gregory Maxwell Content-Type: multipart/alternative; boundary="0000000000001260b305759bb0e7" X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Wed, 12 Sep 2018 13:40:40 +0000 Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Schnorr signatures BIP X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 11 Sep 2018 17:20:20 -0000 --0000000000001260b305759bb0e7 Content-Type: text/plain; charset="UTF-8" Greg, I added, stripped out, and added analogous musig delinearization 3 times in response to stuff posted here. I'm adding it back now. Not sure why my head is thick around that issue. The security advantages of a redistributable threshold system are huge. If a system isn't redistributable, then a single lost or compromised key results in lost coins... meaning the system is essetntially unusable. I'm actually worried that Bitcoin releases a multisig that encourages loss. On Tue, Sep 11, 2018 at 1:00 PM Gregory Maxwell wrote: > On Tue, Sep 11, 2018 at 4:34 PM Erik Aronesty wrote: > >> To answer points: >> >> - I switched to the medium article so that I could correct, edit and >> improve things to make them more clear. >> - I responded to feedback by modifying the protocol to make it work - not >> by ignoring it. >> > > To this moment there remains no response at your post. > https://bitcointalk.org/index.php?topic=4973123.0 > > I'm not sure how I am supposted to have figured out that you wrote a > somewhat different repost of it elsewhere... > > - An M-1 rogue-key attack would require the attacker would to either >> >> - attack the hash function to produce a predictable R based on a known >> mesage >> - attack the DLP to influence x or k >> >> Neither attack gives any particular advantage to someone who has M-1 keys. >> > > You keep asserting this. It isn't true. Asserting it more does not make it > any more true. I already explained how to attack this style of signature > (e.g. in the BCT thread). > > Set aside your 'interpolation' for a moment, and imagine that you > construct a 2 of 2 signature by just adding the keys. Your tell me your > key, P1 and then I tell you that my key P2 which I derived by computing > -P1 + xG. We now compute P = P1 + P2 = P1 + -P1 + xG = xG ... and now in > spite adding P1 with an unknown discrete log, I know the discrete log of P > with respect to G and I did not need to violate the standard DL security > assumption to achieve that. > > With the 'interpolation' in effect the same attack applies but its > execution is somewhat more complex: instead of adding the negation of P1 I > must add a number of multiplicities of P1 (like P1*2, P1*3, P1*4...) > selected so that their interpolation coefficients add up to -1. Finding a > suitable subset requires solving a randomized modular subset sum problem > and Wagner's algorithm provides a computationally tractable solution to it. > > The potential of rogue keys applies to both the keys themselves and to the > nonces. There are several ways to prevent these attacks, the musig paper > describes a delinearization technique which doesn't require additional > interaction or communication. > > I haven't tested whether the R,s version is susceptible though. >> > > There is a perfect bijection between the two encodings which is easily > computable, so they're the same thing from an abstract security perspective. > > --0000000000001260b305759bb0e7 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Greg,

I added, stripped= out, and added analogous musig delinearization 3 times in response to stuf= f posted here.=C2=A0 I'm adding it back now. Not sure why my head is th= ick around that issue.

The security= advantages of a redistributable threshold system are huge.=C2=A0=C2=A0 If = a system isn't redistributable, then a single lost or compromised key r= esults in lost coins... meaning the system is essetntially unusable.
<= div>
I'm actually worried that Bitcoin releases a multisi= g that encourages loss.




On Tue, Sep 11, 20= 18 at 1:00 PM Gregory Maxwell <greg@xip= h.org> wrote:
On Tue, Sep 11, 2018 at 4:34 PM Erik Aronesty <erik@q32.com> wrote:
To answer points:

- I switched to the medium = article so that I could correct, edit and improve things to make them more = clear.
- I responded to feedback by modifying the prot= ocol to make it work - not by ignoring it.
To this moment there remains no response at your post.
https://bitcointalk.org/index.php?topic=3D4973123.0
=C2=A0
I'm not sure how I am supposted to have figure= d out that you wrote a somewhat different repost of it elsewhere...

- An M-1 rogue-key attack would require the attacker would to eith= er

=C2=A0 - attack the hash function to produce a p= redictable R based on a known mesage
=C2=A0 - attack the DLP to i= nfluence x or k=C2=A0

Neither attack gives any par= ticular advantage to someone who has M-1 keys.

You keep asserting this. It isn't true. Asserting it mo= re does not make it any more true.=C2=A0 I already explained how to attack = this style of signature (e.g. in the BCT thread).

<= div>Set aside your 'interpolation' for a moment, and imagine that y= ou construct a 2 of 2 signature by just adding the keys.=C2=A0 Your tell me= your key, P1=C2=A0 and then I tell you that my key P2 which I derived by c= omputing -P1=C2=A0 + xG.=C2=A0=C2=A0 We now compute P =3D P1 + P2 =3D P1=C2= =A0+ -P1=C2=A0+ xG =3D xG ... and now in spite adding P1 with an unknown di= screte log, I know the discrete log of P with respect to G and I did not ne= ed to violate the standard DL security assumption to achieve that.

With the 'interpolation' in effect the same attack= applies but its execution is somewhat more complex: instead of adding the = negation of P1=C2=A0 I must add a number of multiplicities of P1 (like P1*2= , P1*3, P1*4...) selected so that their interpolation coefficients add up t= o -1. Finding a suitable subset requires solving a randomized modular subse= t sum problem and Wagner's algorithm provides a computationally tractab= le solution to it.

The potential of rogue keys app= lies to both the keys themselves and to the nonces. There are several ways = to prevent these attacks, the musig paper describes a delinearization techn= ique which doesn't require additional interaction or communication.
=

I haven't tested whether the R,s version is susceptib= le though.=C2=A0=C2=A0

The= re is a perfect bijection between the two encodings which is easily computa= ble, so they're the same thing from an abstract security perspective.
=C2=A0
--0000000000001260b305759bb0e7--