Re: KDF definition and goal [was: [Cfrg] Fwd: Hash-Based Key Derivation]
"D. J. Bernstein" <djb@cr.yp.to> Sat, 29 October 2005 23:59 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 1EW0bZ-0004ZN-VV; Sat, 29 Oct 2005 19:59:21 -0400
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EW0bY-0004Yd-T5 for cfrg@megatron.ietf.org; Sat, 29 Oct 2005 19:59:20 -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 TAA01606 for <cfrg@ietf.org>; Sat, 29 Oct 2005 19:59:03 -0400 (EDT)
Received: from stoneport.math.uic.edu ([131.193.178.160]) by ietf-mx.ietf.org with smtp (Exim 4.43) id 1EW0pQ-00038T-0v for cfrg@ietf.org; Sat, 29 Oct 2005 20:13:41 -0400
Received: (qmail 38264 invoked by uid 1016); 29 Oct 2005 23:59:41 -0000
Date: Sat, 29 Oct 2005 23:59:41 -0000
Message-ID: <20051029235941.38263.qmail@cr.yp.to>
Automatic-Legal-Notices: See http://cr.yp.to/mailcopyright.html.
From: "D. J. Bernstein" <djb@cr.yp.to>
To: cfrg@ietf.org
Subject: Re: KDF definition and goal [was: [Cfrg] Fwd: Hash-Based Key Derivation]
References: <200510291655.j9TGtIxg007767@taverner.CS.Berkeley.EDU>
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 97adf591118a232206bdb5a27b217034
X-BeenThere: cfrg@ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
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
David Wagner writes: > The key assumption about is that the hash and the message must be > *independent*. 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 _______________________________________________ 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