BIP0032 HD Wallet private key derivation incorrect?

[Wink]

I have been implementing the BIP0032 HD Wallet protocol, and ran into an issue in the documentation at https://en.bitcoin.it/wiki/BIP_0032 which slowed me down for an entire day. Here is the documentation on private child key derivation.

Private child key derivation
To define CKD((kpar, cpar), i) → (ki, ci):
Check whether the highest bit (0x80000000) of i is set:
If 1, private derivation is used: let I = HMAC-SHA512(Key = cpar, Data = 0x00 || kpar || i) [Note: The 0x00 pads the private key to make it 33 bytes long.]
If 0, public derivation is used: let I = HMAC-SHA512(Key = cpar, Data = χ(kpar*G) || i)
Split I = IL || IR into two 32-byte sequences, IL and IR.
ki = IL + kpar (mod n).
ci = IR.

It says you should add IL to kpar(mod n).
In pseudo code, this would be:

Code:

i_left + (kpar % n)

Adding these two values together should always create a new number that is 32 bytes long. However, for some values of IL and kpar(mod n), adding them together can create a number that is greater than 32 bytes long, and is therefore no longer a valid 256bit private key.

It appears the parenthesis are in the wrong place in the documentation. It should read:

ki = (IL + kpar) mod n.

or in pseudo code:

Code:

(i_left + kpar) % n

Changing the parenthesis finally made all of my test vectors pass. I'm posting this to hopefully save someone else a world of trouble. Can we change the documentation?

[riplin]

I think that the (mod n) was added as an indication that this should happen, not as a mathematical notation. It's syntactically incorrect, which kind of gives it away.

[Wink]

I think that the (mod n) was added as an indication that this should happen, not as a mathematical notation. It's syntactically incorrect, which kind of gives it away.

Yes, I believe you're right. And in retrospect that makes total sense! However, it's confusing given its placement right next to the equation. At any rate, it wouldn't hurt to make the documentation more clear in case any other developers are as unfamiliar with crypto concepts and byte management as I was. At least I learned a lot about bits/bytes/elliptic curves and everything else I tried in search of the answer.

[fpgaminer]

(mod n) is typical notion, and it implies that all the arithmetic in the preceding equation is modulo n.  So the wiki is correct.  (Look at the ECDSA wiki article for great examples.)

I don't think that particular part of the wiki should be changed to make it more clear for those unfamiliar with crypto.  I would argue that if one is unfamiliar with crypto, one should not implement HD wallets (at least in production; for fun, sure).

I would, however, argue for better reference implementations (code is gospel).  I found the Python one rather confusing.  The Java one isn't bad, but it suffered from a few bugs at first glance.

On a related note, I found the wiki confusing for other reasons.  "Private derivation" uses a node's private key.  If a second party is given only the public key for a node, they can't calculate that particular leaf.  So, later in the article, how is the use case "Audit: M" possible?

Since the wiki never explains "private derivation" beyond giving the algorithm, I can only make assumptions.  My assumption is that it is a means of creating a branch in the tree that can be given to a second party, but from which that party cannot derive the proceeding tree.  Backtracking resistance, in other words.  Well ... that's useful.  It means that, in the canonical wallet structure, compromises of one account do not endanger other accounts.  But this is never explained, so I can only make assumptions.

As the developer for the Titan hardware wallet project, BIP 0032 is relevant to me.  But I was put off from it because of its current opaqueness.  It's good in theory, but not well documented in my opinion.  I'll probably revisit and implement it later.

[gmaxwell]

There is a lot of additional documentation for BIP32 in addition to the BIP itself:

For example, http://www.youtube.com/watch?v=WcnMjkc31Fs

I'm disappointed that this is the first time I've heard your complaints.  It has now been independently implemented by at least four parties.  Your feedback sounds good though, do you have any proposed revised text? (And indeed, your understanding is correct).

The motivation there is that the ECC homomorphism based public derivation has that highly surprising backwards enumeration property.  In some use-cases it could easily cause a total loss.  E.g. I export a private key from my wallet and give it to you, and you already have the extended key for that chain for auditing... oops now you have all the coins on that chain.

