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
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
|
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 6CDE1DB5
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 11 Sep 2018 17:20:20 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-wm0-f43.google.com (mail-wm0-f43.google.com [74.125.82.43])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 906FE7D3
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 11 Sep 2018 17:20:19 +0000 (UTC)
Received: by mail-wm0-f43.google.com with SMTP id y139-v6so1818794wmc.2
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 11 Sep 2018 10:20: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=mdsTcfMugvJFX+aqQgQ1zwJMvFDhkrA8j3l25BBxcPc=;
b=yhR23sKovsM0w1ME7O1hguSelrv/iShavqxjOLYgSantD6n7s0g9d5Q59S5n7U3TTT
Zeig4c7zjcJX2HZqjJy+X25MrDVnl4LBMeNFmlqUI4MrSZtyFkLXwPGaHhrmVnY0kzjs
7yD7k3eNAzOk+2lk0XGsCWSdqqFf6SbLGnAb4dyhDaZ2T/RcwehSTS0X26vAyXQVIjnQ
JgjLsiuoiR98/qNu91C/kR5/ADLBXGQSyY6odYRgt3a3ldof4c5X9jzOWc7+yNPOBBoS
8Ewq2aBiqZYlD0bhQ21yVEWptDtb079kPcpkln4v1o65sDnc9fEBnTCZ5bUqyWVmmF2G
aK5A==
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=mdsTcfMugvJFX+aqQgQ1zwJMvFDhkrA8j3l25BBxcPc=;
b=UddGFqiOyPSDHauGM4aEYZRRfsyWwKxZx/stCxxQ4tgixBUY21Ssu1pCwriCPOnpYm
oJdM0ngUNaHRvrxLF96kMQO73BmY6luAQPlJG/9uSlwdgEeDDmvOkhBwxMIK4a+T09/L
oiyHqQANMhlPQULWXMBm2eIeLcpaWDgZUEalxaVbVdFydvcSbtn46vOO6jrKYVOD+BGO
/+Iy/RomAbwV5TzAAo5wDLle2JXABpb670d6DOySsctC0iTaGE8AnhtzGh0UQTZUIEiF
lmOlKxemGv3iLg+5dnhAHFt0TiR1GIIxa7bJn+8Zdh8GKlM5F4/oJ4L4NFoIiPrzDG5t
G34A==
X-Gm-Message-State: APzg51AZy/opBhrLY6689ILQR6D4ks2jbs/yFC6NqkmQH9eFk1pExVuv
bZloxogNHezYcKkGCSFLNZqs7tVzyKRwFZUrw1fORkaNjsze
X-Google-Smtp-Source: ANB0Vdb0N14ymvMalEJGSLPaKJbi+AGjHE5Bx4i9Sfh7fZzucuKncADNuyogm7jafK+bKeYm66KmVB6FwFYQTjXK0+E=
X-Received: by 2002:a1c:70b:: with SMTP id 11-v6mr2018201wmh.151.1536686417926;
Tue, 11 Sep 2018 10:20:17 -0700 (PDT)
MIME-Version: 1.0
References: <CAPg+sBj7f+=OYXuOMdNeJk3NBG67FSQSF8Xv3seFCvwxCWq69A@mail.gmail.com>
<2e620d305c86f65cbff44b5fba548dc85c118f84.camel@timruffing.de>
<20180812163734.GV499@boulet.lan>
<CAJowKg+h11YkwOo-gyWCw+87Oh-9K34LOnJ1730hhpoVR2m5sA@mail.gmail.com>
<20180903000518.GB18522@boulet.lan>
<CAJowKg+PDtEV3je_N9Ra6u3n4+ZQ3ozYapt8ivxGYYU28Qad+w@mail.gmail.com>
<CAAS2fgT0uBGbLBOW4TxA-qCzOLwoQ1qSV-R0dMKRzPLAm_UOqQ@mail.gmail.com>
<CAJowKg+-45h6vraL1PpnqfhHSbG+G40L+FD7xN+C-Dn1E6Y_Vg@mail.gmail.com>
<CAAS2fgSfdfQ2CiEabjrjspQGQufwzk84f1mzM1j_LRWqAPd8wA@mail.gmail.com>
In-Reply-To: <CAAS2fgSfdfQ2CiEabjrjspQGQufwzk84f1mzM1j_LRWqAPd8wA@mail.gmail.com>
From: Erik Aronesty <erik@q32.com>
Date: Tue, 11 Sep 2018 13:20:01 -0400
Message-ID: <CAJowKgK3Pxev4pDH4xVLPvmHda8oAfq=fya4TY+_dodUJ7j9Nw@mail.gmail.com>
To: Gregory Maxwell <greg@xiph.org>
Content-Type: multipart/alternative; boundary="0000000000001260b305759bb0e7"
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, 12 Sep 2018 13:40:40 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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 <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: Tue, 11 Sep 2018 17:20:20 -0000
--0000000000001260b305759bb0e7
Content-Type: text/plain; charset="UTF-8"
Greg,
I added, stripped out, and added analogous musig delinearization 3 times in
response to stuff posted here. I'm adding it back now. Not sure why my
head is thick around that issue.
The security advantages of a redistributable threshold system are huge.
If a system isn't redistributable, then a single lost or compromised key
results in lost coins... meaning the system is essetntially unusable.
I'm actually worried that Bitcoin releases a multisig that encourages loss.
On Tue, Sep 11, 2018 at 1:00 PM Gregory Maxwell <greg@xiph.org> wrote:
> On Tue, Sep 11, 2018 at 4:34 PM Erik Aronesty <erik@q32.com> 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.
>
>
--0000000000001260b305759bb0e7
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>Greg, <br></div><div><br></div><div>I added, stripped=
out, and added analogous musig delinearization 3 times in response to stuf=
f posted here.=C2=A0 I'm adding it back now. Not sure why my head is th=
ick around that issue.<br></div><div></div><div><br></div><div>The security=
advantages of a redistributable threshold system are huge.=C2=A0=C2=A0 If =
a system isn't redistributable, then a single lost or compromised key r=
esults in lost coins... meaning the system is essetntially unusable.</div><=
div><br></div><div>I'm actually worried that Bitcoin releases a multisi=
g that encourages loss.<br></div><div><br></div><div><br></div><div><br></d=
iv></div><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Tue, Sep 11, 20=
18 at 1:00 PM Gregory Maxwell <<a href=3D"mailto:greg@xiph.org">greg@xip=
h.org</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"ma=
rgin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"lt=
r"><div dir=3D"ltr">On Tue, Sep 11, 2018 at 4:34 PM Erik Aronesty <<a hr=
ef=3D"mailto:erik@q32.com" target=3D"_blank">erik@q32.com</a>> wrote:<br=
><div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"marg=
in:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1e=
x"><div dir=3D"ltr">
<div>To answer points:</div><div><br></div><div>- I switched to the medium =
article so that I could correct, edit and improve things to make them more =
clear.</div><div></div><div>- I responded to feedback by modifying the prot=
ocol to make it work - not by ignoring it.</div></div></blockquote><div><br=
></div><div>To this moment there remains no response at your post.<br></div=
><div><a href=3D"https://bitcointalk.org/index.php?topic=3D4973123.0" targe=
t=3D"_blank">https://bitcointalk.org/index.php?topic=3D4973123.0</a><br></d=
iv><div>=C2=A0</div><div>I'm not sure how I am supposted to have figure=
d out that you wrote a somewhat different repost of it elsewhere...<br></di=
v><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px =
0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=
=3D"ltr">- An M-1 rogue-key attack would require the attacker would to eith=
er <br><div><br></div><div>=C2=A0 - attack the hash function to produce a p=
redictable R based on a known mesage</div><div>=C2=A0 - attack the DLP to i=
nfluence x or k=C2=A0</div><div><br></div><div>Neither attack gives any par=
ticular advantage to someone who has M-1 keys.</div></div></blockquote><div=
><br></div><div>You keep asserting this. It isn't true. Asserting it mo=
re does not make it any more true.=C2=A0 I already explained how to attack =
this style of signature (e.g. in the BCT thread).<br></div><div><br></div><=
div>Set aside your 'interpolation' for a moment, and imagine that y=
ou construct a 2 of 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 c=
omputing -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 di=
screte log, I know the discrete log of P with respect to G and I did not ne=
ed to violate the standard DL security assumption to achieve that.</div><di=
v><br></div><div>With the 'interpolation' in effect the same attack=
applies but its 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 t=
o -1. Finding a suitable subset requires solving a randomized modular subse=
t sum problem and Wagner's algorithm provides a computationally tractab=
le solution to it.</div><div><br></div><div>The potential of rogue keys app=
lies to both the keys themselves and to the nonces. There are several ways =
to prevent these attacks, the musig paper describes a delinearization techn=
ique which doesn't require additional interaction or communication.<br>=
</div><div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px =
0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div=
dir=3D"ltr"><div>I haven't tested whether the R,s version is susceptib=
le though.=C2=A0=C2=A0 <br></div></div></blockquote><div><br></div><div>The=
re is a perfect bijection between the two encodings which is easily computa=
ble, so they're the same thing from an abstract security perspective.<b=
r></div><div>=C2=A0</div></div></div></div>
</blockquote></div>
--0000000000001260b305759bb0e7--
|
