Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 0D175D4C for ; Wed, 11 Jul 2018 14:46:02 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wr1-f53.google.com (mail-wr1-f53.google.com [209.85.221.53]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 4286DFC for ; Wed, 11 Jul 2018 14:46:01 +0000 (UTC) Received: by mail-wr1-f53.google.com with SMTP id h9-v6so18470707wro.3 for ; Wed, 11 Jul 2018 07:46:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc; bh=84URiSqgF13xDohoNhdPWqQpn3iD8jNMlj7tIY5O914=; b=sKAM1/7TEaCMq1bZudgPB1L0BzF+cJ2+OLtUqoPbyZhSzuvo+jcjR7J46+IQkYIG+9 7EtvwrI/UUwP+5KoqTRElUrb+vyqpqYIUCF/156v/URTbqGqCK1o+vftzwHEaZMiNfzI x1zXqtP615ThS7OY6r2xdulykoIQJnjsj4+9lLxKU6xVJSJeBv77kfoUeWsZJScLps3x az9qaYxDi7XParoN5LOy58Raud2bPzqr9gdHXIzg/3Sfk+rOrLTZHn+tLbZ5HFSMsHrZ uezcZtp0BtTlKaFC9XdOOSzC4+GP8h5WjRL054l5E0VCeb9+45qpBm6uLJuaRskGufA6 pQHw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=q32-com.20150623.gappssmtp.com; s=20150623; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc; bh=84URiSqgF13xDohoNhdPWqQpn3iD8jNMlj7tIY5O914=; b=jSfahKS3jaHgu5aTmI1yNabBkkFJeVBLRJPFkz7tFYvKDO/NVx8fNxdwhix2aleCMz x+0200VO5wyhf5hBBS0Ive4mInbooflTGVKw6vRPqfN6TBG4wTvmst4fiUFYuMDXn+KT 1dQ1inrmPMMPBqvGQ2gCohYHadstq8X+SNvkfU+vctb/U8JKFr41FngVa4+LKwJFhAbl zVYrjXwJ9BGM1qpj58MDyBEskQbQdQu7NIa2/QlT66JPNdbuvh6PzTj3elwi3uEx5zYb xkHEn671bC9/n/PaRDye4SHtibaTEPaDe7VBWpkNix8rEtQwJzxEqEfBEzfbzhXU/G14 Y5zg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc; bh=84URiSqgF13xDohoNhdPWqQpn3iD8jNMlj7tIY5O914=; b=fQpOJcKQVEojs1Y2OQ4HIeQUAT3NTaeoZXFs98UetgI5JFfGeKTB96OMoRs27wKb4l 7KO8A5sr5RGKEH5d9ICjKjm5PwPzdK4eG6Va+N0QC/djdgJPJSwoKIvJv45MzXXpNbB0 F9qROHj2O/JVEDpYUCkNS/YTfKir6N3cHorrF8+hfzA6ZjUEyApHiFTtaYzHC2kngCRq 732ypXpljhJJ4KkdgV/M/hr6kLDKQDo6WQ3gvHhKb3NHVsYvcI2htrGrLfQcBtB/KXOG HlpcmfEVOa8i2HqIPGPteljMezYRXGQ1UQuiIOQF55xM+VInrHn1MOKaOwqZ+uXgGbpD Onrw== X-Gm-Message-State: APt69E0QqR6CxyI/UmVWSJQJgtIQ8scnQmKW3aK1V6Xo3i4t7ddmfG9m 2iMKYUYLNEUl2yqvtxQv4AKfKljtraUrvBw9kHzIpak= X-Google-Smtp-Source: AAOMgpcYLl657xyTIZD5TaDewqhPCuDvPWNN7Tt1Qzui2vFy6tDO2+kAlBA2diptLOXqhsR2Bl54WXFFTlsqnFP2F1M= X-Received: by 2002:adf:9d1c:: with SMTP id k28-v6mr22570660wre.29.1531320359703; Wed, 11 Jul 2018 07:45:59 -0700 (PDT) MIME-Version: 1.0 Sender: earonesty@gmail.com Received: by 2002:a1c:b786:0:0:0:0:0 with HTTP; Wed, 11 Jul 2018 07:45:58 -0700 (PDT) In-Reply-To: References: <08201f2292587821e6d23f6cc201d95e6e5ad2cd.camel@timruffing.de> From: Erik Aronesty Date: Wed, 11 Jul 2018 10:45:58 -0400 X-Google-Sender-Auth: mV1nADyiQXTxDyow8OBwuz7DxQs Message-ID: To: adam@cypherspace.org Content-Type: multipart/alternative; boundary="00000000000013db360570ba4e00" 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, 11 Jul 2018 14:46:26 +0000 Cc: Bitcoin Dev 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: Wed, 11 Jul 2018 14:46:02 -0000 --00000000000013db360570ba4e00 Content-Type: text/plain; charset="UTF-8" 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 > --00000000000013db360570ba4e00 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
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

<= /div>
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=C2=A0hash of the p= ublic key as the X coordinate in the polynomial, because in order to satisf= y the equation and factor out C, you would need to be able to break the has= h.

With an additive construction, yes... adaptive = attacks are possible.=C2=A0 =C2=A0But in a shamir secret sharing interpolat= ion, you need a public X coordinate as well as a secret share.=C2=A0 =C2=A0= Choosing hash(pub) as X, prevents this attack.


On Wed, Jul 11, 201= 8 at 6:35 AM, Adam Back <adam.back@gmail.com> wrote:
On Wed, Jul 11, 2018, 02:42 Erik Aro= nesty via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>= ; wrote:
> Basically you= 're just replacing addition with interpolation everywhere in the musig = construction=C2=A0

Yes, but you can't do that without a delinearization mechanism to pr= event adaptive public key choice being used to break the scheme using Wagne= r's attack. It is not specific to addition, it is a generalized birthda= y attack.

Look at the de= linearization 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 n= on-adaptively chosen.=C2=A0

Adaptively chosen public keys are dangerous and simple to exploit for e= xample 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 delineariz= ation scheme S=3DH(A)*A+H(B)*B+H(C)*C

Adam

--00000000000013db360570ba4e00--