The Recovery Phrase, Fail-Safe Or Not?

By Aat de Kwaasteniet on ALTCOIN MAGAZINE

Aat de Kwaasteniet

Published in

The Dark Side

6 min readMay 26, 2019

Dutch version here

Introduction

The serious cryptocurrencies use a backup technique in their wallets that we call the “recovery phrase”. Is this backup technique safe and reliable? In this article, we will discuss this technique in more detail.

History

In the early days of cryptocurrencies, and still now with some current cryptocurrencies, a lost digital wallet, through theft or technical malpractice, could only be recovered if you had made regular backups of the wallet. The first generation wallets created a “pool” of 100 random “private keys / public keys” sets and these were stored in a file called “wallet.dat”. Every time an amount was sent from the wallet, or a new recipient address was chosen, a new set of a private key/public key was used and when the Pool of 100 keys sets became empty, the wallet generated a new additional pool of 100 keys sets.
So it was important to make regular backups of the file “wallet.dat”, a job that was often forgotten and therefore caused a lot of suffering when someone had to restore his wallet and found out that the backup was too old and that the last transactions were not included.

Deterministic Wallet

Later, the deterministic wallet came into use and it was sufficient to make a backup once during installation because the deterministic wallet created a random “master seed” from which all subsequent private keys / public keys could be derived. So saving the master seed was enough to restore the entire history of transactions in a wallet.
Even later, the “master seed” technique was improved by not allowing the “master seed” to consist of an enormous long string of numbers but a more useful, readable way for people to use a number of words that formed the so-called recovery phrase. Other names are recovery sentence, mnemonic sentence and so on.

The Recovery Phrase Dissected

A recovery phrase can consist of 12, 15, 18, 21 or 24 words. All words are written in lower case and are chosen from a standardized list of 2048 words. This list has been compiled with care and all words meet the following conditions:

the wordlist has been drawn up in such a way that it is sufficient to type the first four letters in order to unambiguously identify the word.
word pairs such as “build” and “built”, “woman” and “women”, or “quick” and “quickly” not only make it difficult to remember the sentence but are also more prone to error and more difficult to guess.
The wordlist may contain native characters, but they must be encoded in UTF-8 using Normalization Formatibility Decomposition (NFKD).

Wordlists have been compiled for several main languages, such as:

For the technically interested:
Each word has been given a number from 0 to 2047 and all these numbers in a row give the digital representation of the “master seed” from which all sets of private / public keys are generated. A number between 0–2047 can be represented by 11 bits (2¹¹ = 2048). If we assume a recovery sentence of 12 words, the “master seed” is 12 x 11 bits = 132 bits long. Because the last word contains a checksum in the last 4 bits, the effective length of the “master seed” is 128 bits. According to the agreement, the length of the seed should be a multiple of 32 bits and should be between 128 and 256 bits in length. The size of the checksum is the useful length of the master seed divided by 32. This leads to the following table:

Operation

A wallet of a cryptocurrency generates a random recovery phrase during installation and presents it to the person who installs the wallet. This person has to save the recovery phrase neatly and carefully. With this recovery phrase as “master seed”, the wallet can calculate private keys and associated public keys using a fixed calculation method.
Because the recovery phrase is unique to a wallet, the entire wallet can always be restored in case of a disaster by entering the recovery phrase so that the wallet software can calculate the corresponding private keys and public keys again. So if the original computer breaks down or is stolen, the wallet can always be restored to another computer using the recovery phrase. It is not possible to point out with sufficient emphasis that the recovery phrase must be kept carefully because without a recovery phrase the wallet can never be restored again.
The recovery phrase must, of course, be entered in the correct order and the words must appear in the list and the last word contains a checksum so that it can be checked at the time of entry whether the phrase is valid. Therefore, not every randomly selected set of words gives a valid recovery phrase.

Safety-reliability

So each wallet has its own unique healing spirit. But what happens when a million people have such a wallet or even a billion people? Are all recovery phrases also unique?
Many people believe that with just twelve words it is easy to “guess” the recovery phrase. You mess around with the words and before you know it you have a recovery phrase from one of the billion existing wallets and you can empty that wallet.

But is that really the case?

We can calculate that a recovery phrase consisting of twelve words from a list of 2048 words has a chance of 1 in 2048¹² to arise.
This is not entirely true because not all combinations of words are permissible due to the presence of the checksum. The last word is therefore not free to choose but depends on the previous 11 words. If we look at bit-level of the “master seed” we can say that we have a chance of 1 in 2¹²⁸ to compose a recovery phrase that is equal to your unique recovery sentence. 2¹²⁸ doesn’t seem like much but when we write down the number we get an impression of the size of the number.
2¹²⁸ = 340.282.366.920.938.000.000.000.000.000.000.000.000

But if there are a billion wallets now? The chance is a billion times greater! Even then the chance is still minimal. Namely 9 zeros less.
1 out of 340.282.366.920.938.000.000.000.000.000

If we consider that we have to test every attempt and we have to go through the blockchain for every attempt to see if there is anything in a particular wallet belonging to that recovery phrase. It takes time.
Let’s say that we have a super-fast computer that scans the entire blockchain within 1 second and checks if we hit it, then we can calculate that we are busy for 10,790,283,070,806,000,000,000,000 years to hit one of the billion wallets that are in use.

But if we get quantum computers, then what? Maybe those computers are a factor of a billion faster?
Well, then it only takes 10,790,283,070,806 years to find a wallet that is in use.

I hope that the mathematical examples will convince you of the practical impossibility that a wallet can be cracked by “brute force” or “guessing” the recovery phrase.