Security of N bit HMAC

Question

Lets say that I am using 128 bit HMAC. How many operations are needed to find a "non secure" message. Is a birthday attack possible?

Answer 1

The short answer is: $2^{128}$ operations, no known birthday-like attack.

The long answer: when HMAC was first published, it came with a security proof, tailored for iterated constructions like Merkle-Damgård. In a MD hash function (MD4, MD5 and the whole SHA family are MD hash functions), the data to hash is processed by blocks with a compression function: the compression function takes as input the block and the current state (the state is a 128-bit value for a function with a 128-bit output), and produces the new state (which will be used as input for the processing of the next block). The final state is the function output.

The original proof claimed that if the compression function is a PRF (i.e. the choice of a block value "selects" the compression function as if randomly among functions which take the state as input and produce the corresponding output) and the hash function is collision-resistant (in a "weak" way; it needs not be resistant to all kinds of collisions) then HMAC is secure. That proof worked up to $2^{n/2}$ invocations of the compression function (for a hash function with a $n$-bit output). Later on, Bellare published a new security proof which removes the condition on weak collision resistance, and enhances proven security up to $2^{n}$ .

Now the fine print: the security proof works only as long as the PRF assumption holds. However, if the PRF assumption holds, then the hash function which uses that compression function in the MD construction is necessarily resistant to collisions up to $2^{n/2}$. Therefore, if a MD-like hash function is proven not to be collision resistant up to $2^{n/2}$, then this implies that its underlying compression function is not as PRF as it should. This is true, in particular, for MD4, MD5, SHA-0 and SHA-1. For these functions, the PRF assumption cannot be held, hence the HMAC security proof is not applicable to HMAC/MD4, HMAC/MD5, HMAC/SHA-0 and HMAC/SHA-1. This does not mean that we know a way to turn collision attacks into attacks on HMAC. Indeed there is no known attack faster than $2^{128}$ on HMAC/MD5. However, there is a known forgery attack on HMAC/MD4. Note that this attack has cost $2^{58}$, which is quite a lot (and explains why the attack was never actually demonstrated), whereas resistance of MD4 to collisions is, by itself, zero (generating the collision takes less time than simply hashing the two messages to verify that it works).

Also, all these proofs are for MD-like constructions and do not apply, directly, to non-MD functions. However, one can say that HMAC is defined as it is, with its two nested hash function invocations, precisely to overcome some shortcomings of the MD construction. So there is "no reason" why a non-MD hash function would not do fine in HMAC. Most SHA-3 candidates include statements and/or proofs of security of the hash function when used in HMAC.