Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd)
Hugo Krawczyk <hugo@ee.technion.ac.il> Wed, 26 October 2005 23:07 UTC
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EUuMj-0001Or-NB; Wed, 26 Oct 2005 19:07:29 -0400
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org) by megatron.ietf.org with esmtp (Exim 4.32) id 1EUuMi-0001Nk-8X for cfrg@megatron.ietf.org; Wed, 26 Oct 2005 19:07:28 -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 TAA08442 for <cfrg@ietf.org>; Wed, 26 Oct 2005 19:07:11 -0400 (EDT)
Received: from mailgw1.technion.ac.il ([132.68.238.34]) by ietf-mx.ietf.org with esmtp (Exim 4.43) id 1EUuZw-0002Ae-Bp for cfrg@ietf.org; Wed, 26 Oct 2005 19:21:09 -0400
Received: from localhost (localhost.localdomain [127.0.0.1]) by mailgw1.technion.ac.il (Postfix) with ESMTP id EE97FFF842 for <cfrg@ietf.org>; Thu, 27 Oct 2005 01:07:03 +0200 (IST)
Received: from mailgw1.technion.ac.il ([127.0.0.1]) by localhost (mailgw1.technion.ac.il [127.0.0.1]) (amavisd-new, port 10024) with LMTP id 19447-02-23 for <cfrg@ietf.org>; Thu, 27 Oct 2005 01:07:03 +0200 (IST)
Received: from ee.technion.ac.il (ee.technion.ac.il [132.68.48.5]) by mailgw1.technion.ac.il (Postfix) with ESMTP id BDDD7FF839 for <cfrg@ietf.org>; Thu, 27 Oct 2005 01:07:03 +0200 (IST)
Received: from ee.technion.ac.il (localhost [127.0.0.1]) by ee.technion.ac.il (8.12.10+Sun/8.12.2) with ESMTP id j9QN92Ol020555 for <cfrg@ietf.org>; Thu, 27 Oct 2005 01:09:02 +0200 (IST)
Received: from localhost (hugo@localhost) by ee.technion.ac.il (8.12.10+Sun/8.12.2/Submit) with ESMTP id j9QN91tO020551 for <cfrg@ietf.org>; Thu, 27 Oct 2005 01:09:01 +0200 (IST)
Date: Thu, 27 Oct 2005 01:09:01 +0200
From: Hugo Krawczyk <hugo@ee.technion.ac.il>
To: cfrg@ietf.org
Subject: Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd)
Message-ID: <Pine.GSO.4.44_heb2.09.0510270108410.9033-100000@ee.technion.ac.il>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset="US-ASCII"
X-Virus-Scanned: by amavisd-new at technion.ac.il
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 36b1f8810cb91289d885dc8ab4fc8172
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
I will not enter a too detailed technical discussion here (there is enough material in this thread to write a full book). My only intent in this note is to propose a change to the KDF described in the recent NIST internet draft. This is something I already pointed out in my public comments to NIST SP 800-56 (where the KDF is originally described) and is essentially the same as Dave Wagner (and possibly others) pointed out earlier in this discussion. The KDF function takes input SV in the form of some "shared value" between two parties and it derives certain amount of keying material KM using some hash function and some "context information" (ID's, algorithm-id, shared-info, etc) The current proposal (in very sketchy form) is: KM = H1||H2||... where Hi = H(counter++ || SV || context-information) Here, H is used as a random oracle without a well-defined cryptographic key, instead H is used to repeatedly hash the SV. The proposed change is to move to a more modular, two layer, scheme First step: K=H(SV || [context-information1]) Second step: Hi=PRF(K, counter++ || [context-information2] The PRF can be instatiated with HMAC (or with CBC-MAC if using a block cipher instead of a hash function). The values context-information1 and 2 can be defined as needed (I don't want to get into this level of detail here). In this way the use of an "idealized primitive" (i.e. H as a random oracle) is confined to its necessary minimum and with as little inputs (or iterations) as possible. A further advantage is that this modular construct allows (eventually or in some other applications) to replace H with other non-ideal primitives. Depending on the application such H may be simply the identity function (for example, if the value SV is already a full cryptographic key), or a randomness extractor as those discussed earlier in this thread. Personally, I would also suggest changing the counter mode currently used with H (and which I copied to the PRF setting) with a feedback mode much alike the TLS and IKE KDFs. Those interested may want to take a look at the design of the KDF function in the IKE protocols (the description is cleaner in IKEv2) which has tried to apply the existing randomness-extraction theory in an engineering-friendly way, and which could be applicable to other KDF scenarios. I have written briefly about this IKE's KDF design (in simple plain English) in appendix C of my SIGMA paper http://www.ee.technion.ac.il/sigma.ps, and have provided more theoretical backing in a paper with Gennaro and Rabin from Eurocrypt 2004 (on the subject of computational entropy in DH values), and in another paper with Dodis, Gennaro, Hastad and Rabin from Crypto04 (which tries to bridge between the theory of randomness extractors and practical PRF schemes). These apers touch in many of the issues raised during this discussion. One final comment about random oracles. Take the example of NIST's KDF. Note that the counter value comes before the the SV value. Why? 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. Going back to the KDF example: should counter come before or after SV? I do not know and I do not care. If we move to the two-layer prf-based scheme the question does not even come up (in a prf one does not have to guess, or consult other cryptographers, about the "right place" to put a key). Hugo PS: Well, I must say this for the record. The above is not trying to say let's abandon the random oracle model. We do need it. In many cases it is the best alternative when considering theoretical and practical issues. But let's always be very careful about it and let's minimize our reliance on it. On Tue, 25 Oct 2005, David McGrew wrote: > FYI > > Begin forwarded message: > > > From: Russ Housley <housley@vigilsec.com> > > Date: October 25, 2005 9:44:42 AM PDT > > To: saag@mit.edu > > Subject: Hash-Based Key Derivation > > > > > > I wanted call your attention to an individual draft on "Hash-Based > > Key Derivation." > > > > http://www.ietf.org/internet-drafts/draft-dang-nistkdf-00.txt > > > > This draft specifies a soon to be NIST-approved algorithm for > > deriving secret key material from a shared secret using a hash > > algorithm.This algorithm is in the NIST draft SP 800-56. > > > > I encourage review and comment.If you have concerns with this > > document, then the concerns probably apply to he NIST draft SP > > 800-56 document too. > > > > I am considering sponsoring this document asan Informational RFC. > > Please let me know if you have any concerns with this proposed action. > > > > Thanks, > > Russ > > _______________________________________________ > Cfrg mailing list > Cfrg@ietf.org > https://www1.ietf.org/mailman/listinfo/cfrg > _______________________________________________ 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