Subject: Re: [Cfrg] comments and questions on draft-krawczyk-hkdf and related work

From: David McGrew <[email-masked]>
Date: Mon, 8 Feb 2010 13:01:19 -0800

Hi Hugo,

I never heard back from you on my security questions about HKDF.  I'm  
resending the original email from last year, with the questions that  
Pasi answered stripped out.

On Oct 20, 2009, at 2:43 PM, David McGrew wrote:

> Hi Hugo and Pasi,
>
> I have some comments and questions on draft-krawczyk-hkdf-00 and "On
> Extract-then-Expand Key Derivation Functions and an HMAC-based KDF".
> First, thanks for taking on this work; it makes strong contributions
> in an important area.
>
> The most important question is: what is the precise security statement
> for HKDF?  What assumptions does one need to make about the hash
> function used in HKDF in order that the security analysis applies?
> The paper says that "it is shown in [23] (see Section 8) that using
> HMAC with a truncated output as an extractor allows to prove security
> under considerably weaker assumptions on the underlying hash
> function."  However, both of the Lemmas in that paper (and the
> implication in Section 8) make random oracle assumptions.
>
> A recommended instantiation of HKDF from the paper uses HMAC-SHA-512
> (with output truncated to 256 bits) in the extract stage and
> HMAC-SHA-256 in the expand stage.  I understand from [23] that "if we
> are interested in an output of L close-to-uniform bits then the key to
> the underlying compression function needs to be sufficiently larger
> than L," which motivates the use of SHA-512 in the extraction stage.
> But I don't see any exact security statement for this instantiation.
>
> What is the impact of the salt (and its omission) on the security
> properties?
>
> <snip>
> </snip>
>
> A minor point: The HKDF analysis asserts that OFB mode is better than
> CTR, because the attacker has less knowledge on the inputs to the PRF,
> and because successive values of a counter differ in very few bits.
> These are valid points, but are they strong enough to justify the
> implementation of a new algorithm for an "expand" stage?
>
> It would be a valuable contribution to theory to isolate the security
> requirements of the hash function that are needed to build a
> good computational extractor, and provide these requirements to the
> NIST hash function competition.
>
> I was unsatisfied with my results in trying to track down references
> on a computational extractor.  It would be valuable to have a precise
> and concise statement of the security goal (reference [35] in the
> paper doesn't mention min-entropy - should I be looking somewhere
> else?).  Also, the citation "Randomness Extraction and Key Derivation
> Using the CBC, Cascade and HMAC Modes", includes the statement
> "Computational Security: Our second approach to analyzing NMAC is
> similar to the analysis of the padded cascade from Lemma 5. We will
> present it in the full version."  Is the full version available
> online?  Or is there another reference that you could recommend?
>
> Regards,
>
> David
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Hugo Krawczyk <[email-masked]>
Date: Tue, 9 Feb 2010 15:21:30 -0500

On Mon, Feb 8, 2010 at 4:01 PM, David McGrew <[email-masked]> wrote:
> resending the original email from last year, with the questions that Pasi
> answered stripped out.
>

David, I am sorry for not having answered these (very good) questions at the
time.  I lost them among many other messages on the subject.

I am preparing a revision of the paper that will be much more detailed on the
formal side than the one I posted in my website. The latter had a focus on
explaining the rationale for the construction in general and informal terms.

In the meantime let me give you specific answers to you questions below.

>> implication in Section 8) make random oracle assumptions.

