KDF definition and goal [was: [Cfrg] Fwd: Hash-Based Key Derivation]
David Wagner <daw@cs.berkeley.edu> Sat, 29 October 2005 16:55 UTC
Received: from localhost.cnri.reston.va.us ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EVtzP-00054D-EZ; Sat, 29 Oct 2005 12:55:31 -0400
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EVtzK-00051F-S5 for cfrg@megatron.ietf.org; Sat, 29 Oct 2005 12:55:27 -0400
Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA10530 for <cfrg@ietf.org>; Sat, 29 Oct 2005 12:55:09 -0400 (EDT)
Received: from taverner.cs.berkeley.edu ([128.32.168.222]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EVuD8-0008Tf-6j for cfrg@ietf.org; Sat, 29 Oct 2005 13:09:43 -0400
Received: from taverner.CS.Berkeley.EDU (localhost.localdomain [127.0.0.1]) by taverner.CS.Berkeley.EDU (8.13.1/8.13.1) with ESMTP id j9TGtIFE007771 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Sat, 29 Oct 2005 09:55:18 -0700
Received: (from daw@localhost) by taverner.CS.Berkeley.EDU (8.13.1/8.13.1/Submit) id j9TGtIxg007767; Sat, 29 Oct 2005 09:55:18 -0700
From: David Wagner <daw@cs.berkeley.edu>
Message-Id: <200510291655.j9TGtIxg007767@taverner.CS.Berkeley.EDU>
Subject: KDF definition and goal [was: [Cfrg] Fwd: Hash-Based Key Derivation]
To: cfrg@ietf.org
Date: Sat, 29 Oct 2005 09:55:18 -0700
Secret-Bounce-Tag: 9a029cbee41caf2ca77a77efa3c13981
X-Mailer: ELM [version 2.5 PL6]
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 0ddefe323dd869ab027dbfff7eff0465
Content-Transfer-Encoding: 7bit
X-BeenThere: cfrg@ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
Reply-To: David Wagner <daw-usenet@taverner.CS.Berkeley.EDU>
List-Id: Crypto Forum Research Group <cfrg.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@ietf.org?subject=unsubscribe>
List-Post: <mailto:cfrg@ietf.org>
List-Help: <mailto:cfrg-request@ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@ietf.org?subject=subscribe>
Sender: cfrg-bounces@ietf.org
Errors-To: cfrg-bounces@ietf.org
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@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg
- KDF definition and goal [was: [Cfrg] Fwd: Hash-Ba… David Wagner
- Re: KDF definition and goal [was: [Cfrg] Fwd: Has… David McGrew
- KDF definition and goal [was: [Cfrg] Fwd: Hash-Ba… David Wagner
- KDF definition and goal [was: [Cfrg] Fwd: Hash-Ba… David Wagner
- Re: KDF definition and goal [was: [Cfrg] Fwd: Has… D. J. Bernstein
- Re: KDF definition and goal [was: [Cfrg] Fwd: Has… David McGrew
- RE: KDF definition and goal [was: [Cfrg] Fwd: Has… Simon Blake-Wilson
- KDF definition and goal [was: [Cfrg] Fwd: Hash-Ba… David Wagner
- [Cfrg] Re: Extractors/KDF definition and goal csjutla
- KDF definition and goal [was: [Cfrg] Fwd: Hash-Ba… David Wagner
- RE: KDF definition and goal [was: [Cfrg] Fwd: Has… Simon Blake-Wilson
- RE: KDF definition and goal [was: [Cfrg] Fwd: Has… Daniel Brown
- KDF definition and goal [was: [Cfrg] Fwd: Hash-Ba… David Wagner
- KDF definition and goal [was: [Cfrg] Fwd: Hash-Ba… David Wagner
- KDF definition and goal [was: [Cfrg] Fwd: Hash-Ba… David Wagner
- KDF definition and goal [was: [Cfrg] Fwd: Hash-Ba… David Wagner
- Re: KDF definition and goal [was: [Cfrg] Fwd: Has… D. J. Bernstein
- KDF definition and goal [was: [Cfrg] Fwd: Hash-Ba… David Wagner
- Re: KDF definition and goal [was: [Cfrg] Fwd: Has… D. J. Bernstein
- KDF definition and goal [was: [Cfrg] Fwd: Hash-Ba… David Wagner
- Re: KDF definition and goal [was: [Cfrg] Fwd: Has… D. J. Bernstein
- KDF definition and goal [was: [Cfrg] Fwd: Hash-Ba… David Wagner
- Re: KDF definition and goal [was: [Cfrg] Fwd: Has… John Wilkinson
- KDF definition and goal [was: [Cfrg] Fwd: Hash-Ba… David Wagner
- Re: KDF definition and goal [was: [Cfrg] Fwd: Has… D. J. Bernstein
- KDF definition and goal [was: [Cfrg] Fwd: Hash-Ba… David Wagner
- Re: KDF definition and goal [was: [Cfrg] Fwd: Has… canetti