The text on that is a bit weaker because we added it later... we'd hoped for a while that there would be a way to remove that property but couldn't find one.  The auditing behavior still exists, but works only in publicly derived chains.

Some client software may choose to only use public derivation, thus facilitating auditing. If they do they should probably avoid offering key export function for single private keys, simply because it has turned out to be really hard to educate users about the exposure.

[riplin]

Some client software may choose to only use public derivation, thus facilitating auditing.

I use the private derivation for change addresses of a key and auditing would be limited to the public branch off that key.

[Mike Hearn]

By "Java implementation" did you mean the one Matija wrote for bitcoinj? If there are bugs we'd like to know about it.

[grau]

I would, however, argue for better reference implementations (code is gospel).  I found the Python one rather confusing.  The Java one isn't bad, but it suffered from a few bugs at first glance.

I wrote one of the Java implementations that is also listed on the BIP page. If this is the one you refer to, then please elaborate on the bugs.

[natb]

Thanks much for that video reference, its a handy addition to BIP 0032 and helps flesh out some of the motivations behind the scheme. I am also creating a HW wallet prototype and am happily using BIP 0032 as my foundation for key generation. I appreciate the python implementation as it's a great check and reference.

One thing I've heard a bit about is BIP "0032.5" - could you comment on the motivations for this and what the key differences with BIP 0032 are - or maybe point me to a draft version of this that I can read? Thanks!

There is a lot of additional documentation for BIP32 in addition to the BIP itself:

For example, http://www.youtube.com/watch?v=WcnMjkc31Fs

I'm disappointed that this is the first time I've heard your complaints.  It has now been independently implemented by at least four parties.  Your feedback sounds good though, do you have any proposed revised text? (And indeed, your understanding is correct).

The motivation there is that the ECC homomorphism based public derivation has that highly surprising backwards enumeration property.  In some use-cases it could easily cause a total loss.  E.g. I export a private key from my wallet and give it to you, and you already have the extended key for that chain for auditing... oops now you have all the coins on that chain.

The text on that is a bit weaker because we added it later... we'd hoped for a while that there would be a way to remove that property but couldn't find one.  The auditing behavior still exists, but works only in publicly derived chains.

Some client software may choose to only use public derivation, thus facilitating auditing. If they do they should probably avoid offering key export function for single private keys, simply because it has turned out to be really hard to educate users about the exposure.

[fpgaminer]

I wrote one of the Java implementations that is also listed on the BIP page. If this is the one you refer to, then please elaborate on the bugs.

Yes, I was referring to the one linked from the BIP 0032 wiki page.  I only took a quick glance over it, to double check my understanding of BIP 0032.  More likely than not the things I noticed at a glance were either misunderstandings on my part, or pedantic bugs.  I'll do a proper code audit in a day or two and let you know if I find anything.

One thing I've heard a bit about is BIP "0032.5" - could you comment on the motivations for this and what the key differences with BIP 0032 are - or maybe point me to a draft version of this that I can read? Thanks!

I have a discussion thread on the RFC that BIP is based on:  https://bitcointalk.org/index.php?topic=285142.0

Check gmaxwell's first reply for a link to his proposal for BIP 0032.5.  I don't think there's a draft BIP yet.

I'm disappointed that this is the first time I've heard your complaints.  It has now been independently implemented by at least four parties.  Your feedback sounds good though, do you have any proposed revised text? (And indeed, your understanding is correct).

By the way, don't take my post as harsh criticism.  As I alluded to, I like the idea, and I appreciate the efforts of those who researched and developed it.  My comments merely reflect the trouble I had with it on a first time read through.  I did a second read last night, and still think the wording could be greatly improved.  There are a lot of overloaded words which make it difficult to read.  When I get a chance I'll sit down and see if I can come up with alterations which may help make the document clearer.

Here's an example of what I mean by overloaded words.  Using the verbiage of BIP 0032 in its current state, I could write the following declaration: "The private child key derivation function can be used for both public and private derivation of public and private extended keys."  Pretty confusing, eh?

[fpgaminer]

I wrote one of the Java implementations that is also listed on the BIP page. If this is the one you refer to, then please elaborate on the bugs.

