Subject: [Cfrg] Fwd: Hash-Based Key Derivation (fwd)

From: David Wagner <[email-masked]>
Date: Sat, 29 Oct 2005 09:25:15 -0700 (PDT)

Dan Bernstein writes:
>David Wagner writes:
>> Dan Bernstein writes:
>> > You can turn AES into a hash function by applying, e.g., Luby-Rackoff
>> > plus Miyaguchi-Preneel. Using this hash function to derive keys is then
>> > identical to using AES to derive keys.
>> Is it?  I don't see it.  AES-OMAC(K,X) is provably secure (as a PRF) assuming
>
>Irrelevant. I said nothing about PRFs. I said that using a particular
>hash function to derive keys is exactly the same as using AES to derive
>keys.

Sure.  I know you said that.  But what you said looked wrong to me,
or at least, I couldn't see any reason why it would be true.  I was
hoping someone would explain.

As far as I can tell, the M-P scheme you mention computes a different
function than the OMAC scheme I described, and they will have different
security properties.  So, I don't know what you mean by "exactly the
same", but it doesn't seem to mean "computes the same outputs" or "secure
under the same assumptions".  If you think differently, I'd welcome an
explanation or elaboration.

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

---

From: John Wilkinson <[email-masked]>
Date: Sat, 29 Oct 2005 14:10:56 -0400

I suspect that Dr. Bernstein's will claim that the following two  
KDF's are equivalent, from a provable security perspective:

KDF1: Ki = CMAC-AES256(SHA256(x),i), where x is the shared secret,  
SHA256(x) is used as the key to CMAC, and i is a counter used as the  
message input to CMAC.

KDF2: Ki = SHA256(i,x), where i is a counter, x is the shared secret,  
and (i,x) represents the concatenation of i and x.

I suppose he's correct in the sense that for KDF1 we need to assume  
that the output of SHA256(x) is uniformly distributed and random for  
CMAC to retain its proven properties as a PRF. If we're willing to  
assume that SHA256(x) is uniform and random, then I don't see why we  
can't assume that SHA256(i,x) is also uniform and random, in which  
case we might as well use KDF2.

KDF1 may "feel" more secure, but it seems to me to be akin to double  
encrypting with, say, AES and RC6. You might gain some security over  
using AES alone, but it seems an expensive way to do so. I guess it  
all comes down to how much confidence we place in our cryptographic  
primitives, and to what extent we desire to "overengineer" our higher  
level protocols to compensate for any potential weaknesses in the  
primitives.

-John

---

From: "D. J. Bernstein" <[email-masked]>
Date: 29 Oct 2005 22:59:33 -0000

David Wagner writes:
> So, I don't know what you mean by "exactly the same"

I mean that the functions are equal: same output for every input. I'm
talking about _one_ key-derivation function that can be described in two
equivalent ways:

   * a very simple application of a particular ``hash function'' or
   * a complicated multi-layer Canetti-style application of a particular
     ``cipher,'' namely AES.

This disproves the religious notion that Canetti-style key-derivation
functions are safe while hash-based key-derivation functions are not.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago