Subject: [Cfrg] Can CMAC and/or GMAC be substituted in an HMAC-styled KDF?

From: Robert Moskowitz <[email-masked]>
Date: Wed, 09 Dec 2009 10:37:28 -0500

I am working on addressing the crypto-agility needs of HIP, and feel 
that I should go as far as possible.  Thus instead of staying locked in 
to HMAC of the selected hash, I want to allow other MACs, most likely 
CMAC and GMAC as they are 'NIST approved' (for some case of approved :) ).

So of course there are a couple of uses of HMAC, from MACing within the 
protocol to the KDF.  The NIST documents explain how to use these MACs 
for their data MACing purpose, but I am hazy on the KDF part, 
particularly in light of the KDF discussions going on here.

So for my 1st approximation of KDFs based on CMAC or GMAC, can they be 
directly substituted for HMAC.  I think that part of the answer for GMAC 
will be 'where is the IV'...

The 2nd level becomes a best practice KDF available now (or in the next 
2 months) that supports a selection of interchangeable MACs.

Or do we write up the KDF separately for each supported MAC.

---

From: Hugo Krawczyk <[email-masked]>
Date: Wed, 9 Dec 2009 12:29:40 -0500

Bob,

I believe these questions were answered in recent discussions in the list,
in particular the recent exchange with Zooko.
At the risk of boring everyone else, I will repeat:

*Being a secure MAC does NOT mean being a secure KDF*. That is, you can have
a very secure MAC that is a bad KDF, and a very insecure MAC that is very
secure as KDF. In particular, one essential difference between the two
functionalities is: a MAC function does NOT exist without a secret key and a
HKDF does NOT have a secret key.

That is why the proposed scheme is called HKDF and not HMAC. It is NOT the
same construction even if HKDF uses HMAC as a component.

Regarding GMAC please also see the recent exchange with Zooko.
The same considerations as for using Poly1305 or UMAC apply to GMAC. You
could use GHASH as part of (a statistical) extractor/KDF but then you would
need much larger parameters than those used for GMAC as MAC and other
additional processing.

As for CMAC, you could use it, in principle, but you would need to be
careful about HOW to use it. In particular, how are you going to key the
cipher, what happens when you need more bits of output than those coming out
of the cipher (e.g. you want a key for AES-256 but the output is only 128
bits), and even  if your application can get all things right, the
analytical results for this construction are weaker than for HMAC. For
example, the only results we have for block ciphers as extractors assume
these ciphers are ideal random permutations (even if you can use salt to key
the cipher) while for HMAC, in many usage scenarios you do not need to
resort to ideal assumptions.

Hugo

On Wed, Dec 9, 2009 at 10:37 AM, Robert Moskowitz
<[email-masked]>wrote:

> I am working on addressing the crypto-agility needs of HIP, and feel that I
> should go as far as possible.  Thus instead of staying locked in to HMAC of
> the selected hash, I want to allow other MACs, most likely CMAC and GMAC as
> they are 'NIST approved' (for some case of approved :) ).
>
> protocol to the KDF.  The NIST documents explain how to use these MACs for
> their data MACing purpose, but I am hazy on the KDF part, particularly in
> light of the KDF discussions going on here.
>
> The 2nd level becomes a best practice KDF available now (or in the next 2
> months) that supports a selection of interchangeable MACs.
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Zooko Wilcox-O'Hearn <[email-masked]>
Date: Wed, 9 Dec 2009 11:15:00 -0700

There are a lot of questions that I don't yet understand the answers  
to.  The first one is: what is the definition of a secure KDF?

I didn't see such a definition in the HKDF paper [1].  If we have a  
definition, then we can productively argue about whether this or that  
algorithm will meet the goal.

Clearly we haven't achieved this first step yet, since Hugo Krawczyk  
writes:  "a MAC function does NOT exist without a secret key and a  
HKDF does NOT have a secret key.".  This surprises me because I think  
of a KDF as having a secret key, and in particular HKDF has a secret  
key, named "SKM" on page 1 of hkdf.pdf.