Let H be a hash function with output length k. Consider the NMAC construction
using H and where the output of NMAC is truncated from k bits to k' bits (e.g.,
in the case of SHA2-512 we could truncate the output from k=512 to k'=256).
Then if you assume the compression function of H to be strongly universal
(or paiwise independent) and the iterated Merkle-Damard function H to be
delta-AU (AU=almost univesal) then the output of the truncated NMAC is
statistically close to uniform with distance at most sqrt(2^{k-k'}+2^k'*delta).

For a collision resistant hash function H we expect delta to be close to 2^{-k}.
Indeed, if H is delta-AU then there is a trivial linear (non-uniform) algorithm
that finds collisions in H (seen as a family of functions) with probability
delta. We expect our hash functions to have collision resistance in the order
of a birthday attack and that means delta1 being approximate 2^{-k}.

Thus, in the above case we get that the statistical distance between the output
of truncated NMAC and the uniform distribution is about 2^{-c/2} where c is the
number of bits we dropped from the output (in the SHA2-512 example above c=256
and then the statistical difference is 2^{-128}. This is an excellent bound
especially that it is statistical not computational.

Even if H turns out to be less secure as collision resistant, say that instead
of having a probability of finding collisions under trivial linear attacks of
2^-k this probability is 2^100 times worst then the above result will say that
the statistical distance is 2^50 times worst than above, i.e. 2^{-78}, still a
very good bound.

The above results generalize to the case where the compression function is a
good statistical extractor or when it is delta'-AU for delta'>0
(the case delta'=0 is the "strongly universal" case cited above).

To apply these results to HMAC (rather than NMAC) one needs an additional
assumption that for random and secret key the values h(key xor ipad) and
h(key xor opad) are computationally independent (i.e., given one of the two
values, but not k, the other one remains semantically secure).

The latter is the only computational assumption on the above result.
(Note that the collision resistance property mentioned above is not a necessary
condition, but rather a sufficient one to guarantee delta-AU for small delta).

>> But I don't see any exact security statement for this instantiation.

The "sufficiently larger" refers to the need for k-k' be sufficiently large so
in particular you need k to be large. In the case of HKDF using HMAC with
SHA2-512 in the extraction part with an output of 256 bits, and then using
SHA2-256 in the expansion part is a perfect example of the applicability of the
above results.
As for exact security bounds these were outlined above.

>> What is the impact of the salt (and its omission) on the security

The short answer is that salt is required for having *generic* extractors
(those that can extract randomness from arbitrary distributions of sufficiently
high entropy). Without it you have to resort to the idealized modeling of the
underlying hash function as a random oracle (where the implicit salt comes from
the randomness of the function), or to the use of deterministic extractors that
may be well suited for some distributions but not all. Another clear use of salt
is to make the extractor function independent from the input source.
These issues are explained in the posted paper especially in Section 5.

>> implementation of a new algorithm for an "expand" stage?

First, this is not a new algorithm. It is just part of the spec of HKDF.
If we wanted a more general scheme that can be instantiated with different
components then we could perfectly allow the expansion part to be implemented
with any secure pseudorandom function. However, the HKDF draft as is purposely
written in a "narrow" option-less way. If there is interest one could have a
separate document defining a more modular scheme that allows for replaceable
modules but that is not the intention of the current draft. Also, remember that
the feedback mode used here is the same used in IKE and in TLS so there is
nothing really new about it.

As for the security of the scheme relative to a counter mode: If your PRF
function is as secure as we use in our definitions then counter mode or feedback
gives the same assurance. Personally, I feel that feedback mode is more
resistant to future, unexpected  weaknesses. Robustness to future cryptanalysis
is a main driving force behind this design.

>> NIST hash function competition.

Together with some of my IBM colleagues we attempted to do so in our comments to
NIST before the SHA3 rules were announced, particularly stressing the importance
of universality (in the Carter-Wegman sense). See
http://www.csrc.nist.gov/pki/HashWorkshop/Public_Comments/May_2007/IBM%20-%20TJ%20Watson.pdf
or
http://webee.technion.ac.il/~hugo/nistcom.pdf

Our recommendation made it to
slides used in some of NIST's pre-competition presentations but not to the
actual list of requirements. Still, I would consider the ability of designers of
a hash function to argue about universal properties of their design as a
valuable consideration in judging the proposal. The nice thing about
universality (as in the results I stated above) is that they are statistical
in nature and can be argued without computational assumptions.

>> online?  Or is there another reference that you could recommend?

The full version of [23] has not been published.
But I am including a formal definition of computational extractor and its
relation to KDFs in my (promised) upcoming revision of my HKDF paper.

>> David

Thanks for your great questions and interest (makes me feel much better about
writing the "boring" formal details :)

Hugo