Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id ADE9FC74 for ; Thu, 19 Jul 2018 12:16:20 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wr1-f54.google.com (mail-wr1-f54.google.com [209.85.221.54]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 3A6FD25A for ; Thu, 19 Jul 2018 12:16:19 +0000 (UTC) Received: by mail-wr1-f54.google.com with SMTP id r16-v6so7829362wrt.11 for ; Thu, 19 Jul 2018 05:16: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=HgHMen4ptfaldXTBm19xqah7PtL+lhZtsrGWvW7yzOs=; b=wNGMihDqzI4zTuigFTyXIyCCUGMoI1juBF4LrH5hd22qaA2OkwGDCjFUEZ0UFB5XGb NdIOTaK9QK3RWwc471EEdC589s/KnN54/lOhB881tiPLlMiXcBEgPlMEjIb2brKCBeph exxEic+Z/UCwV/yfhHhmyyxhF3cP25T6Yj4IoEYrA2cKLAZi9cezxkie2C/zkrtU50fa N0WXePVS3ctePgQTUk+sRiez8BoGnvuARUqeUCRUeJH0PMCuK/Y8VhCiZU7Fb1NMifTU HHc4upQYdTJzlWgVyjGaI/1kZ927oHik1cNV+/tcpwlBzbL/JEWOgQM/XPf04irN7OCH akyg== 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=HgHMen4ptfaldXTBm19xqah7PtL+lhZtsrGWvW7yzOs=; b=gJNoR8c3WyuSSMbMvynF+Uw9B/vqyEmQ3BFM+eU0HrP2zJDlGzo1cmacIe7LKtp9JT PouwnsjehDJ0eW99rY7ImABIXYS4M3KW4E7kis/MkOjfJdQxmDgxyNN47td9UPSOxw4o yHiGkfvSUx3CCHSbmrO8BFpN1Biu6M9sR+QzXCUsmsTZge4ApZshhMK4pSs4CUGrqSs1 4jJ6LmHxNEUGlnt+SJYOIfh8INhTx1wEFjrVABUGaQ9+dTUnPJMP9BbQtarshJ2zYD9Y BmVFWjVCBftaJdMkcRXJlo1aYXDnAus8JUiGFkqn87UhPv4cA60qWmDq+Ki/OM88OjwV EyDw== X-Gm-Message-State: AOUpUlGC1PtFNYz9YZWukUJTt4LTjaxSgSlbfhFMjUWsjAAv4NJp6NGd 9gc/+wkYf1ni1MNCn4033ykz+citmGUXSAWrXCjxU0/KNw== X-Google-Smtp-Source: AAOMgpcfO/kuCRWnEz1CW/uWYEewbR15Lyr4u3JF794pBfZLeKLbgchaD264Mf1dQ0N3KK6B3DXQVYO6XrWgb9Z7ag4= X-Received: by 2002:adf:9d1c:: with SMTP id k28-v6mr7629328wre.29.1532002577707; Thu, 19 Jul 2018 05:16:17 -0700 (PDT) MIME-Version: 1.0 References: <08201f2292587821e6d23f6cc201d95e6e5ad2cd.camel@timruffing.de> In-Reply-To: From: Erik Aronesty Date: Thu, 19 Jul 2018 08:16:04 -0400 Message-ID: To: adam@cypherspace.org Content-Type: multipart/alternative; boundary="0000000000007078d7057159252b" 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: Thu, 19 Jul 2018 12:51:32 +0000 Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] Multiparty signatures 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: Thu, 19 Jul 2018 12:16:20 -0000 --0000000000007078d7057159252b Content-Type: text/plain; charset="UTF-8" Also Wagner's algorithm shouldn't be applicable for a number of reasons. you can't birthday attack something where there's only a single variable that you can modify. And when you change the equation from additive you now have a multi-dimensional equation we're partitioning won't function. this is the basis of the perfect security of Shamir secret sharing. On Wed, Jul 11, 2018, 10:45 AM Erik Aronesty wrote: > OK, so you're going with this scenario: > > 1. I know Apub and Bpub, > 2. I know M is 3 > 3. I'm choosing a random number for C's private key > > Cpub is g^C > > The equation I am solving for .. and trying to factor myself out of is > g^Ax + g^B*2 + g^C*3 > > I don't know A or B... I only know their public keys. > > I don't think it's possible to adaptively choose C for an attack on the > multisig construction, when using hash of the public key as the X > coordinate in the polynomial, because in order to satisfy the equation and > factor out C, you would need to be able to break the hash. > > With an additive construction, yes... adaptive attacks are possible. But > in a shamir secret sharing interpolation, you need a public X coordinate as > well as a secret share. Choosing hash(pub) as X, prevents this attack. > > > On Wed, Jul 11, 2018 at 6:35 AM, Adam Back wrote: > >> On Wed, Jul 11, 2018, 02:42 Erik Aronesty via bitcoin-dev < >> bitcoin-dev@lists.linuxfoundation.org> wrote: >> > Basically you're just replacing addition with interpolation everywhere >> in the musig construction >> >> Yes, but you can't do that without a delinearization mechanism to prevent >> adaptive public key choice being used to break the scheme using Wagner's >> attack. It is not specific to addition, it is a generalized birthday attack. >> >> Look at the delinearization mechanism for an intuition, all public keys >> are hashed along with per value hash, so that pre-commits and forces the >> public keys to be non-adaptively chosen. >> >> Adaptively chosen public keys are dangerous and simple to exploit for >> example pub keys A+B, add party C' he chooses C=C'-A-B, now we can sign for >> A+B+C using adaptively chose public key C. >> >> Btw Wagner also breaks this earlier delinearization scheme >> S=H(A)*A+H(B)*B+H(C)*C >> >> Adam >> > > --0000000000007078d7057159252b Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Also Wagner's algorithm shouldn't be applicable f= or a number of reasons.=C2=A0 you can't birthday attack something where= there's only a single variable that you can modify.=C2=A0 =C2=A0 And w= hen you change the equation from additive you now have a multi-dimensional = equation we're partitioning won't function.=C2=A0 this is the basis= of the perfect security of Shamir secret sharing.

