Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd)
Daniel Brown <DBrown@certicom.com> Thu, 27 October 2005 19:12 UTC
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EVDBH-0007d4-Up; Thu, 27 Oct 2005 15:12:55 -0400
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EVDBG-0007cv-QB for cfrg@megatron.ietf.org; Thu, 27 Oct 2005 15:12:54 -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 PAA23290 for <cfrg@ietf.org>; Thu, 27 Oct 2005 15:12:37 -0400 (EDT)
Received: from [216.183.86.37] (helo=mail.ca.certicom.com) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EVDOf-0007sA-9u for cfrg@ietf.org; Thu, 27 Oct 2005 15:26:47 -0400
Received: from spamfilter.certicom.com (localhost.localdomain [127.0.0.1]) by mail.ca.certicom.com (Postfix) with ESMTP id 676B810181974; Thu, 27 Oct 2005 15:12:35 -0400 (EDT)
Received: from mail.ca.certicom.com ([127.0.0.1]) by spamfilter.certicom.com (storm [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 14573-24; Thu, 27 Oct 2005 15:12:33 -0400 (EDT)
Received: from certicom1.certicom.com (domino1.certicom.com [10.0.1.24]) by mail.ca.certicom.com (Postfix) with ESMTP id BE64410181975; Thu, 27 Oct 2005 15:12:33 -0400 (EDT)
In-Reply-To: <Pine.GSO.4.44_heb2.09.0510270108410.9033-100000@ee.technion.ac.il>
To: Hugo Krawczyk <hugo@ee.technion.ac.il>
Subject: Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd)
MIME-Version: 1.0
X-Mailer: Lotus Notes Release 6.5.1 January 21, 2004
Message-ID: <OF9F9EB38A.2273A0A8-ON852570A7.006713F9-852570A7.0069970F@certicom.com>
From: Daniel Brown <DBrown@certicom.com>
Date: Thu, 27 Oct 2005 15:13:34 -0400
X-MIMETrack: Serialize by Router on Certicom1/Certicom(Release 6.5.4|March 27, 2005) at 10/27/2005 03:13:30 PM, Serialize complete at 10/27/2005 03:13:30 PM
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 2e8fc473f5174be667965460bd5288ba
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>
Content-Type: multipart/mixed; boundary="===============0069878879=="
Sender: cfrg-bounces@ietf.org
Errors-To: cfrg-bounces@ietf.org
Hugo Krawcyzk wrote on 10/26/2005 07:09:01 PM: > > One final comment about random oracles. Take the example of NIST's KDF. > Note that the counter value comes before the SV value. Why? The paper: C. Adams, G. Kramer, S. Mister and R. Zuccherato, "On the Security of Key Derivation Functions", Information Security - 7th International Conference, ISC 2004, Lecture Notes in Computer Science 3225 (2004), Springer-Verlag, pp. 134-145. provides some grounds that putting the counter after the SV in a such a KDF based on an iterated hash function like SHA-1 has some risks. Suppose that the SV was before the counter, the SV is the length of a input block of SHA-1, (i.e. 512 bits), SV has min-entropy at least 256 bits, the KDF is used to generate some number of AES-256 keys. If Eve obtains one of the AES keys, and it happens to contain a whole hash output block from the KDF, then she can determine all the other AES keys with only 2^160 work. Eve just searches through all possible values of the first chaining variable, until she finds a match with her sample. All other blocks have the same first value of the chaining variable, so she can then determine this too. Although this amount of work is infeasible today (and for the foreseeable future), it is considerably below the objective security level for AES-256, so qualifies as an attack. Placing the counter before the SV seems to stop this particular attack. The paper also provides an analysis of the IKE "KDF", and seems to draw a similar conclusion. > I do not really know. Of course, if H is a random oracle then the > order of counter and SV is immaterial (as long as it is kept fixed). > But with an actual function such as SHA-1 it may make a difference. > For example, Preneel and van Oorschot showed that if you are putting > a key as part of a hash message then it is best not to put it across > block boundaries. If this advise holds here then it might have been better > to put SV before counter. Now, I have not tried to really analyze this. > I am using this as an example showing that the idealization of H as a > random oracle may be too much of an abstraction driving us to bad > decisions. > > To make this last (important) point even clearer, think of the > design of a MAC. If SHA-1 is to be treated as a random oracle then > MAC(K,msg)=SHA-1(K||msg) makes a "provably secure" MAC. But as we > know it is *completely insecure* due to extension attacks. One can > say: "well we know about extension attacks so we won't do that" > (note that this is already an important realization that SHA-1 is > NOT a random oracle -- even if the compresion function was purely random). > So we'll try another construct: MAC(K,msg)=SHA-1(msg||K). > How about this one? Again, it is provable secure in the RO model. > How secure is it in practice? Until a couple of years ago very secure. > Now it is not secure anymore since it is vulnerable to collision attacks > on SHA-1! Again, too much confidence (or reliance) on the random oracle > approach can easily lead us to bad (or at least sub-optimal) choices. > I agree. The RO model is great for ignoring the role of the hash function when analyzing a scheme with many ingredients, i.e. hash and DLog Group, but if the hash is the key ingredient, then a proof in the RO model says very little. Dan Brown (905) 501-3857 http://www.certicom.com
_______________________________________________ Cfrg mailing list Cfrg@ietf.org https://www1.ietf.org/mailman/listinfo/cfrg
- [Cfrg] Fwd: Hash-Based Key Derivation David Wagner
- [Cfrg] Fwd: Hash-Based Key Derivation David Wagner
- [Cfrg] Fwd: Hash-Based Key Derivation David McGrew
- RE: [Cfrg] Fwd: Hash-Based Key Derivation Scott Fluhrer
- RE: [Cfrg] Fwd: Hash-Based Key Derivation Simon Blake-Wilson
- [Cfrg] Fwd: Hash-Based Key Derivation David Wagner
- [Cfrg] Fwd: Hash-Based Key Derivation David Wagner
- RE: [Cfrg] Fwd: Hash-Based Key Derivation Tom Shrimpton
- RE: [Cfrg] Fwd: Hash-Based Key Derivation Simon Blake-Wilson
- RE: [Cfrg] Fwd: Hash-Based Key Derivation Blumenthal, Uri
- RE: [Cfrg] Fwd: Hash-Based Key Derivation Simon Blake-Wilson
- RE: [Cfrg] Fwd: Hash-Based Key Derivation Simon Blake-Wilson
- RE: [Cfrg] Fwd: Hash-Based Key Derivation Scott Fluhrer
- RE: [Cfrg] Fwd: Hash-Based Key Derivation Blumenthal, Uri
- [Cfrg] Fwd: Hash-Based Key Derivation David Wagner
- RE: [Cfrg] Fwd: Hash-Based Key Derivation Tom Shrimpton
- RE: [Cfrg] Fwd: Hash-Based Key Derivation Simon Blake-Wilson
- Re: [Cfrg] Fwd: Hash-Based Key Derivation Daniel Brown
- Re: [Cfrg] Fwd: Hash-Based Key Derivation Paul Hoffman
- RE: [Cfrg] Fwd: Hash-Based Key Derivation Tom Shrimpton
- RE: [Cfrg] Fwd: Hash-Based Key Derivation Simon Blake-Wilson
- Re: [Cfrg] Fwd: Hash-Based Key Derivation D. J. Bernstein
- [Cfrg] Fwd: Hash-Based Key Derivation David Wagner
- [Cfrg] Fwd: Hash-Based Key Derivation David Wagner
- Re: [Cfrg] Fwd: Hash-Based Key Derivation Jack Lloyd
- [Cfrg] Fwd: Hash-Based Key Derivation David Wagner
- [Cfrg] Fwd: Hash-Based Key Derivation David Wagner
- KDF definition and goal [was: [Cfrg] Fwd: Hash-Ba… David McGrew
- [Cfrg] Fwd: Hash-Based Key Derivation David Wagner
- [Cfrg] Fwd: Hash-Based Key Derivation David Wagner
- Re: [Cfrg] Fwd: Hash-Based Key Derivation Daniel Brown
- Re: [Cfrg] Fwd: Hash-Based Key Derivation Jack Lloyd
- Re: KDF definition and goal [was: [Cfrg] Fwd: Has… David McGrew
- Re: [Cfrg] Fwd: Hash-Based Key Derivation Daniel Brown
- Re: [Cfrg] Fwd: Hash-Based Key Derivation Daniel Brown
- [Cfrg] Fwd: Hash-Based Key Derivation David Wagner
- [Cfrg] Fwd: Hash-Based Key Derivation David Wagner
- Re: [Cfrg] Fwd: Hash-Based Key Derivation Daniel Brown
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) Hugo Krawczyk
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) Daniel Brown
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) D. J. Bernstein
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) Hugo Krawczyk
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) Hugo Krawczyk
- [Cfrg] Fwd: Hash-Based Key Derivation (fwd) David Wagner
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) Hugo Krawczyk
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) D. J. Bernstein
- [Cfrg] Fwd: Hash-Based Key Derivation (fwd) David Wagner
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) D. J. Bernstein
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) John Wilkinson
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) Jack Lloyd
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) John Wilkinson
- [Cfrg] Fwd: Hash-Based Key Derivation (fwd) David Wagner
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) John Wilkinson
- [Cfrg] Fwd: Hash-Based Key Derivation (fwd) David Wagner
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) John Wilkinson
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) D. J. Bernstein
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) D. J. Bernstein
- [Cfrg] Fwd: Hash-Based Key Derivation (fwd) David Wagner
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) John Wilkinson
- Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd) D. J. Bernstein