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
|
Return-Path: <gmaxwell@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 230C1E32
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 11 Sep 2018 17:00:43 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ua1-f50.google.com (mail-ua1-f50.google.com
[209.85.222.50])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9FBBF7D2
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 11 Sep 2018 17:00:41 +0000 (UTC)
Received: by mail-ua1-f50.google.com with SMTP id h1-v6so21273355uao.8
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 11 Sep 2018 10:00:41 -0700 (PDT)
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=Mt6R4gbBls8winZD1ERnSxK8Rvgzn97PR+2Tqw33ls8=;
b=FtNNjdgwuoFjeEno5uk0/JISbx0T6CiAX50Th6/xlmHdl+MOYLBiEt7NO3NV5wuVEl
P+bLO2oxcZOgg6huBfp8fezm38zD9+jlOrbAircQrvQLm8ELRf+7DY7Ly2gfwHwZZqAa
gP63qANoyEZy2qrlAoTngPm/VvNo5YRGRi23Bc0st5eUH5W21LbLEXun5ERnr5LBeoK8
uU1R/yumZlIFSjkhSi/6xwpEnaxvzaczBermfxLpEz+cO6VkjjrgqmOkDsPATKViHO8n
723s02Grqq8QGYf/4VSQOh4ljJIcE/cGHpMeQETPRyHcR0Kz6m37HqStE0skqa4osZJk
Ofqg==
X-Gm-Message-State: APzg51BjLNMKY2Hp/qSODJo2weuKifdNF8sgpC6S7PE+c5Tx0omfr1W/
PdFEMkUG5pJqtUSU9zJB5J6fOdk0JdaIW3h1Tvl3BPSJ
X-Google-Smtp-Source: ANB0VdbdcVRHt4JL7RCijZEv7zPF0uCg1zyHwx93s8oBDDYh9iBofNNmC/K9RronM/q7PdauSCS38n40UMcUQNiKZuU=
X-Received: by 2002:a67:eb01:: with SMTP id a1-v6mr9216960vso.13.1536685240457;
Tue, 11 Sep 2018 10:00:40 -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>
In-Reply-To: <CAJowKg+-45h6vraL1PpnqfhHSbG+G40L+FD7xN+C-Dn1E6Y_Vg@mail.gmail.com>
From: Gregory Maxwell <greg@xiph.org>
Date: Tue, 11 Sep 2018 17:00:25 +0000
Message-ID: <CAAS2fgSfdfQ2CiEabjrjspQGQufwzk84f1mzM1j_LRWqAPd8wA@mail.gmail.com>
To: Erik Aronesty <erik@q32.com>
Content-Type: multipart/alternative; boundary="000000000000e3a0c905759b696c"
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,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:39:47 +0000
Cc: Bitcoin Dev <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:00:43 -0000
--000000000000e3a0c905759b696c
Content-Type: text/plain; charset="UTF-8"
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.
--000000000000e3a0c905759b696c
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div dir=3D"ltr">On Tue, Sep 11, 2018 at 4:34 PM Erik Aron=
esty <<a href=3D"mailto:erik@q32.com">erik@q32.com</a>> wrote:<br><di=
v class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:0=
px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><=
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">https=
://bitcointalk.org/index.php?topic=3D4973123.0</a><br></div><div>=C2=A0</di=
v><div>I'm not sure how I am supposted to have figured out that you wro=
te a somewhat different repost of it elsewhere...<br></div><div><br></div><=
blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l=
eft: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 either <br><div><br></=
div><div>=C2=A0 - attack the hash function to produce a predictable R based=
on a known 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 someone who has M-1 keys.</div></div></blockquote><div><br></div><div>Yo=
u keep asserting this. It isn't true. Asserting it more does not make i=
t any more true.=C2=A0 I already explained how to attack this style of sign=
ature (e.g. in the BCT thread).<br></div><div><br></div><div>Set aside your=
'interpolation' for a moment, and imagine that you construct a 2 o=
f 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 computing -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 discrete log, I k=
now the discrete log of P with respect to G and I did not need to violate t=
he standard DL security assumption to achieve that.</div><div><br></div><di=
v>With the 'interpolation' in effect the same attack applies but it=
s 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 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.</div><div><br></div><div>The potential of rogue keys applies to both t=
he keys themselves and to the nonces. There are several ways to prevent the=
se attacks, the musig paper describes a delinearization technique which doe=
sn'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 susceptible though.=C2=
=A0=C2=A0 <br></div></div></blockquote><div><br></div><div>There is a perfe=
ct bijection between the two encodings which is easily computable, so they&=
#39;re the same thing from an abstract security perspective.<br></div><div>=
=C2=A0</div></div></div></div>
--000000000000e3a0c905759b696c--
|