On Wed, Jul 11, 2018, 10:45 AM Erik Aronesty &= lt;erik@q32.com> wrote:
OK, so you're going with t= his scenario:

1. I know Apub and Bpub,
2. = I know M is 3
3. I'm choosing a random number for C's pri= vate key

Cpub is g^C

The = equation I am solving for .. and trying to factor myself out of is g^Ax + g= ^B*2 + g^C*3

I don't know A or B... I only kno= w their public keys.

I don't think it's po= ssible to adaptively choose C for an attack on the multisig construction, w= hen using=C2=A0hash of the public key as the X coordinate in the polynomial= , because in order to satisfy the equation and factor out C, you would need= to be able to break the hash.

With an additive co= nstruction, yes... adaptive attacks are possible.=C2=A0 =C2=A0But in a sham= ir secret sharing interpolation, you need a public X coordinate as well as = a secret share.=C2=A0 =C2=A0Choosing hash(pub) as X, prevents this attack.<= /div>


On Wed, Jul 11, 2018 at 6:35 AM, Adam Back <<= a href=3D"mailto:adam.back@gmail.com" target=3D"_blank" rel=3D"noreferrer">= adam.back@gmail.com> wrote:
= On Wed, Jul 11, 2018, 02:42 Erik Aronesty via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> Basically you're just replacing ad= dition with interpolation everywhere in the musig construction=C2=A0=

Yes, but you can't= do that without a delinearization mechanism to prevent adaptive public key= choice being used to break the scheme using Wagner's attack. It is not= specific to addition, it is a generalized birthday attack.

Look at the delinearization mechanism= for an intuition, all public keys are hashed along with per value hash, so= that pre-commits and forces the public keys to be non-adaptively chosen.= =C2=A0

Adaptively chosen= public keys are dangerous and simple to exploit for example pub keys A+B, = add party C' he chooses C=3DC'-A-B, now we can sign for A+B+C using= adaptively chose public key C.

Btw Wagner also breaks this earlier delinearization scheme S=3DH(= A)*A+H(B)*B+H(C)*C

Adam
<= /font>

--0000000000007078d7057159252b--