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

Sorry, my mistake, I was confusing PRF with PRG.

David Wagner wrote on 10/26/2005 12:53:41 PM:

> Daniel Brown writes:
> >A KDF should be "one-way" [...]
> >certain PRFs can fail to be 1-way.
> 
> I believe a KDF only needs to be one-way in the sense that given
> KDF(K,X) you cannot recover K.  (It does not need to be one-way in
> the usual sense: it doesn't matter if given Y=KDF(K,X) you can recover
> some other K' s.t. KDF(K',X)=Y, so long as K' reveals nothing about K.)
> 

Aside: does the PRF property ensure the functions to be one-way with 
respect to X?  That is, for random K, given two functions F(K,.) (the 
challenge function to distinguish) and G(K,.) (an adversary that finds 
preimages) such that G(K,F(K,X)) = X with high probability, can one 
distinguish F(K,.) from a random function R(.)?

I ask because X might contain sensitive (but low-entropy) information, 
e.g. password or private identifier, in the context of a KDF. 

> 
> So this is not an issue: the PRF requirement already implies all the
> one-wayness properties that you might want a KDF to have.
> 
> >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.
> 

Ok, I was thinking of a PRG, i.e. a function F(.) such that F(K) is 
indistinguishable from random if K is fully random.  (For more 
practicality, one would only need K to have enough min-entropy, 
computational or info-theoretic.)

My example was that the identity function F(K) = K is a length-preserving 
PRG and K is fully random, but would not be good enough for KDF, because 
it is not 1-way.

> If you mean F(K,X)=K, that's not a PRF.  The attack: Choose X, X'
> distinct.  Send X and X' to your oracle, receiving Y and Y'.  If Y=Y',
> then your oracle is a F(K,.) oracle; otherwise, your oracle is a random
> function.  So you've distinguished F(K,.) from random.
> 

NIST SP 800-56 says that raw DH shared secrets should be destroyed after 
they are used to generate a key with a KDF, thus one doesn't need to 
resist (very much) multiple chosen-input access to the KDF function. 

If there are "KDF" applications where the same secret K is fed into a 
function several times, potentially in conjunction with adversarially 
supplied inputs X, then I can see why the full power of a PRF may be 
necessary.  Doesn't TLS do this with master secrets and nonces? 

Is a 1-way (moreover leakage-resistant?) PRG sufficient for a KDF, or is 
the full power of a PRF needed?  It seems to me that a PRG used for KDF 
should be more than just 1-way: it should not leak info about the input, 
e.g. if the input is S||T, where S is a strong secret, then T should not 
be leaked.