What is key derivation and why would we need it?

## Public Key Cryptography refresh

It is assumed that the reader is somehow familiar with Asymmetric Key Cryptography: that is, the body of knowledge that deals with encryption algorithms that use pairs of values (called asymmetric keys) to encrypt and decrypt content. For a refresh on the subject, please check [i]

In any case, let us start with a quick reminder: Bitcoin and its blockchain has got is technical foundations rooted – amongst other mathematical principles and techniques – in cryptography, the art of hiding information from unauthorized disclosure using mathematical algorithms and small pieces of information that we call keys. The combination of the algorithm and the key is what protects the confidential data by making it unusable in its transformed form, by encrypting it.

More specifically, in asymmetric key cryptography we work with pairs of two different keys that are related to each other and that work together. Keys are generated in pairs and are specific to each other. What one key does encrypt using one algorithm, only the other key is able to decrypt using the same algorithm. And vice versa. Then we proceed to keep one of the keys secret – we call it the private key – while the other we make it available publicly – the public key -.

After this quick refresh, what usage do we give in bitcoin to asymmetric cryptography? In Bitcoin world, we use our public key to receive bitcoins. They are – sort of – the destination address where the bitcoins are sent. We use our private key to prove that we are the owners of the public key were the bitcoins were sent.

How does this work? Well, we first generate our private key. Then its corresponding public key is obtained from the private key through a mathematical process based on Elliptic Curve mathematics. The mathematical process ensures that it is practically impossible to guess the private key from the public key. So, if we keep the private key secret, we will be the only ones that are able to decrypt what the public key encrypts because

- Nobody else knows our private key
- Nobody can deduce our private key from our public key.
- What our public key encrypts, only our private key can decrypt.

This way we can implement a “proof of ownership” as follows:

- When someone sends bitcoins, they link them to a specific public key and to a message that is encrypted by that specific public key
- Remember the keys in bitcoin are always generated in pairs, first the private and then from the private key we obtain the public key. Only the owner of the correspondent private key knows the private key. And it is nearly impossible to guess the private key from the public key. Hence only the person who first created the private and public key will know the private key and then will be the only one able to use it to decrypt that message.
- By decrypting the message, the bitcoin core nodes recognize you as the owner of the public key and allow you to claim the bitcoins that were sent to the public key / public key associated message.
- As the recognized owner of the bitcoins eventually you can do something with them such as send them to someone else. Well to be more precise we would be sending them to someone else’s public key and link them to a message encrypted by that public key.

In summary, to receive and send Bitcoins and register these transactions on the blockchain, we need just two “related-to-each-other keys”, one public (to receive bitcoins) and one private (to prove we own the received bitcoins). And that would be it.

## The need for key derivation

However, it is usually more practical to have several pairs of private/public keys. We might want to have more than 1 destination address for receiving bitcoins. It would be like having several bank accounts, where we would be using different addresses for different purposes.

- We could generate different pairs of private/public keys independently and use each pair for different purposes. For example, to deal with different providers, or with different customers.
- One downside of this approach would be that the management of these key pairs can become unpractical as the number of key pairs increases. We would need to back up our private keys individually (remember our privatekeys.org mantra: “Your keys, your bitcoins, not your keys, not your bitcoin”) and maintain a registry of where did we put the backed up private keys, make sure they can be restored, etc.
- On the positive side, if the private keys are generated independently, there is no relationship between them, and if one of the private keys is compromised, and the funds it controls are at danger, our other private keys are not at risk. This is because the private keys are not related in any way and exfiltration of a private key does not represent a danger for the exfiltration of the other (unrelated) private keys

- Or we could generate an initial pair of private/public keys and have every other private/public key pairs derived from the original pair through mathematical processes. This, you have guessed, is more practical from the operations point of view, but we must make sure that we keep sufficient barriers between derived and original keys, in order to prevent that a single exfiltration of a private could cause a massive exfiltration our private keys.
- A method for doing so is described in BIP-0032 [ii] and the purpose of this article is to explain how this key derivation is done.

## Cryptography Nomenclature for this article

Before we start diving into dissecting BIP-0032, let me first talk about what abbreviations and variable names I am going to use in this article. I need to talk about this because it is unfortunate that “Private” and “Public” words both start with the same letter: letter P. Hence when we try to put in formulas a variable that represents of our keys and the different relationships between private and public keys such as how ones are derived or related to the others, we face the problem of choosing a variable name that represents them unambiguously.

