# How should I implement a secure recovery of encryption?

I want to create a system to host as securely as possible encrypted data in a way that not even the system can know the content of the data, but that it could be recovered.

I would like to know how is it that other systems implement the use of a multiword recovery passphrase, like some bitcoin wallets for example, where the user defines its password, but also gets a set of words to be written and saved securely in case the password is forgotten.

Is this an additional key so that they are 2 possible keys to decrypt the data? or just another form of the same key? What algorithms support this?

I would appreciate any hint or link so I can research deeper.

Thanks

• Usually: The recovery key is a second (asymmetric) key (the words may be the seed for a PRNG used to generate it) used to encipher the symmetric bulk data key. – SEJPM Mar 30 '16 at 12:49

## 2 Answers

Usually, you have one important key (the master key).
This can be your private bitcoin key, your password database key, the drive encryption key, or really whatever.
Normally you encrypt this key, because you want to change it as infrequently as possible and encrypt it using some user input (e.g. a password) because of costly re-setups of the system.

You now have two ways to implement backups (easily):

1. Give the user the key and tell them to store it properly (probably ends bad)
2. Give the user another means of authentication (e.g. a password) and store a copy of the master key that is protected using this mean next to your standard encrypted key.

Method 1:
The advantage of the first way is that it probably is a full backup of the header and thus you can still recover data if the header is corrupted.
The disadvantage of course is that you have to trust the user to store extremely sensitive data of course and this data usually is highly unfriendly to humans, being a random chunk of bytes.
The usual solution to this is to follow the second approach and let the user do backups of the header.

Method 2:
This way you store two copies of your encrypted master key: One for normal operation and one for the backup case. The backup material then allows for access to the data via this encrypted backup copy of the key. Usually you'd also do a backup of the entire header containing this key to prevent data loss.

Finally there's one last method, which is much more difficult to use and may make securing a system very difficult: deterministic key generation. This way you generate your master key in a deterministic way using a password and the same password input will always yield the same key. The advantage being of course that header backups are not really required and that all it takes is a single password. The disadvantage is of course that if the user choses a bad password (if this is an option) that brute-forcing the key via this method probably is a viable attack vector.

Your description of "a set of words" is rather vague and I'm not sure what it means. Since you don't say what those systems do, you are in fact asking "I'm not telling you what these systems do, but how do they do it?"

However, one other way of implementing recovery keys is to take your master key and split it into $N$ pieces, such that any $M$ of them will reconstruct the master key but any $M-1$ of them are insufficient. That does give you the possibility of saving the key pieces in such a way that neither the loss nor the theft of one of them will be a disaster. They can be stored in different places or even given to different people.

This Wikipedia article covers the subject in general. However, here are two simple examples:

1. Think of an $n$th-degree polynomial $f(x)$, randomly chosen, such that $f(0)$ is the value of your master key. The pieces are $f(1)$, $f(2)$, $f(3)$,... $f(N)$. Any $n+1$ pieces will allow you to deduce $f(0)$, but any $n$ pieces won't. This is the first such scheme proposed, originally at Crypto '81. It may well have weaknesses.

2. Consider your master key as a point $P$ in $3$-dimensional space. The pieces are random planes through $P$. One of them tells you nothing; two of them tell you nothing except a line that $P$ is on; three of them tell you $P$. And four of them either confirm $P$ or tell you that one of the planes must be a fake. If those numbers aren't enough, use $n$-dimensional space instead.