Subject: [Cfrg] Answers to HKDF questions

From: Hugo Krawczyk <[email-masked]>
Date: Wed, 21 Oct 2009 21:38:16 -0400

Here is a list of questions people asked related to HKDF in the last two
days
with some answers. I wrote it in this way as it seems more manageable than
answering 20 or so messages, many raising similar questions.
SEE ALSO MY LONG MESSAGE FROM EARLIER TODAY WITH MORE
GENERAL RATIONALE.

>Many comments ask "why we need yet another KDF, if we have so many".

Answer: Because we have too many! (*)
Designers of new protocols/applications do not have any guidance to choose
between them. No one took the effort to sort out what properties we are
looking
for. What does each of these schemes provide and what they lack, etc etc.
Well, I did.
My work is far from a full taxonomy of properties, scenarios and existing
schemes. But it does provide the main guidelines, and it does show (I want
to
believe) that analysis does favor some schemes over others. In particular,
HKDF
is the closest I could get to something that is general purpose enough and
well-founded in analytics.

(*) The best answer to the above question is given by Peter's own question:
> In fact every protocol that I know of has invented its own KDF,
incompatible
> with every other KDF out there, thus my question about why we need yet
another
> one.
We do not need another one, we need one...

> Dan Harkins and others: How is HMAC(0,X) better than SHA256(X||X).

Merkle-Damgard (MD), the iteration mode underlying SHA256, does not preserve
"randomness" in the following sense: Even if the compression function that
you
use as the underlying hash is purely random, the result you get from M-D
iterating this compression function is NOT random (actually not even a good
extractor). HMAC, on the other hand, if you start with a random compression
function you end with a random oracle (i.e., a function that looks random to
an
adversary that can only query the function in a bounded number of points).
This is known in the literature as "random oracle indifferentiability".
It is not a result about actual hash functions but a strong result about the
STRUCTURAL STRENGTH OF HMAC (if it starts with something good it preserves
the
goodness). There are several papers on this; the main ones are [23,17] in my
paper.

>What is the value of HKDF when salt is set to 0.

In this case we can only say useful things if we assume the compression
function
to be random. In this case, as said above in the context of
indifferentiability,
HMAC implies a random oracle and then good extraction properties while in
the
case of a plain M-D hash an underlying random compression function does not
imply randomness and not even extraction. Moreover, the fact that you apply
HMAC
only once (with salt=0) to concentrate the input entropy in one key, and
then
use this key with the PRF is much better than the naive (unsalted)
repetition
SHA(X||1)||SHA(X||2)||... common to other KDFs -- for more on this see the
paper.

>Dan: HKDF is a GENERALIZATION of IKE's HKDF.

True, but only for the unsalted case. Note that IKEv1 illustrates nicely the
versatility of HKDF. It can use public nonces for salt in the signature
mode,
and it can use a secret salt in PK encryption mode. The latter gives you a
much
stronger KDF. One that is only based on the PRF properties of HMAC (since
the
salt acts as a secret key to the PRF). IKE is also a good example of how
applications may use/find salt. Most other protocols do not use salt even if
they have it available (e.g., SP 800-56A). Salting the KDF has important
benefits for randomization and independence.

>Uri repeatedly asks what makes HMAC appropriate for extraction/KDF.

You should read the paper and the results cited there (especially section
8).
Keep in mind that HMAC can only inherit its properties from the underlying
hash
function. It cannot transform a bad hash function into a good one, but for
some
functionalities (KDF is one of them) it can use weaker hash functions for
stronger purposes than alternative schemes using the plain hash.
If you are not willing to assume anything from the underlying hash function
other than collision resistance, then there is only one result I can offer
to
you: Look at the result from [23] quoted in page 24 of my paper (second
bullet).
That result assumes properties of the hash function implied by collision
resistance only. The downside: It applies only when you truncate the output
of
the extract part (for example, you use SHA-512 for extraction and SHA-256
for
PRF). But it may not be totally foolish (smiley inserted) for you to make a
heuristic leap of faith and accept this as an indication of strength also
when
you do not truncate.

>Peter Gutman and Simon J.: PBKDF.

