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 230C1E32 for ; Tue, 11 Sep 2018 17:00:43 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ua1-f50.google.com (mail-ua1-f50.google.com [209.85.222.50]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9FBBF7D2 for ; Tue, 11 Sep 2018 17:00:41 +0000 (UTC) Received: by mail-ua1-f50.google.com with SMTP id h1-v6so21273355uao.8 for ; Tue, 11 Sep 2018 10:00:41 -0700 (PDT) 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=Mt6R4gbBls8winZD1ERnSxK8Rvgzn97PR+2Tqw33ls8=; b=FtNNjdgwuoFjeEno5uk0/JISbx0T6CiAX50Th6/xlmHdl+MOYLBiEt7NO3NV5wuVEl P+bLO2oxcZOgg6huBfp8fezm38zD9+jlOrbAircQrvQLm8ELRf+7DY7Ly2gfwHwZZqAa gP63qANoyEZy2qrlAoTngPm/VvNo5YRGRi23Bc0st5eUH5W21LbLEXun5ERnr5LBeoK8 uU1R/yumZlIFSjkhSi/6xwpEnaxvzaczBermfxLpEz+cO6VkjjrgqmOkDsPATKViHO8n 723s02Grqq8QGYf/4VSQOh4ljJIcE/cGHpMeQETPRyHcR0Kz6m37HqStE0skqa4osZJk Ofqg== X-Gm-Message-State: APzg51BjLNMKY2Hp/qSODJo2weuKifdNF8sgpC6S7PE+c5Tx0omfr1W/ PdFEMkUG5pJqtUSU9zJB5J6fOdk0JdaIW3h1Tvl3BPSJ X-Google-Smtp-Source: ANB0VdbdcVRHt4JL7RCijZEv7zPF0uCg1zyHwx93s8oBDDYh9iBofNNmC/K9RronM/q7PdauSCS38n40UMcUQNiKZuU= X-Received: by 2002:a67:eb01:: with SMTP id a1-v6mr9216960vso.13.1536685240457; Tue, 11 Sep 2018 10:00:40 -0700 (PDT) MIME-Version: 1.0 References: <2e620d305c86f65cbff44b5fba548dc85c118f84.camel@timruffing.de> <20180812163734.GV499@boulet.lan> <20180903000518.GB18522@boulet.lan> In-Reply-To: From: Gregory Maxwell Date: Tue, 11 Sep 2018 17:00:25 +0000 Message-ID: To: Erik Aronesty Content-Type: multipart/alternative; boundary="000000000000e3a0c905759b696c" X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,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:39:47 +0000 Cc: Bitcoin Dev 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:00:43 -0000 --000000000000e3a0c905759b696c Content-Type: text/plain; charset="UTF-8" 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. --000000000000e3a0c905759b696c Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Tue, Sep 11, 2018 at 4:34 PM Erik Aron= esty <erik@q32.com> wrote:
<= div dir=3D"ltr">
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.
=C2=A0
I'm not sure how I am supposted to have figured out that you wro= te a somewhat different repost of it elsewhere...

<= blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l= eft:1px solid rgb(204,204,204);padding-left:1ex">
- An M-1 = rogue-key attack would require the attacker would to either

=C2=A0 - attack the hash function to produce a predictable R based= on a known mesage
=C2=A0 - attack the DLP to influence x or k=C2= =A0

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

Yo= u keep asserting this. It isn't true. Asserting it more does not make i= t any more true.=C2=A0 I already explained how to attack this style of sign= ature (e.g. in the BCT thread).

Set aside your= 'interpolation' for a moment, and imagine that you construct a 2 o= f 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 computing -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 discrete log, I k= now the discrete log of P with respect to G and I did not need to violate t= he standard DL security assumption to achieve that.

With the 'interpolation' in effect the same attack applies but it= s 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 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 t= he keys themselves and to the nonces. There are several ways to prevent the= se attacks, the musig paper describes a delinearization technique which doe= sn't require additional interaction or communication.
<= div>I haven't tested whether the R,s version is susceptible though.=C2= =A0=C2=A0

There is a perfe= ct bijection between the two encodings which is easily computable, so they&= #39;re the same thing from an abstract security perspective.
= =C2=A0
--000000000000e3a0c905759b696c--