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

From: David Wagner <[email-masked]>
Date: Wed, 26 Oct 2005 09:53:41 -0700 (PDT)

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.)

Assuming that is what you meant, every PRF is one-way in this sense.
If you could recover the key K from F(K,X), then you could distinguish
the PRF from random (just choose some other X' and confirm that on
input K' your oracle responds with F(K,X')).

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.

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.

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Daniel Brown <[email-masked]>
Date: Wed, 26 Oct 2005 13:52:55 -0400

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

> 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. 

> >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.

> 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.
_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg