# Security of N bit HMAC

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?

-

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.

-
It might be worth restating that these security properties of HMAC rely on the attacker not having significant knowledge of the secret key, i.e., the key must represent at least 128 bits of entropy to the attacker. Sometimes you see HMAC used as an ordinary hash function with a fixed 'key' input, or the key might be something weak like a password. – Marsh Ray Aug 3 '11 at 7:28
I would disagree that existence of collisions violates the PRF assumption. The PRF property talks about the function behaviour when one of inputs is randomly chosen, whereas the collision is a property of only two function inputs. Moreover, all compression functions have collisions, which certainly does not imply that there is no PRF among them. – Dmitry Khovratovich Apr 21 '14 at 14:26