Should HMAC or NMAC or plain Keccak be used for a secure MAC?

Question

After some digging around in the HMAC spec I found this (paraphrased):

Step 1: If the length of Key equals the block size of the hash function (512 bits/64 Bytes for SHA-256), set the key equal to the key. Go straight to step 4.

Step 2: If the length of key is greater than the block size of hash function, hash the key to obtain a string the same length as the hash function output, then append 0s up to the length of the Block Size.

Step 3: If the length of key is less than the block size of the hash function, append 0s to the end of the key so that the key length is now the same size as the block length.

So if you input a 512 bit key of:

ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a
2192992a274fc1a836ba3c23a3feebbd454d4423643ce80e2a9ac94fa54ca49f

Then it will be untouched. If however you add at least one Byte to the end e.g. 'aa', the key now becomes:

3f78f631195be2c7675973fb6c542a7b9b6cda1e6ba59bd1093ebacf70408f53
0000000000000000000000000000000000000000000000000000000000000000

Or if you have less than the block size, perhaps a 256 bit key of:

ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a

Then it now becomes:

ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a
0000000000000000000000000000000000000000000000000000000000000000

It would seem that the more secure way to use HMAC would be to input a key that is exactly equal to the block length of the cipher being used, which for SHA-256 would be 512 bits. This must give full 512 bit diffusion of the key into the HMAC. Otherwise HMAC will turn at least half of the key to zeros.

I did a bit more reading and found that the there is an NMAC spec which is similar to HMAC but requires two independent random keys:

NMAC = H(k1 || H(k2 || m)).

Questions:

• What is the security impact of having at least half the key as null Bytes in HMAC (which would happen in the majority of cases, unless care was taken to specifically choose key sizes the same length as the block size)?

• In general, which is the more secure construction, HMAC or NMAC? Given that the spec for HMAC seems to not use two independent random keys, but derives the inner and outer keys from the main key, and also weakens the main key in the first 3 steps.

• If I had a key longer than the block length of the hash function, would it be stronger to use the NMAC construction instead of HMAC? Perhaps by splitting the full random key in half to use as k1 and k2. For example, I have a random 768 bit key, I split that into two 384 bit keys then use that with NMAC. Under HMAC that 768 bit key would be reduced to 256 bits psuedo random concatenated with 256 bits of 00000000000000000000... In this case I think NMAC would be more secure, correct?

• I know HMAC is designed specifically for the Merkle–Damgård type hashes, but can Keccak (sponge construction) be used with HMAC? Or is it better to use it with the NMAC? Or simply do H(k || m) as the Keccac authors intended? Length extension attacks are no longer an issue for Keccak.

Answer 1

HMAC and NMAC make assumptions of the underlying hash function $H$ for their security proofs. Additionally they are designed to eliminate known flaws in other MAC constructions using MD type hashes.

NMAC is not $H(k1$ $||$ $H(k2$ $||$ $m))$, it actually uses the keys as the initial hash values, which require a higher level of access to the internals of the hash, meaning a large variety of implementations cannot use NMAC the same way they can use HMAC.

In response to your questions..

• For HMAC, when the key length is shorter than the block length, there is no exploitable impact on security due to padding with null bytes. The maximum security will be the output length of $H$ or the input length of $k$, whichever is shorter.

• NMAC is considered the stronger MAC, but because it requires modification of the initial hash value, it is less used in practice. Attacks on NMAC are applicable to HMAC, but not always the other way around. I would be concerned that there may be choices of IV that weaken $H$ with respect to it being a PRF, which could invalidate the security claims, however resistance against forgery in that case is most likely not compromised; this is only the case if the compression function is weak, and in that case there are other security issues with the hash.

• Once again, since NMAC modifies the IV, you cannot have keys larger than the output length of $H$ for MD type hash functions. In HMAC, a key larger than the block size is hashed down to the output size, so the maximum effective size of the key is smaller.

• Keccak can be used with HMAC but not NMAC, since the sponge construction security claim requires the state to be 0, and NMAC requires the state to be the key. The keyed sponge function $H(k$ $||$ $m)$ is likely more secure than HMAC for a given key length, due to the inner state being larger than the output length.

HMAC padding to the block size essentially allows a single iteration over that part of the message space to change the IV, making it closer to NMAC, since the next input to the compression function is the message. For HMAC, you will get the maximum security if the key length is equal to the blocklength, assuming that more security than the output length of $H$ can be achieved. The padding constants are there so the IV of both the inner and outer hash function are unique, but still related to $k$.

Keyed sponge functions gain security from capacity, with the bound being $min(2^{c-1}/M$ $,$ $2^k)$, where $c$ is the capacity, unless $M$ exceeds $2^{c/2}$. This means more security over large messages with a large enough capacity, since the security of HMAC starts to drop with every subsequent input block (correct me if I am wrong on that one), and is upper bound by $2^{c/2}$, where c is the digest size. This implies that a keyed sponge function can have a smaller capacity than is required for the security proof of HMAC, making it either more efficient or more secure given appropriate choice of $c$.

As fgrieu pointed out, HMAC and NMAC were not from NSA or NIST, but rather university research. The fact that NIST endorses it does not imply there is a weakness. The internal hash chain size is our limiting security factor here, as well as HMAC being constructed to make use of a hash function without limitation.