Subject: Re: [Cfrg] Fwd: Hash-Based Key Derivation (fwd)

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 27 Oct 2005 01:09:01 +0200 (IST)

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 <[email-masked]>
> > Date: October 25, 2005 9:44:42 AM PDT
> > To: [email-masked]
> > 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
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/cfrg
>

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: Daniel Brown <[email-masked]>
Date: Thu, 27 Oct 2005 15:13:34 -0400

Hugo Krawcyzk wrote on 10/26/2005 07:09:01 PM:

> 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.

> 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

---

From: "D. J. Bernstein" <[email-masked]>
Date: 28 Oct 2005 10:40:31 -0000

> Second step:  Hi=PRF(K, counter++ || [context-information2]

How do we build PRFs? By hashing the key and the input. So this
construction boils down to something like H(H(SV,context),counter++). Or
maybe you want H(H(H(SV,context),counter++),H(SV,context)) because you
don't really trust your H. Or perhaps you meant

   H(SV,H(counter++,H(H(H(SV,context),counter++),H(SV,context))))

because security is really measured by the number of H's, right? Whoops,
looks like the added implementation difficulty made me double-increment
the counter, which I'll have to fix; nobody said security was easy!

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 28 Oct 2005 18:51:45 +0200 (IST)

On 28 Oct 2005, D. J. Bernstein wrote:

> Hugo Krawczyk writes:
> > Firststep:  K=H(SV || [context-information1])
> > Second step:Hi=PRF(K, counter++ || [context-information2]
>

No.I do not recommend (actually I object to) the approach of building a
PRF by "hashing the key and the input". That is an error-prone approach
which easily leads, for example, to define PRF(K,M)=SHA-1(M||K) which, as
I said in a previous posting, assumes SHA-1 is collision resistant and
therefore insecure. I use well-structured constructions based on as weak
as possible requirements from the hash function. In HMAC, for example, it
is the pseudo-random property of the compression function. If you are
going to say that we do not know how pseudorandom this compression functon
is then I will certainly agree with you (which is the case for almost
everything else in cryptography) But it certainly states a well-defined
property of the compresion function that can be judged relative to current
cryptanlytical knowledge. In particular, for all we know today HMAC-SHA-1
is a good PRF while SHA-1(M||K) is not.

In addition, when you specify a scheme with a generic PRF (and analyze it
accordingly) you allow for different implementation of the PRF including
non hash-based ones such as AES in CBC-MAC mode

> the counter, which I'll have to fix; nobody said security was easy!

I do not know what you are trying to say. The counter++ was a short hand
expression to avoid using i explicitly as counter (which NIST does not
mandate) and saving the i=i+1 notation outside the Hi. It was not meant as
a programming specification just to simplify presentation.

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 28 Oct 2005 19:07:02 +0200 (IST)

Dan,

thanks for the explanation and the pointer to the paper you
mentioned. I do not know if the explanation you give to the prepended
counter is the real reason behind NIST design (unfortunately they do
not offer public rationale) but if so it is yet another good example of
abusing random oracles and leading to ad-hoc constructions

At a high level what the NIST KDF does is to define a transformation from
a shared value SV and counter i into an output Hi using the transformation
Hi=H(i||SV) and assuming that Hi is pseudo random (since Hi is used a
cryptographic key).

In other words they are applying a function with key SV and input i and
hope to produce a pseudo random output. Or, in math notation:
Hi=PRF(SV,i) where PRF(SV,i)=H(i||SV) is intended as a pseudo-random
function and SV as a key (actually they are assuming much more than a
pseudorandom function since SV is NOT a uniform or pseudo-random key but I
will ignore this for now).

The interesting thing is that, according to what you say, they chose to
implement this Hash-based PRF to avoid attacks of complexity 2^160 (!).
For achieving that they resort to a very "sub-optimal" construction of PRF
whose analysis would need to assume that the underlying hash function is
collision resistant. So not only this does not give a "160-bit" security
but an 80-bit security at best (and we know that now it is even <80 bit).

Hugo

On Thu, 27 Oct 2005, Daniel Brown wrote:

> Derivation Functions",Information Security - 7th International
> bits, the KDF is used to generate some number of AES-256 keys.If Eve
> 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
> can then determine this too.Although this amount of work is infeasible
> > 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
> > How about this one?Again, it is provable secure in the RO model.
> > on SHA-1!Again, too much confidence (or reliance) on the random oracle
> 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 andDLog Group,

---

From: Hugo Krawczyk <[email-masked]>
Date: Fri, 28 Oct 2005 20:58:19 +0200 (IST)

A couple of days ago I sent a message to this list with a link to my
SIGMA paper (see below). Some people pointed out to me that they had
trouble accessing the link so I have posted the paper also under
http://www.research.ibm.com/security/sigma.ps

Also, if you have a copy of the CRYPTO'03 proceedings where this
paper appeared, note that the Appendix to which I am referring is
not part of that (shorter) version of the paper.

Hugo