Naor and Reingold [2] suggest that the formal definition of a MAC is  
an Unpredictable Function.  I think they are right.  They also show a  
black-box reduction from UF to PRF.

An Unpredictable Function is one where if I give you black-box access  
to it, i.e. you can invoke it but you can't examine its  
implementation, then you won't be able to predict what f(x) will  
return for some x that you didn't actually invoke it with.

Now an Unpredictable Function is an unkeyed thing, but a KDF (in my  
view) has a secret key which is unknown to the adversary.  So let's  
model that by saying that we use the key to select one Unpredictable  
Function, f_s(), out of a family of Unpredictable Functions.

Does anyone agree that this notion of a function chosen from a family  
of Unpredictable Functions is a good enough definition of what we  
want out of our KDFs?

Regards,

Zooko Wilcox-O'Hearn

[1] Hugo Krawczyk: "On Extract-then-Expand Key Derivation Functions  
and an HMAC-based KDF" http://webee.technion.ac.il/~hugo/kdf/kdf.pdf
[2] Moni Naor, Omer Reingold: "From unpredictability to  
indistinguishability: A simple construction of pseudo-random  
functions from MACs" http://citeseerx.ist.psu.edu/viewdoc/summary? 
doi=10.1.1.121.6517
---
Your cloud storage provider does not need access to your data.
Tahoe-LAFS -- http://allmydata.org

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 09 Dec 2009 13:41:36 -0500

Hugo Krawczyk wrote:
> Bob,
>
> I believe these questions were answered in recent discussions in the 
> list, in particular the recent exchange with Zooko.

Thank you for the quick reply.  This issue, for me, has only come to the 
top of my thoughts in the past couple days.  At least I figured out to 
come over to this list to look for some answers and I was getting lost 
in some of the discussions so figured, "take it on the chin, just get up 
and ask."

Well there goes a good arguement based on smaller code base through 
component reuse!

> At the risk of boring everyone else, I will repeat:

And now I will have to study this carefully.

>
> *Being a secure MAC does NOT mean being a secure KDF*. That is, you 
> can have a very secure MAC that is a bad KDF, and a very insecure MAC 
> that is very secure as KDF. In particular, one essential difference 
> between the two functionalities is: a MAC function does NOT exist 
> without a secret key and a HKDF does NOT have a secret key.
>
> That is why the proposed scheme is called HKDF and not HMAC. It is NOT 
> the same construction even if HKDF uses HMAC as a component.
>
> The same considerations as for using Poly1305 or UMAC apply to GMAC. 
> You could use GHASH as part of (a statistical) extractor/KDF but then 
> you would need much larger parameters than those used for GMAC as MAC 
> and other additional processing.
>
> careful about HOW to use it. In particular, how are you going to key 
> the cipher, what happens when you need more bits of output than those 
> coming out of the cipher (e.g. you want a key for AES-256 but the 
> output is only 128 bits), and even  if your application can get all 
> things right, the analytical results for this construction are weaker 
> than for HMAC. For example, the only results we have for block ciphers 
> as extractors assume these ciphers are ideal random permutations (even 
> if you can use salt to key the cipher) while for HMAC, in many usage 
> scenarios you do not need to resort to ideal assumptions.
>
> Hugo
>
> <[email-masked] <mailto:[email-masked]>> wrote:
>
>     I am working on addressing the crypto-agility needs of HIP, and
>     feel that I should go as far as possible.  Thus instead of staying
>     locked in to HMAC of the selected hash, I want to allow other
>     MACs, most likely CMAC and GMAC as they are 'NIST approved' (for
>     some case of approved :) ).
>
>     So of course there are a couple of uses of HMAC, from MACing
>     within the protocol to the KDF.  The NIST documents explain how to
>     use these MACs for their data MACing purpose, but I am hazy on the
>     KDF part, particularly in light of the KDF discussions going on here.
>
>     So for my 1st approximation of KDFs based on CMAC or GMAC, can
>     they be directly substituted for HMAC.  I think that part of the
>     answer for GMAC will be 'where is the IV'...
>
>     The 2nd level becomes a best practice KDF available now (or in the
>     next 2 months) that supports a selection of interchangeable MACs.
>
>     [email-masked] <mailto:[email-masked]>
> ------------------------------------------------------------------------
>

