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

["Simon Blake-Wilson" <[e-mail]>]

Hi David,

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

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

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