Achieving 256-bit encryption strength with PBKDF2 - HMAC-SHA1

Question

I am interested in the theoretical consideration of the bit strength of an encryption key and its precursor.

Assume a given environment as follows:
a. My encryption algorithm is AES-256
b. My key derivation function is PBKDF2 with HMAC-SHA1 with
b1. Salt strength of 128 bit (32 chars of a truely random hex string)
b2. Iteration count is 4096

My objective is to achieve 256 bit "encryption strength" based on the above environment

Evidently, I can not achieve a "true 256-bit total strength" with the environment as stated above, since the randomness provided by the SHA1 in the PBKDF2 standard is at most 160 bit.

From RSA Document "PKCS #5 v2.0: Password-Based Cryptography Standard", March 25, 1999:
"The length of the derived key is essentially unbounded. (However, the maximum effective search space for the derived key may be limited by the structure of the underlying pseudorandom function"

and

"....Thus, even if a long derived key consisting of several pseudorandom function outputs is produced from a key, the effective search space for the derived key will be at most 160 bits. Although the specific limitation for other key sizes depends on details of the HMAC construction, one should assume, to be conservative, that the effective search space is limited to 160 bits for other key sizes as well."

My questions is: Since the most I can expect is "160-bit encryption strength" from my existing environment, if I feed the result of the PBKDF2 output to a Skein 512-512 hash function, and use the left-most 61 hex (=244 bit) characters of its output as an encryption key, will I then have my sought-after 256-bit total encryption strength (I have added the 12 bit extra "strength", due to iteration count, to my calculations)?

Answer 1

The conservative assumption regarding the PBKDF-HMAC-SHA1 function you mention in your question, implies that an adversary that is able to perform $O(2^{160})$ operations, will have a non-negligible probability of predicting bits 160..319 of the output, given only the first bits 0..159 of the output. If we accept this assumption (which is, to some extent, arguable), it means that you cannot use a single invocation of PBKDF-HMAC-SHA1 to produce a derived key with 256 bits of entropy. Passing the derived key through Skein 512-512 will not add back any entropy that has already been lost, so you need a different approach.

Instead, use Skein 512-512 in KDF mode on the input key material, to produce a 512 bit output you parse as two 256 bit strings $P_0||P_1$. Given the Skein security claims, an oracle that will just tell you if your guess is correct or not, and assuming that the input key material has at least 256 bits of entropy, the problem of computing $P_1$ given $P_0$ will correspond to 256 bits of security.

Hence, if you let

• $DK_0 = $PBKDF-HMAC-SHA1$(P_0,Salt,Iterations,160)$ and
• $DK_1 = $PBKDF-HMAC-SHA1$(P_1,Salt,Iterations,96)$, then

$DK = DK_0||DK_1$ will have 256 bits of entropy. Computing $DK_1$ given $DK_0$ will be at least as hard as computing $P_1$ given $P_0$.

Answer 2

As others have pointed out, you are never going to get more strength out of it than you put into it; you are just going to make it so the attacker has to go after the password instead of brute forcing the key. And because nobody would try to brute force a 128 bit key, stretching to 256 bits isn't going to do any good. The attacker will go after the password. (I'm assuming that the salt is not secret.)

However, there is still a good reason to move from SHA1 to SHA256 for deriving a 256 bit key with PBKDF2. There is a bug in the design of PBKDF2. If you extract 256 bits from PBKDF2-HMAC-SHA1 then the attacker can go after the first 128 bits using only half of the hash compressions that you did to generate it.

This shouldn't be a problem where the attacker needs the entire 256 bits as in your usage, but there are cases where this does give a 1 bit advantage to the attacker.

So I would strongly recommend that you use HMAC-SHA256 as your PRF in PBKDF2 when deriving a 256 bit key.