8
$\begingroup$

Assuming I already have a 256-key (32 char password) for AES encryption, comprised of random alpha-numeric characters and punctuation (95 possible ascii chars), generated by a decent PRNG, is there any reason to use a KDF to convert this into another key of the same length? Is a derivative hash in some way stronger?

Obviously if a password was shorter than the intended key-length, or if the password was predictable (ie, memorizable), I can see how a KDF would be useful. But given the above circumstances, I reason that a KDF (like BCrypt of PBKDF2) would actually reduce the character-range of the key (to 64 chars in bcrypt, and 16 chars in PBKDF2), effectively increasing the chance of a brute-force attack (however unlikely). Any insights?

$\endgroup$
3
  • $\begingroup$ Your password has only $95^{32} \approx 2^{210}$ possible values, which is quite smaller than $256^{32} = 2^{256}$, which are all the possibilities of a 256-bit key, but still way above the range of a brute-force attack. I'm not sure if there might be any weaknesses due to the fact that all upper bits of all the key bytes are zero, so I would still throw at least a fast salted hash on it before using it as a key. $\endgroup$ Dec 21, 2012 at 8:37
  • $\begingroup$ As mentioned by @StephenTouset, wouldn't hashing (in this case) reduce the keyspace, therefore increasing the possibily of a brute-force attack? Assuming the output of the hash is hexadecimal, the keyspace would be reduced to 16^32, as opposed to the original 95^32. This is assuming the original key is 32 chars, comprised of 95 possible ascii chars, generated by a CSPRNG. Forgive me if I'm mistaken - I'm on a pretty steep learning curve. $\endgroup$
    – hunter
    Dec 21, 2012 at 17:19
  • $\begingroup$ You should use a hash function fitting to the later use of your "password". For an AES-256 key, use a hash function with output size of 256 bits, like SHA-256 or SHA-512/256. Don't use a hash function with only 128 bit output (which would be 32 hex digits). There will be some collisions, but this will not really help any attacker. $\endgroup$ Dec 21, 2012 at 18:44

3 Answers 3

17
$\begingroup$

The point of a KDF is to take a low-entropy input and significantly increase the amount of computational power (and thus time or cost) it requires to brute-force, hopefully to a level on-par with a truly random value.

If you're already using a 256-bit value generated from a CSPRNG, there is no need to use a KDF.

In fact, using a KDF can only reduce the security of your keys. If there are any collisions in your hash function for 256-bit inputs, the number of possible KDF-generated keys will be fewer than the number of inputs, and you have a smaller possible keyspace. On the other hand, it can't possibly increase security, because if you're using a KDF to expensively turn 256-bit keys into different 256-bit keys, attackers have no need to go through the KDF. They can just enumerate the 256-bit keyspace in the first place.

$\endgroup$
2
  • 1
    $\begingroup$ this is exactly the answer I was looking for - very concise - thank you. $\endgroup$
    – hunter
    Dec 20, 2012 at 21:58
  • 1
    $\begingroup$ I should slightly clarify that running this key through a KDF won't meaningfully impact the security of your keys. My point in the last paragraph is that a KDF can only mathematically reduce or maintain constant entropy, but never increase it. Any non-pathological KDF is exceedingly unlikely to reduce the entropy of your keys by more than an infinitesimal amount. $\endgroup$ Feb 20, 2014 at 19:14
4
$\begingroup$

Take the following points into consideration:

  • A 32 character password composed of 95 ASCII characters only has $\log95^{32}\approx 210$ bits.

    As long as there are no quantum computers (which would reduce the key strength to 105 bits), that's not a practical problem.

  • Not taking the previous point into account, if your password really gets generated randomly, there's no need for a KDF.

    However, if the password is user-provided, it usually has low entropy and a good KDF can make a brute-force attack much more difficult.

  • If only 192 bits of security are required, AES-192 could be used.

    Although a KDF will take some time to derive the key, AES-192 w/KDF will still be faster for large messages.

  • Bcrypt was originally designed as a deliberately slow has function, not a key derivation function. This explains the "limited" output (448 bits).

  • PBKDF2 can generate keys of arbitrary length.

  • The fact that specific implementations of Bcrypt and PBKDF2 use Base64 and hexadecimal encoding doesn't mean that the algorithms are limited to that.

    If the possible encodings of the KDF (output) and the cipher (key input) do not match, there's always conversion.

  • Memory-intensive KDFs such as Scrypt use large amounts of memory in addition to processor powers, making parallelization more expensive.

$\endgroup$
4
  • $\begingroup$ I mentioned that using a KDF would reduce the character-range of the key, not the length. The output of PBKDF2 is hexadecimal - 16 possible chars for a 32-byte key = 16^32, Bcrypt's output is case-sensitive alphanumeric + './', (64^32). So, it would seem to me that a 32 char randomly-generated password comprised of 95 possible ascii characters would be the most secure (95^32). So if 95^32 'only' equates to 210 bits of entropy - how can 256 bits be achieved, when the key is limited to 32 chars? Regarding Bcrypt - as far as I know it's a KDF, regardless of it's original design. $\endgroup$
    – hunter
    Dec 20, 2012 at 18:51
  • $\begingroup$ The output of a PBKDF2 implementation may be hexadecimal, but you can convert that output to whatever you want. Although, there are AES implementations that accept hexadecimal keys. $\endgroup$
    – Dennis
    Dec 20, 2012 at 19:04
  • $\begingroup$ That's a fair point - I guess the output could easily be encoded as Base64 also. As far as I know - most AES implementations will accept a key in any format - as long it conforms to the standard 128, 192 and 256 bit lengths. $\endgroup$
    – hunter
    Dec 20, 2012 at 19:15
  • 2
    $\begingroup$ @hunter When using AES-256, you should use a key (pseudo-)randomly selected between all possible 256-bit strings. It might be encoded as 32 bytes, 64 hex digits, a 44 character base64 string or 39 characters of your 95-char-alphabet, it doesn't matter. For using them as a key, you'll most likely have to convert them to the 32-byte form. $\endgroup$ Dec 21, 2012 at 18:51
2
$\begingroup$

I don't have reputation enough to comment but felt this was important to add as I detected a misunderstanding in several comments, so I ended up writing an answer.

It was suggested that because a KDF (Key Derivation Function) would return a hexadecimal result it would limit the entropy as it will only allow 16 different characters in the derived key.

This is a misunderstanding.

The result from a KDF does not have to be represented as a hexadecimal ASCII-string. It can be binary or if represented as hexadecimal it can be converted to binary.

Assuming a 32-char random password, you can use a KDF to generate a 64-char hexadecimal key and then convert that to binary.

To answer the original question, a KDF can help safeguard against vulnerabilities in your password generation code even if the resulting key length is the same. Especially if the KDF uses a salt.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.