In other words, how do we shorten “Public Key”? With an uppercase “P”? With an uppercase “K”? If so, what about “Private Key”? With a lowercase “p”? With a lowercase “k”? Unfortunately, these options, although very common, are poor choices, as uppercase and lowercase versions of the same letter may have got different size but they have a very similar shape. When reading formulas, it is sometimes difficult to tell if we are talking about a private key or a public key, since it may be too ambiguous to be able to distinguish between uppercase “K” and lowercase “k” at first sight.

Having that in mind, in this blog entry I have decided to name private keys with an “S” as in Secret. Public keys will go with a “P”. Our chain code – see my previous article “Private Key Generation in Bitcoin as defined in BIP-0039” [iii] – will go with a “C”. For completeness

- S
_{0}represents our initial Private Key. The “0” represents “level 0”, or the root private key. - C
_{0}represents our initial Chain code. The “0” represents “level 0”, or the root chain code - P
_{0}represents our initial Public Key, level 0, derived from S_{0}through the application of the Elliptic Curve point multiplication used in Bitcoin – see next point -. - EC[S
_{0}] represents the application of the EC point multiplication (repeated application of the EC group operation) of the secp256k1 (see [iv]) base point with the integer S_{0}. This technique is used in Bitcoin to derivate the corresponding public key from the private key. For example EC[S_{0}]=P_{0}means that we have applied the Elliptic Curve function to our initial private key S_{0}(that is: we have applied the EC group operation to the sec256k1 origin point a total amount of S_{0}times) and we have then obtained our initial public key P_{0}. For more details about the Elliptic Curve point multiplication and the origin point please check [v] - In deterministic hierarchical wallets, all other keys will be derived from S
_{0}and C_{0}in a way or another. - N is the primer number used in secp256k1. It is equal to 2
^{256}– 2^{32}– 2^{9}– 2^{8}– 2^{7}– 2^{6}– 2^{4}– 1. The coordinates of points that belong to the secp256p1 elliptic curve are defined over the field Z_{N}so they cannot be bigger than this number. Bitcoin uses it as a high limit for valid private keys. If by a small chance we randomly generate a private key bigger than N, it gets discarded and a new one gets generated. The probability of such occurrence is small as N is “almost” as large as 2^{256}-1 (256 bits all set to 1). To visualize the difference, please consider both numbers written in hexadecimal- 2
^{256}= FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF - N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

- 2

## Private Key Derivation: Hardened vs. Non-Hardened

Now let’s see how BIP-0032 describes two ways to derive first level private keys from level-0 private key S_{0}, chain block C_{0} and public key P_{0}.

- We can derive our first level private key using our zero-level private key S
_{0}and zero level chain code C_{0}. That means we would not be using our zero level Public key P_{0}to obtain a derived private key. We will call this method “Hardened Secret Key Derivation” or HSKD for short and we will describe how it works later in this article. HSKD first level private keys will be named S’_{1}. - Or we could derive our first level Private key using a combination of our zero-level private key S
_{0}, our zero-level chain block C_{0}and our zero-level public key P_{0}. We will call this method “Non-Hardened Secret Key Derivation” or NSKD for short and we will describe how it works later in this article as well. NSKD first level private keys will be named S_{1}. - As you can see we use the “ ’ ” to distinguish between HSKD keys and NSKD keys.

## Multiple Key Derivation

Also in deterministic hierarchical wallets, it has been considered that we can derive multiple times the initial private key. All these derived keys will be located at level 1. To obtain multiple level-1 derived keys we will use a 32-bit integer in our calculations (a 32-bit integer is a number between 0 and 2^{32} -1, a number rather large). We will use this number into the mathematical process involved in the derivation, in a fashion that we can use the same S_{0} and C_{0} , and by changing this number we will be changing the resulting key.

We will call that integer “i” and it has been stated in BIP-0032 that.

- For NSDK keys we will use values of “i” between 0 and 2
^{31 }-1 - For HSDK keys we will use values of “i” between 2
^{31}and 2^{32}– 1.