PBKDF is quite specific to passwords since it has the iterations count that
is
not needed in general and you certainly do now want to artificially slow
down
your KDF when your source has decent entropy. I believe that PBKDF2 is a
good
design for passwords: it uses an iteration counter, salt, and HMAC as the
underlying PRF (better in that sense than PBKDF1). You could make it general
purpose by having the option of using it with iteration-count=1. However,
even
in this case the design is not great as a general purpose KDF since it uses
the
source keying material directly as a PRF key. There is nothing we can say in
general if you key a PRF with a non-uniform key (some PRFs do not even
accept
arbitrary-long keys). That's why you first extract (or concentrate) the
entropy
of the input into a short key and then use that key for keying the PRF in
the
extraction stage.

> Can we use HKDF for passwords?

Not as defined. For passwords you need to replace the entropy of the source
with
slowing iterations of the function to slow down dictionary attacks (see page
25
in my paper). This can be added, but it is not included now. For example,
for
the specific case of passwords one could replace the extract part of HKDF
with
the F(P,S,c,1) function from PBKDF2. I am not sure if this is something we
want
to include in our draft. I will discuss with Pasi.

>The input source is random (a strong cryptographic key), can we skip
extract?

When your input is already a strong cryptographic key you may choose to skip
the
extract part and go directly to expansion. For this any (variable output)
PRF
will do. The expansion part of HKDF is an implementation of such a PRF.

>David McGrew raises the question that we may need different KDFs for
different
>settings.

I believe that having one general-purpose KDF is IMPORTANT. It does not
preclude
an application to choose another one or a variant. But if we start
standardizing
a KDF for each usage scenario (including different types of key material
sources)
we will have to leave in the user's or protocol designer's hands to choose
what
is best for his setting. Not only this is not an easy task (understanding
entropy and extraction in full generality is hard) but what you may assume
for
an application today may be different tomorrow. The one case where a special
variant may be needed is for passwords (see above).

>Are block ciphers better than hash for KDF?

Block ciphers are good as a basis for a PRF (e.g via a variable input PRF
mode).
However, they are more problematic for extraction. For block ciphers as
extractors we can only say things under the assumption that the block cipher
is
a truly random permutation. In the case of HMAC we have much richer results
including those that do not idealize the hash function.
(BTW, those that said to believe more on ideal ciphers than in random
oracles,
should pay attention to the related-key attacks against AES-256!)

>David McGrew: Should we standardize on the extract part and allow for
multiple
>expansion modules?
Good question. From a modularity point of view the answer is yes.
>From the IETF point of view that wants to have as specific transforms as
possible this may be problematic. In other words, my academic side would
prefer
modularity in the spec and independence between extraction and expansion
(as long as the latter uses a good appropriate PRF mode). But I think that
the
IETF (well represented in this work by Pasi :) will not like that.

>Zooko: How about outputting a random (algebraic) group element instead of a
>(close to) uniform string?

