Emergency Key Recovery Without Third Parties

[page last modified September 22, 1996]

In order to recover a small secret (such as a cryptographic key), one can use Shamir Secret Sharing. In this process, the small secret is split into N shares, K of which are needed to recover the secret. If someone assembles any (K-1) of these shares, he or she can learn nothing about the secret, according to Shamir's original scheme.

The next step is to distribute these N shares among N trusted friends, to be returned to you in the event that you have lost normal access to the small secret. If these friends do not know of one another, then there is little chance that they can collude to obtain your small secret behind your back. Similarly, if no intruder can find a list of these friends in your possession, then he is unlikely to track them down. However, that requires that you keep the list in your head. If you forget some of them, as long as you remember at least K of them, you can recover your secret.

With roughly the same amount of mental effort on your part, you can keep these secret shares in your own hands, and thus avoid the possibility of collusion among your friends.

To do this, each share needs to be enciphered by a conventional algorithm. In the Shamir scheme, each share looks like a purely random number and it is important that this remain true for the shares you use, prior to encipherment. That is, a trial decipherment of one share must not reveal whether the cryptographic key was correct.

To obtain the cryptographic keys for enciphering the N shares, you need to compose N questions of yourself -- going into your memory to find things which happened to you or which you thought, probably long ago (to make sure they remain remembered), but which you have never shared with anyone (possibly because the answer would be embarrassing, or maybe because it is too trivial).

For example, "What was the name of the first person on whom I had a crush?" or "What was the first car (year, make, model and color) I wished I could have owned?". The questions should be as generic and even misleading as possible.

Each share is then attached to one such question and the answer to that question is cryptographically hashed to obtain a conventional cryptographic key for enciphering that share. The question and enciphered share remain stored together. It is important to store copies of the set of questions and enciphered shares in multiple locations (perhaps with friends, perhaps in data storage provided by ISPs) so that physical loss of the data is prevented.

Each answer to such a question is relatively easy to guess. That means that it has very low entropy. For example, a person's first name has only about 8 bits of entropy. Car makes and models have only 2 to 4 bits of entropy -- especially if one is naming cars desirable to a teenager.

However, because there is no redundancy inside a secret share, there is no way for an attacker to tell if he has the correct answer until he acquires at least K correct answers. Therefore, if each answer has entropy E, the attacker must correctly guess T=(EK) bits of answers. If T exceeds 90 bits or so, then the user is reasonably secure from answer-guessing attacks.

From that relation, the user can choose K. To choose N, the user needs to evaluate the possibility of guessing values wrong. In particular, N should be large enough that the probability of randomly selecting a correct K answers is relatively high, given the user's own knowledge of the answers and very low given an attacker's knowledge.

- Carl Ellison

[This material was presented during a rump session talk at CRYPTO '96.]