To distinguish between these multiple level-1 keys we will use an additional sub index. Hence S’_{1,0} would be the first HSKD derived level-1 private key. And S’_{1,m} would be our m+1 HSKD derived level-1 key.

As you can see for the first HSDK key m= 2^{31} = 2147483648 and in that case our first level-1 HSDK would be written S_{1,} _{2147483648 }. Well, this is impractical. So, let’s say that for both HSDK and NSDK our index “m” goes from 0 to 2^{31}-1 (that is a 31-bit number).

- For NSDK, the integer “i” that is used in the calculations equals “m”.
- But for HSDK the integer “i” that is used in the calculations equals 2
^{31}+ “m”

Or in other words,

- If the variable that represents the key has not got the “ ’ ”, then the integer “i” that was used to obtain equals the variable index “m”
- if the variable that represents the key has got the “ ’ ”, then the integer “i” that was used to obtain it is the result of adding 2
^{31}to the variable index “m”

Original Private Key | Key Derivation Method | Integer Value “i” | Index Value “m” | Derived Private Key |

S_{0} |
NSDK | 0 | 0 | S_{1,0} |

S_{0} |
NSDK | 1 | 1 | S_{1,1} |

S_{0} |
NSDK | 2 | 2 | S_{1,2} |

… | … | … | ||

S_{0} |
NSDK | 2^{31} – 1 (=2147483647) |
2^{31} – 1 (=2147483647) |
S_{1,2147483647} |

S_{0} |
HSDK | 2^{31} (=2147483648) |
0 | S’_{1,0} |

S_{0} |
HSDK | 2^{31} +1 (=2147483649) |
1 | S’_{1,1} |

S_{0} |
HSDK | 2^{31} +2 (=2147483650) |
2 | S’_{1,2} |

… | … | … | … | … |

As you can see, we simplify the nomenclature of the first HSDK keys and we resolve the ambiguity for the index value “m” by adding a “ ‘ “ to the variable name, that indicates us if “i” = “m” or if “i” = 2^{31} + “m”

Now that we have got all the names clarified, what is the logic that allows us to derive a 1-level key from a 0-level key? Let us see what are the options

## Hardened Private Key Derivation (HSKD)

The process is as follows

- We take S
_{0}, C_{0}and i, and apply them to a HMAC-SHA512 (more info here [vi] and here [vii] ) function as follows- We concatenate S
_{0}and i and use them as “Data” on the HMAC-SHA512 algorithm - We use C
_{0}as “Key” on the HMAC-SHA512 algorithm

- We concatenate S
- As a result of that process we obtain a 512-bit string that we will divide into two 256-bit parts. The left part will be notated I
_{L}and the right part will be notated I_{R}- We will make the addition modulo N of the left part I
_{L}and the original private key S_{0}. The result will be our newly HSDK derived level-1 private key, called S’_{1,m} - Our right part I
_{R}will be our level-1 chain code C’_{1,m}

- We will make the addition modulo N of the left part I

## Obtaining the Hardened Public Key (HS2P)

When it comes to obtain level-1 public keys of the corresponding HSDK derived level-1 private key we use that level 1 private key S’_{1,m }and apply the Elliptic Curve group function to it to obtain its corresponding public key P’_{1,m} by applying EC[S’_{1,m}]= P’_{1,m}. We call this process Hardened Secret Key to Public Key Calculation or HS2P.

## Non-Hardened Private Key Derivation (NSKD)

The process is as follows

- We apply the Elliptic Curve point multiplication (repeated application of the EC group operation) of the secp256k1 base point with the integer S
_{0}. In other words, we obtain our level-0 public key P_{0}from our level-0 private key S_{0}. - We take P
_{0}, C_{0}and i, and apply them to a HMAC-SHA512 function as follows- We concatenate P
_{0}and i and use them as “Data” on the HMAC-SHA512 algorithm - We use C
_{0}as “Key” on the HMAC-SHA512 algorithm

- We concatenate P
- As a result of that process we obtain a 512-bit string that we will divide into two 256-bit parts. The left part will be notated I
_{L}and the right part will be notated I_{R}- We will make the addition modulo N of the left part I
_{L}and the original private key S_{0}. The result will be our newly HSDK derived level-1 private key, called S_{1,m} - Our right part I
_{R}will be our level-1 chain code C_{1,m}

- We will make the addition modulo N of the left part I