Even a "general purpose" KDF has limits to its generality. To me, the main
need
for applications is to have a KDF that produces uniform (or "close to
uniform")
strings of a certain length(s). In particular, the problem with choosing a
random group element is that techniques to do so are group-dependent (you do
it
differently in a finite field multiplicative group than in an RSA group than
in
an elliptic curve; you may even have different techniques for different
types of
curves). So I do not see that you can find a "fits all" solution here.
(Neither is HKDF a fit-all solution - for example it doesn't do what you
want -
but it as close as it get to serve the most common applications).

> David McGrew: 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.

Section 8 contains a summary of results from [23,17] regarding the
properties of
HMAC extractor. These results are quantitative, relating the strength of the
underlying hash function with the quality of extraction. They cover a
variety of
situations depending on the entropy of the source and the existence of salt.
The truncated output result that does not require any form of idealized
assumption (uses almost universality and/or collision resistance) is quoted
in
my paper page 24 second bullet and is proven in [23].

I apologize for questions I missed.

Hugo

---

From: Zooko Wilcox-O'Hearn <[email-masked]>
Date: Wed, 21 Oct 2009 21:01:16 -0600

Dear Hugo Krawcyck:

Thank you for the detailed answers.  I still have a question about  
HMAC as compared to other MACs.  Feel free to point me to existing  
documents if they answer my question.  Suppose I were to instantiate  
HKDF with the keyed PRF being a cipher based MAC such as Poly1305  
instead of HMAC.  Which of the arguments for HKDF's security would  
still apply?

Regards,

Zooko

---

From: David McGrew <[email-masked]>
Date: Thu, 22 Oct 2009 04:59:58 -0700

Hi Zooko,

> instead of HMAC.  Which of the arguments for HKDF's security would  

HKDF has two stages, extract and expand.  Replacing HMAC in the  
extract stage with Poly1305 is not going to work as well as you would  
like.   It will have provable security bounds given realistic  
assumptions (because universal hash functions like that in Poly1305  
can be used as statistical extractors), but to get the security bound  
to be as high as you would like will force you to do things very  
inefficiently.  To use this instantiation to extract keys from Diffie- 
Hellman, for example, would require you to double the size of the DH  
keys in order to claim the benefit of the security bound.   Hugo's  
paper points this out: "Statistical extractors require a signiﬁcant  
gap between the min-entropy m of the source and the required number m 
′ of extracted bits (no statistical extractor can achieve a  
statistical distance, on arbitrary sources, better than 2^(−(m−m 
′)/2) [59])".

The use of CBC-MAC as a computational extractor has been studied, and  
its security bounds also do not match that we can achieve with hash- 
based extractors.

David

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 22 Oct 2009 19:09:32 -0400

On Wed, Oct 21, 2009 at 11:01 PM, Zooko Wilcox-O'Hearn <[email-masked]>wrote:

> Dear Hugo Krawcyck:
>
> Thank you for the detailed answers.  I still have a question about HMAC as
> compared to other MACs.  Feel free to point me to existing documents if they
> answer my question.  Suppose I were to instantiate HKDF with the keyed PRF
> being a cipher based MAC such as Poly1305 instead of HMAC.  Which of the
> arguments for HKDF's security would still apply?
>
>
To answer these questions I need to ask you some questions myself:

Can you explain how do you plan to use poly1305 for KDF.
Is it as an extractor, or for key expansion or both? You say as a "keyed
PRF": how do you get a PRF out of your MAC and where does the key to the PRF
come from?
Are you going to use only the universal hash part of poly1305 or the whole
construction?
If the latter, where does the key for AES come from?

In general a MAC function does not imply a good KDF. Even a good PRF does
not.
(If that was the case it would have been much easier to argue that HMAC is a
good basis for KDF).

If you give me more details on what you mean by your "MAC-based KDF" I can
try to answer more specifically.

Hugo

---

From: Zooko Wilcox-O'Hearn <[email-masked]>
Date: Sun, 25 Oct 2009 17:06:17 -0600

> Can you explain how do you plan to use poly1305 for KDF.

I was thinking firstly of the expansion stage, but a similar question  
applies to the extraction stage.

Poly1305 and HMAC have the same "interface" -- that of a MAC which  
takes a key and a message and perhaps a nonce and generates a tag.   
In your paper you describe a general structure for the Extract then  
Expand ("XtX") KDF which uses in the expansion stage a function named  
"PRF".  Then you suggest to instantiate PRF(PRK, m) as HMAC(PRK, m)  
(section 2).

My question is, suppose I instead instantiated PRF(PRK, m) as  
Poly1305-AES(PRK, m).  HMAC and Poly1305 each have arguments for  
their security as MACs.  But are the arguments of the security of  
HKDF predicated on the assumption that the PRK is a secure MAC?  In  
other words: what property is required of the PRK function in order  
for HKDF to be a good KDF?

David McGrew wrote a nice note in answer to my question: http:// 
www.ietf.org/mail-archive/web/cfrg/current/msg02672.html

In the context of the extraction stage, he seemed to say that a  
Carter-Wegman MAC such as Poly1305 should be analyzed merely as a  
statistical extractor, not as a computational extractor.  Is that  
what you meant to say, David?  I don't see why that would be so.

Regards,

Zooko

---

From: David McGrew <[email-masked]>
Date: Mon, 26 Oct 2009 04:07:50 -0700

Hi Zooko,

On Oct 25, 2009, at 4:06 PM, Zooko Wilcox-O'Hearn wrote:

> I was thinking firstly of the expansion stage, but a similar  
> question applies to the extraction stage.
>
> Expand ("XtX") KDF which uses in the expansion stage a function  
> named "PRF".  Then you suggest to instantiate PRF(PRK, m) as  
> HMAC(PRK, m) (section 2).
>
> David McGrew wrote a nice note in answer to my question: http://www.ietf.org/mail-archive/web/cfrg/current/msg02672.html
>
> what you meant to say, David?

Yes, that's right.

> I don't see why that would be so.

Check out S2.1 of http://cs.haifa.ac.il/~ronen/online_papers/survey.ps

David

>
> Regards,
>
> Zooko
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg