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

From: "Blumenthal, Uri" <[email-masked]>
Date: Tue, 25 Oct 2005 15:21:05 -0400

> Is there a proof somewhere that pre-hashing then MACing makes a good
KDF?

AFAIK - such a proof does not exist (yet?). 

Regarding hash - some people claim, that based on their experience,
crypto-hash output is "random enough". I personally find it somewhat
"unscientific". :-)

> I'd be interested to see it. 

Me too.

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of David Wagner
> Sent: Tuesday, October 25, 2005 2:41 PM
> To: [email-masked]
> Subject: [Cfrg] Fwd: Hash-Based Key Derivation
> 
> 
> Simon Blake-Wilson writes:
> >Is it really true that you can build a KDF like this based 
> on standard 
> >assumptions about a MAC? [...] MACs are by design secure only if the
> >key is pseudorandom, aren't they?
> 
> Yes, in general, you are right.  The fix is to pre-hash the 
> key. So you might use F(S,X) = SHA256-HMAC(SHA256(S), X), 
> where S is the secret.
> 
> For HMAC, it might just happen to be the case that 
> pre-hashing is unnecessary -- I don't know, and I haven't 
> tried to do the analysis.
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/cfrg
> 

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

---

From: "Simon Blake-Wilson" <[email-masked]>
Date: Tue, 25 Oct 2005 15:31:43 -0400

Right ... A few years ago when I tried to sit down and right a good
definition of secure KDF, I pretty quickly convinced myself that a random
oracle and some length encoding produced one ;-).

Best regards. Simon

> Behalf Of Blumenthal, Uri
> Sent: Tuesday, October 25, 2005 3:21 PM
> To: [email-masked]
> Subject: RE: [Cfrg] Fwd: Hash-Based Key Derivation
> 
> 
> Regarding hash - some people claim, that based on their 
> experience, crypto-hash output is "random enough". I 
> personally find it somewhat "unscientific". :-)
>

---

From: Scott Fluhrer <[email-masked]>
Date: Tue, 25 Oct 2005 13:01:15 -0700 (PDT)

>> I'd be interested to see it.

Actually, such a proof doesn't exist; you need further assumptions beyond 
the standard.  Trivial example: take a secure MAC, and produce a varient 
by prepending the output with a zero bit:

    tMAC(key, text) = 0 + MAC(key, text)

tMAC is obviously a secure MAC if the underlying MAC is, however, it is 
obviously not a secure PRF.

Sigh...

---

From: David McGrew <[email-masked]>
Date: Tue, 25 Oct 2005 15:04:03 -0700

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.

---

From: David McGrew <[email-masked]>
Date: Wed, 26 Oct 2005 06:41:19 -0700

> this security goal, based on a PRP and/or collision-resistant hash.

To continue the tradition of replying to one's own email, here's a  
better challenge: show a KDF design that's secure in the random  
oracle model, but which is not secure in the reduction-based model.

Here's an idea of how to do it: assume a conventional hash-based KDF,  
and then assume that the hash h(R || M) is distinguishable from a  
random function with advantage A(q) after q queries, with R unknown  
and fixed and M chosen.  Then for some value of q, the KDF isn't  
secure in the reduction-based model, but of course it is still secure  
in the random oracle model.  (Yeah, I know it's contrived ;-)

David