Length of truncated HMAC output

Question

RFC 2104 says:

Applications of HMAC can choose to truncate the output of HMAC by outputting the t leftmost bits of the HMAC computation for some parameter t [...]. We recommend that the output length t be not less than half the length of the hash output (to match the birthday attack bound) and not less than 80 bits (a suitable lower bound on the number of bits that need to be predicted by an attacker).

Obviously, different lengths of HMAC outputs provide different levels of security. What's not obvious to me, is: If one needs the security provided by a 128-bit MAC, why is HMAC-SHA-256 suitable to generate such (half the length of the hash = 128 bits) but HMAC-SHA-512 is not (half the length of the hash = 256 bits)?

Answer 1

HMAC doesn't suffer the issue with collision resistance (in other words: the birthday bound does not apply). This is simply because an attacker doesn't have the secret key used to generate the HMAC authentication tag, so there is no way to build a huge table of possible outputs that can be compared against.

So usually the security of a hash is defined as half the number of output bits because of the birthday bound. To get the same level of security you can therefore output half of the output bits of HMAC because the birthday attacks do not apply.

You can use HMAC-SHA-512 to generate 128 bits of security by using the leftmost 128 bits (and it may even be slightly faster than HMAC-SHA-256 for large messages on a 64 bit CPU). But it won't provide the 256 bits of security that SHA-512 promises; this is what the RFC tries to communicate.

---

Note that the 80 bit security is half the output size of SHA-1 (or RIPEMD-160 for that matter). Nowadays 80 bits is not considered (all that) secure anymore.