Re: [Cfrg] On using ROs for analyzing randomness extraction functions
canetti <canetti@watson.ibm.com> Tue, 01 November 2005 04:19 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 1EWncA-0002eY-TP; Mon, 31 Oct 2005 23:19:14 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EWnc9-0002e6-1h for cfrg@megatron.ietf.org; Mon, 31 Oct 2005 23:19:13 -0500
Received: from ietf-mx.ietf.org (ietf-mx [132.151.6.1]) by ietf.org (8.9.1a/8.9.1a) with ESMTP id XAA08553 for <cfrg@ietf.org>; Mon, 31 Oct 2005 23:18:52 -0500 (EST)
Received: from igw2.watson.ibm.com ([129.34.20.6]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EWnqQ-0007je-Mn for cfrg@ietf.org; Mon, 31 Oct 2005 23:34:01 -0500
Received: from sp1n294en1.watson.ibm.com (sp1n294en1.watson.ibm.com [129.34.20.40]) by igw2.watson.ibm.com (8.12.11/8.13.1/8.13.1-2005-04-25 igw) with ESMTP id jA14Knio008541; Mon, 31 Oct 2005 23:20:50 -0500
Received: from sp1n294en1.watson.ibm.com (localhost [127.0.0.1]) by sp1n294en1.watson.ibm.com (8.11.7-20030924/8.11.7/01-14-2004_2) with ESMTP id jA14Itn34026; Mon, 31 Oct 2005 23:18:55 -0500
Received: from mgsmtp00.watson.ibm.com (mgsmtp00.watson.ibm.com [9.2.40.58]) by sp1n294en1.watson.ibm.com (8.11.7-20030924/8.11.7/01-14-2004_1) with ESMTP id jA14IsN34024; Mon, 31 Oct 2005 23:18:54 -0500
Received: from prf.watson.ibm.com (prf.watson.ibm.com [9.2.16.112]) by mgsmtp00.watson.ibm.com (8.12.11/8.12.11/2005/09/01) with ESMTP id jA14IsfN018722; Mon, 31 Oct 2005 23:18:54 -0500
Received: from localhost (canetti@localhost) by prf.watson.ibm.com (AIX5.1/8.11.6p2/8.11.0/03-06-2002) with ESMTP id jA14Irj31588; Mon, 31 Oct 2005 23:18:53 -0500
Date: Mon, 31 Oct 2005 23:18:53 -0500
From: canetti <canetti@watson.ibm.com>
To: John Wilkinson <wilkjohn@gmail.com>
Subject: Re: [Cfrg] On using ROs for analyzing randomness extraction functions
In-Reply-To: <7D5CF428-3FD3-40CE-A05D-4E1A22CC7068@gmail.com>
Message-ID: <Pine.A41.4.58.0510312303570.43856@prf.watson.ibm.com>
References: <200510282114.j9SLEarq012372@taverner.CS.Berkeley.EDU> <Pine.A41.4.58.0510290053020.30282@prf.watson.ibm.com> <5719CDC5-3557-4E5F-9E82-9342BC8685ED@gmail.com> <20051031054127.21824.qmail@cr.yp.to> <E3D2B4ED-668C-4A71-97D6-BCD61F414920@gmail.com> <20051031181050.30808.qmail@cr.yp.to> <7D5CF428-3FD3-40CE-A05D-4E1A22CC7068@gmail.com>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset="US-ASCII"
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 7aafa0432175920a4b3e118e16c5cb64
Cc: cfrg@ietf.org
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
John, Again, if I may intervene... my take here is that, yes, in principle the method you suggest works for the reasons you stated. But Dan is right that care should be taken: First, the leftover hash lemma guarantees almost-randomness of the output only if the output size is much shorter than the input (and is roughly the size of the underlying entropy). Also, there is dependence of the specific key exchange method in use, and in some cased UH is not enough. an example is the case mentioned by Dan, where parties use related exponents for different exchanges. other examples includes, say, exchanges where the peer identities must be incorporated into the derivation procedure to prevent "identity misbinding attacks". so, in all, it is probably hard to come up with a generic method that will provide a good extraction/derivation function for all KE methods, even if an independent R is given. however, for "standard" ke methods such as the ISO-9798-3 or IKE, without reuse of the ephemeral exponents, universal hashing with sufficiently short output should work. Ran On Mon, 31 Oct 2005, John Wilkinson wrote: > On Oct 31, 2005, at 1:10 PM, D. J. Bernstein wrote: > > > John Wilkinson writes: > > > >> 2.3) K_i = PRF( UH( R, SV ), i || context ) > >> 2.3 seems to be the only one that offers security in the standard > >> model, > >> > > > > You've been misled. That construction does _not_ guarantee secure key > > derivation under standard assumptions. > > OK, clearly I'm in way over my head, but isn't that what the > discussion about the Leftover Hash Lemma was about? Doesn't that > lemma guarantee that UH(R,SV) is delta-uniform when R is chosen > independently of SV? And if the output of UH is delta-uniform, then > isn't the PRF secure under standard assumptions? I know this falls > far short of a real proof, but, as I said, I'm in over my head here. > > -John > > _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg
- [Cfrg] On using ROs for analyzing randomness extr… David Wagner
- Re: [Cfrg] On using ROs for analyzing randomness … Jack Lloyd
- [Cfrg] On using ROs for analyzing randomness extr… David Wagner
- Re: [Cfrg] On using ROs for analyzing randomness … Jack Lloyd
- RE: [Cfrg] On using ROs for analyzing randomness … Ilya Mironov
- Re: [Cfrg] On using ROs for analyzing randomness … canetti
- Re: [Cfrg] On using ROs for analyzing randomness … John Wilkinson
- Re: [Cfrg] On using ROs for analyzing randomness … D. J. Bernstein
- Re: [Cfrg] On using ROs for analyzing randomness … John Wilkinson
- Re: [Cfrg] On using ROs for analyzing randomness … D. J. Bernstein
- Re: [Cfrg] On using ROs for analyzing randomness … John Wilkinson
- Re: [Cfrg] On using ROs for analyzing randomness … D. J. Bernstein
- Re: [Cfrg] On using ROs for analyzing randomness … canetti