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
|
Return-Path: <marek@palatinus.cz>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 8EF84267
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 8 May 2016 13:48:58 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-yw0-f176.google.com (mail-yw0-f176.google.com
[209.85.161.176])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8F8AD174
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 8 May 2016 13:48:57 +0000 (UTC)
Received: by mail-yw0-f176.google.com with SMTP id j74so229556656ywg.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 08 May 2016 06:48:57 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=palatinus-cz.20150623.gappssmtp.com; s=20150623;
h=mime-version:in-reply-to:references:from:date:message-id:subject:to;
bh=GY1IUQuxspTHukLmFvGHiicwc2rKBL3ATtfUSF7W1A0=;
b=tnCNn5sXMYxNIAREvDKrfOPYoO5FvbiGh8WdsZZ84WNGI2+F3nuDq8OfUWi7Em/u6/
Quk9xzKXWKj1zjEx0W0r/YZwDVTQTAaSr/I0OXrT2zg0xsRyG8C1GDQIov0kRyQAxqCT
0UuTB3GiGUI8UdEFKJHy+6iKrKstXDPKetWExNbBb5zmACklHmXmy+7zTw6o6j0eX62K
iyOTSqK67O0YjKanz6F/JrXTVrJGImdwEVebJ7tk1HwaokAXV9f0nx56PQmJnPLDDfHg
D88xx2/ZfnzAH87Ii6mjtqRu4QRYAgXzQ+wXG2SdbRscZHGd21Ij0djm9ztLn22Nwmat
EekQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20130820;
h=x-gm-message-state:mime-version:in-reply-to:references:from:date
:message-id:subject:to;
bh=GY1IUQuxspTHukLmFvGHiicwc2rKBL3ATtfUSF7W1A0=;
b=LYxXJKWDHdET0Jt7qs4IsL5Ayb9gIUHYOW0bcqeJSUYwj6dz3KMyCtkotBRFhdVMuX
JiMXPGXeTQKo3jEZhm+d1f9x14B3tB6EdvptdRkUryLt9hfcdG7dYFfn6vycMzJW546B
SbANwvDbbPrscMSihUcUjHEGEasSKnQ2IVb7ll4487HyGJWKwSMeq5PNFyiYyQQeT/xV
YbfxzZQO2Use8T5zrjQLAi8N5kkxX2T36jemTx9xjpCKyna5hl6SI8nbfvKtLPR3eyh4
o8wgWgzfh97RNjBGQBtexCoGCE31WysdVURsTk2zSIyoDkEkt/p0D/bH01z3Ejp2nUYF
pkcg==
X-Gm-Message-State: AOPr4FVyTGHhsqIbsxEdZQNJZLiFn/QIGWedZb++GXvzB9GNaOpVrWcvmdn6LcGsrOsC9p5eDR4Wx68zLN68jA==
X-Received: by 10.129.84.193 with SMTP id i184mr20003684ywb.285.1462715336526;
Sun, 08 May 2016 06:48:56 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.129.92.2 with HTTP; Sun, 8 May 2016 06:48:27 -0700 (PDT)
In-Reply-To: <CAPg+sBiAv7PFWEw5s=BPcOkL-x9GfWqi24pD3xMnfxvz9xQy4g@mail.gmail.com>
References: <5717AF19.1030102@gmail.com>
<CAJna-HiG5Nq_c0nZ28bTV4ZQKaU-zY1YiSEEaRK9ZvFO7LH-EA@mail.gmail.com>
<CAPg+sBiAv7PFWEw5s=BPcOkL-x9GfWqi24pD3xMnfxvz9xQy4g@mail.gmail.com>
From: Marek Palatinus <marek@palatinus.cz>
Date: Sun, 8 May 2016 15:48:27 +0200
Message-ID: <CAJna-HjiN9-KbVgUVFeaDWeFgQV9o5o_omEV5bh4drEyEALdnw@mail.gmail.com>
To: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary=001a114d9a500ac429053254f48d
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, 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: Sun, 08 May 2016 14:16:09 +0000
Subject: [bitcoin-dev] Fwd: Proposal to update BIP-32
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development 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: Sun, 08 May 2016 13:48:58 -0000
--001a114d9a500ac429053254f48d
Content-Type: text/plain; charset=UTF-8
I received this:
---------- Forwarded message ----------
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Fri, Apr 22, 2016 at 6:44 PM
Subject: Re: [bitcoin-dev] Proposal to update BIP-32
To: Marek Palatinus <marek@palatinus.cz>
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
On Thu, Apr 21, 2016 at 2:08 PM, Marek Palatinus <marek@palatinus.cz> wrote:
> On Wed, Apr 20, 2016 at 6:32 PM, Jochen Hoenicke via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> Hello Bitcoin Developers,
>>
>> I would like to make a proposal to update BIP-32 in a small way.
>>
>> I think the backward compatibility issues are minimal. The chance
>> that this affects anyone is less than 10^-30. Even if it happens, it
>> would only create some additional addresses (that are not seen if the
>> user downgrades). The main reason for suggesting a change is that we
>> want a similar method for different curves where a collision is much
>> more likely.
>>
>
I think I change like this makes a lot of sense technically, and I wish I
had known how BIP-32 would end up being used inside higher level mechanisms
that automatically increment the position beyond the control of the
application generating them. The inclusion of the requirement was there
because ECDSA is notorious for security problems under biased secret keys,
though it's really only a certificational issue for secp256k1 (due to its
group order being so close to 2^256).
>
>> #QUESTIONS:
>>
>> What is the procedure to update the BIP? Is it still possible to
>> change the existing BIP-32 even though it is marked as final? Or
>> should I make a new BIP for this that obsoletes BIP-32?
>>
>
BIPs are not supposed to be updated with new ideas, only
remarks/links/typos/clarifications/..., so that their bumbers can
unambiguously be used to refer to an idea. My suggestion would be to write
a new BIP that overrides parts of BIP32, and then put a note in BIP32 that
a better mechanism is available that is unlikely to change things in
reality for the secp256k1 curve.
I guess
> What algorithm is preferred? (bike-shedding) My suggestion:
>>
>> ---
>>
>> Change the last step of the private -> private derivation functions to:
>>
>> . In case parse(I_L) >= n or k_i = 0, the procedure is repeated
>> at step 2 with
>> I = HMAC-SHA512(Key = c_par, Data = 0x01 || I_R || ser32(i))
>
>
>> ---
>>
>> I think this suggestion is simple to implement (a bit harder to unit
>> test) and the string to hash with HMAC-SHA512 always has the same
>> length. I use I_R, since I_L is obviously not very random if I_L >= n.
>> There is a minimal chance that it will lead to an infinite loop if I_R
>> is the same in two consecutive iterations, but that has only a chance
>> of 1 in 2^512 (if the algorithm is used for different curves that make
>> I_L >= n more likely, the chance is still less than 1 in 2^256). In
>> theory, this loop can be avoided by incrementing i in every iteration,
>> but this would make an implementation error in the "hard to test" path
>> of the program more likely.
>>
>
The chance for failure is a bit higher than that, as it only requires a
failed key (one in 2^128) in the first step, followed by an iteration that
results in the same I_R to cause a cycle. If you take multiple failures
before the cycle starts into account, the combined chance for failure is
p/(1-p)^2 / 2^256 (with p the chance for a random inadmissable key), which
is not much better than 1 in 2^128 for high values of p.
An alternative that always converges is to retry with an appended iteration
count is possible:
{
I = HMAC-SHA512(Key = c_par, Data = 0x01 || || ser32(i)) for the first
iteration
I = HMAC-SHA512(Key = c_par, Data = 0x01 || || ser32(i) || ser32(j)) for
iteration number j, with j > 0
}
Cheers,
--
Pieter
--001a114d9a500ac429053254f48d
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">I received this:<div><br><div class=3D"gmail_quote">------=
---- Forwarded message ----------<br>From: <b class=3D"gmail_sendername">Pi=
eter Wuille</b> <span dir=3D"ltr"><<a href=3D"mailto:pieter.wuille@gmail=
.com">pieter.wuille@gmail.com</a>></span><br>Date: Fri, Apr 22, 2016 at =
6:44 PM<br>Subject: Re: [bitcoin-dev] Proposal to update BIP-32<br>To: Mare=
k Palatinus <<a href=3D"mailto:marek@palatinus.cz">marek@palatinus.cz</a=
>><br>Cc: Bitcoin Dev <<a href=3D"mailto:bitcoin-dev@lists.linuxfound=
ation.org">bitcoin-dev@lists.linuxfoundation.org</a>><br><br><br><div di=
r=3D"ltr"><span class=3D"">On Thu, Apr 21, 2016 at 2:08 PM, Marek Palatinus=
<span dir=3D"ltr"><<a href=3D"mailto:marek@palatinus.cz" target=3D"_bla=
nk">marek@palatinus.cz</a>></span> wrote:<br></span><div class=3D"gmail_=
extra"><div class=3D"gmail_quote"><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 class=3D"gmail_extra"><div class=3D"gmail_=
quote"><span class=3D"">On Wed, Apr 20, 2016 at 6:32 PM, Jochen Hoenicke vi=
a bitcoin-dev <span dir=3D"ltr"><<a href=3D"mailto:bitcoin-dev@lists.lin=
uxfoundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</=
a>></span> wrote:<br></span><blockquote class=3D"gmail_quote" style=3D"m=
argin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left=
:1ex"><span class=3D"">Hello Bitcoin Developers,<br>
<br>
I would like to make a proposal to update BIP-32 in a small way.<br><br></s=
pan><span class=3D"">
I think the backward compatibility issues are minimal.=C2=A0 The chance<br>
that this affects anyone is less than 10^-30.=C2=A0 Even if it happens, it<=
br>
would only create some additional addresses (that are not seen if the<br>
user downgrades).=C2=A0 The main reason for suggesting a change is that we<=
br>
want a similar method for different curves where a collision is much<br>
more likely.<br></span></blockquote></div></div></div></blockquote><div><br=
></div><div>I think I change like this makes a lot of sense technically, an=
d I wish I had known how BIP-32 would end up being used inside higher level=
mechanisms that automatically increment the position beyond the control of=
the application generating them. The inclusion of the requirement was ther=
e because ECDSA is notorious for security problems under biased secret keys=
, though it's really only a certificational issue for secp256k1 (due to=
its group order being so close to 2^256). <br></div><span class=3D""><bloc=
kquote 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 class=3D=
"gmail_extra"><div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" =
style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);pa=
dding-left:1ex">
<br>
#QUESTIONS:<br>
<br>
What is the procedure to update the BIP?=C2=A0 Is it still possible to<br>
change the existing BIP-32 even though it is marked as final?=C2=A0 Or<br>
should I make a new BIP for this that obsoletes BIP-32?<br></blockquote></d=
iv></div></div></blockquote><div><br></div></span><div>BIPs are not suppose=
d to be updated with new ideas, only remarks/links/typos/clarifications/...=
, so that their bumbers can unambiguously be used to refer to an idea. My s=
uggestion would be to write a new BIP that overrides parts of BIP32, and th=
en put a note in BIP32 that a better mechanism is available that is unlikel=
y to change things in reality for the secp256k1 curve.<br></div><div><br></=
div><div>I guess <br>=C2=A0<br></div><span class=3D""><blockquote class=3D"=
gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(20=
4,204,204);padding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_extra"><d=
iv class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:=
0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
What algorithm is preferred? (bike-shedding)=C2=A0 My suggestion:<br>
<br>
---<br>
<br>
Change the last step of the private -> private derivation functions to:<=
br>
<br>
=C2=A0. In case parse(I_L) >=3D n or k_i =3D 0, the procedure is repeate=
d<br>
=C2=A0 =C2=A0at step 2 with<br>
=C2=A0 =C2=A0 I =3D HMAC-SHA512(Key =3D c_par, Data =3D 0x01 || I_R || ser3=
2(i))=C2=A0</blockquote></div></div></div></blockquote><blockquote class=3D=
"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(2=
04,204,204);padding-left:1ex"><div dir=3D"ltr"><div class=3D"gmail_extra"><=
div class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin=
:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"=
>
<br>
---<br>
<br>
I think this suggestion is simple to implement (a bit harder to unit<br>
test) and the string to hash with HMAC-SHA512 always has the same<br>
length.=C2=A0 I use I_R, since I_L is obviously not very random if I_L >=
=3D n.<br>
There is a minimal chance that it will lead to an infinite loop if I_R<br>
is the same in two consecutive iterations, but that has only a chance<br>
of 1 in 2^512 (if the algorithm is used for different curves that make<br>
I_L >=3D n more likely, the chance is still less than 1 in 2^256).=C2=A0=
In<br>
theory, this loop can be avoided by incrementing i in every iteration,<br>
but this would make an implementation error in the "hard to test"=
path<br>
of the program more likely.<br></blockquote></div></div></div></blockquote>=
<div><br></div></span><div>The chance for failure is a bit higher than that=
, as it only requires a failed key (one in 2^128) in the first step, follow=
ed by an iteration that results in the same I_R to cause a cycle. If you ta=
ke multiple failures before the cycle starts into account, the combined cha=
nce for failure is p/(1-p)^2 / 2^256 (with p the chance for a random inadmi=
ssable key), which is not much better than 1 in 2^128 for high values of p.=
<br><br></div><div>An alternative that always converges is to retry with an=
appended iteration count is possible:<br>{<br></div><div>=C2=A0 I =3D HMAC=
-SHA512(Key =3D c_par, Data =3D 0x01 ||=C2=A0 || ser32(i)) for the first it=
eration<br>=C2=A0 I =3D HMAC-SHA512(Key =3D c_par, Data =3D 0x01 ||=C2=A0 |=
| ser32(i) || ser32(j)) for iteration number j, with j > 0<br>}<br><br><=
/div><div>Cheers,<span class=3D"HOEnZb"><font color=3D"#888888"><br><br></f=
ont></span></div><span class=3D"HOEnZb"><font color=3D"#888888"><div>-- <br=
></div><div>Pieter<br><br></div></font></span></div></div></div>
</div><br></div></div>
--001a114d9a500ac429053254f48d--
|