K-of-M Private Key Generation and Backup in Bitcoin Wallets.

Introduction

You may already guessed it, one of our main interests at ‘privatekeys.org’ and ‘privatekeys.biz’ is precisely, well, private keys. As mentioned in a previous article of mine, our bitcoin wallets contain the most important piece of information when it comes to our cryptocurrency: the private keys that can unlock the UTXOs that were locked to the corresponding public keys and public key hashes. Please allow me to quote myself once again “Your (private) keys, then your bitcoins. Not your (private) keys, then I’m sorry pal, but not your bitcoins”.

Bitcoin community has some creative ways to protect private keys and the utxos, let me mention them here, and then we will propose a way to better protect our private keys backups.

Hardware Wallets

First of all the bitcoin community has produced secured hardware private key holders – called hardware wallets – where we can keep our private keys safe from the prying eyes of hackers and thieves. Calling them a wallet is a misnomer, (they contain keys but not coins, as coins live in the block chain so they should be called hardware keyrings) but we can live with that. In any case, these wallets usually come in the shape of specialized hardened hardware that can sign bitcoin transactions without exposing the private key. Generating the transaction itself is usually done somewhere else (a computer program) and the communication between them needs to be fluid, so that

the computer program can ask the wallet which public keys owns,
also check the balance with the blockchain,
generate a transaction according to the user input,
send it to the wallet to sign,
the wallet signs the transaction, usually showing the details in a built-in display to make sure that the computer program is not asking us to sign anything different
the computer program then receives the signed transaction from the wallet
and sends it to the miners to have it mined during next block

Much of the security in this procedure resides in the wallet itself and its capability to protect the private key. Hardware wallets usually implement a two-factor authentication mechanism, where the owner:

needs physical access to the wallet to approve the signature
a pincode (i.e. a password) needs to be inserted on the wallet itself to have access to it

Password and physical token, a classical two-factor authentication mechanism. However, this implementation has some drawbacks especially important under the bitcoin light

Due to the decentralized nature of Bitcoin, and the current anonymous character of who own which keys, there is no mechanism to undo mined transactions, apart from forcing a chain fork from an earlier point. This makes the access to our private keys especially sensitive, as there is no bank representative or local authority to which we could complain to get our money back.
The pincodes that represent our second access factor are usually weaker than the key they are trying to protect. Bitcoin private keys are 256 bits long, and a similar level of entropy in digits requires a very large number of digits to remember. We may be better just remembering the key itself.

Overall, hardware wallets perform a reasonable good job protecting our private keys. However, hardware wallet are physical devices that are susceptible to break. Unless we can remember all of our 256 bits by heart, we will need a backup of our private key.

There are mechanisms to encode private keys in dictionary words that they can used as a backup, but then we need to protect our dictionary words as much as we protect our wallet. How do we protect the words? Unless we find an equivalent way to protect the 24 words [i] – equivalent in security to having the private key stored in the wallet – we will see the utility of a wallet reduced to just a secure hardware to sign, but not a secure place to store our private key.

As of today, with hardware wallets there is always a compromise between availability (reinforced by a backup) and security. In other words, as of today we typically need to sacrifice some of its security for the availability.

Multi signature Schemas

Other alternative to protect private keys has been to dilute the responsibility between several individuals. Let me explain with an example: imagine that the transactions would need to be approved by a quorum of say K of a total of M potential signers (where K < M), then each member responsibility decreases, as its only signature would not be enough to approve the transaction (another K-1 members would also be needed). Henceforth the protection of each individual private key becomes less critical and we can happily store them in wallets and write down the 24 words in post-it papers stuck to our computer screens.

Bitcoin Script scripting language permits creative multi-signature schemas, but the main barrier these days is to have computer programs that can create and handle multi-signature transactions, as well as wallets that can bring individual signatures into a multi-signature transaction.

There is also research on how to implement multi-signature capabilities in the DSA/ECDSA signature itself [ii]. This would remove the complexity from the Script language and the program that generates the signature and would place it on the cryptography, i.e. on the wallet that would need to know how to calculate a partial signature. Nevertheless, as far as I know this has not been implemented in Bitcoin.

Applying K-of-M schema to private key generation in Bitcoin wallets

I personally think that the fastest way to improve the security of the backups of our private keys while at the same time reinforcing the availability of our private keys can be to implement a K-of-M schema for the generation and protection of a backup our private keys. The remaining of this article describe a proposal on how this could be implemented

Requirements for the solution

I will describe a key generation mechanism that is aimed at individual owners of bitcoins, where

Their private key will be divided on a K-of-M schema using Shamir Secret sharing protocol [iii]
It will give the capability to one individual (presumably the owner of the bitcoins) to be required to unlock the bitcoins, while the rest of the users would be optional

Bitcoin owners will have

