... | ... | @@ -22,25 +22,18 @@ 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.
|
|
|
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.
|
|
|
|
|
|
What about KDF using sha256?
|
|
|
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.
|
|
|
|
|
|
* A typical unix crypt-style sha256 password digest is 5000 rounds of sha256 (with salt). PBKDF2-HMAC-SHA256 typically uses a similar number of rounds (although it is configurable).
|
|
|
* Off the shelf products like Brutalis can do 23 billion SHA256 hashes per second
|
|
|
* Brutalis are kind of cheap, so lets assume an adversary has 10 of them. This makes their attempt_rate = 46e6/second. e.g. `23e9 * 10 / 5000`
|
|
|
* There are 3.37e20 seconds in 10 trillion years. e.g. `10.7e12 * 365 * 24 * 60 * 60`
|
|
|
* You could make 1.55e28 attempts in that time. e.g. `46e6 * 3.37e20`, or 93.64 bits of entropy
|
|
|
* It would require an alphanumeric code of length 16 to achieve similar entropy. e.g. `log2(63**16)`
|
|
|
* So, to achieve the same security with a short code as you get with a raw 128 key, against this hypothetical adversary, it would require recovery codes with 16 random digits. If we wanted to make it case insensitive and remove digits that are easily confused (e.g. zero and 'o'), it would require 20 digits.
|
|
|
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.
|
|
|
|
|
|
This assumes there is a salt. In other words, the salt is stored on disk in the clear and is available to anyone attempting recovery for a particular user (after authenticating using the recovery code, with a different salt).
|
|
|
* Intel's AES-NI instruction set for CPU-based AES performs one AES round in 2 clock cycles, and AES128 requires 10 rounds.
|
|
|
|
|
|
This rough estimation does not include the time to attempt to decrypt once the symmetric key is derived, but it gives a ballpark estimate of how short you can make the code without compromising any resistance to brute force attacks.
|
|
|
|
|
|
A reduction in size from 22 characters to 16 characters does not seem so beneficial.
|
|
|
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/.
|
|
|
|
|
|
What about a KDF using argon2?
|
|
|
|
|
|
* Lets assume the attacker has 1000x the CPU power, but limited memory.
|
|
|
|