6
$\begingroup$

I'm quite new to this topic and have several questions concerning HMAC and NMAC:

  • Why does NMAC need two keys? How can it be attacked if we just used some sort of initialization vector instead of the first/second key?

  • What is the purpose of ipad and opad in HMAC?

  • What if the key is longer than the block size?

  • Can the key be longer than the number of input bits of a hash function?
$\endgroup$
9
$\begingroup$

NMAC is really just an "education tool" on the way to HMAC and I don't think anyone intended it to be used. The two keys are needed since the first and second hashes have different purposes. The first hash on the message is just needed to get collision resistance, whereas the second hash is supposed to provide a pseudorandom function type property. As such, it actually suffices to have just one key (on the second hash). However, the first key is included as a conservative measure so that even if the hash is broken and collisions can be found, it does not mean that NMAC/HMAC are broken since the attacker has to find a collision where a key is used that it doesn't know. The best way to look at NMAC/HMAC is a specific implementation of "hash and MAC" (analogous to "hash and sign").

The purpose of ipad and opad in HMAC is to get computationally independent keys for the first and second hashes. If we assume that the compression function acts like a pseudorandom generator when used in this special way with ipad and opad, then this follows. (It of course follows immediately in the random oracle model, but this is overkill and not needed.)

Nothing inherently bad happens if the key is longer than the block size, but nothing is gained either.

I'm not sure what you mean by the key being longer than the number of inputs bits of the hash function. I guess that you mean the compression function (since the hash function is practically unlimited). If yes, then the key can be longer, but nothing is gained by it, so you shouldn't do it.

$\endgroup$
  • $\begingroup$ Thank you, yes the last question was a bit ignorant ... $\endgroup$ – user3142067 Jul 22 '15 at 9:50
3
$\begingroup$

Adding to Yehuda Lindell's answer, there are two special cases that one should take care to avoid:

  • If the HMAC key $k$ is longer than the block size of $H$, then it is compressed into $k' = H(k)$ and $k'$ is used instead with HMAC as usual. This means that there are easily constructed collisions in HMAC keys, namely $k' = H(k)$ and $k$ for any key $k$ that is longer than a block. Incautiously designed applications that use $k$ and $H(k)$, like the capability system of Tahoe-LAFS would be if it were incautiously designed, might step on this rake.

  • If the HMAC key is exactly one block long, or one bit shorter than a block, then two keys $k_0$ and $k_1$ might collide when padded: $k_0 \oplus \mathrm{ipad} = k_1 \oplus \mathrm{opad}$. A priori it is not obvious that this is a problem, but since the inner hash under $k_0$ coincides with the outer hash under $k_1$, $$\operatorname{HMAC-}\!H_{k_1}(\operatorname{HMAC-}\!H_{k_0}(m)) = H_{k_1 \oplus \mathrm{opad}}({H_{k'}}^2(H_{k_0 \oplus \mathrm{ipad}}(m))),$$ where $k' = k_0 \oplus \mathrm{ipad} = k_1 \oplus \mathrm{opad}$ and $H_\kappa(m) = H(\kappa \mathbin\| m)$. The ${H_{k'}}^2$ structure in the case of a block-long key poses a quadratic barrier to proving indifferentiability of the HMAC construction.

What this means is that there can be protocols in terms of a random function $F$ which are secure when instantiated with $F = f$ for a uniform random function $f$, but not when instantiated with $F = \operatorname{HMAC-}\!H_k$ for a uniform random $H$ and a uniform random key $k$ equal to or longer than one block length. The story may still be different when $H$ is chosen to be a particular fixed hash function rather than a uniform random function, but the indifferentiability bound about HMAC lets us focus on the properties of $H$ itself rather than on the HMAC construction.

Fortunately, every $H$ you are likely to use—MD5, SHA-1, SHA-2, SHA-3—has a block size of at least 512 bits, so the standard symmetric key size of 256 bits fits comfortably without danger of these collisions.

$\endgroup$

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.