Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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: ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a2192992a274fc1a836ba3c23a3feebbd454d4423643ce80e2a9ac94fa54ca49f

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

3f78f631195be2c7675973fb6c542a7b9b6cda1e6ba59bd1093ebacf70408f530000000000000000000000000000000000000000000000000000000000000000

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

ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a

Then it now becomes:

ddaf35a193617abacc417349ae20413112e6fa4e89a97ea20a9eeee64b55d39a0000000000000000000000000000000000000000000000000000000000000000

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.

share|improve this question
    
128-bit security is very strong w.r.t. brute force search, and 256-bit security is over 300.000.000.000.000.000.000.000.000.000.000.000.000 times stronger (to classical computers); does that "look strong" enough to you? HMAC does not aim at being stronger than its output width. See this related answer. –  fgrieu Apr 23 at 6:25
    
You asking nine (9) questions in total. You might want to split that up into separate and more specific questions, so people don’t have to write a book to be able to provide a useful and complete answer. –  e-sushi Apr 23 at 19:55
    
@fgrieu - I am mainly interested in the special case where the key is the exact length of the block size of the hash (ie 512 bits). This allows the full key to be input without hashing or zero padding the key. This appears to provide a stronger output than the other two options as the full key is used without alteration. Why was it designed to have distinct differences in output quality depending on the key size, but have the strongest output if the key is exactly the length of the block size? Is this a deliberate weakness in the design? Is there an internal nsa memo specifying the proper use? –  user13183 Apr 23 at 22:33
    
HMAC is NIST-endorsed, but I have no indication that its claimed inventors M. Bellare, R. Canetti, and H. Krawczyk) are affiliated to the NSA. Again, HMAC aims at a security level against key search equal to its output size, and thus does not need a wider key. There is not indication that it would much increase practical security: if a 256-bit random key can be found, we should fear that a 512-bit one can be found by similar means (which can't be key brute-force key search) with marginally more effort. –  fgrieu Apr 23 at 23:12
    
@e-sushi, let me try consolidate a few of the questions. And fgrieu answered a couple of them with his link in the comments so I will take those out. –  user13183 Apr 23 at 23:45
show 5 more comments

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
Thank you, great answer Richie. A few quick follow up questions, feel free to update your answer: seeing it would be preferred to avoid NMAC as it modifies the IVs of the hash function, what happens if you just do H(k1 || H(k2 || m)) as is by splitting a key into two pieces, is there anything wrong with that? Or even simply doing H(k || H(k || m)) with the full length key, rather than padding the key like in HMAC, is this stronger? Perhaps this could be used as a generic strengthening method on the keyed hash in case some other attack can uncover the internal state of Keccac in future. –  user13183 Apr 25 at 7:58
    
Same key with no padding is weaker (H now has the same IV), 2 independent keys is stronger. For MD hashes anyway, for sponges I cant say for sure –  Richie Frame Apr 25 at 9:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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