1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
|
Return-Path: <earonesty@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 0D175D4C
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 11 Jul 2018 14:46:01 +0000 (UTC)
Received: by mail-wr1-f53.google.com with SMTP id h9-v6so18470707wro.3
for <bitcoin-dev@lists.linuxfoundation.org>;
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: <CALqxMTHYaspkn8JupaHBeLDxLOfZbnwcne2AVeFZe2ADOefktA@mail.gmail.com>
References: <CAJowKgLrSe77sqO2iB7mYboo_HW=YjO4=AFdv7L5FUi2vygMiQ@mail.gmail.com>
<08201f2292587821e6d23f6cc201d95e6e5ad2cd.camel@timruffing.de>
<CAAS2fgSPUc7xRq36rZ9BVLjUTdd152Fgho4sjJXLhfrc71vPMw@mail.gmail.com>
<CAJowKgL-nRcruXhWdGWrT4x+oV7i3jYST2Wa3bF5m6iT_mOyMw@mail.gmail.com>
<CAPg+sBjdu4mnda-P0y7Ddu-rN7a1GiUt0hY_wYGsy_bJLKOYMA@mail.gmail.com>
<CAJowKgLSQZ1LrZayDi7EFc-NSfK_AD+zBdyaF7jBeQRP7tOwYQ@mail.gmail.com>
<CAPg+sBizrx20XShpeZRvZd4bfq1=E+MFUDmSC9X-xK1CSbV5kQ@mail.gmail.com>
<CAJowKg+=7nS4gNmtc8a4-2cu1uCOPqxjfchFwDVqUciKNMUYWQ@mail.gmail.com>
<CAJowKgJ3K=wmCEtoZXJZhrnnA8XJcHYg788KP+7MCeP4Mxf-0w@mail.gmail.com>
<CAAS2fgSmA02s6Vdk_FYv6NJ4smLBgxnuT4jRYU44G7=bbzv2MA@mail.gmail.com>
<CAJowKgJjQ8EGgbCurOSjTh8ij42_BVeD6dE0y67tzN0Zop3pyg@mail.gmail.com>
<CAAS2fgRrkzq6Fa5T_-YDwLDkwi30LpDtMObMEBE+Fmmj0LJpBw@mail.gmail.com>
<CAJowKgL0b3RT7XwRTF+ohoJCyZAW-ZJ+-8Lijj_s1rqqxgU7VQ@mail.gmail.com>
<CAJowKg+UaMsY_nL6SBfb20Ltki+LdhXOwwvG_mAsUq_ww3Tesg@mail.gmail.com>
<CALqxMTHYaspkn8JupaHBeLDxLOfZbnwcne2AVeFZe2ADOefktA@mail.gmail.com>
From: Erik Aronesty <erik@q32.com>
Date: Wed, 11 Jul 2018 10:45:58 -0400
X-Google-Sender-Auth: mV1nADyiQXTxDyow8OBwuz7DxQs
Message-ID: <CAJowKg+rC9rmv--NxtrFQ=ea4B20u0ozkmA5hARpA4wLinnVQg@mail.gmail.com>
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 <bitcoin-dev@lists.linuxfoundation.org>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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 <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 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
<div dir=3D"ltr">OK, so you're going with this scenario:<br><div><br></=
div><div>1. I know Apub and Bpub,</div><div>2. I know M is 3</div><div>3. I=
'm choosing a random number for C's private key</div><div><br></div=
><div>Cpub is g^C</div><div><br></div><div>The equation I am solving for ..=
and trying to factor myself out of is g^Ax + g^B*2 + g^C*3</div><div><br><=
/div><div>I don't know A or B... I only know their public keys.</div><d=
iv><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div></div><d=
iv class=3D"gmail_extra"><br><div class=3D"gmail_quote">On Wed, Jul 11, 201=
8 at 6:35 AM, Adam Back <span dir=3D"ltr"><<a href=3D"mailto:adam.back@g=
mail.com" target=3D"_blank">adam.back@gmail.com</a>></span> wrote:<br><b=
lockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px =
#ccc solid;padding-left:1ex"><div dir=3D"auto"><span class=3D""><div dir=3D=
"ltr" style=3D"font-family:sans-serif">On Wed, Jul 11, 2018, 02:42 Erik Aro=
nesty via bitcoin-dev <<a href=3D"mailto:bitcoin-dev@lists.linuxfoundati=
on.org" target=3D"_blank">bitcoin-dev@lists.<wbr>linuxfoundation.org</a>>=
; wrote:<br></div><span style=3D"font-family:sans-serif">> Basically you=
're just replacing addition with interpolation everywhere in the musig =
construction</span>=C2=A0<div dir=3D"auto"><br></div></span><div dir=3D"aut=
o">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.</div><div dir=3D"auto"><br></div><div dir=3D"auto">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</div><div dir=3D"auto"><br></div><div dir=3D"au=
to">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.</div><div dir=3D"auto"=
><br></div><div dir=3D"auto">Btw Wagner also breaks this earlier delineariz=
ation scheme S=3DH(A)*A+H(B)*B+H(C)*C</div><span class=3D"HOEnZb"><font col=
or=3D"#888888"><div dir=3D"auto"><br></div><div dir=3D"auto">Adam</div></fo=
nt></span></div>
</blockquote></div><br></div>
--00000000000013db360570ba4e00--
|