Their private key securely generated stored in their wallets
The wallet, at key generation time, will also
- Split the private key into two halves, both needed to reconstruct the private key
- One half will be kept by the owner of the keys, encoded into 24 words by the wallet, and saved outside the wallet
- The other half will be splitted by the wallet into a K-of-M schema, where the bitcoin owner should be able to choose both K and M
- Each of the M pieces would then be encoded into 24 words by the wallet.
- The bitcoin owner will distribute each set of 24 words to M people of his choice

The rationale behind this implementation lays in that the bitcoin owner would be required to bring his half of the private key but he would also need K out of M of other key holders to reconstruct the other half and finally reconstruct the complete private key. This relieves the pressure on the confidentiality of the key backups. If the owner half of the private key is compromised – or any of the M shares – the private key remains private.

At the same time, the owner and only the owner remains in full control of the private key both for its usage – stored at the hardware key – and its backup. M key administrators are not the owners of the bitcoins protected so they must not and cannot reconstruct the key themselves, as they. They can only contribute to the reconstruction, or refuse to help, but they cannot rebuild the key by themselves.

The protocol

The new private key generation protocol takes the following assumptions

We will distinguish between “A participant” and “B participant”
- “A Participant” is considered the owner of the bitcoins protected by the private key. It will have a backup of half of the private key. He/She will be required to reconstruct the whole private key, however he/she needs as well a quorum of K-of-M “B Participants”
- “B Participant” is considered someone trusted by “A Participant” but not the owner of the protected bitcoins. A quorum of K out of M “B Participants” will be required to reconstruct the second half of the private key

The new private key generation protocol takes the following steps

Use a Deterministic Random Bit Generator to generate two sets of 256 bits, that we will call “Random Sequence A” and “Random Sequence B”.
- Each of these sequences need to be lower than N (2**256 – 2**32 – 977)
- Whether we use them directly, or if we apply sha256 on them (and check the <N limit) would be an implementation choice. In our example we will use Python’s Bitcoin code that performs the sha256
Add these two random bit sequences, modulo N, to obtain the private key that will be securely stored in the wallet
- Again the private key will need to be lower than N
- Again it could be sha256 hashed and retain the hash as private key

For Random Sequence A, we perform BIP-0039 transformation. The resulting 24 words will be assigned to user A, presumably the owner of the bitcoins protected by that private key
For Random Sequence B we apply a Shamir Shared Secret algorithm to divide it into M parts, K of which would be required to reconstruct “Random Sequence B”
We apply BIP-0039 to each M_i The resulting 24 words for every M_i share will be distributed to “B participants”

Shamir Secret Sharing Algorithm

The mathematical description can be found here [iv] or in its Wikipedia page, mentioned earlier.

The basis of its working, in our specific case, would be as follows

For encoding

Let the end user choose a combination of K and M. For practical reasons our implementation will force that M would remain equal or below 12.
Build a polynomial of degree K-1 in the form

f(x) = a₀ + a₁x + a₂x² + … a_K-1x^K-1

Where

f(0)= a₀ is our “Random Sequence B”
a₁ … a_K-1 are K-1 random generated numbers, modulo N

Calculate M points of f(x), for x=1 until x=M. We will get
- f(1) = (a₀ + a₁ + … + a_K-1) (mod N)
- …
- f(M) = (a₀ + a₁*M + … a_K-1 * (M)^K-1 ) (mod N)

Encode f(1) … f(M) with BIP-0039 and distribute the sets of 24 words to “B Participants”

For decoding

1.- Calculate using Lagrange Polynomials (originally here [v] also explained here [vi])

Example code in Python

I have implemented a proof of concept script showing the whole process, up to BIP-0039 (which is not shown). Most of the code was adapted from here [vii]

Flowchart

Code

It is not optimized for speed but for – hopefully – clarity.

Run example

Applying K-of-M protocol to existing private key backups

If a backup of the private key already exists, in the form of a list of 24 words, the process to obtain “Random Sequence A” and “Random Sequence B” would be

Reconstruct the private key from the 24 words list
Use a Deterministic Random Bit Generator to generate a set of 256 bits, that we will call “Random Sequence A”
Substract “Random Sequence A” from the private key, modulo N, thus obtaining “Random Sequence B”
Apply steps 3 through 5 from previous algorithm
Securely discard the original 24 words

Conclusion

We have presented a way to improve the security of the backup of a private key for personal users. By splitting the key in shares that can be distributed to different users, and making some of those optional and other compulsory for key reconstruction, we have achieved a secured way to backup a private key, while ensuring the owner remains in control and implementing redundancy and fault tolerance to the system.

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

[i] https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki

[ii] https://eprint.iacr.org/2016/013.pdf

[iii] https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

[iv] https://dl.acm.org/citation.cfm?doid=359168.359176

[v] http://rstl.royalsocietypublishing.org/content/69/59

[vi] https://www.encyclopediaofmath.org/index.php/Lagrange_interpolation_formula

[vii] https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing#Python_example