## Obtaining the Non-Hardened Public Key (NS2P)

When it comes to obtain level-1 public keys of the corresponding NSDK derived level-1 private key, we can use the NSKD level-1 private key S_{1,m }and apply the Elliptic Curve group function to it to obtain its corresponding public key P_{1,m} by applying EC[S_{1,m}]= P_{1,m}. We call this process Non-Hardened Secret Key to public Key Calculation or NS2P

That would be all, right? Well, no. BIP-0032 defines a very interesting alternative, let’s look into it

## Non-Hardened Public Key Derivation (NPKD)

Yes, we can use Non-Hardened key derivation to obtain … another public key. Remember that for non-hardened key derivation we were using the level-0 public key as input. Well, why would we want to derive a level-1 public key directly from a level-0 public key without involving a level-0 private key in the process?

The answer is that level-0 public keys are, well, public. There is nothing secret in them. If we combine P_{0} with C_{0} and the index i, we could obtain level-1 public keys without involving the private key S_{0}. That is a good feature for less secure environments, where we cannot or don’t want to use and store the level-0 private key S_{0}. Say for example online-shopping web servers that would be creating a new public key (a.k.a. a new bitcoin address where we receive the payments) for every new customer, without the hassle to handle the level-0 private key S_{0} every time.

The process is as follows

- We apply the Elliptic Curve point multiplication (repeated application of the EC group operation) of the secp256k1 base point with the integer S
_{0}. In other words, we obtain our level-0 public key P_{0}from our level-0 private key S_{0}. - We take P
_{0}, C_{0}and i and apply them to HMAC-SHA512 function as follows- We concatenate P
_{0}and i and use them as “Data” on the HMAC-SHA512 algorithm - We use C
_{0}as “Key” on the HMAC-SHA512 algorithm

- We concatenate P
- As a result of that process we obtain a 512-bit string that we will divide into two 256-bit parts. The left part will be notated I
_{L}and the right part will be notated I_{R}- We take I
_{L}and apply the Elliptic Curve point multiplication (repeated application of the EC group operation) of the secp256k1 base point with the integer I_{L}. As if we were obtaining our level-1 public key P_{1}from I_{L}. We will call this PRE_{1,m}as it is a previous step before obtaining the level-1 public key - We will make the addition modulo N of PRE
_{1,m}and the original public key P_{0}. The result will be our newly NPDK derived level-1 private key, called P_{1,m} - Our right part I
_{R}will be our level-1 chain code C_{1,m}

- We take I

The question that remains to be answered is as follows: where is the corresponding level-1 private key S_{1,m}? Remember we will need that private key to claim the bitcoins that are going to be sent to our newly NPKD public key. And we cannot derive it from its corresponding newly NPKD derived public key P_{1,m}.

In fact, the question can be formulated differently: is this NPKD P_{1,m} key the same as the one we would obtain by applying Elliptic Curve to the NSKD level-1 S_{1,m} private key? If so, then our problem is solved, because if we have two methods that produce the same public key (either NSKD plus Elliptic curve of the result, or NPKD), then the corresponding private keys are the same too, because there is a 1-to-1 relationship between private and public keys (the Elliptic Curve group function takes care of that).

I so, we could use NPKD to derive level-1 public keys P_{1,m} from level-0 public key P_{0}, without involving the level-0 private key S_{0}, in a non-secured web server for example. And when we need the corresponding level-1 private key S_{1,m} (to claim the bitcoins that we have been sent to P_{1,m}), then we apply NSKD to derive and find our corresponding private key S_{1,m} from S_{0} and P_{0}

Well, the good news is that

- whether we use NSKD + EC to calculate P
_{1,m} - or that we use NPKD to calculate P
_{1,m},

the resulting P_{1,m} is the same. Let me show you.

## Non-Hardened Private or Public Key Derivation?

Let’s start with NSKD. We are applying NSKD to a level-0 private key and we are obtaining a level-1 private key. Then we can apply Elliptic Curve group function to that level-1 private key and we would obtain the corresponding lelvel-1 public key. Graphically is as follows.

And in formulae, NSKD would be first calculating HMAC-512 of P_{0}, C_{0} and i, taking the left part and adding it modulo N to S_{0}, to obtain S_{1,m}.

