5
$\begingroup$

HMACs depend on preimage resistance, or so I have read. The security strength of hash function with an $n$-bit output against collision attacks is $2^{\frac{n}{2}}$. Against preimage attacks, it is $2^{n}$. What is the security strength of an $n$-bit HMAC?

$\endgroup$
  • $\begingroup$ n bits against blindly guessing at tags, and an unknown amount against attacks that want their guesses at tags to have a non-negligibly higher probability of being correct. ​ (key-length will probably control the latter security level) ​ ​ ​ ​ $\endgroup$ – user991 Apr 11 '16 at 18:05
4
$\begingroup$

See NIST SP 800-107, section 5.3.4:

The effective security strength of the HMAC key is the minimum of the security strength of $K$ and the value of $2C$. That is, security strength = min(security strength of $K$, $2C$). For example, if the security strength of $K$ is 128 bits, and SHA-1 is used, then the effective security strength of the HMAC key is 128 bits, since for SHA-1, $2C = 320$. Note that, in this example, even if the security strength of $K$ is greater than 320 bits, the effective security strength of the key is limited to 320 bits (the value of $2C$ for SHA-1). In general, there is no benefit in generating $K$ with more than $2C$ bits of security. In particular, it is not sensible to generate $K$ with a bit length that exceeds the input block size of the approved $L$-bit hash function employed in the HMAC construction. Such a $K$ is hashed, and the resulting $L$-bit value is used instead. Returning to the SHA-1 example, suppose that the key $K$ has a bit length greater than 512 (the input block size for SHA-1). Instead of using $K$ directly, HMAC replaces $K$ by its 160-bit SHA-1 hash value, and so the effective security strength of that choice of $K$ is no more than 160 bits.

Note that $C$ is defined as the size of the chaining value in above, which is generally equal to the output size without any reduction (so 256 for SHA-224 and 512 for SHA-512/256).

This of course doesn't mean that the security of the HMAC isn't related to the output size. The above description shows the security of the key, not the security of the final hash. You won't get 512/1024 bit security when you only generate a 256 bit result. In general though the final strength should therefore be min(keysize, output_size).

$\endgroup$
  • $\begingroup$ Where does the value $2C$ come from? $\endgroup$ – Melab Apr 14 '16 at 21:41
  • $\begingroup$ Probably because the key is hashed twice, before and after the message (after XOR'ing the key with two different constant bit strings to create ipad & opad, to be precise). Not 100% on that, but it seems the most reasonable explanation. $\endgroup$ – Maarten Bodewes Apr 14 '16 at 21:42
  • $\begingroup$ The padded keys may be different, but they are not independent, so how could the strength of the key be larger than the key size? $r$ round keys derived from a key of size $k$ does not make the strength of a cipher equal to $r \times k$ bits. $\endgroup$ – Melab May 2 '16 at 15:55
  • $\begingroup$ "The effective security strength of the HMAC key is the minimum of the security strength of K and the value of 2C." So it isn't. For HMAC, the key size and key strength are usually 1:1 as 2C will be such a large value that it doesn't play any role. In other words, HMAC strength = key strength = key size. $\endgroup$ – Maarten Bodewes May 4 '16 at 16:20
  • $\begingroup$ So, the strength of the whole HMAC scheme is equal to the strength of the key? $\endgroup$ – Melab Jul 13 '17 at 17:57

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.