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

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

Dan Bernstein writes:
>David Wagner writes:
>> > > The hash function also has to be independent of the adversary's choices.
>> > No, that sort of assumption is always wrong for public hash functions.
>> Exactly my point. I'm saying the assumption is necessary for provable
>> security under the Leftover Hash Lemma
>
>No. Your false hypothesis is not an assumption of the lemma.

Actually, yes, it is.  Since you seem to prefer Shoup's statement,
let me quote from his Theorem 6.21:

  ``Let H denote a random variable with the uniform distribution on
  [a universal family of hashes], and let A denote a random variable
  taking values in [a message space], and with H,A independent. [...]
  Then (H,H(A)) is \delta-uniform [...]''       http://shoup.net/ntb/

The key assumption about is that the hash and the message must be
*independent*.

If the protocol calls for Alice to pick the hash H first and publish
it, and Mallory later picks the message A, then there is no reason to
think that H,A will be independent.  Consequently, for such a protocol,
the Leftover Hash Lemma will not be applicable.

>You clearly understand that the lemma applies to public hash functions
>used for one message; [..]

I'm afraid you have over-estimated what I understand.  As far as I can
tell, the Leftover Hash Lemma does *not* apply to public hash functions,
no matter how many messages it is applied to, if the message is chosen
after the hash function is made public.

Note: the *family* of universal hash functions may be made public;
it is only the selection and publication of one particular function
within that family that I am referring to.

>I have no idea why you think that the multiple-message case is
>different. Anyway, I already cited a Shoup page that explains all this
>in detail.

Yes, you referred to Theorem 6.22.  That theorem also contains an
independence requirement: ``with H,A_1,\dots,A_\ell mutually
independent.''  Consequently, I believe all of my comments about the
problems with public hash functions apply both to the single-message
and the multiple-message case.

If you think I've gone wrong somewhere, I'd welcome a detailed
technical explanation of where I went wrong.  I've done my best to
explain, at length, what I am trying to say; now it's your turn.

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

---

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

> the Leftover Hash Lemma will not be applicable.

Since the original scenario was DH key exchange, let Alice and Bob be  
the legitimate parties to the communication, and let A = g^xy, where  
x and y are uniform random values chosen by Alice and Bob. Let H be  
chosen in advance by the protocol designer, and made public. How does  
Mallory, a would-be eavesdropper, influence the selection of x and y  
so as to choose A dependent on H? If Mallory has this level of  
influence over Alice and/or Bob, it seems that he would have other  
ways to eavesdrop. So, I'm not sure I see the problem of using the  
leftover hash lemma in the context of entropy extraction for key  
exchange. Any thoughts? -John

---

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

> The key assumption about is that the hash and the message must be

But you are wildly exaggerating this when you say that the hypothesis is
that the hash is ``independent of the adversary's choices.'' That
hypothesis is both unnecessary and false.

Here's the standard example. The legitimate users exchange authenticated
public keys g^x and g^y, and an independent authenticated random H. They
compute the Diffie-Hellman shared secret g^xy and a short hash H(g^xy).
If the attacker can't distinguish g^xy from a uniform random group
element then, by the leftover-hash lemma, the attacker can't distinguish
H(g^xy) from a uniform random short string.

There is no requirement that H be kept secret. One can even reuse H for
many messages; see Shoup's Theorem 6.22. As Shoup comments after the
theorem:

   We have a ``secret'' random variable A that is distributed uniformly
   over a large subset of some set A, but we want to derive from A a
   ``secret key'' whose distribution is close to that of the uniform
   distribution on a specified ``key space'' Z (typically, Z is the set
   of all bit strings of some specified length). The leftover hash
   lemma, combined with Theorem 6.22, allows us to do this using a
   ``public'' hash function---generated at random once and for all,
   published for all to see, and used over and over to derive secret
   keys as needed.

There are some serious limitations here, notably the short H output
length, but the limitations shouldn't be exaggerated.

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