Key Derivation in Bitcoin Wallets as defined in BIP-0032

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

  • S0 represents our initial Private Key. The “0” represents “level 0”, or the root private key.
  • C0 represents our initial Chain code. The “0” represents “level 0”, or the root chain code
  • P0 represents our initial Public Key, level 0, derived from S0 through the application of the Elliptic Curve point multiplication used in Bitcoin – see next point -.
  • EC[S0] 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 S0. This technique is used in Bitcoin to derivate the corresponding public key from the private key. For example EC[S0]=P0 means that we have applied the Elliptic Curve function to our initial private key S0 (that is: we have applied the EC group operation to the sec256k1 origin point a total amount of S0 times) and we have then obtained our initial public key P0. 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 S0 and C0 in a way or another.
  • N is the primer number used in secp256k1. It is equal to 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1. The coordinates of points that belong to the secp256p1 elliptic curve are defined over the field ZN 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 2256-1 (256 bits all set to 1). To visualize the difference, please consider both numbers written in hexadecimal
    • 2256 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFFFF
    • N = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

 

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 S0, chain block C0 and public key P0.

  • We can derive our first level private key using our zero-level private key S0 and zero level chain code C0. That means we would not be using our zero level Public key P0 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 S0, our zero-level chain block C0 and our zero-level public key P0. 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 S1.
  • 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 232 -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 S0 and C0 , 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 231 -1
  • For HSDK keys we will use values of “i” between 231 and 232 – 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= 231 = 2147483648 and in that case our first level-1 HSDK would be written S1, 2147483648  . Well, this is impractical. So, let’s say that for both HSDK and NSDK our index “m” goes from 0 to 231-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 231 + “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 231 to the variable index “m”
Original Private Key Key Derivation Method Integer Value “i” Index Value “m” Derived Private Key
S0 NSDK 0 0 S1,0
S0 NSDK 1 1 S1,1
S0 NSDK 2 2 S1,2
S0 NSDK 231 – 1 (=2147483647) 231 – 1 (=2147483647) S1,2147483647
S0 HSDK 231 (=2147483648) 0 S’1,0
S0 HSDK 231 +1 (=2147483649) 1 S’1,1
S0 HSDK 231 +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” = 231 + “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 S0, C0 and i, and apply them to a HMAC-SHA512 (more info here [vi] and here [vii] ) function as follows
    • We concatenate S0 and i and use them as “Data” on the HMAC-SHA512 algorithm
    • We use C0 as “Key” on the HMAC-SHA512 algorithm
  • 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 IL and the right part will be notated IR
    • We will make the addition modulo N of the left part IL and the original private key S0. The result will be our newly HSDK derived level-1 private key, called S’1,m
    • Our right part IR will be our level-1 chain code C’1,m

Captura1

 

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.

Captura2

 

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 S0. In other words, we obtain our level-0 public key P0 from our level-0 private key S0.
  • We take P0, C0 and i, and apply them to a HMAC-SHA512 function as follows
    • We concatenate P0 and i and use them as “Data” on the HMAC-SHA512 algorithm
    • We use C0 as “Key” on the HMAC-SHA512 algorithm
  • 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 IL and the right part will be notated IR
    • We will make the addition modulo N of the left part IL and the original private key S0. The result will be our newly HSDK derived level-1 private key, called S1,m
    • Our right part IR will be our level-1 chain code C1,m

Captura3

 

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 S1,m and apply the Elliptic Curve group function to it to obtain its corresponding public key P1,m by applying EC[S1,m]= P1,m. We call this process Non-Hardened Secret Key to public Key Calculation or NS2P

Captura4

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 P0 with C0 and the index i, we could obtain level-1 public keys without involving the private key S0. 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 S0. 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 S0 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 S0. In other words, we obtain our level-0 public key P0 from our level-0 private key S0.
  • We take P0, C0 and i and apply them to HMAC-SHA512 function as follows
    • We concatenate P0 and i and use them as “Data” on the HMAC-SHA512 algorithm
    • We use C0 as “Key” on the HMAC-SHA512 algorithm
  • 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 IL and the right part will be notated IR
    • We take IL and apply the Elliptic Curve point multiplication (repeated application of the EC group operation) of the secp256k1 base point with the integer IL. As if we were obtaining our level-1 public key P1 from IL. We will call this PRE1,m as it is a previous step before obtaining the level-1 public key
    • We will make the addition modulo N of PRE1,m and the original public key P0. The result will be our newly NPDK derived level-1 private key, called P1,m
    • Our right part IR will be our level-1 chain code C1,m

Captura5

The question that remains to be answered is as follows: where is the corresponding level-1 private key S1,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 P1,m.

In fact, the question can be formulated differently: is this NPKD P1,m key the same as the one we would obtain by applying Elliptic Curve to the NSKD level-1 S1,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 P1,m from level-0 public key P0, without involving the level-0 private key S0, in a non-secured web server for example. And when we need the corresponding level-1 private key S1,m (to claim the bitcoins that we have been sent to P1,m), then we apply NSKD to derive and find our corresponding private key S1,m from S0 and P0

Well, the good news is that

  • whether we use NSKD + EC to calculate P1,m
  • or that we use NPKD to calculate P1,m,

the resulting P1,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.

Captura8

And in formulae, NSKD would be first calculating HMAC-512 of P0, C0 and i, taking the left part and adding it modulo N to S0, to obtain S1,m.

S1,m = HMACL (P0,C0,i) + S0

Then, we apply Elliptic Curve group function to S1,m and obtain P1,m

P1,m = EC [ HMACL (P0,C0,i) + S0 ]

Captura9

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.

Captura10

And in formulae we would be applying Elliptic Curve group function to S0 and we would be obtaining P0.

P0 = EC [ S0 ]

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

P1,m = EC [ HMACL (P0,C0,i) ] + P0 = EC [ HMACL (P0,C0,i) ] + EC [ P0 ]

Captura11

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

If we replace HMACL (P0,C0,i) by letter “A”, and S0 by letter “B”, then our first key

P1,m = EC [ HMACL (P0,C0,i) + S0 ] = EC [ A + B ]

Our second key

P1,m = EC [ HMACL (P0,C0,i) ] + EC [ P0 ] = 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).

Captura12

 

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

Captura3

 

Modulo N addition is a reversible operation. If you know the result (S1,m) and one of the operands you can obtain the other operand. So if you know S1,m and C0, they you can calculate S0. 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 C0, then he can calculate all the IR and  IL iterations, as P0 and i are public and known. All children chain codes would be exfiltrated as well. If by some unfortunate mistake one of the S1,m is exfiltrated too, then S0 could be calculated. Disaster ensues. Exfiltration of S1,m (or any child private keys) should not put S0 (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

2 pensamientos en “Key Derivation in Bitcoin Wallets as defined in BIP-0032

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

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

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s