davidwr's Journal: How to store your private key "in the cloud" safely

Storing a private key "in the cloud":

Key is K1. Key is thousands of seemingly-random bits, probably based on a pair of 1024-bit-or-larger prime numbers. You typically store K1 on your computer using a good encryption algorithm. Your password to decrypt the key is P1. P1 is typically tens of characters. Decrypting K1 with P1 is a fast (in human-time-scale) operation, under a second.

Although K1 is typically used to encrypt or decrypt data, for the purposes of this document, K1 is the thing to be encrypted. It will not be used to encrypt or decrypt anything.

Problem:

How to safely store a backup of key K1 online such that the end user can access it from any device if he has both the password P1 and something else that is not mathematically related to K1.

Method 1, the "something else" is a one-time pad:

Create a random one-time pad, R1, which is the same size as K1.
"Encrypt" (XOR) K1 with R1 then encrypt both with P1, creating the safe copy S1. Store S1 online.
Print off a copy of R1 such that it can be easily photographed and re-constructed. Store R1 or an encrypted version of it in a safe place, such as a safe-deposit box or distributed in parts to trusted secret-keepers.
Without R1 it is provably impossible to extract K1 from S1, so S1 is "safe."
R1 by itself is useless.
R1 with S1 constitutes a compromise but it will mean the attacker has to either guess P1 or exhaustively search for it.

If the person loses their local copy of K1, they can use R1, P1, and S1 to reconstruct K1.

Method 2, create a file S2 which from which is computationally hard to extract K1 without P1, acceptably moderately difficult to extract K1 with P1 and no other information, and easy to extract K1 with P1 and "something else" not related to K1.

For example, create a one-time pad R2 which consists of P1 combined with some random-ish filler-number B2 whose size is dependent on how "moderately difficult" it can be to extract K1 given only P1.

If this pad R2 is at least as long as K1, proceed on as in Method 1: "Encrypting" (XOR) K1 with R2 and encrypting both with P1, creating a safe copy S2. As neither P1 nor B2 are known or predicatble, S2 is safe.
The time to recover K from S2 with only P1 will be the time it takes to go through all (or, on average, half) of the possible values of B2. Since the length of B2 was chosen in advance based on how hard this decription should be, K1 will be recoverable in a predicable, acceptable amount of time. With B2 and P1 recovering K1 from S2 is quick.

If the pad R2 is not as long as K1, one option is to re-use the one-time pad and as such will not satisfy the goal o being "comptationally hard to extract K1 without P1," but it may be good enough for some applications.

A different solution is to encrypt K1 with P1 (the file that is normally stored on the person's local computer will qualify) then encrypt the result with either B2 or some combination of P1 and B2 to create S2. The difficulty of extracting K1 from S2 with only P1 depends on the time it takes to go through all (or, on average, half) of the possible values of B2. Depending on the lenghts of P1 and B2 and the encryption algorithms used, this may not be safe enough. With B2 and P1, recovery is quick.

This method has the advantage that the "something else," B2 in this case, need not be kept at all.

A typical scenario where the "B2" method would be preferred over the "R1" method is where it is acceptable if key K1 becomes unavailable for an extended period of time in exchange for a zero-risk that an adversary will acquire or discover R1.