---

From: "Santosh Chokhani" <[email-masked]>
Date: Wed, 9 Dec 2009 13:45:52 -0500

I thought all KDF and HMAC functions are white box functions, assuming
key is part of input to the function. 

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Zooko Wilcox-O'Hearn
Sent: Wednesday, December 09, 2009 1:15 PM
To: [email-masked]
Subject: Re: [Cfrg] Can CMAC and/or GMAC be substituted in an
HMAC-styledKDF?

There are a lot of questions that I don't yet understand the answers to.
The first one is: what is the definition of a secure KDF?

Clearly we haven't achieved this first step yet, since Hugo Krawczyk
writes:  "a MAC function does NOT exist without a secret key and a HKDF
does NOT have a secret key.".  This surprises me because I think of a
KDF as having a secret key, and in particular HKDF has a secret key,
named "SKM" on page 1 of hkdf.pdf.

Naor and Reingold [2] suggest that the formal definition of a MAC is an
Unpredictable Function.  I think they are right.  They also show a
black-box reduction from UF to PRF.

An Unpredictable Function is one where if I give you black-box access to
it, i.e. you can invoke it but you can't examine its implementation,
then you won't be able to predict what f(x) will return for some x that
you didn't actually invoke it with.

Does anyone agree that this notion of a function chosen from a family of
Unpredictable Functions is a good enough definition of what we want out
of our KDFs?

Regards,

Zooko Wilcox-O'Hearn

[1] Hugo Krawczyk: "On Extract-then-Expand Key Derivation Functions and
an HMAC-based KDF" http://webee.technion.ac.il/~hugo/kdf/kdf.pdf
[2] Moni Naor, Omer Reingold: "From unpredictability to
indistinguishability: A simple construction of pseudo-random functions
from MACs" http://citeseerx.ist.psu.edu/viewdoc/summary? 
doi=10.1.1.121.6517
---
Your cloud storage provider does not need access to your data.
Tahoe-LAFS -- http://allmydata.org

---

From: Hugo Krawczyk <[email-masked]>
Date: Wed, 9 Dec 2009 13:57:11 -0500

The HKDF paper does have a (very detailed) definition: See appendix B.
(I have a somewhat more complete/formal version which I can send to you
off-line but I do not think it makes a significant difference for the
understanding)