S_{1,m} = HMAC_{L} (P_{0},C_{0},i) + S_{0}

Then, we apply Elliptic Curve group function to S_{1,m} and obtain P_{1,m}

P_{1,m} = EC [ HMAC_{L} (P_{0},C_{0},i) + S_{0} ]

Let’s look at NPKD now. We are applying Elliptic Curve Group function to a level-0 private key and we are obtaining a level-0 public key. We are then applying NPDK to our 0-level public key and we obtain our level-1 public key.

And in formulae we would be applying Elliptic Curve group function to S_{0} and we would be obtaining P_{0}.

P_{0} = EC [ S_{0} ]

Then we apply NPKD to that result, that is we use our P_{0} key in HMAC-512 together with C_{0} and i, take the left part, we apply Elliptic Curve to that left part and finally we add it to P_{0}

P_{1,m} = EC [ HMAC_{L} (P_{0},C_{0},i) ] + P_{0} = EC [ HMAC_{L} (P_{0},C_{0},i) ] + EC [ P_{0 }]

Are these two level-1 public keys the same P_{1,m}? In the first case, we first do key derivation and then we do Elliptic Curve to obtain P_{1,m}. In the second case, we first do elliptic curve and then we us (a slightly different) key derivation to obtain P_{1,m}. So let me insist, are they the same?

If we replace HMAC_{L} (P_{0},C_{0},i) by letter “A”, and S_{0} by letter “B”, then our first key

P_{1,m} = EC [ HMAC_{L} (P_{0},C_{0},i) + S_{0} ] = EC [ A + B ]

Our second key

P_{1,m} = EC [ HMAC_{L} (P_{0},C_{0},i) ] + EC [ P_{0 }] = EC [ A ] + EC [ B ]

So, is EC [ A + B ] equal to EC [ A ] + EC [ B ] ? The question resrts to: Is the Elliptic Curve point multiplication associative? Don’t forget to ask that to the next mathematician you cross on the street. Otherwise you can go check it for yourself at, for example, here [viii] (Hint: the answer is Yes).

## Security Consideration for Non-Hardened Key Derivation (NSKD and NPKD)

NPKD is very practical way of securely deriving level-1 public keys from level-0 public keys. But it must be accompanied with NSKD, that is, from deriving our level-1 private keys from our level-0 public keys. And deriving private keys from public keys is considered bad security practice by some cryptography professionals. Let’s look at the NSKD diagram once again and let’s see why

__ __

Modulo N addition is a reversible operation. If you know the result (S_{1,m}) and one of the operands you can obtain the other operand. So if you know S_{1,m} and C_{0}, they you can calculate S_{0}. So, we see that a good part of the secrecy of the private keys resides as well on the secrecy of the chain code. If someone happens to know C_{0}, then he can calculate all the I_{R} and I_{L} iterations, as P_{0} and i are public and known. All children chain codes would be exfiltrated as well. If by some unfortunate mistake one of the S_{1,m} is exfiltrated too, then S_{0} could be calculated. Disaster ensues. Exfiltration of S_{1,m} (or any child private keys) should not put S_{0} (father private keys) at risk under any circumstances. Purists would say that exfiltration of a private key should not put at risk any other private key. This is not the case of NSKD and that’s why seasoned cryptography architects frown upon Non-Hardened key derivation.

*This article was written by ignacio. You can contact him at* admin@privatekeys.org

[i] https://en.wikipedia.org/wiki/Public-key_cryptography

[ii] https://github.com/bitcoin/bips/blob/master/bip-0032.mediawiki

[iii] https://privatekeys.org/2017/09/03/private-key-generation-in-bitcoin-wallets-as-defined-in-bip-0039/

[iv] https://en.bitcoin.it/wiki/Secp256k1

[v] http://www.secg.org/sec2-v2.pdf

[vi] https://tools.ietf.org/html/rfc2104

[vii] https://web.archive.org/web/20130526224224/http://csrc.nist.gov/groups/STM/cavp/documents/shs/sha256-384-512.pdf

[viii] Rational Points on Elliptic Curves http://www.springer.com/us/book/9780387978253

Pingback: Key Derivation in Bitcoin Wallets as defined in BIP-0032 - privatekeys.biz

Pingback: Key Derivation in Bitcoin Wallets as defined in BIP-0032