Re: [saag] Re: [Cfrg] KDF: Randomness extraction vs. key expansion
canetti <canetti@watson.ibm.com> Mon, 31 October 2005 15:05 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 1EWbE5-0001xQ-Hc; Mon, 31 Oct 2005 10:05:33 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EWbE2-0001wh-26 for cfrg@megatron.ietf.org; Mon, 31 Oct 2005 10:05:30 -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 KAA12674 for <cfrg@ietf.org>; Mon, 31 Oct 2005 10:05:10 -0500 (EST)
Received: from igw2.watson.ibm.com ([129.34.20.6]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EWbSD-0004Pi-Jq for cfrg@ietf.org; Mon, 31 Oct 2005 10:20:10 -0500
Received: from sp1n293en1.watson.ibm.com (sp1n293en1.watson.ibm.com [129.34.20.41]) by igw2.watson.ibm.com (8.12.11/8.13.1/8.13.1-2005-04-25 igw) with ESMTP id j9VF6jBN007084; Mon, 31 Oct 2005 10:06:45 -0500
Received: from sp1n293en1.watson.ibm.com (localhost [127.0.0.1]) by sp1n293en1.watson.ibm.com (8.11.7-20030924/8.11.7/01-14-2004_2) with ESMTP id j9VF4oF314370; Mon, 31 Oct 2005 10:04:50 -0500
Received: from mgsmtp00.watson.ibm.com (mgsmtp00.watson.ibm.com [9.2.40.58]) by sp1n293en1.watson.ibm.com (8.11.7-20030924/8.11.7/01-14-2004_1) with ESMTP id j9VF4n4314176; Mon, 31 Oct 2005 10:04:49 -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 j9VF4m5G015948; Mon, 31 Oct 2005 10:04:48 -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 j9VF4m930390; Mon, 31 Oct 2005 10:04:48 -0500
Date: Mon, 31 Oct 2005 10:04:47 -0500
From: canetti <canetti@watson.ibm.com>
To: "D. J. Bernstein" <djb@cr.yp.to>
Subject: Re: [saag] Re: [Cfrg] KDF: Randomness extraction vs. key expansion
In-Reply-To: <20051031052610.4157.qmail@cr.yp.to>
Message-ID: <Pine.A41.4.58.0510310951050.43856@prf.watson.ibm.com>
References: <Pine.A41.4.58.0510281538050.38438@prf.watson.ibm.com> <20051029101512.16308.qmail@cr.yp.to> <Pine.A41.4.58.0510291921370.72162@prf.watson.ibm.com> <20051031052610.4157.qmail@cr.yp.to>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset="US-ASCII"
X-Spam-Score: 0.0 (/)
X-Scan-Signature: f607d15ccc2bc4eaf3ade8ffa8af02a0
Cc: saag@mit.edu, 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
Dan, we seem to be in violent agreement, at least on the main point of this thread. You say: > too weak or too strong. You do _not_ have, and you will never have, a > key-derivation function that's provably secure assuming AES security. Exactly. Being a block cipher is not a strong enough property for randomness extraction (or, key derivation if you prefer this name). In contrast, being a block cipher is a perfect fit for key expansion. So let's separate the two tasks! BTW. In spite of the date, I dont share your pessimistic view that key derivation/randomness extraction is doomed to be a vague notion where sorcery rules forever. I think we do have tools to make mathematical sense of it and to make concrete security claims. But I certainly agree that it's a very different (and harder) task than key expansion. Ran On Mon, 31 Oct 2005, D. J. Bernstein wrote: > canetti writes: > > But then, as you point out, we're left with one main analytical tool: > > the vague notion of a "serious cryptographic function". > > The security of a key-derivation function is _always_ a vague notion. > You _must_ combine key derivation with a Diffie-Hellman group to produce > a clear security notion, namely HDH. _Every_ key-derivation function can > have its security destroyed by a poor choice of Diffie-Hellman function. > In fact, _every_ key-derivation function, no matter how many buzzwords > were used in its construction, can potentially have security destroyed > by a choice of Diffie-Hellman function that would have been secure with > most key-derivation functions. Even worse, if you make a sufficiently > poor choice of key-derivation function, then your security _will_ be > destroyed by _standard_ choices of Diffie-Hellman functions. > > You've made a contrary claim, namely that you can build a conjecturally > secure key-derivation function by combining any randomness extractor and > any conjectured PRG. That claim is _false_. Your construction can lose > all the security that would have been produced by the NIST KDF. Your > construction fails to prevent related-key attacks. The last two > paragraphs of my previous message explain this in detail. > > You could try to fix your security mistake by replacing ``randomness > extractor'' with a stronger notion---but if you continue trying to avoid > vague notions then you'll inevitably end up with something that's either > too weak or too strong. You do _not_ have, and you will never have, a > key-derivation function that's provably secure assuming AES security. > > ---D. J. Bernstein, Professor, Mathematics, Statistics, > and Computer Science, University of Illinois at Chicago > _______________________________________________ > saag mailing list > saag@mit.edu > https://jis.mit.edu/mailman/listinfo/saag > _______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg
- [Cfrg] KDF: Randomness extraction vs. key expansi… canetti
- [Cfrg] KDF: Randomness extraction vs. key expansi… David Wagner
- [Cfrg] On using ROs for analyzing randomness extr… canetti
- [Cfrg] Re: [saag] KDF: Randomness extraction vs. … Bill Sommerfeld
- Re: [Cfrg] KDF: Randomness extraction vs. key exp… canetti
- [Cfrg] KDF: Randomness extraction vs. key expansi… David Wagner
- [Cfrg] Re: [saag] KDF: Randomness extraction vs. … canetti
- [Cfrg] Re: [saag] KDF: Randomness extraction vs. … Nicolas Williams
- Re: [Cfrg] KDF: Randomness extraction vs. key exp… D. J. Bernstein
- Re: [saag] Re: [Cfrg] KDF: Randomness extraction … canetti
- Re: [saag] Re: [Cfrg] KDF: Randomness extraction … D. J. Bernstein
- Re: [saag] Re: [Cfrg] KDF: Randomness extraction … canetti