How to generate backup key for PBKD functions?

Question

I would like to encrypt some files using AES, Ill derive key from password using some standard PBKD function and use that as AES encryption key.

My question is, if user forgets the main password, then he has no input into PBKD function thus no way of getting the AES encryption key.

What algorithm/technique should I use to generate together with the key also a kind of "backup key", preferably a 16 digit number (so ~53 bit key) which can also be used to derrive correct AES encryption key? User would be encouraged to write down this key on paper and save it on a safe place in case main pwd is forgotten.

My idea was to actually encrypt the password used by client using a 53 key, and when needed decrypt it and let user replace or view his lost password, but this would severely compromise the security, as itd lower the difficulty of attack to just getting the 53bit backup key.

So it looks to me that I have to use at least 128bit random key (same strength as the main derived key), which I can convert to ~38digit decimal number or 32digit hexadec number. This is way longer than Id like.

Now while using a 53bit key as a backup key may seem as a crypto joke, when we actually consider that an average password would be 8 digit alphanum string, using lowercase, uppercase, numbers and something like 10 special chars (if only users followed at least these guidelines...), this gives us about 72^8 ~~ 2^50 options, i.e. the output key from PBKD func is an equivalent to 50bit key. a 128bit key would require PBKD input to be at least 21 of these mixed chars and I dare guess users dont usually use such long passwords.

So what are your suggestions and comments on the scenario I described? Thanks.

Answer 1

The other answer's suggestion of encrypting the file-encryption key twice is good, so I will only answer the part about backup key size.

Now while using a 53bit key as a backup key may seem as a crypto joke, when we actually consider that an average password would be [...]

If you go with the average password complexity, those users who do choose a strong password will have a false sense of security. If you go that way, you cannot claim e.g. 128-bit security.

Since the key in question is a backup key, you have the option of making using it very slow. With a typical password hashing function that means also making encryption slow, however, which may not be acceptable. You could instead use what is sometimes called "key strengthening" which essentially amounts to dropping bits of a random key. One way you could do that:

1. Generate a random 128-bit AES key $k$ and random salt $s$.
2. Store $s, H(s||k)$ in the file.
3. Truncate $k$ to the initial $b$ bits $k_b$ and store that as backup key.
4. When using the backup key, iterate through all $128-b$ bit values $x$, calculate $H(s||k_b||x)$ and compare to the stored hash. Stop when you find a match and thus $k = k_b||x$.

Encryption is fast. Decryption takes an expected $2^{127-b}$ hash evaluations. With typical speeds of at least 50 million hashes per second on a modern CPU (SHA-256 on my 4-core), you could drop 30 bits ($b = 97$) and always decrypt in <30s.

You could additionally use a smaller actual key-space by generating a shorter $k$ and using e.g. $H(k)$ as the actual key. For example, with 64-bit backup keys (16 hex characters) and 32 bits of key strengthening (a minute or two of CPU time when decrypting), you would have 96-bit security.

Answer 2

This kind of key management problem is a big reason why encryption is not more widely used for everyday data.

I see a single easy way to do this, I think it is similar to the way disk encryption systems work, and it may not work for your uses.

For each file, a random key $kf$ is generated. 2 copies of the key are encrypted, one with a key derived from the password ($kp$), the other with a key derived from the backup code ($kb$). The original key is used to encrypt the file, and the 2 encrypted copies of this key are stored with the file.

$EncFile = E_{kp}(kf) \ || \ E_{kb}(kf) \ || \ E_{kf}(File)$

This can also be done on a per user basis. The encrypted keys are not stored with each file, just one copy with a group of encrypted files, and backed up somewhere else.

This scheme allows decryption of the files using either the password or the backup code, and also allows the password to be changed without changing the backup code or reencrypting the files, only the encrypted file key is changed, which is the first few bytes of the encrypted file, or stored in a separate file. It also slows down brute force attacks slightly, thanks to the additional encryption operation.

The scheme would store the 2 encrypted keys with the encryption software, and decrypt the file key from the password when encrypting new files, so that the user or the software does not need to know the backup code. There should be some way of knowing that the file key is decrypted correctly before using it, here is one of many methods:

We have a 16B random plaintext block $P_r$, and a known hash of $E_{kf}(P_r)$. Once the password key is derived we generate:
$kt = D_{kp}(E_{kp}(kf))$
$ht = Hash(E_{kt}(P_r))$
Then $ht$ is compared to the known hash, a match means the password is correct. This may seem a little more complex than just comparing it against an encrypted copy of the block, but it eliminates a plaintext/ciphertext pair an attacker could use for key recovery attacks.