Subject: KDF definition and goal [was: [Cfrg] Fwd: Hash-Based Key Derivation]

From: David Wagner <[email-masked]>
Date: Tue, 25 Oct 2005 15:41:04 -0700 (PDT)

David McGrew writes:
>Okay, I got carried away and wrote up the following definition and
>goal for a key derivation function (KDF) which seems appropriate and
>also seems amenable to reduction-based security proofs.  Comments welcome.

I'm afraid I don't think this is the right formulation.  Your definition
is only relevant to practice if we assume that our source of secret
inputs has a certain special class of distributions: namely, that some
fixed number of bit positions will be uniformly random and independent
of everything else.  In many settings this is not realistic.

Consider, for example, using a Diffie-Hellman shared secret g^{xy}
as your secret input.  This does not come from your special class of
distributions, since there is no bit position that is independent of
all others.  Thus proving that a candidate KDF meets your definition
will not be sufficient to show that the KDF can be safely used with
Diffie-Hellman shared secrets.  The problem is pervasive and not limited
to Diffie-Hellman.

I gave a competing definition that I find more useful in practice, and
that is easy to achieve in the random oracle model, and that guarantees
the KDF will be secure and useful when applied to any secret input
whose distribution satisifies a few weak conditions (high min-entropy,
independence from the hash, efficiently samplable).  I can spell it out
more precisely if you like, though I don't think there would be anything
especially new or surprising in a more detailed statement.  The only
bad news is that my competing definition seems to require that the KDF
use random oracles, but in my opinion that's not the end of the world.

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

---

From: David McGrew <[email-masked]>
Date: Tue, 25 Oct 2005 16:49:55 -0700

Hi David,

thanks for your comments, more inline:

> of everything else.  In many settings this is not realistic.

Agreed, the KDF as stated would only be useful for deriving a set of  
keys from a master key, and would not be useful for other problems.

> use random oracles, but in my opinion that's not the end of the world.

Sure, the random oracle model and KDFs based on it are well  
accepted.  It would be nice to get something based on a reduction- 
based proof, though.

David

---

From: "Simon Blake-Wilson" <[email-masked]>
Date: Wed, 26 Oct 2005 10:44:41 -0400

Hi David,

OK ... A couple of stupid questions embedded below.

Best regards. Simon

> I gave a competing definition that I find more useful in 
> practice, and that is easy to achieve in the random oracle 
> model, and that guarantees the KDF will be secure and useful 
> when applied to any secret input whose distribution 
> satisifies a few weak conditions (high min-entropy, 
> independence from the hash, efficiently samplable).  

min-entropy is an information-theoretic, as opposed to complexity
theoritic, concept, isn't it? If so, how can it be useful in this
situation? Typically an attacker of a KDF will have witnessed a DH
exchange that precedes it ... Meaning that the secret has no information
theoretic entropy, only complexity theoretic unpredictability.

> I can 
> spell it out more precisely if you like, though I don't think 
> there would be anything especially new or surprising in a 
> more detailed statement.  The only bad news is that my 
> competing definition seems to require that the KDF use random 
> oracles, but in my opinion that's not the end of the world.

I think it would be a great contribution to spell out a good definition.
One comment though: I think a more palatable definition would be to take
an unpredictable input and produce an indistinguishable output, in the
face of an oracle that gives access to various other bits of the output.
This is probably somehow equivalent to other more PRF-like definitions,
but as a protocol designer, it seems to me to be much closer to my
intuitive idea of what is needed. I think having an intuitive definition
therefore really helps to promote formal analysis.

One aspect that the definition should also capture is what the security
requirement is surrounding the auxiliary data that is bound to the key. I
must confess that I have always been wary of this feature, since I think
that just getting from an unpredictable secret to a key is already hard
enough without trying to achieve extra capabilities. Personally I wonder
is it isn't better to leave this out of the KDF, and achieve it by
immediately MACing the relevant data ... Identities, cipher suites, etc
.. This is essentially the TLS approach.