Re: IKEv2 use of HMAC-SHA-1 for Key Derivation
Hugo Krawczyk <hugo@ee.technion.ac.il> Tue, 03 December 2002 23:54 UTC
Received: from lists.tislabs.com (portal.gw.tislabs.com [192.94.214.101]) by above.proper.com (8.11.6/8.11.3) with ESMTP id gB3NsWg10579; Tue, 3 Dec 2002 15:54:33 -0800 (PST)
Received: by lists.tislabs.com (8.9.1/8.9.1) id SAA15080 Tue, 3 Dec 2002 18:23:46 -0500 (EST)
Date: Wed, 04 Dec 2002 01:24:15 +0200
From: Hugo Krawczyk <hugo@ee.technion.ac.il>
To: Bill Sommerfeld <sommerfeld@east.sun.com>
cc: "The Purple Streak, Hilarie Orman" <ho@alum.mit.edu>, housley@vigilsec.com, IPsec WG <ipsec@lists.tislabs.com>
Subject: Re: IKEv2 use of HMAC-SHA-1 for Key Derivation
In-Reply-To: <200212030032.gB30WpMf019196@thunk.east.sun.com>
Message-ID: <Pine.GSO.4.21.0212031915000.13193-100000@ee.technion.ac.il>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset="US-ASCII"
Sender: owner-ipsec@lists.tislabs.com
Precedence: bulk
Bill, You are right in your description below of what HMAC does. And surely enough HMAC is not stronger than its key length. If the key is 160 bits (as in SHA-1) then you can break the function in 2^160 operations by exhaustive search. In particular the key derivation procedures of IKEv1 and IKEv2 are NOT STRONGER than the strength of the prf. If you use HMAC-SHA1 as the prf then the whole key derivation is no stronger than 2^160. If someone finds this level of security insufficient (?) then this someone can use longer-keys prf's (e.g. HMAC with SHA2-256). But then this someone wil have to use (prohibitively costly?) DH groups, 192-bit key AES, etc. Nothing that (baring major cryptanalytical breakthroughs) makes sense today or in the visible future in commercial applications. Let me also note that the dependncy on the strength of the prf shows up already in the definition of SKEYSEED (which is later used as K in the key derivation mechanism that you refer to). Indeed, SKEYSEED is obtained by hashing down the full DH key into L bits (where L is the length of the prf output). A naive observer of this hashing could think that it is silly to give up many g^xy bits (say 1024) for "just" 160 bits of the prf output. But it is actually the other way around: the hashing of the DH key represents a strengthening of the DH exchange in the sense that instead of directlty using the long g^xy key with relatively low "computational entropy" you apply the hashing to "extract" and concentrate the ful entropy in a single (shorter) key. The theoretical basis for this type of "entropy smoothing" (this is the usual technical term) via hash functions can be found in Goldreich's book (Foundations of Cryptography). The only heuristic twist in IKE's key derivation (v1 and v2) is that the prf is used in lieu of a universal hash family (using an explicit UH family would have been better from the theoretical point of view but would have required to add yet another transform to the protocol). Hugo On Mon, 2 Dec 2002, Bill Sommerfeld wrote: > [note: from my perspective, I don't think the truncation described > below will be a problem in the near term -- i.e., it's definitely not > worth holding up IKEv2 to fix; moreover, if you believe > draft-ietf-ipsec-ike-modp-groups-04.txt, the estimated limits on group > strength seem to be a weaker link than the key derivation hash..] > > > Hilarie, can you clarify what you mean by your comment below? > > In particular, what is wrong if K is large and what > > do you mean by "blocksize" in this context? > > I'm not Hilarie but I was in a side discussion on this very issue in > Atlanta. I believe she's referring to the output size of the > underlying compression function. > > (notation: || constitutes concatenation; B is the input block size in > bytes; L is the output block size. I'm reusing some of the notation > from RFC2104 but distinguishing between concatenation and separate > parameters). > > Hmac is: > > HMAC(K, text) == H(K XOR opad || H(K XOR ipad || text)) > > [with K padded with zeros to the input blocksize (B) of the hash's > compression function; ipad and opad are different constants.] > > The underlying hash function H is built out of repeated applications > of a compression function CF which takes a previous value of size L > and an input block of size B and produces an output block of size L. > > so, when "text" is short, the inner value: > > H1 = H(K XOR ipad || text) > > is computed: > > C1 = CF(C0, K XOR ipad) > C2 = CF(C1, text || pad) > > H1 = C2 > > and the final value is computed: > > H2 = H(K XOR opad || H1) > > D1 = CF(D0, K XOR opad) > D2 = CF(D1, H1 || pad) > > H2 = D2 > > [other details: C0 and D0 are equal and are the constant initial value > for the iterated hash; "pad" is the usual MDn/SHAn "fill to near the > end of the input block then add bitcount"] > > Note that: > > - the value of both C1 and D1 depend only on the key > - the key is not used directly as input in any later stage. > - sizeof(C1) == sizeof(D1) == L > > so, this isn't a problem for a single hmac invocation since you only > have L bytes of output, but in the iterated hmac case: > > > T1 = HMAC-SHA1(K, S | 0x01) > > T2 = HMAC-SHA1(K, T1 | S | 0x02) > > T3 = HMAC-SHA1(K, T2 | S | 0x03) > > T4 = HMAC-SHA1(K, T3 | S | 0x04) > > .. the intermediate C1/D1 values above are the same for each of > T1,T2,T3, ... > > if we regard [T1,T2,T3,...] as a keystream, it would seem that there > can be at most 2^(8*2*L) possible keystreams for a given HMAC, even if > K is significantly longer than 2*L bytes. > > Hilarie seemed to have a more pessimistic evaluation than this but I'm > not sure what it is. > > - Bill >
- IKEv2 use of HMAC-SHA-1 for Key Derivation Russ Housley
- Re: IKEv2 use of HMAC-SHA-1 for Key Derivation The Purple Streak, Hilarie Orman
- Re: IKEv2 use of HMAC-SHA-1 for Key Derivation Hugo Krawczyk
- Re: IKEv2 use of HMAC-SHA-1 for Key Derivation Hugo Krawczyk
- Re: IKEv2 use of HMAC-SHA-1 for Key Derivation Russ Housley
- Re: IKEv2 use of HMAC-SHA-1 for Key Derivation Bill Sommerfeld
- Re: IKEv2 use of HMAC-SHA-1 for Key Derivation The Purple Streak, Hilarie Orman
- Re: IKEv2 use of HMAC-SHA-1 for Key Derivation David Wagner
- Re: IKEv2 use of HMAC-SHA-1 for Key Derivation Joseph J. Tardo
- Re: IKEv2 use of HMAC-SHA-1 for Key Derivation Hugo Krawczyk
- Re: IKEv2 use of HMAC-SHA-1 for Key Derivation Hugo Krawczyk
- Re: IKEv2 use of HMAC-SHA-1 for Key Derivation Hugo Krawczyk
- Re: IKEv2 use of HMAC-SHA-1 for Key Derivation Andrew Krywaniuk
- Re: IKEv2 use of HMAC-SHA-1 for Key Derivation Hugo Krawczyk