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

[David McGrew <[e-mail]>]

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.  It may well
be the case that something like this exists in the literature (if so
please send me a pointer :-)  Comments welcome.

A KDF takes as input a bit string S such that l < len(S) < m, and an
integer L, and returns a bit string of length L.  Security is defined
using the following experiment:

     The adversary is given access to the oracle defined below, and is
     allowed precisely q queries. At the outset of the experiment, a
     bit B is chosen uniformly at random (and is hidden from the
     adversary).  If B = 0, then a bit string R of length l is chosen
     uniformly at random (and is hidden from the adversary).  The
     adversary is allowed to make queries in which she provides an
     input of the form X, Y, where X and Y are bit strings such that l
     < len(X) = len(Y) < m, and exactly l bits of Y are set to one.

     If B = 0, then each query is handled as follows.  The bit string S
     of length len(X) is formed by setting S_i = X_i if Y_i = 0, and
     setting S_i = R_i otherwise.  S is input to KDF, and the result is
     returned.

     If B = 1, then each query is handled by generating a bitstring
     of length L uniformly at random, and returning it.

     At the end of the experiment, the adversary returns a bit D
     that indicates her guess at the value of B.

We define the advantage the usual way:

     A = P[ D = 1 | B = 1 ] - P[ D = 1 | B = 0 ]

If the adversary's advantage can be bounded to a very small value
(e.g.  2^-80), then the KDF is secure.

We could make the adversary stronger by allowing her to choose which
bit of R goes into which position in S, or make her weaker by
requiring her to choose the same value of Y for each query.

A KDF that met this definition would be fairly idiot-proof.  It would
probably be useful in distilling entropy from a random source as well.

It would be even more interesting to consider cases in which the
attacker's uncertainty about S isn't just determined by a bit-mask.
For example, allow her to choose a value S' but then exor it with a
value chosen from a source with min-entropy l.

Here's a challenge for the day: design a KDF that provably meets
this security goal, based on a PRP and/or collision-resistant hash.

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