You can think of the KDF definition, essentially, as a computational
extractor: It gets as input a sample from a Source of Keying Material SKM,
is keyed with a salt value XTS (for eXTractor Salt), a length parameter L
and outputs L bits that are computationally indistinguishable from the
uniform distribution for any SKM that has sufficiently high entropy.
Actually what differentiates a KDF from a computational extractor as above
is that it gets another "context parameter" CTXT that represents some
context information to be bound to the key (such as a session id, a protocol
identifier, etc). This CTXT parameter can be chosen by the adversary and you
want that the output of the KDF with same SKM but different CTXT values to
be computationally independent (i.e., seeing the output with CTXT gives no
efficiently computable information about the output with any other value
CTXT' ).

The core technique for building such KDFs is to first extract  a short but
cryptographically strong key K from the SKM and then use K as a key to a PRF
(with variable length output) and using CTXT as part of the input to the
PRF.

If you want to use an "unpredictable function" as the single KDF you need to
argue why that is secure in the above sense. Or why the definition sketched
above is not the  right one.

One last remark: If you want to use the SKM as a key to any function (as you
seem to indicate), you need to argue that this "any function" has whatever
properties you are assuming when keyed with a high-entropy but NOT UNIFORM
(or not pseudorandom) key. ALso, note that as you say correctly, MAC
functions are unpredictable but this is guaranteed only when they are keyed
with a UNIFORM (or pseudo-random) key -- nothing can be said for
high-entropy non-uniform keys -- and even then the output of the MAC must
not be pseudorandom. If you use a PRF instead the MAC, then the output is
pseudo-random but ONLY when keyed with a UNIFORM (or pseudorandom) key which
you do NOT have in KDF context (if you had such a PRF key to start with you
could use any PRF to expand it -- no need for extraction.

Hugo

On Wed, Dec 9, 2009 at 1:15 PM, Zooko Wilcox-O'Hearn <[email-masked]>wrote:

> writes:  "a MAC function does NOT exist without a secret key and a HKDF does
> NOT have a secret key.".  This surprises me because I think of a KDF as
> having a secret key, and in particular HKDF has a secret key, named "SKM" on
> page 1 of hkdf.pdf.
>
> Unpredictable Function.  I think they are right.  They also show a black-box
> reduction from UF to PRF.
>
> it, i.e. you can invoke it but you can't examine its implementation, then
> you won't be able to predict what f(x) will return for some x that you
> didn't actually invoke it with.
>
> Now an Unpredictable Function is an unkeyed thing, but a KDF (in my view)
> has a secret key which is unknown to the adversary.  So let's model that by
> saying that we use the key to select one Unpredictable Function, f_s(), out
> of a family of Unpredictable Functions.
>
> Unpredictable Functions is a good enough definition of what we want out of
> our KDFs?
>
> Regards,
>
> Zooko Wilcox-O'Hearn
>
> [1] Hugo Krawczyk: "On Extract-then-Expand Key Derivation Functions and an
> HMAC-based KDF" http://webee.technion.ac.il/~hugo/kdf/kdf.pdf<http://webee.technion.ac.il/%7Ehugo/kdf/kdf.pdf>
> indistinguishability: A simple construction of pseudo-random functions from
> MACs" http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.6517
> ---

---

From: "Dan Brown" <[email-masked]>
Date: Wed, 9 Dec 2009 15:41:51 -0500

This raises a minor, non-security issue: isn't a KDF a lower level primitive than a MAC?  E.g. the key in a MAC is one of the intended purposes of the output of a KDF, not the other way.   If so, isn't it architecturally awkward to define a KDF that has built-in component of a MAC?  E.g. HKDF has HMAC built-in. 

More philosophically, is building new primitives from old primitives, where the old have to do more than their original aim (e.g. HMAC as more than MAC, SHA1 as more than CRHF) the wisest approach?  Does it put too much reliance on these retrofitted primitives?

---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.

---

From: Hugo Krawczyk <[email-masked]>
Date: Wed, 9 Dec 2009 18:41:02 -0500

On Wed, Dec 9, 2009 at 3:41 PM, Dan Brown <[email-masked]> wrote:

> This raises a minor, non-security issue: isn't a KDF a lower level
> primitive than a MAC?  E.g. the key in a MAC is one of the intended purposes
> of the output of a KDF, not the other way.   If so, isn't it architecturally
> awkward to define a KDF that has built-in component of a MAC?  E.g. HKDF has
> HMAC built-in.
>

We are building HKDF on HMAC not on a generic MAC (did I say that before?)
We are using specific properties of the HMAC scheme (with suitable
assumptions on the underlying hash function) and not those of a MAC.
If at all, we are building on HMAC being a PRF since we are using it for the
expansion part as such.

But for extraction you need other properties.  These properties change
according to the usage scenario and what you can assume about your source of
keying material. In some cases you need to assume more than a MAC and PRF,
namely, model the hash function as a random oracle (especially when you do
not have a salt value and you need to output almost all entropy of the
source). In other cases, you need MUCH LESS than PRF/MAC, namely, just
properties of universal hashing from the underlying hash function. Such
properties are combinatorial in nature and do not require, in principle,
computational assumptions let alone the idealized modeling of random
oracles.

So, for extraction, sometimes you are assuming more from the hash functions
than what you need for MAC/PRF and sometimes less.

But however you define the KDF functionality, and however you build it,
remember that a KDF is in particular a PRF (this is actually the easy case,
when your source of keying material is uniform or pseudo-random and you need
to produce more pseudorandom bits than the input). Thus for the whole
construction you cannot avoid having some form of pseudorandomness
assumption.

> More philosophically, is building new primitives from old primitives, where
> the old have to do more than their original aim (e.g. HMAC as more than MAC,
> SHA1 as more than CRHF) the wisest approach?  Does it put too much reliance
> on these retrofitted primitives?
>

If you can build a generic KDF based on MAC and collision resistance only,
you are more than welcome to present it.
Remember that you will need to first be able to build a PRF out of these
properties, a simpler task which I do not know how to accomplish.

On the other hand, why rely on collision resistance which may be the weakest
point of hash functions anyway?

Would you feel better with the traditional KDFs of the form Hash (SKM||1) ||
Hash(SKM||2)||...
that may only be justified assuming Hash is a random oracle (which is more
than a MAC, PRF, collision resistance, universal hashing, etc,)???
Would you even buy that construction as a PRF (which as said, is a
particular case of a KDF)??

Hugo

> This transmission (including any attachments) may contain confidential
> information, privileged material (including material protected by the
> solicitor-client or other applicable privileges), or constitute non-public
> information. Any use of this information by anyone other than the intended
> recipient is prohibited. If you have received this transmission in error,
> please immediately reply to the sender and delete this information from your
> system. Use, dissemination, distribution, or reproduction of this
> transmission by unintended recipients is not authorized and may be unlawful.

---

From: David McGrew <[email-masked]>
Date: Sat, 19 Dec 2009 06:20:30 -0800

Hi Zooko,

On Dec 9, 2009, at 10:15 AM, Zooko Wilcox-O'Hearn wrote:

> definition, then we can productively argue about whether this or  
> that algorithm will meet the goal.

I agree that it would be useful to come up with a definition of what  
we expect from a KDF.   I don't think the HKDF paper has a concise  
definition.  The really important aspect to capture is that of the  
computational extractor.  If I recall correctly, that paper cites a  
definition of computational min-entropy, but the definition was not  
immediately applicable (or at least I couldn't see how to apply it).

> HKDF does NOT have a secret key.".  This surprises me because I  
> think of a KDF as having a secret key, and in particular HKDF has a  
> secret key, named "SKM" on page 1 of hkdf.pdf.

The important aspect here is that SKM is not uniformly random, but  
instead has a min-entropy that has a known lower bound.

A document that defined of a KDF and that explained (computational)  
min-entropy and (computational) extractors would be valuable.  If we  
can find enough people to write and review this work, it would be  
valuable to have it as a CFRG draft.   I think that a good approach  
here would be to write it up as something like a requirements  
document, saying what applications the KDF is targeting (this was  
already discussed on the list), what assumptions go into its use, and  
what security properties it should have.   This approach would make  
the new work a nice complement to the HKDF draft.   Any other thoughts?

David

> an Unpredictable Function.  I think they are right.  They also show  
> a black-box reduction from UF to PRF.
>
> An Unpredictable Function is one where if I give you black-box  
> access to it, i.e. you can invoke it but you can't examine its  
> Does anyone agree that this notion of a function chosen from a  
> family of Unpredictable Functions is a good enough definition of  
> what we want out of our KDFs?
>
> Regards,
>
> Zooko Wilcox-O'Hearn
>
> functions from MACs" http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.6517
> ---

---

From: Sean Shen 沈烁 <[email-masked]>
Date: Mon, 21 Dec 2009 10:21:46 +0800

Hi，David, Zooko and CRFG,
I would like to contribute on such a document.
Best,

Sean

> definition.  The really important aspect to capture is that of the
computational
> extractor.  If I recall correctly, that paper cites a definition of
computational
> min-entropy, but the definition was not immediately applicable (or at
least I
> couldn't see how to apply it).
> 
> >
> The important aspect here is that SKM is not uniformly random, but instead
has
> a min-entropy that has a known lower bound.
> 
> min-entropy and (computational) extractors would be valuable.  If we can
find
> enough people to write and review this work, it would be
> here would be to write it up as something like a requirements document,
> saying what applications the KDF is targeting (this was already discussed
on
> the list), what assumptions go into its use, and