2
$\begingroup$

Key derivation functions, such as HKDF (standardized in RFC 5869), are meant to stretch some initial keying material having enough entropy, like a Diffie-Hellman shared value, into one or more strong cryptographic secret keys.

Password-hashing schemes, such as the PHC winner Argon2, are meant to hash usually low-entropy passwords with the goal of making the hash digest inversion as costly as possible for an adversary with respect to CPU and memory consumption, as well as parallelization.

Is it exact to consider that password-hashing schemes are actually key derivation functions specialized for low-entropy inputs? Or is there any other essential difference of theoretical nature between these two types of cryptographic schemes?

$\endgroup$
  • 2
    $\begingroup$ There are two kinds of KDF, the slow, strengthening kind fed by a password(e.g. PBKDF2), and a fast one that only derives secondary keys from a master key(e.g. HMAC). The second one obviously shouldn't be used for password hashing. $\endgroup$ – CodesInChaos Oct 11 '12 at 21:42
  • $\begingroup$ Right, I knew that actually. I clarified the question. $\endgroup$ – Jason Oct 11 '12 at 22:30
  • $\begingroup$ I believe this comment answers your question. $\endgroup$ – Swashbuckler May 21 at 13:59
3
$\begingroup$

A key derivation function does a few things:

  1. Turn a random bit string with high min-entropy,* initial key material, into an effectively uniform random bit string.
  2. Label the parts of the resulting uniform bit string by purpose for reproducible derivation.
  3. Prevent multi-target attacks from saving a factor of $n$ cost in attacking one of $n$ targets with an optional salt.

Often, parts (1) and (3) are done separately from part (2) in an extract/expand form, as in, e.g., $\operatorname{HKDF-Extract}(\mathit{salt}, \mathit{ikm})$ which turns a high min-entropy initial key material $\mathit{ikm}$ into an effectively uniform random master key $\mathit{prk}$ with an optional salt, and $\operatorname{HKDF-Expand}(\mathit{prk}, \mathit{info}, \mathit{noctets})$ which derives effectively independent subkeys from a uniform random master key $\mathit{prk}$ labeled by the $\mathit{info}$ parameter. If you already have a uniform random master key to start, you can skip HKDF-Extract and pass it directly on to HKDF-Expand.

A password hash serves one additional purpose:

  1. Cost a lot to evaluate—in time, memory, and parallelism.

This way, even if we can't control the expected number of guesses to find a password, we can control the cost of testing each guess to drive up the expected cost of finding a password.

Specifically, password hashes usually do parts (1), (3), and (4), leaving the reproducible labeled derivation of subkeys in (2) to functions like HKDF-Expand. For example, it can actually hurt to use PBKDF2 to generate more than a single block of output, so you should absolutely use HKDF-Expand to turn a single master key from PBKDF2 into many subkeys. That said, this particular pathology is fixed in Argon2, but HKDF-Expand may still be more convenient for labeling the subkeys by purpose.

Summary:

  • If you have a high min-entropy but nonuniform secret like a Diffie–Hellman shared secret, then use HKDF-Extract.
  • If you have a low min-entropy secret like a password, use Argon2.

Then pass the resulting effectively uniform master key you get out of them through HKDF-Expand to derive subkeys for labeled purposes.


* The min-entropy of a procedure for making a choice is a measure of the highest probability of any outcome; specifically, if, among a finite space of (say) passwords chosen by some procedure, the probability of the $i^{\mathit{th}}$ password is $p_i$, the min-entropy of the procedure is $-\max_i \log_2 p_i$ bits. If there procedure is to choose uniformly at random from $n$ options, the min-entropy of this procedure is simply $\log_2 n$. For example, the diceware procedure with ten words has $\log_2 7776^{10} \approx 129.2$ bits of min-entropy.

$\endgroup$
  • $\begingroup$ So, you essentially answered my question by "yes". That said, if you look at the respective designs of HKDF and Argon2, the former requires a PRF for the extraction step, while the latter contents itself with a hash function. So, clearly, the extraction phases in both designs do not seem to target the same security requirements. This is something that had not caught my eye during the PHC period. $\endgroup$ – cryptopathe May 21 at 16:53
  • $\begingroup$ Another point that puzzles me is that this answer suggests to use Argon2 only as a low-min-entropy extractor, but not as an expander, although Argon2 offer the possibility to generate as many output bytes as necessary. $\endgroup$ – cryptopathe May 21 at 16:59
  • $\begingroup$ HKDF-Extract relies on more than just PRF security of, e.g., HMAC-SHA256, because neither input (salt, IKM) is necessarily uniformly distributed; HKDF-Expand relies only on PRF security. And yes, you can use Argon2 to produce as many output bytes as you want, but it doesn't provide convenient labeling for fast reproducible subkey derivation as a separate step. $\endgroup$ – Squeamish Ossifrage May 21 at 17:01
  • $\begingroup$ Your first sentence is misleading: the HKDF paper (Lemma 2) proves that a PRF is a sufficiently good randomness extractor, so it's incorrect to say that one needs "more than just PRF security", since PRF security is sufficient, but maybe not necessary. $\endgroup$ – cryptopathe May 21 at 17:11
  • 1
    $\begingroup$ A PRF may serve as a randomness extractor, but that's not sufficient to justify the security of, e.g., HKDF-Extract(salt, DH(...)), where neither input—not the merely distinct salt, not the nonuniform DH secret—is uniformly distributed and therefore neither input satisfies the criteria of a PRF key. $\endgroup$ – Squeamish Ossifrage May 21 at 17:13
15
$\begingroup$

KDF must produce results that have certain randomness properties, and be very difficult to reverse. Password hashes only need to satisfy the property "difficult to reverse", without randomness requirements. This is why all KDFs work as password hashes but not the other way around.

$\endgroup$
  • $\begingroup$ This is completely backwards. KDFs and password hashes both have randomness and irreversibility requirements. Password hashes, sometimes called password-based KDFs, additionally have parameters to scale how costly they are to evaluate. $\endgroup$ – Squeamish Ossifrage May 24 at 16:01

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.