I just finished a more detailed look at the code.  There were only two bugs, both pedantic in nature.  The rest of the code looks fine to me.

Code:

Audit of https://github.com/bitsofproof/supernode/blob/1.1/api/src/main/java/com/bitsofproof/supernode/api/ExtendedKey.java



Line 155: l compared to `n`, but not 0.
If the code is going to compare to n, it should be consistent and also compare to 0.
One could also argue that both checks are useless; it'll never occur and is untestable.


Line 235: Does it mean anything for depth to overflow?
Perhaps an exception should be thrown if this key is already at maximum depth
(0xFF). Whether this matters or not depends on the application using the
class.

[grau]

I wrote one of the Java implementations that is also listed on the BIP page. If this is the one you refer to, then please elaborate on the bugs.

I just finished a more detailed look at the code.  There were only two bugs, both pedantic in nature.  The rest of the code looks fine to me.

Thanks for the audit. Since the "rest of the code" does the work in practically all cases, I think it is fine.
I will add an exception checking the max depth and 0.

[plaprade]

ki = IL + kpar (mod n).

I'm independently implementing BIP32 in Haskell on a private repo for now. It'll pop up on my github page when I'm happy with it in a few days.

I understood the above documentation line as follows: You need to treat IL as an EC private key. If it is == 0 or >= n then it is an invalid private key. If it is valid, you add it to kpar, which is another private key. Now as private keys are field elements (modulo n), addition is defined as field addition (modulo n) instead of regular integer addition. Adding them together produces a new private key ki which will be < than n. However, this new value could be equal to 0 so you need to check that.

It is considered a standard notation to put the order of the field in parenthesis when writing operations within that field.
For example:

2 + 3 = 2 (mod 3)
3 + 8 = 4 (mod 7)

Cheers!

Edit: IL can be equal to zero

[fpgaminer]

You need to treat IL as an EC private key. If it is == 0 or >= n then it is an invalid private key.

For both CKD functions, it is okay for IL to be 0.  You only need to check that IL < n.  (and that k_i != 0)

IL being 0 means the child's EC key pair is equal to the parent's EC key pair, which is a bit odd, but not explicitly forbidden by the current BIP 0032.  (NOTE: The extended key may still differ in these cases)

[plaprade]

For both CKD functions, it is okay for IL to be 0. 

My bad. IL can be equal to 0 indeed.

[Crowex]

The motivation there is that the ECC homomorphism based public derivation has that highly surprising backwards enumeration property.  In some use-cases it could easily cause a total loss.  E.g. I export a private key from my wallet and give it to you, and you already have the extended key for that chain for auditing... oops now you have all the coins on that chain.

The text on that is a bit weaker because we added it later... we'd hoped for a while that there would be a way to remove that property but couldn't find one.  The auditing behavior still exists, but works only in publicly derived chains.

Some client software may choose to only use public derivation, thus facilitating auditing. If they do they should probably avoid offering key export function for single private keys, simply because it has turned out to be really hard to educate users about the exposure.

I'm probably missing something here, but if I wanted to allow auditing of any branch without worrying about knowledge of a private key compromising other addresses can't I just generate another key pair, x,X, and derive all public addresses for that branch by using the group operation (i.e. point addition) on any public key K derived on that branch by defining the public addresses as X+K (here +is point addition) for all addresses generated on that branch. That way I could give away individual private keys x+k (and the extended key for generating K (and auditor easily generates X+K) without compromising any other private keys.
 Why couldn't you do this for each branch adding extra protection against loss of the master extended key? Is it because of the extra key management? Or have I missed something?

[plaprade]

The motivation there is that the ECC homomorphism based public derivation has that highly surprising backwards enumeration property.  In some use-cases it could easily cause a total loss.  E.g. I export a private key from my wallet and give it to you, and you already have the extended key for that chain for auditing... oops now you have all the coins on that chain.

I'm probably missing something here, but if I wanted to allow auditing of any branch without worrying about knowledge of a private key compromising other addresses can't I just generate another key pair, x,X, and derive all public addresses for that branch by using the group operation (i.e. point addition) on any public key K derived on that branch by defining the public addresses as X+K (here +is point addition) for all addresses generated on that branch. That way I could give away individual private keys x+k (and the extended key for generating K (and auditor easily generates X+K) without compromising any other private keys.
 Why couldn't you do this for each branch adding extra protection against loss of the master extended key? Is it because of the extra key management? Or have I missed something?

In BIP32, say you have a master public key (Kpar, Cpar) which has an associated private key (kpar, cpar).

You derive a child private key (number i) through non-prime derivation using:

Code:

1) (L, R) = HMAC( Cpar, Kpar || i )
2) ki = L + kpar (mod n)
3) return (ki, R)

