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
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
|
Return-Path: <lloyd.fourn@gmail.com>
Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137])
by lists.linuxfoundation.org (Postfix) with ESMTP id BFBDAC0177
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 26 Feb 2020 04:21:26 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by fraxinus.osuosl.org (Postfix) with ESMTP id A9B0086239
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 26 Feb 2020 04:21:26 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from fraxinus.osuosl.org ([127.0.0.1])
by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id nSTabF3z2oGI
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 26 Feb 2020 04:21:25 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-il1-f169.google.com (mail-il1-f169.google.com
[209.85.166.169])
by fraxinus.osuosl.org (Postfix) with ESMTPS id 4C1D186237
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 26 Feb 2020 04:21:25 +0000 (UTC)
Received: by mail-il1-f169.google.com with SMTP id l4so1229042ilj.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 25 Feb 2020 20:21:25 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
bh=vMDezTw8qww8kMIugdSd0Pgarp3iSz2JS5dAx8hiqd8=;
b=BAPEhwuZcNhoVzk1kI107nkxI7Z5vtu6sPUaqmfIj22xEfiHZuXJNDFSXWTnXBzLDL
YvjW961aEDRdFq9hCyxIR8oc3e+D027DVICyHSXZowcka5juGLnEMf6m9fsMvFPxWk31
pfFPmVknTBG6CaBCJMyHCfvT8B1JnlsqtFph1+CqLyRjGXmVx1MqbB3vlnnYIEJ+H1cO
Wpyn/tU4W0ZZwo6BRnyEABJSzjXkXGMF5zT1PtjRodUk1Iu3XzN3ahcKUkwDIf4TGhif
l9RDtE+27PtPSq6leOEkHe6tK9+PxpE+TiZVDMSXZJU+qSvRq4ft8iyL2Cyn0p80CG1E
lpog==
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=vMDezTw8qww8kMIugdSd0Pgarp3iSz2JS5dAx8hiqd8=;
b=l7rpSMvl5c4N8NaZjkQmQdthDMZSc0qYrNx27KlA8H9NALfpcFodZUaCVjCOyS7rPa
9FMjNjKneyF6TndpA9gioliaLTpKsrhyvbE4O5/IIhv+WsJ7Zi/cyWvAX2Adl+AKA0op
gdJYfxYKyTZkOUTtWgbFxJJlLa1y9EZ/S8xPn5fNk2M5wkp1U2Ik2BPUAVBLu8zMnsnM
dF/i2USd6LVcdCwg8oiqYSAsuadxBCegkuH2upE7nmNkcDKoIgxcM4le9xrNUkNa0VJ2
8GWjell1uC33iMpZZv8DOrDL2ZiVGopyHQ6JWPSJV1CqOuco6gNlIcOQQoxfHFagincf
TDog==
X-Gm-Message-State: APjAAAW8jRLxJYfpheeZGxD0ZnL3L1pAChRrX6O1mix+te2SJ+NmEzvM
1UY9XBXqxVWhgeb3D+eAi/aYNqhMTtW/QmhABbE=
X-Google-Smtp-Source: APXvYqwBfp+AJYizzwjhw+ih1LeFnAUpfi6XBKQ99usrpgrMtP3pRxNgs85Mv8v42PZGFMGJh+fVuteaDr0WAU7sDQE=
X-Received: by 2002:a92:af44:: with SMTP id n65mr2121708ili.158.1582690884386;
Tue, 25 Feb 2020 20:21:24 -0800 (PST)
MIME-Version: 1.0
References: <CAPg+sBgxvRM5ncQAnbNLN=4bdkQrM+-DxibMoTG+6gqk7EY9hQ@mail.gmail.com>
In-Reply-To: <CAPg+sBgxvRM5ncQAnbNLN=4bdkQrM+-DxibMoTG+6gqk7EY9hQ@mail.gmail.com>
From: Lloyd Fournier <lloyd.fourn@gmail.com>
Date: Wed, 26 Feb 2020 15:20:58 +1100
Message-ID: <CAH5Bsr0ws2GT12+1rXTAXUkrpJXaeDqDgkfW_sdz7CqvwRCEkg@mail.gmail.com>
To: Pieter Wuille <pieter.wuille@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000f4055c059f72ef6d"
X-Mailman-Approved-At: Wed, 26 Feb 2020 04:59:27 +0000
Subject: Re: [bitcoin-dev] BIP 340 updates: even pubkeys,
more secure nonce generation
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
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, 26 Feb 2020 04:21:26 -0000
--000000000000f4055c059f72ef6d
Content-Type: text/plain; charset="UTF-8"
Hi Pieter,
Let me put change (1) into my own words. We are already computing affine
coordinates since we store public keys as the affine x-coordinate. It is
faster to compute is_even(y) than is_quadratic_residue(y) so we get a speed
up here during keypair generation. In the verification algorithm, we do the
following for the public key x_only => affine + negate if not is_even(y)
=> jacobian. The minor slowdown in verification comes from the extra
evenness check and possible negation which we didn't have to be done in the
previous version. This seems like a reasonable change if it makes things
easier for existing code bases and infrastructure.
With change (2), I feel like including this auxiliary random data is
overkill for the spec. For me, the main point of the spec is the
verification algorithm which actually affects consensus. Providing a note
that non-deterministic signatures are preferable in many cases and here's
exactly how you should do that (hash then xor with private key) is
valuable. In the end, people will want several variations of the signing
algorithm anyway (e.g. pass in public key with secret key) so I think
specifying the most minimal way to produce a signature securely is the most
useful thing for this document.
I feel similarly about hashing the public key to get the nonce. A note in
the alternative signing section that "if you pass the public key into
`sign` along with the secret key then you should do hash(bytes(d) ||
bytes(P) || m)" would suffice for me.
Despite only being included in the alternative signing section, I it would
be nice to have a few of test vectors for these alternative methods anyway.
Perhaps they even deserve their own BIP?
Cheers,
LL
On Mon, Feb 24, 2020 at 3:26 PM Pieter Wuille via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> Hello list,
>
> Despite saying earlier that I expected no further semantical changes
> to BIP 340-342, I've just opened
> https://github.com/bitcoin/bips/pull/893 to make a number of small
> changes that I believe are still worth making.
>
> 1. Even public keys
>
> Only one change affects the validation rules: the Y coordinate of
> 32-byte public keys is changed from implicitly square to implicitly
> even. This makes signing slightly faster (in the microsecond range),
> though also verification negligibly slower (in the nanosecond range).
> It also simplifies integration with existing key generation
> infrastructure. For example BIP32 produces public keys with known
> even/oddness, but squaredness would need to be computed separately.
> Similar arguments hold for PSBT and probably many other things.
>
> Note that the Y coordinate of the internal R point in the signature
> remains implicitly square: for R the squaredness gives an actual
> performance gain at validation time, but this is not true for public
> keys. Conversely, for public keys integration with existing
> infrastructure matters, but R points are purely internal.
>
> This affects BIP 340 and 341.
>
> 2. Nonce generation
>
> All other semantical changes are around more secure nonce generation
> in BIP 340, dealing with various failure cases:
>
> * Since the public key signed for is included in the signature
> challenge hash, implementers will likely be eager to use precomputed
> values for these (otherwise an additional EC multiplication is
> necessary at signing time). If that public key data happens to be
> gathered from untrusted sources, it can lead to trivial leakage of the
> private key - something that Greg Maxwell started a discussion about
> on the moderncrypto curves list:
> https://moderncrypto.org/mail-archive/curves/2020/001012.html. We
> believe it should therefore be best practice to include the public key
> also in the nonce generation, which largely mitigates this problem.
>
> * To protect against fault injection attacks it is recommended to
> include actual signing-time randomness into the nonce generation
> process. This was mentioned already, but the update elaborates much
> more about this, and integrates this randomness into the standard
> signing process.
>
> * To protect against differential power analysis, a different way of
> mixing in this randomness is used (masking the private key completely
> with randomness before continuing, rather than hashing them together,
> which is known in the literature to be vulnerable to DPA in some
> scenarios).
>
> 3. New tagged hash tags
>
> To make sure that any code written for the earlier BIP text fails
> consistently, the tags used in the tagged hashes in BIP 340 are
> changed as well.
>
> What do people think?
>
> --
> Pieter
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--000000000000f4055c059f72ef6d
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div dir=3D"ltr">Hi Pieter,<div><br></div><div>Let me put =
change (1) into my own words. We are already computing affine coordinates s=
ince we store public keys as the affine x-coordinate. It is faster to compu=
te is_even(y) than is_quadratic_residue(y) so we get a speed up here during=
keypair generation. In the verification algorithm, we do the following for=
the public key=C2=A0 x_only =3D> affine=C2=A0+ negate if not is_even(y)=
=3D> jacobian. The minor slowdown in verification comes from the extra =
evenness check and possible negation which we didn't have to be done in=
the previous version. This seems like a reasonable change if it makes thin=
gs easier for existing code bases and infrastructure.</div><div><br></div><=
div>With change (2), I feel like including this auxiliary=C2=A0random data =
is overkill for the spec.=C2=A0For me, the main point of the spec is the ve=
rification algorithm which actually affects consensus. Providing a note tha=
t non-deterministic signatures are preferable=C2=A0in many cases and here&#=
39;s exactly how you should do that (hash then xor with private key) is val=
uable. In the end, people will want several variations of the signing algor=
ithm anyway (e.g. pass in public key with secret key) so I think specifying=
the most minimal way to produce a signature securely is the most useful th=
ing for this document.</div><div><br></div><div>I feel similarly about hash=
ing the public key to get the nonce. A note in the alternative signing sect=
ion that "if you pass the public key into `sign` along with the secret=
key then you should do=C2=A0hash(bytes(d) || bytes(P) || m)" would su=
ffice for me.</div><div><br></div><div>Despite only being included in the a=
lternative signing section, I it would be nice to have a few of test vector=
s for these alternative methods anyway. Perhaps they even deserve their own=
BIP?</div><div><br>Cheers,</div><div><br></div><div>LL</div><div><br></div=
></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr"=
>On Mon, Feb 24, 2020 at 3:26 PM Pieter Wuille via bitcoin-dev <<a href=
=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.linuxfo=
undation.org</a>> wrote:<br></div><blockquote class=3D"gmail_quote" styl=
e=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);paddin=
g-left:1ex">Hello list,<br>
<br>
Despite saying earlier that I expected no further semantical changes<br>
to BIP 340-342, I've just opened<br>
<a href=3D"https://github.com/bitcoin/bips/pull/893" rel=3D"noreferrer" tar=
get=3D"_blank">https://github.com/bitcoin/bips/pull/893</a> to make a numbe=
r of small<br>
changes that I believe are still worth making.<br>
<br>
1. Even public keys<br>
<br>
Only one change affects the validation rules: the Y coordinate of<br>
32-byte public keys is changed from implicitly square to implicitly<br>
even. This makes signing slightly faster (in the microsecond range),<br>
though also verification negligibly slower (in the nanosecond range).<br>
It also simplifies integration with existing key generation<br>
infrastructure. For example BIP32 produces public keys with known<br>
even/oddness, but squaredness would need to be computed separately.<br>
Similar arguments hold for PSBT and probably many other things.<br>
<br>
Note that the Y coordinate of the internal R point in the signature<br>
remains implicitly square: for R the squaredness gives an actual<br>
performance gain at validation time, but this is not true for public<br>
keys. Conversely, for public keys integration with existing<br>
infrastructure matters, but R points are purely internal.<br>
<br>
This affects BIP 340 and 341.<br>
<br>
2. Nonce generation<br>
<br>
All other semantical changes are around more secure nonce generation<br>
in BIP 340, dealing with various failure cases:<br>
<br>
* Since the public key signed for is included in the signature<br>
challenge hash, implementers will likely be eager to use precomputed<br>
values for these (otherwise an additional EC multiplication is<br>
necessary at signing time). If that public key data happens to be<br>
gathered from untrusted sources, it can lead to trivial leakage of the<br>
private key - something that Greg Maxwell started a discussion about<br>
on the moderncrypto curves list:<br>
<a href=3D"https://moderncrypto.org/mail-archive/curves/2020/001012.html" r=
el=3D"noreferrer" target=3D"_blank">https://moderncrypto.org/mail-archive/c=
urves/2020/001012.html</a>. We<br>
believe it should therefore be best practice to include the public key<br>
also in the nonce generation, which largely mitigates this problem.<br>
<br>
* To protect against fault injection attacks it is recommended to<br>
include actual signing-time randomness into the nonce generation<br>
process. This was mentioned already, but the update elaborates much<br>
more about this, and integrates this randomness into the standard<br>
signing process.<br>
<br>
* To protect against differential power analysis, a different way of<br>
mixing in this randomness is used (masking the private key completely<br>
with randomness before continuing, rather than hashing them together,<br>
which is known in the literature to be vulnerable to DPA in some<br>
scenarios).<br>
<br>
3. New tagged hash tags<br>
<br>
To make sure that any code written for the earlier BIP text fails<br>
consistently, the tags used in the tagged hashes in BIP 340 are<br>
changed as well.<br>
<br>
What do people think?<br>
<br>
-- <br>
Pieter<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></div>
--000000000000f4055c059f72ef6d--
|