[bitcoin-dev] Proposal to update BIP-32

[bitcoin-dev] Proposal to update BIP-32

[Jochen Hoenicke]

Hello Bitcoin Developers,

I would like to make a proposal to update BIP-32 in a small way.

TL;DR: BIP-32 is hard to use right (due to its requirement to skip
addresses).  This proposal suggests a modification such that the
difficulty can be encapsulated in the library.

#MOTIVATION:

The current BIP-32 specifies that if for some node in the hierarchy
the computed hash I_L is larger or equal to the prime or 0, then the
node is invalid and should be skipped in the BIP-32 tree.  This has
several unfortunate consequences:

- All callers of CKDpriv or CKDpub have to check for errors and handle
  them appropriately.  This shifts the burden to the application
  developer instead of being able to handle it in the BIP-32 library.

- It is not clear what to do if an intermediate node is
  missing. E.g. for the default wallet layout, if m/i_H/0 is missing
  should m/i_H/1 be used for external chain and m/i_H/2 for internal
  chain?  This would make the wallet handling much more difficult.

- It gets even worse with standards like BIP-44.  If m/44' is missing
  should we use m/45' instead?  If m/44'/0' is missing should we use
  m/44'/1' instead, using the same addresses as for testnet?
  One could also restart with a different seed in this case, but this
  wouldn't work if one later wants to support another BIP-43 proposal
  and still keep the same wallet.

I think the first point alone is reason enough to change this.  I am
not aware of a BIP-32 application that handles errors like this
correctly in all cases.  It is also very hard to test, since it is
infeasible to brute-force a BIP-32 key and a path where the node does
not exists.

This problem can be avoided by repeating the hashing with slightly
different input data until a valid private key is found.  This would
be in the same spirit as RFC-6979.  This way, the library will always
return a valid node for all paths.  Of course, in the case where the
node is valid according to the current standard the behavior should be
unchanged.

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.

#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?

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 other derivation functions should be updated in a similar matter.
Also the derivation of the root node from the seed should be updated
in a similar matter to avoid invalid seeds.

If you followed until here, thanks for reading this long posting.

  Jochen

Re: [bitcoin-dev] Proposal to update BIP-32

[Marek Palatinus]

[-- Attachment #1: Type: text/plain, Size: 4480 bytes --]

Sipa, you are probably the most competent to answer this. Could you please
tell us your opinion? For me, this is straightforward, backward compatible
fix and I like it a lot. Not sure about the process of changing "Final" BIP
though.

Slush

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.
>
> TL;DR: BIP-32 is hard to use right (due to its requirement to skip
> addresses).  This proposal suggests a modification such that the
> difficulty can be encapsulated in the library.
>
> #MOTIVATION:
>
> The current BIP-32 specifies that if for some node in the hierarchy
> the computed hash I_L is larger or equal to the prime or 0, then the
> node is invalid and should be skipped in the BIP-32 tree.  This has
> several unfortunate consequences:
>
> - All callers of CKDpriv or CKDpub have to check for errors and handle
>   them appropriately.  This shifts the burden to the application
>   developer instead of being able to handle it in the BIP-32 library.
>
> - It is not clear what to do if an intermediate node is
>   missing. E.g. for the default wallet layout, if m/i_H/0 is missing
>   should m/i_H/1 be used for external chain and m/i_H/2 for internal
>   chain?  This would make the wallet handling much more difficult.
>
> - It gets even worse with standards like BIP-44.  If m/44' is missing
>   should we use m/45' instead?  If m/44'/0' is missing should we use
>   m/44'/1' instead, using the same addresses as for testnet?
>   One could also restart with a different seed in this case, but this
>   wouldn't work if one later wants to support another BIP-43 proposal
>   and still keep the same wallet.
>
> I think the first point alone is reason enough to change this.  I am
> not aware of a BIP-32 application that handles errors like this
> correctly in all cases.  It is also very hard to test, since it is
> infeasible to brute-force a BIP-32 key and a path where the node does
> not exists.
>
> This problem can be avoided by repeating the hashing with slightly
> different input data until a valid private key is found.  This would
> be in the same spirit as RFC-6979.  This way, the library will always
> return a valid node for all paths.  Of course, in the case where the
> node is valid according to the current standard the behavior should be
> unchanged.
>
> 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.
>
> #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?
>
> 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 other derivation functions should be updated in a similar matter.
> Also the derivation of the root node from the seed should be updated
> in a similar matter to avoid invalid seeds.
>
> If you followed until here, thanks for reading this long posting.
>
>   Jochen
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 5387 bytes --]

Re: [bitcoin-dev] Proposal to update BIP-32

[Eric Lombrozo]

