User Stories
Code Generation
Entropy
We want to divorce the recovery code from the actual symmetric key that is derived from the recovery code, for two reasons:
- There is no need to force the user to write down the long symmetric key
- Every cipher needs a different key length, and there is no reason to tie the recovery code length to any particular cipher.
Keys for symmetric encryption do not need to be longer than 128 bits. Even if a computer could do trillions of attacks a second, and you had a million of these computers, it would still take a long time to exhaust the potential key space by brute force.
- possibilities = 2**128
- tries_per_second = 1e6 * 1e12 (million computers that could make a trillion attempts a second)
- 10 trillion years before the key space will be exhausted (possibilities / tries_per_second / years_in_seconds)
If we wanted to force users to have 128 bits in their recovery code:
- a hex code would require 32 characters
- an alphanumeric code would require 22 characters (e.g. Log2(63**22) = 131)
Both of those are higher than we would like. Typically, no one bothers with making users write down the raw 128 symmetric key because there is no need. Instead, a user is given a shorter key that is then passed through a key stretching algorithm or Key Derivation Function (KDF) to achieve the same effect at a lower entropy. This works really well so long as the code is actually random. If it is not random, like a user chosen password, then obviously there are ways to shortcut the brute force attack process.
Lets suppose that we want to use a key stretching algorithm to shorten the recovery code but retain the exact same security properties as a raw 128 bit recovery code. Hypothetically, then, we would want some function that ensures that the time to try all the possibilities of the short code is not substantially less than the time to try all the possibilities in a 128 bit code.
One problem is that the computation required to test if a given 128 bit symmetric key will decrypt a given block is not comparable to the computation required in a key stretching algorithm. They are apples and oranges. But lets try to come up with some comparison anyway.
- Intel's AES-NI instruction set for CPU-based AES performs one AES round in 2 clock cycles, and AES128 requires 10 rounds.
Notes:
Will GPU-based block ciphers greatly overtake the speed specialized instructions sets for CPUs? In other words, perhaps the comparison here is faulty because eventually GPUs will be able to decrypt a block of AES128 at an order of magnitude cheaper than current CPU approaches. GPUs now have integer and bitwise operations needed for block ciphers, so this is a possibility. According to this, GPU-based approaches are not much faster, however: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch36.html. This company claims to have a GPU-based approach that is much faster: http://gkrypt.com/.