Key length and hash function in PBKDF2

Question

On this page:

http://www.ruby-doc.org/stdlib-2.0/libdoc/openssl/rdoc/OpenSSL/PKCS5.html

they make a statement that strikes me as rather weird:

Key Length

Specifies the length in bytes of the output that will be generated. Typically, the key length should be larger than or equal to the output length of the underlying digest function.

So if we take this seriously, if we are using SHA-512 (64 bytes), we should only obtain key sizes that are more than 64 bytes. This would mean that we cannot (or should not) obtain 32 byte keys for use with AES-256.

But according to this logic, we should instead opt for SHA-1 (20 bytes), since 32 bytes are now larger than the 20 bytes of SHA-1.

What am I missing?

Answer 1

The statement is weird, because it comes from a knee-jerk ritualistic reflex about key lengths.

The full text from the page is:

Specifies the length in bytes of the output that will be generated. Typically, the key length should be larger than or equal to the output length of the underlying digest function, otherwise an attacker could simply try to brute-force the key. According to PKCS#5, security is limited by the output length of the underlying digest function, i.e. security is not improved if a key length strictly larger than the digest output length is chosen. Therefore, when using PKCS5 for password storage, it suffices to store values equal to the digest output length, nothing is gained by storing larger values.

There's some confusion here, indeed. Let's see the details:

• PBKDF2 is a Key Derivation Function: its output can have a configurable length, and is meant to be a "key".

• Key for cryptography must not be too small, to avoid being inherently weak. For instance, a DES key, being 56-bit long (ok, 64 bits, but 8 bits are ignored, so 56 "real" bits). However, beyond about 100 bits, exhaustive search is so ludicrously expensive that it ceases to become a threat.

• Similarly, PBKDF2 can be "attacked" with an effort of cost 2ⁿ if the underlying hash function has an output of n bits. This is totally unfeasible even if using MD5 (128 bits are already enough for that). But, in a certain bureaucratic light, PBKDF2 has "strength n bits".

So the reasoning goes: if you use PBKDF2 to generate a key which is not of at least n bits, then your key is "weaker" than what PBKDF2 could have produced. Now it would be kind of stupid to refuse to generate a 128-bit key with PBKDF2/SHA-256 because SHA-256 offers "256-bit security". But it makes some kind of twisted sense, if seen through a procedural prism by a frustrated auditor who does not have a clue about what a key actually is.

Summary: ignore that weird passage of the doc. Use PBKDF2 with HMAC/SHA-256 or HMAC/SHA-512, whichever floats your boat (SHA-512 might be slightly stronger against attacker who use GPU as they are sold in early 2013, because current GPU are bad at doing 64-bit arithmetic). Generate the key length that you need for the algorithm at hand. 128 bits are anyway more than enough for symmetric keys.