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
|
Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194]
helo=mx.sourceforge.net)
by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
(envelope-from <mh.in.england@gmail.com>) id 1VAIGt-0001Fm-0q
for bitcoin-development@lists.sourceforge.net;
Fri, 16 Aug 2013 11:32:47 +0000
Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of gmail.com
designates 209.85.219.46 as permitted sender)
client-ip=209.85.219.46; envelope-from=mh.in.england@gmail.com;
helo=mail-oa0-f46.google.com;
Received: from mail-oa0-f46.google.com ([209.85.219.46])
by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
(Exim 4.76) id 1VAIGr-0003sb-DQ
for bitcoin-development@lists.sourceforge.net;
Fri, 16 Aug 2013 11:32:46 +0000
Received: by mail-oa0-f46.google.com with SMTP id l10so2108390oag.33
for <bitcoin-development@lists.sourceforge.net>;
Fri, 16 Aug 2013 04:32:40 -0700 (PDT)
MIME-Version: 1.0
X-Received: by 10.60.93.67 with SMTP id cs3mr942778oeb.12.1376652759949; Fri,
16 Aug 2013 04:32:39 -0700 (PDT)
Sender: mh.in.england@gmail.com
Received: by 10.76.80.165 with HTTP; Fri, 16 Aug 2013 04:32:39 -0700 (PDT)
In-Reply-To: <CAAS2fgQFOei6we8nfSr9DuQuHEjXT+G8_XGMk9um14DBgRuPyA@mail.gmail.com>
References: <CAAS2fgQFOei6we8nfSr9DuQuHEjXT+G8_XGMk9um14DBgRuPyA@mail.gmail.com>
Date: Fri, 16 Aug 2013 13:32:39 +0200
X-Google-Sender-Auth: bUFl4npicudybEVTvxpHn03ksbM
Message-ID: <CANEZrP0Kr+jJA5r1uPELPR_7a5CmwewFuLb0Xr-sno4KxVK1cA@mail.gmail.com>
From: Mike Hearn <mike@plan99.net>
To: Gregory Maxwell <gmaxwell@gmail.com>
Content-Type: multipart/alternative; boundary=047d7b33d176bc668b04e40ef291
X-Spam-Score: -0.5 (/)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
See http://spamassassin.org/tag/ for more details.
-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
sender-domain
0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider
(mh.in.england[at]gmail.com)
-0.0 SPF_PASS SPF: sender matches SPF record
1.0 HTML_MESSAGE BODY: HTML included in message
0.1 DKIM_SIGNED Message has a DKIM or DK signature,
not necessarily valid
-0.1 DKIM_VALID Message has at least one valid DKIM or DK signature
X-Headers-End: 1VAIGr-0003sb-DQ
Cc: Bitcoin Development <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] BIP 32.5
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Fri, 16 Aug 2013 11:32:47 -0000
--047d7b33d176bc668b04e40ef291
Content-Type: text/plain; charset=UTF-8
I filed a bug in the bitcoinj tracker for this a few days ago referencing
rfc 6967, but that RFC is very complicated and I'm not sure it's really
necessary to go that far. H(sighash||key) is easy to implement and I feel I
understand it better.
In our case it wouldn't have helped anyway - if anything it would just
delayed discovery of the underlying weakness. The same RNG is typically
used to generate both keys and signatures today. However in future it may
be the case that people put more effort into generating a really random key
because they only have to do it once, and then the signing RNG would be
different.
Your concern about hardware devices leaking private key bits via a side
channel is also well made, although I think you have to find some way to
establish trust in these devices anyway as sniffing all their IO traffic
and analysing it is really hard (plus it inverts the threat model - if you
trust your computer and not your hardware wallet, why do you have a
hardware wallet?)
The other advantage is that deterministic keys and signatures together mean
two instances of the same wallet generate identical transactions given an
identical sequence of commands. This could help keep wallets in sync. For
example we had a few users who got confused because they had cloned their
Android wallets across devices (NOT SUPPORTED!) and then one device updated
first, did key rotation, and then the other device showed a transaction
that sent all their money to a new address it knew nothing about. If they
didn't realise the other device had updated this looked identical to theft!
I don't think fractional BIP numbers are the way to go :) but a new BIP
that standardised a way to select K would, if reviewed, be something I'd
implement.
On Fri, Aug 16, 2013 at 4:26 AM, Gregory Maxwell <gmaxwell@gmail.com> wrote:
> I am wondering if we shouldn't have a BIP32 addendum which makes the
> following signing related recommendations:
>
> (1) Recommend a specific deterministic DSA derandomization procedure
> (a deterministic way to generate the DSA nonce), presumably one based
> on HMAC-SHA512 (since BIP32 uses that construct) or SHA256 in the
> style of RFC 6979.
>
> DSA systems being compromised due to poor randomness at runtime is not
> new. It effected other systems before it effected Bitcoin systems,
> it's not a new problem and it's not going away. It's difficult to
> tell if an implementation is correct or not.
>
> Use of a fully deterministic signature would allow for complete test
> vectors in signing and complete confidence that there is no random
> number related weakness in a signing implementation.
>
> In particular, with relevance to our ecosystem a maliciously modified
> difficult to audit hardware wallet could be leaking its keys material
> via its signatures. Even without producing insecure K values it could
> use the choice of K to leak a couple bits of an encrypted root key
> with every signature, and allow the malicious party to recover the
> keys by simply observing the network. Making the signatures
> deterministic would make this kind of misbehavior practically
> discoverable.
>
> We wouldn't be alone in making this change, in general industry is
> moving in this direction because it has become clear that DSA is a
> hazard otherwise.
>
> The primary arguments in most spaces against derandomizing DSA are
> FIPS conformance (irrelevant for us) and reasonable concerns about the
> risks of using a (less) reviewed cryptographic construct. With
> widespread motion towards derandomized DSA this latter concern is less
> of an issue.
>
> Libcrypt has also implemented derandomized DSA in git. The ed25519
> signature system of DJB, et. al. also uses a similar derandomization.
>
> An alternative is implementing a still random construct where K is
> some H(message||key||random) which should remain secure even where the
> randomness is poor, but this loses the advantage of being able to
> externally verify that an implementation is not leaking information.
> OpenSSL development has implemented a form of this recently.
>
> See also: http://tools.ietf.org/rfc/rfc6979.txt
>
> (2) Recommends a procedure for using only even S values in signatures,
> eliminating this source of mutability in transactions.
>
> This can be accomplished via post-processing of existing signatures,
> but since it requires bignum math it is usually preferable to
> implement it along with signing. I believe someday this will become a
> network requirement for Bitcoin, but regardless it makes sense to
> implement it as a best practice sooner rather than later.
>
> Thoughts?
>
>
> ------------------------------------------------------------------------------
> Get 100% visibility into Java/.NET code with AppDynamics Lite!
> It's a free troubleshooting tool designed for production.
> Get down to code-level detail for bottlenecks, with <2% overhead.
> Download for free and get started troubleshooting in minutes.
> http://pubads.g.doubleclick.net/gampad/clk?id=48897031&iu=/4140/ostg.clktrk
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
--047d7b33d176bc668b04e40ef291
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">I filed a bug in the bitcoinj tracker for this a few days =
ago referencing rfc 6967, but that RFC is very complicated and I'm not =
sure it's really necessary to go that far. H(sighash||key) is easy to i=
mplement and I feel I understand it better.<div>
<br></div><div>In our case it wouldn't have helped anyway - if anything=
it would just delayed discovery of the underlying weakness. The same RNG i=
s typically used to generate both keys and signatures today. However in fut=
ure it may be the case that people put more effort into generating a really=
random key because they only have to do it once, and then the signing RNG =
would be different.</div>
<div><br></div><div>Your concern about hardware devices leaking private key=
bits via a side channel is also well made, although I think you have to fi=
nd some way to establish trust in these devices anyway as sniffing all thei=
r IO traffic and analysing it is really hard (plus it inverts the threat mo=
del - if you trust your computer and not your hardware wallet, why do you h=
ave a hardware wallet?)</div>
<div><br></div><div>The other advantage is that deterministic keys and sign=
atures together mean two instances of the same wallet generate identical tr=
ansactions given an identical sequence of commands. This could help keep wa=
llets in sync. For example we had a few users who got confused because they=
had cloned their Android wallets across devices (NOT SUPPORTED!) and then =
one device updated first, did key rotation, and then the other device showe=
d a transaction that sent all their money to a new address it knew nothing =
about. If they didn't realise the other device had updated this looked =
identical to theft!</div>
<div><br></div><div>I don't think fractional BIP numbers are the way to=
go :) but a new BIP that standardised a way to select K would, if reviewed=
, be something I'd implement.</div></div><div class=3D"gmail_extra"><br=
>
<br><div class=3D"gmail_quote">On Fri, Aug 16, 2013 at 4:26 AM, Gregory Max=
well <span dir=3D"ltr"><<a href=3D"mailto:gmaxwell@gmail.com" target=3D"=
_blank">gmaxwell@gmail.com</a>></span> wrote:<br><blockquote class=3D"gm=
ail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-le=
ft:1ex">
I am wondering if we shouldn't have a BIP32 addendum which makes the<br=
>
following signing related recommendations:<br>
<br>
(1) Recommend a specific deterministic DSA derandomization procedure<br>
(a deterministic way to generate the DSA nonce), presumably one based<br>
on HMAC-SHA512 (since BIP32 uses that construct) or SHA256 in the<br>
style of RFC 6979.<br>
<br>
DSA systems being compromised due to poor randomness at runtime is not<br>
new. It effected other systems before it effected Bitcoin systems,<br>
it's not a new problem and it's not going away. =C2=A0It's diff=
icult to<br>
tell if an implementation is correct or not.<br>
<br>
Use of a fully deterministic signature =C2=A0would allow for complete test<=
br>
vectors in signing and complete confidence that there is no random<br>
number related weakness in a signing implementation.<br>
<br>
In particular, with relevance to our ecosystem a maliciously modified<br>
difficult to audit hardware wallet could be leaking its keys material<br>
via its signatures. Even without producing insecure K values it could<br>
use the choice of K to leak a couple bits of an encrypted root key<br>
with every signature, and allow the malicious party to recover the<br>
keys by simply observing the network. Making the signatures<br>
deterministic would make this kind of misbehavior practically<br>
discoverable.<br>
<br>
We wouldn't be alone in making this change, in general industry is<br>
moving in this direction because it has become clear that DSA is a<br>
hazard otherwise.<br>
<br>
The primary arguments in most spaces against derandomizing DSA are<br>
FIPS conformance (irrelevant for us) and reasonable concerns about the<br>
risks of using a (less) reviewed cryptographic construct. With<br>
widespread motion towards derandomized DSA this latter concern is less<br>
of an issue.<br>
<br>
Libcrypt has also implemented derandomized DSA in git. The ed25519<br>
signature system of DJB, et. al. also uses a similar derandomization.<br>
<br>
An alternative is implementing a still random construct where K is<br>
some H(message||key||random) which should remain secure even where the<br>
randomness is poor, but this loses the advantage of being able to<br>
externally verify that an implementation is not leaking information.<br>
OpenSSL development has implemented a form of this recently.<br>
<br>
See also: <a href=3D"http://tools.ietf.org/rfc/rfc6979.txt" target=3D"_blan=
k">http://tools.ietf.org/rfc/rfc6979.txt</a><br>
<br>
(2) Recommends a procedure for using only even S values in signatures,<br>
eliminating this source of mutability in transactions.<br>
<br>
This can be accomplished via post-processing of existing signatures,<br>
but since it requires bignum math it is usually preferable to<br>
implement it along with signing. =C2=A0I believe someday this will become a=
<br>
network requirement for Bitcoin, but regardless it makes sense to<br>
implement it as a best practice sooner rather than later.<br>
<br>
Thoughts?<br>
<br>
---------------------------------------------------------------------------=
---<br>
Get 100% visibility into Java/.NET code with AppDynamics Lite!<br>
It's a free troubleshooting tool designed for production.<br>
Get down to code-level detail for bottlenecks, with <2% overhead.<br>
Download for free and get started troubleshooting in minutes.<br>
<a href=3D"http://pubads.g.doubleclick.net/gampad/clk?id=3D48897031&iu=
=3D/4140/ostg.clktrk" target=3D"_blank">http://pubads.g.doubleclick.net/gam=
pad/clk?id=3D48897031&iu=3D/4140/ostg.clktrk</a><br>
_______________________________________________<br>
Bitcoin-development mailing list<br>
<a href=3D"mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-develo=
pment@lists.sourceforge.net</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/bitcoin-development=
" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/bitcoin-de=
velopment</a><br>
</blockquote></div><br></div>
--047d7b33d176bc668b04e40ef291--
|
