3
$\begingroup$

I've seen it mentioned more than once that PBKDF2 should not be used to create a longer key than the native output (such as 160 bits when used with HMACSHA1). Since an attacker could test only the native size and rule out a password. (Example)

But what if we hash the (complete) result one more time? This would seem to solve the problem. Since without the whole calculation - no part will be known.

Am I correct?

$\endgroup$
  • 2
    $\begingroup$ So you are asking whether kdf(phs(pw,s,small_output,high_parameters),large_output) yields a secure, large output? yes. $\endgroup$ – SEJPM Jan 22 '18 at 17:05
  • $\begingroup$ @SEJPM Not exactly. My question is whether the attacker will have to do the same work as the defender, in case the result is rehashed. Which is not the case if the result is not rehashed. So yes, the result will be "secure" in both cases, but no, it won't be as secure. $\endgroup$ – ispiro Jan 22 '18 at 18:22
  • $\begingroup$ "But what if we hash the (complete) result one more time..." - The entropy does not change, regardless of how much you hash it or stretch it. Also see Krawczyk's HMAC-based Extract-and-Expand Key Derivation Function (HKDF). There are some subtle differences between PBKDF2 and HKDF. HKDF uses a byte counter on each iteration of the hash, so HKDF can stretch the key up to 255*HASH_LENGTH. $\endgroup$ – user10496 Jan 23 '18 at 3:05
  • $\begingroup$ @jww The point is not to add entropy. See the link in my question for more info. As for There are some subtle differences between PBKDF2 and HKDF. - they're for 2 different goals. $\endgroup$ – ispiro Jan 23 '18 at 13:07
5
$\begingroup$

Restating and expanding on what the linked example says: when using PBKDF2-HMAC-H for storing a password hash (salted/peppered) for later comparison, it makes no sense to make PBKDF2's output size parameter $\mathsf{dkLen}$ more than the output size $h$ octets of H (if $h\ge16$ octets or similar threshold), nor more than perhaps $20$ octets, because:

  • The adversary doing brute force password search will seldom find a match of the first $h$ octets: when having found the right password, or with probability $2^{-8h}$ for random other inputs. The search can thus skip the (independent) computing of the other octets for the overwhelming majority of passwords tested. The extra data past $h$ has a cost for the legitimate user, but almost none (in proportion of total effort) for the attacker. Thus the legitimate user is better lowering $\mathsf{dkLen}$ to $h$ (as long as it remains enough to repel accidental match with the wrong password, which $\mathsf{dkLen}\ge16$ insures well-enough in practice), and should increase the PBKDF2 iteration count instead, which will cost the attacker.
  • In practice, odds of finding a password other than the genuine one that matches the hash over more than about $20$ octets are impossibly low, and adding more octets adds no useful security from that standpoint.

So there's not really a problem to solve; when using PBKDF2-HMAC-H for storing a password hash (with a common cryptographic hash thus $h\ge16$), we can just use $\min(h,20)$ for $\mathsf{dkLen}$, and pump PBKDF2's iteration count to whatever we can afford for comparable performance in legitimate use. If $\mathsf{dkLen}$ was $l$ octets with $l>h$, we can multiply the iteration count (thus attack time) by a factor of $\lceil l/h\rceil$ at comparable cost for the legitimate user.

However, yes, it is correct that in an application keeping a password hash for later comparison, re-hashing the result of PBKDF2-HMAC-H with H (or another hash) with $h\ge16$ octets, and truncating to $20$ octets, will similarly shorten the result, and won't harm compared to storing the whole result. Indeed, computing the whole PBKDF2 output is necessary to find the overall hash, forcing an attacker to perform for each password tested all the work a legitimate user does. Security is thus comparable to reducing $\mathsf{dkLen}$.

The only benefit that I can think of in asking for longer output, and hashing it to get the final result, is that the increased complexity will require a slightly more complex code for a brute force password cracker. But that does not even require memory proportional to $\mathsf{dkLen}$ (the final hash can be computed on the fly), thus it will not markedly increase build and operating cost of a password cracker well designed with that oddity in mind.

Note: large $\mathsf{dkLen}$ can still make sense in applications of PBKDF2 other than testing if the password is correct.

Note: contrary to what the quoted remark suggest, it is not mathematically certain that if the first $h$ octets match, the others will; that's just very likely.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. (The question was not implying that more than 20 octets are needed. I just wanted to confirm my understanding that though those comments I've read implied that asking for more octets (then the native underlying output) will not cost the attacker, it is in fact only so if the result is not hashed again. And I understand from your answer that my understanding was correct.) $\endgroup$ – ispiro Jan 22 '18 at 18:18
1
$\begingroup$

Yes, you could use a larger output hash function over the result. This won't benefit the adversary nor increase your work factor (or iteration count) much.

However, as you seem to want to derive key material you are better off using a key based KDF such as HKDF. That would give you the algorithm and parameters that SEJPM proposed in the comments.

HKDF-expand was defined to derive larger output key material from a given input key material.

The security will be bound by the hash used in PBKDF2 regardless of the output key size of the KBKDF. That's not an issue though; KDF's generally generate cryptographically strong output.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks. As for use a larger output hash function over the result - even without it being larger, it's not supposed to introduce any vulnerability. (Though it might be pointless.) Is that not true? $\endgroup$ – ispiro Jan 23 '18 at 13:10
  • $\begingroup$ Sure, as long as you keep in mind that the total security will likely be about the same as the security of the least secure algorithm. As said, that's not likely to be an issue; focussing on the strength of the pass phrases is much more important. $\endgroup$ – Maarten Bodewes Jan 23 '18 at 13:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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