Key Derivation Functions offering better than 2^hlen security?

Question

On page 21 of his HKDF paper, Krawczyk criticized one of the stated desirable features of KDFs from the paper “On The Security of Key Derivation Functions” (Emphasis mine):

Due to the way the hash function is used by these schemes, their strength (measured by the work factor it takes to guess the output of the KDF) is never more than $2^k$ where $k$ is the output length of the hash function, and this is the case even when the entropy of the source key material is (much) larger than $k$. Indeed, in these schemes it suffices to guess $Hash(SKM)$ to be able to compute all the derived key material. While we agree with this fact, we do not agree with the criticism. If a work factor of $2^k$ is considered feasible (say $2^{160}$) then one should simply use a stronger hash function. Counting on a $2^k$-secure hash function to provide more than $2^k$ security, even on a high-entropy source, seems as unnecessary as unrealistic.

This seems like good advice in general: If you want a KDF with a strength larger than $2^k$, then make sure the output length length of your hash is greater than $k$. (You should also, of course, make sure the SKM is stronger than $2^k$)

However, in some highly constrained environments the use of a hash with a larger output length (Like SHA512) is computationally infeasible due to a lack of a hardware implementation, such is the case on many smart cards.

Is there any formally-defined KDF which allows for an output strength larger than $2^{hlen}$ (where $hlen$ is the hash output length), while only using a common hash function like SHA1 or SHA256?

Answer 1

Note that Krawczyk's paper builds the extract-and-expand paradigm from a notion that he labels computational randomness extractor. This is a modification of the concept of randomness extractor such that the output of the computational extractor need only be computationally near to a uniform random distribution, while a plain old randomness extractor needs to be unconditionally near to such a distribution. So an extract-and-expand KDF is a combination of:

1. A computational extractor, which takes weakly random inputs and "condenses" it into a computationally-strong master key;
2. A pseudorandom function keyed off the computational extractor's output, which is used to produce expanded pseudorandom outputs.

So a KDF that can extract the maximum entropy that can be extracted from the source key material would replace the composition of these two submodules with a randomness extractor that's capable of producing output with the desired entropy from the source key material. This is akin to the techniques used in true random number generators to produce full-entropy, uniform outputs from biased or correlated noise sources.

Randomness extraction is a big topic; searching the web for "randomness extractor" produces some technical introductory material.