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
224
225
226
227
|
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 5CD5AFB6
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 11 Sep 2018 16:34:29 +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 7ADD5716
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 11 Sep 2018 16:34:27 +0000 (UTC)
Received: by mail-wm0-f43.google.com with SMTP id t25-v6so1672836wmi.3
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 11 Sep 2018 09:34:27 -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;
bh=wm/1Ch6r+zTvO8Geqs0SsAy6qZGNk2RGbhVajCIp7Ds=;
b=ce9Cs//G5D9FnXwoKyOABg8GdO+zPNgK17bvzmBTLEmnJZk6GmYoknKghbxKn5yjX9
mQZrF+62n30G4lAYvXxR98vNuh2xr4PG5w3wlHbiYVsMKwBwcntu9udbNSow9KUy9JeN
phoiG46vMgnlscqr/mUaEg9bxm44nUt2NRZSLuBQqWYXuIL/zJLyWsxOeMQrScro9+E5
RlhHAgDWgj5VCE6QywluH9OTlith9NsI6YA/O61AcDII9FoKsPMNwswlFMoLONavuiyz
Vb83omMNiJ2UysvGih8ysyvmKgrPSGSlsSpz+ySmsbHEu83KXrq7AVtQjd8XG/NzQ6kZ
eEVw==
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;
bh=wm/1Ch6r+zTvO8Geqs0SsAy6qZGNk2RGbhVajCIp7Ds=;
b=grj0zO5slmGcYpqSP+YtdWR4uMNTGVFPALb8t4KFPS8691GV9hHn+p6snDxo8ee+AZ
aPrF3VpYo15QS93em3xO9GU0bYhwq0f0fUXMeczqS28iIbu5PpVvE6/OkkXvMi8DUS2C
SelbZa2WMoOPJ4nLHYPYplVQ4gv5qlcEJJjx9bknCAUnqlu2rqdUnEjlBAMl9wkY6KcL
tNE68QRxUGWG8sZ5MVm80TqLObrn4PFgW62xlg76DA0YYZzU32WuRJ+BUGyYc0vmSw5k
wVdvZQq3Ga6QmyqizLz17kaqpjwnk3/RZwO40dWdZ025dptkPeBtkfGvXy26a/Sm8djt
1AVQ==
X-Gm-Message-State: APzg51Bhlt2NAd5GKbeTG7y25AYK9hMTZVLkmLDwQXLPQAuXUCLBiI7B
F0tK49AiczTqrTYIihB8xCwuz3sZMkSx22eZ/xE9Vio=
X-Google-Smtp-Source: ANB0VdblLTCjNhbAfmw1eLbgmNiEWejVl99QUr7QlxswVuv1qLXSzQPtY/ffR/2JuyFREFwvUxs0Nc6oM9PQ7ZwGzTg=
X-Received: by 2002:a1c:1609:: with SMTP id 9-v6mr1979799wmw.12.1536683665674;
Tue, 11 Sep 2018 09:34:25 -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>
In-Reply-To: <CAAS2fgT0uBGbLBOW4TxA-qCzOLwoQ1qSV-R0dMKRzPLAm_UOqQ@mail.gmail.com>
From: Erik Aronesty <erik@q32.com>
Date: Tue, 11 Sep 2018 12:34:11 -0400
Message-ID: <CAJowKg+-45h6vraL1PpnqfhHSbG+G40L+FD7xN+C-Dn1E6Y_Vg@mail.gmail.com>
To: Gregory Maxwell <greg@xiph.org>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000000656ce05759b0ce0"
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:26 +0000
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 16:34:29 -0000
--0000000000000656ce05759b0ce0
Content-Type: text/plain; charset="UTF-8"
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.
- I coded it up in python so I could be sure it worked, because I was
concerned that it was broken
- Yes, coding it up showed me that it's definitely interactive, and no
different than a "standard shnorr sig" in any meaningful way regarding the
security
- No special protocol support is needed over Schnorr signing itself. The
e, s version can be made at least as secure as schnorr + DLP. I haven't
researched the R,s version.
- 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.
I haven't tested whether the R,s version is susceptible though.
On Thu, Sep 6, 2018 at 9:15 AM Gregory Maxwell via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> On Wed, Sep 5, 2018 at 1:49 PM Erik Aronesty via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> > Detailed explanation with code snippets:
> >
> > https://medium.com/@simulx/an-m-of-n-bitcoin-multisig-scheme-[snip]
>
> This appears to be a repost of the broken scheme you posted about on
> Bitcointalk, but then failed to respond to the response.
>
> https://bitcointalk.org/index.php?topic=4973123.0
>
> > The more I look into it and speak to professors about i, the more it
> seems "so trivial nobody really talks about it".
>
> I think you might be falling into the trap of ignoring feedback you
> don't like and and accepting that which sounds like "yea yea,
> something like that".
>
> Something "like that" does work: and is expressly and explicitly
> anticipated by the BIP but to be both secure and functional requires
> proper delineation (E.g. musig) _and_ interaction. What you're
> proposing is continually vague. My best efforts at making sense of
> what you've written indicate that either it's non-interactive and
> not-actually functional at all, OR it's interactive and just a less
> secure subset (no proper delinearization to prevent rogue key attacks)
> of what we already propose.
>
> When Poelstra suggests a CAS implementation he means something like
> this Sage notebook: http://bitcoin.ninja/secp256k1.ecdsa.sage This
> provides for a method of communicating in both directions which is
> completely precise.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--0000000000000656ce05759b0ce0
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<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>- I coded it up in pyt=
hon so I could be sure it worked, because I was concerned that it was broke=
n<br></div><div>- Yes, coding it up showed me that it's definitely inte=
ractive, and no different than a "standard shnorr sig" in any mea=
ningful way regarding the security <br></div><div></div><div>-
No special protocol support is needed over Schnorr signing itself.=C2=A0 T=
he e, s version can be made at least as secure as schnorr + DLP.=C2=A0 I ha=
ven't researched the R,s version.<br></div><div>- An M-1 rogue-key atta=
ck would require the attacker would to either <br></div><div><br></div><div=
>=C2=A0 - attack the hash function to produce a predictable R based on a kn=
own mesage</div><div>=C2=A0 - attack the DLP to influence x or k=C2=A0</div=
><div><br></div><div>Neither attack gives any particular advantage to someo=
ne who has M-1 keys.</div><div><br></div><div>I haven't tested whether =
the R,s version is susceptible though.=C2=A0=C2=A0 <br></div><div><br><div =
class=3D"gmail-yj6qo gmail-ajU"><div id=3D"gmail-:1l8" class=3D"gmail-ajR" =
tabindex=3D"0"><img class=3D"gmail-ajT" src=3D"https://ssl.gstatic.com/ui/v=
1/icons/mail/images/cleardot.gif"></div></div></div>
</div><br><div class=3D"gmail_quote"><div dir=3D"ltr">On Thu, Sep 6, 2018 a=
t 9:15 AM Gregory Maxwell via bitcoin-dev <<a href=3D"mailto:bitcoin-dev=
@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>> w=
rote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex=
;border-left:1px #ccc solid;padding-left:1ex">On Wed, Sep 5, 2018 at 1:49 P=
M Erik Aronesty via bitcoin-dev<br>
<<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_bla=
nk">bitcoin-dev@lists.linuxfoundation.org</a>> wrote:<br>
> Detailed explanation with code snippets:<br>
><br>
> <a href=3D"https://medium.com/@simulx/an-m-of-n-bitcoin-multisig-schem=
e-%5Bsnip%5D" rel=3D"noreferrer" target=3D"_blank">https://medium.com/@simu=
lx/an-m-of-n-bitcoin-multisig-scheme-[snip]</a><br>
<br>
This appears to be a repost of the broken scheme you posted about on<br>
Bitcointalk, but then failed to respond to the response.<br>
<br>
<a href=3D"https://bitcointalk.org/index.php?topic=3D4973123.0" rel=3D"nore=
ferrer" target=3D"_blank">https://bitcointalk.org/index.php?topic=3D4973123=
.0</a><br>
<br>
> The more I look into it and speak to professors about i, the more it s=
eems "so trivial nobody really talks about it".<br>
<br>
I think you might be falling into the trap of ignoring feedback you<br>
don't like and and accepting that which sounds like "yea yea,<br>
something like that".<br>
<br>
Something "like that" does work: and is expressly and explicitly<=
br>
anticipated by the BIP but to be both secure and functional requires<br>
proper delineation (E.g. musig) _and_ interaction. What you're<br>
proposing is continually vague.=C2=A0 My best efforts at making sense of<br=
>
what you've written indicate that either it's non-interactive and<b=
r>
not-actually functional at all,=C2=A0 OR it's interactive and just a le=
ss<br>
secure subset (no proper delinearization to prevent rogue key attacks)<br>
of what we already propose.<br>
<br>
When Poelstra suggests a CAS implementation he means something like<br>
this Sage notebook: <a href=3D"http://bitcoin.ninja/secp256k1.ecdsa.sage" r=
el=3D"noreferrer" target=3D"_blank">http://bitcoin.ninja/secp256k1.ecdsa.sa=
ge</a>=C2=A0 This<br>
provides for a method of communicating in both directions which is<br>
completely precise.<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>
--0000000000000656ce05759b0ce0--
|
