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

From: David Wagner <[email-masked]>
Date: Wed, 26 Oct 2005 22:52:42 -0700 (PDT)

Simon Blake-Wilson writes:
>min-entropy is an information-theoretic, as opposed to complexity
>theoritic, concept, isn't it?

(These are not stupid questions, by the way.)

True.  Actually, I believe that the 2-universal extractor also works
in the case where the input distribution is computationally indistinguishable
from a source with high min-entropy.

Warning: We're at the edge of my knowledge.  My understanding of the
subject of extractors is pretty sketchy.  I know there are others on
this list who know more; maybe they will chime in.

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

Ok.  Let me give it a try:

Let D be a source distribution with min-entropy >= m.
Let S be a sampling algorithm: a randomized algorithm so that
the output of S() is computationally indistinguishable from D,
and so that S() is efficient.

Let H be a random oracle.
(Note: S is not permitted to invoke H, so S is independent of H.)

Let F be a KDF algorithm.  Namely, F is an algorithm that uses an
oracle (H) and accepts two inputs (K,X) and produces an output (Y).
Let R be a random function mapping X to Y.

Say that F is a (t,q,e)-secure KDF for S if for all adversaries A
running in time at most t and making at most q queries, Adv A <= e, where
  Adv A = |Pr[K <- S(); A^{F(K,.),H}=1] - Pr[A^{R(.),H}=1]|
where q counts the number of queries to A's first oracle.

Also we have the notion of a scheme F that is a (t,q,e)-secure KDF
for some class of distributions (e.g., for all distributions with
min-entropy >= m).

The chosen-input queries correspond to cases where the attacker
controls the auxiliary inputs X and somehow manages to learn the
session key (e.g., it leaks; it is cryptanalyzed; an endpoint is
hacked).

The above is probably pretty rough, and maybe there is a better
formalization; any thoughts?

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

---

From: "Simon Blake-Wilson" <[email-masked]>
Date: Thu, 27 Oct 2005 10:56:55 -0400

Hi David,

> the output of S() is computationally indistinguishable from
> D, and so that S() is efficient.
>
> Let F be a KDF algorithm.  Namely, F is an algorithm that
> uses an oracle (H) and accepts two inputs (K,X) and produces
> an output (Y). Let R be a random function mapping X to Y.
>
> Say that F is a (t,q,e)-secure KDF for S if for all
> adversaries A running in time at most t and making at most q
> queries, Adv A <= e, where
> Also we have the notion of a scheme F that is a
> (t,q,e)-secure KDF for some class of distributions (e.g., for
> all distributions with min-entropy >= m).
>
> The chosen-input queries correspond to cases where the
> attacker controls the auxiliary inputs X and somehow manages
> to learn the session key (e.g., it leaks; it is
> cryptanalyzed; an endpoint is hacked).

This seems like the best attempt at a definition that I've seen. My only
thought is whether an attacker should also get access to something like an
F(f(K),.)) oracle. For example in the case of an ephemeral-static DH
protocol where the recipient has a static public key g^x and the legimate
peer contributes an ephemeral public key g^y, an attacker may be able to
to at some point impersonate a legimate peer and send (g^y)^2 and
subsequently learn the session key computed by the recipient using
S=g^2xy. Allowing the attacker access to an F(f(K),.) oracle for any
f:S->S, f \neq 1 of the attacker choice somehow simulates this
possibility. (I suspect formalizing f and how the attacker specifies it
gets messy, but this does seem like a vaguely realistic required property
in some cases.)

Best regards. Simon

---

From: Daniel Brown <[email-masked]>
Date: Thu, 27 Oct 2005 13:17:38 -0400

Hi Simon, 

> gets messy, but this does seem like a vaguely realistic required 
property

That's an excellent point: KDFs need to resist manipulation of the secret 
input value, but the standard PRF notion doesn't seem to cover that.  Of 
course, the existing PRF-based KDFs (e.g. in TLS) may easily resist 
manipulation of the secret input value, but it may not be right to credit 
that to some formal security arguments about PRFs.

The existing PRG-based KDFs (e.g. HKDF from NIST and ANSI) may lack any 
formal security arguments whatsoever, but they probably also resist secret 
input value manipulation attacks.  Since a PRG seems a simpler thing than 
a PRF, I wonder if simpler formal security definitions and arguments can 
be supplied for such a KDF (in a threat model limited to one use of the 
secret value, as typical for making a DH shared secret into a symmetric 
key).  A KDF would need to be both a PRG and 1-way, perhaps more generally 
to not leak information, but surely there are some arguments around .

So, from a security architecture point of view, it may make sense to use 
one tool for making a raw DH shared secret into a symmetric key and 
another different tool for making subsidiary secrets out of a master 
secret.  The first tool needs to resist manipulation of the input secret 
but only has to worry about single use of the secret (or maybe double use 
:first for Alice and second for Bob?).  The second tool does not need to 
resist manipulation of the master secret, but may be subject to a larger 
number of queries, so the existing PRF notion may be perfect.

Yet another, third tool may be best suited for producing pseudorandomness 
from highly biased sources of min-entropy.  But maybe it's not too 
ambitious to find one definition and one tool can cover all three tasks 
either.