Looking at equation 2) you notice that the L component can be computed if you know (Kpar, Cpar). So, knowing any derived private key ki and the master public key Kpar completely leaks kpar:

Code:

kpar = ki - L (mod n)

Essentially, this means that if you gave M/i' to an auditor and you additionally give him m/i'/0 then you are essentially leaking m/i' and any keys derived from it.

[Crowex]

The motivation there is that the ECC homomorphism based public derivation has that highly surprising backwards enumeration property.  In some use-cases it could easily cause a total loss.  E.g. I export a private key from my wallet and give it to you, and you already have the extended key for that chain for auditing... oops now you have all the coins on that chain.

I'm probably missing something here, but if I wanted to allow auditing of any branch without worrying about knowledge of a private key compromising other addresses can't I just generate another key pair, x,X, and derive all public addresses for that branch by using the group operation (i.e. point addition) on any public key K derived on that branch by defining the public addresses as X+K (here +is point addition) for all addresses generated on that branch. That way I could give away individual private keys x+k (and the extended key for generating K (and auditor easily generates X+K) without compromising any other private keys.
 Why couldn't you do this for each branch adding extra protection against loss of the master extended key? Is it because of the extra key management? Or have I missed something?

In BIP32, say you have a master public key (Kpar, Cpar) which has an associated private key (kpar, cpar).

You derive a child private key (number i) through non-prime derivation using:

Code:

1) (L, R) = HMAC( Cpar, Kpar || i )
2) ki = L + kpar (mod n)
3) return (ki, R)

Looking at equation 2) you notice that the L component can be computed if you know (Kpar, Cpar). So, knowing any derived private key ki and the master public key Kpar completely leaks kpar:

Code:

kpar = ki - L (mod n)

Essentially, this means that if you gave M/i' to an auditor and you additionally give him m/i'/0 then you are essentially leaking m/i' and any keys derived from it.

Which is why I suggested this possible solution.
The public addresses that are used are created by adding (point addition) X to all of the  BIP32 addresses
created on that branch. The auditor can create these given X and the master public key.
If a private key is given to the auditor (m/i'/0+x) the auditor cannot deduce m/i'/0 from this private key and so cannot derive any other private keys.
 Only the person holding x and the master private key can derive the private keys on that branch.

[Crowex]

Meant to say...the auditor can create these given X and a public key.

[fpgaminer]

The public addresses that are used are created by adding (point addition) X to all of the  BIP32 addresses
created on that branch. The auditor can create these given X and the master public key.
If a private key is given to the auditor (m/i'/0+x) the auditor cannot deduce m/i'/0 from this private key and so cannot derive any other private keys.

I don't think that'll work.  Here's why:

Suppose we simplify BIP32, to make my explaination easier, but without loss of generality:

Code:

k_i = k_par + HASH(i)
K_i = K_par + HASH(i) * G

The weakness here, that you're trying to solve, is that if any derived private keys are leaked, an attacker can find the parent private key, and thus all derived keys:

Code:

k_0 = k_par + HASH(0)
=> k_par = k_0 - HASH(0)

Now, from what I understand of your proposal, you'd modify that like so:

Code:

k_i = k_par + HASH (i) + x
K_i = K_par + HASH(i) * G + X

Where x is a secret not given to an auditor, and X is the associated public key (given to the auditor).  If a derived private key leaks...

Code:

k_0 = k_par + HASH(0) + x
=> k_par + x = k_0 - HASH(0) = m
=> k_i = m + HASH (i)

Therefore, if one private key in a branch leaks, all derived private keys leak.