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
199
200
201
202
203
204
205
|
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 ADE9FC74
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 19 Jul 2018 12:16:19 +0000 (UTC)
Received: by mail-wr1-f54.google.com with SMTP id r16-v6so7829362wrt.11
for <bitcoin-dev@lists.linuxfoundation.org>;
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: <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>
<CAJowKg+rC9rmv--NxtrFQ=ea4B20u0ozkmA5hARpA4wLinnVQg@mail.gmail.com>
In-Reply-To: <CAJowKg+rC9rmv--NxtrFQ=ea4B20u0ozkmA5hARpA4wLinnVQg@mail.gmail.com>
From: Erik Aronesty <erik@q32.com>
Date: Thu, 19 Jul 2018 08:16:04 -0400
Message-ID: <CAJowKg+QxcU0ECpZrvUckXQfBpn6Qri=gWzLA7+Y2mvTAq_mSw@mail.gmail.com>
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 <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: 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 <erik@q32.com> 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 <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
>>
>
>
--0000000000007078d7057159252b
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"auto">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.</div><br><div class=3D"g=
mail_quote"><div dir=3D"ltr">On Wed, Jul 11, 2018, 10:45 AM Erik Aronesty &=
lt;<a href=3D"mailto:erik@q32.com">erik@q32.com</a>> wrote:<br></div><bl=
ockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #=
ccc solid;padding-left:1ex"><div dir=3D"ltr">OK, so you're going with t=
his 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 pri=
vate 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 kno=
w their public keys.</div><div><br></div><div>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.</div><div><br></div><div>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><div><br></div></div><div class=3D"gmail_extra"><br><div class=3D"gmai=
l_quote">On Wed, Jul 11, 2018 at 6:35 AM, Adam Back <span dir=3D"ltr"><<=
a href=3D"mailto:adam.back@gmail.com" target=3D"_blank" rel=3D"noreferrer">=
adam.back@gmail.com</a>></span> wrote:<br><blockquote class=3D"gmail_quo=
te" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"=
><div dir=3D"auto"><span><div dir=3D"ltr" style=3D"font-family:sans-serif">=
On Wed, Jul 11, 2018, 02:42 Erik Aronesty via bitcoin-dev <<a href=3D"ma=
ilto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank" rel=3D"norefe=
rrer">bitcoin-dev@lists.linuxfoundation.org</a>> wrote:<br></div><span s=
tyle=3D"font-family:sans-serif">> Basically you're just replacing ad=
dition with interpolation everywhere in the musig construction</span>=C2=A0=
<div dir=3D"auto"><br></div></span><div dir=3D"auto">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.</div><div dir=
=3D"auto"><br></div><div dir=3D"auto">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</div><div dir=3D"auto"><br></div><div dir=3D"auto">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.</div><div dir=3D"auto"><br></div><div dir=
=3D"auto">Btw Wagner also breaks this earlier delinearization scheme S=3DH(=
A)*A+H(B)*B+H(C)*C</div><span class=3D"m_-2119242826565656256HOEnZb"><font =
color=3D"#888888"><div dir=3D"auto"><br></div><div dir=3D"auto">Adam</div><=
/font></span></div>
</blockquote></div><br></div>
</blockquote></div>
--0000000000007078d7057159252b--
|