[-- Attachment #1: Type: text/plain, Size: 4711 bytes --]

In practice the probability of this case triggering is on the order of 2^-128 or something astronomically tiny. I've been using BIP32 for a few years already as have many others...I don't think we've ever had to handle this case. Justifiably, many app developers feel like the additional complexity of properly handling this case is not worth the effort.

Having said that, if the handling of this case is simple to implement and easy to isolate in the program flow, I am in favor of doing something along the lines of what you propose.

- Eric

On April 20, 2016 9:32:25 AM PDT, 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.
>
>TL;DR: BIP-32 is hard to use right (due to its requirement to skip
>addresses).  This proposal suggests a modification such that the
>difficulty can be encapsulated in the library.
>
>#MOTIVATION:
>
>The current BIP-32 specifies that if for some node in the hierarchy
>the computed hash I_L is larger or equal to the prime or 0, then the
>node is invalid and should be skipped in the BIP-32 tree.  This has
>several unfortunate consequences:
>
>- All callers of CKDpriv or CKDpub have to check for errors and handle
>  them appropriately.  This shifts the burden to the application
>  developer instead of being able to handle it in the BIP-32 library.
>
>- It is not clear what to do if an intermediate node is
>  missing. E.g. for the default wallet layout, if m/i_H/0 is missing
>  should m/i_H/1 be used for external chain and m/i_H/2 for internal
>  chain?  This would make the wallet handling much more difficult.
>
>- It gets even worse with standards like BIP-44.  If m/44' is missing
>  should we use m/45' instead?  If m/44'/0' is missing should we use
>  m/44'/1' instead, using the same addresses as for testnet?
>  One could also restart with a different seed in this case, but this
>  wouldn't work if one later wants to support another BIP-43 proposal
>  and still keep the same wallet.
>
>I think the first point alone is reason enough to change this.  I am
>not aware of a BIP-32 application that handles errors like this
>correctly in all cases.  It is also very hard to test, since it is
>infeasible to brute-force a BIP-32 key and a path where the node does
>not exists.
>
>This problem can be avoided by repeating the hashing with slightly
>different input data until a valid private key is found.  This would
>be in the same spirit as RFC-6979.  This way, the library will always
>return a valid node for all paths.  Of course, in the case where the
>node is valid according to the current standard the behavior should be
>unchanged.
>
>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.
>
>#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?
>
>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 other derivation functions should be updated in a similar matter.
>Also the derivation of the root node from the seed should be updated
>in a similar matter to avoid invalid seeds.
>
>If you followed until here, thanks for reading this long posting.
>
>  Jochen
>_______________________________________________
>bitcoin-dev mailing list
>bitcoin-dev@lists.linuxfoundation.org
>https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[-- Attachment #2: Type: text/html, Size: 5409 bytes --]

Re: [bitcoin-dev] Proposal to update BIP-32

[Pavol Rusnak]

On 21/04/16 17:28, Eric Lombrozo via bitcoin-dev wrote:
> I don't think we've ever had to handle this case. 

This is the main problem: we are not sure, because not a lot of software
does this checks. Also even if you do check, it's hard to handle an
exception (you can't always skip - what if the problematic node is m/44'?).

One of the motivations is to fix BIP-32 so it can be used for
non-secp256k1 curves as well. For NIST P-256 curve this chance is 2^-32.

Jochen even managed to find an example[1]:

m/28578'/33941 where m is derived from
"000102030405060708090a0b0c0d0e0f" seed.

[1]
https://github.com/trezor/trezor-crypto/commit/16ff4387ae79429e629a5454708abf7385b3a9a3

-- 
Best Regards / S pozdravom,

Pavol "stick" Rusnak
SatoshiLabs.com

Re: [bitcoin-dev] Proposal to update BIP-32

[Jochen Hoenicke]

Am 21.04.2016 um 17:28 schrieb Eric Lombrozo:
> In practice the probability of this case triggering is on the order of
> 2^-128 or something astronomically tiny. I've been using BIP32 for a few
> years already as have many others...I don't think we've ever had to
> handle this case. Justifiably, many app developers feel like the
> additional complexity of properly handling this case is not worth the
> effort.
> 
> Having said that, if the handling of this case is simple to implement
> and easy to isolate in the program flow, I am in favor of doing
> something along the lines of what you propose.
> 

Yes, the idea is to handle the problem in the library so that app
developers don't have to handle the case of missing addresses or just
ignore the problem.  It also doesn't add much complexity to the library
as the current implementations already test for invalid keys.  The
library would then just retry instead of returning an error (that most
app developers would then ignore).

  Jochen

Re: [bitcoin-dev] Proposal to update BIP-32

[Pavol Rusnak]

On 21/04/16 14:08, Marek Palatinus via bitcoin-dev wrote:
> Sipa, you are probably the most competent to answer this.
> Could you please tell us your opinion? For me, this is
> straightforward, backward compatible fix and I like it a lot.
> Not sure about the process of changing "Final" BIP though.

Sipa: Marek told me you posted your answer and he received it, but it
never reached the list. Could you please resend after figuring out what
went wrong?

-- 
Best Regards / S pozdravom,

Pavol "stick" Rusnak
SatoshiLabs.com

Re: [bitcoin-dev] Proposal to update BIP-32

[Gregory Maxwell]

On Sun, May 8, 2016 at 10:07 AM, Pavol Rusnak via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> On 21/04/16 14:08, Marek Palatinus via bitcoin-dev wrote:
>> Sipa, you are probably the most competent to answer this.
>> Could you please tell us your opinion? For me, this is
>> straightforward, backward compatible fix and I like it a lot.
>> Not sure about the process of changing "Final" BIP though.
>
> Sipa: Marek told me you posted your answer and he received it, but it
> never reached the list. Could you please resend after figuring out what
> went wrong?

AFAIK Sipa has not been on this list for some time.

[bitcoin-dev] Fwd: Proposal to update BIP-32

[Marek Palatinus]

[-- Attachment #1: Type: text/plain, Size: 3813 bytes --]

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

[-- Attachment #2: Type: text/html, Size: 6370 bytes --]

Re: [bitcoin-dev] Fwd: Proposal to update BIP-32

[Pavol Rusnak]

On 08/05/16 15:48, Marek Palatinus via bitcoin-dev wrote:
> 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, we'll write that down to SLIP-0032 then.

-- 
Best Regards / S pozdravom,

Pavol "stick" Rusnak
SatoshiLabs.com