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

[David Wagner <daw at cs.berkeley.edu>]

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
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg