Re: [Cfrg] Fwd: Hash-Based Key Derivation

David Wagner wrote on 10/25/2005 06:20:32 PM:

> Daniel Brown writes:
> >David Wagner wrote on 10/25/2005 02:51:58 PM:
> >> >> http://www.ietf.org/internet-drafts/draft-dang-nistkdf-00.txt
> >> 
> 
> >Presumably this is based on two results: (1) HMAC makes a good PRF and 
(2) 
> >PRF makes a good KDF.  Are there convenient references for such 
results? 
> 
> For (2), I don't understand the question.  Isn't a PRF exactly the
> obvious and right way of making precise what we expect from a KDF?
> I have a suspicion that this may be a question of semantics (i.e.,
> of what definitions we attach to KDF).  So probably before I can answer
> whether a PRF makes for something that *you* would call a good PRF, I
> should ask you whether you can make precise what you mean by a KDF.
> For me, when I say KDF, what I mean is almost exactly that it should
> act as a PRF when given secret inputs from some specified 
distribution(s).
> 

A KDF should be "one-way", at least for some protocols.  (For example, see 
http://eprint.iacr.org/2004/306 or the recent papers on HMQV.)

I'm not well-versed in the formal definitions for PRF (not to mention a 
KDF), but as I see it, certain PRFs can fail to be 1-way.  If the PRF is 
the identity and the secret input is uniform and unpredictable, then the 
output is indistinguishable (from random), so it seems to be a PRF.

I realize that length-expanding PRFs must be 1-way, because otherwise one 
can recover the input and re-run the PRF to distinguish its output from 
random.  However KDFs may not necessarily be length-expanding, and in fact 
they are often length-decreasing.

This is not at all to say that any of the existing PRF designs are 
inadequate as a KDFs, (usually the designs have length-expanding options 
and thus must be one-way).  All I'm saying is that there's something's 
more to the KDF security than pseudorandom output.

On the other hand, if the output of KDF is meant to be used as a key in a 
secure algorithm, how crucial is pseudorandomness, or even 1-wayness, in 
practical terms?  (For protocols that use the KDF output directly, e.g. as 
a stream cipher, then full pseudorandomness is essential.)  If the KDF 
output goes directly into a AES key or HMAC key, then having a small 
amount of bias seems relatively harmless.  I appreciate the theoretical 
value: AES is secure with a random key, then AES is secure with a 
pseudorandom key.   I also recall the attacks on ARC4 with the keys have 
extensive structure (highly non pseudorandom), but am not aware if such 
attacks are expected for AES, HMAC, etc.