12
$\begingroup$

First, let me clarify what I mean with a Key Derivation Function (KDF). I'm interested in KDFs that take an $n$-bit symmetric master key and some diversification data of arbitrary length as input and produce an $n$-bit symmetric key as output that can be used in subsequent cryptographic operations.

It seems to me that such KDFs have much in common with MACs:

  • A key and data as input and an output that has the same length as the input key;
  • The output should be unforgeable for an attacker who does not have access to the input key;
  • The probability of producing equal outputs for unequal inputs should be negligible.

Hence my question: is it secure to use any secure MAC algorithm as a KDF?

$\endgroup$
  • 5
    $\begingroup$ "an output that has the same length as the input key"; huh? That's not true in general of either KDFs or MACs. $\endgroup$ – poncho Jun 22 '16 at 13:57
18
$\begingroup$

No. A MAC guarantees unforgeability but not pseudorandomness. It is true that all MACs that I can think of right now are essential pseudorandom functions, but this does not mean that the MAC definition implies this. Indeed, it clearly does not.

So, conceptually, you need a pseudorandom function. You can assume that HMAC is a pseudorandom function. It is proven that CBC-MAC on prefix-free inputs behaves like a pseudorandom function. But this doesn't mean that it's always the case.

$\endgroup$
  • $\begingroup$ Ok that's very clear, thanks! Can I conclude from this that any PRF can be used as a KDF? $\endgroup$ – Job Jun 23 '16 at 7:28
  • $\begingroup$ Yes. But, it needs to have the same domain as the message space, and needs to have a large enough range so that you can't guess a MAC tag with non-negligible probability. $\endgroup$ – Yehuda Lindell Jun 23 '16 at 12:00
4
$\begingroup$

Like Yehuda Lindell already wrote, MAC does not imply PRF, which is pretty much what you would want from a KDF.

Additionally, some of your assumptions are not correct:

  • A key and data as input and an output that has the same length as the input key;

This is frequently not the case with MACs. For example, when you use any MAC based on AES-256 (like CMAC, GMAC, Poly1305-AES) you will likely have at most a 128-bit authentication tag. And frequently much shorter tags are used, like by truncating the MAC to a desired length.

(KDFs often allow larger output, so that they can be used to derive multiple keys.)

  • The output should be unforgeable for an attacker who does not have access to the input key;

This is true.

  • The probability of producing equal outputs for unequal inputs should be negligible.

This is again not required and in fact often not the case – short MACs have non-negligible collision chance. Instead, outputs should be "unrelated", i.e. seeing some outputs cannot help forge others.


In practice many MACs are (believed to be) PRF. E.g. HMAC, CMAC, SipHash, etc. Most MACs based on a universal hash + a PRF are likewise PRF. So as long as the MAC output is large enough, you may be okay, but you should check the particular MAC that you are using.

$\endgroup$
  • 1
    $\begingroup$ "So as long as the MAC output is large enough, you may be okay" I guess that rules out CBC-MAC for (T)DES (of any other 64 bit block cipher) so we actually have an example where a relatively secure MAC is absolutely not fit for use as KDF. $\endgroup$ – Maarten Bodewes Jun 22 '16 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.