Here is the post that explains the failure for doing h(k||m) and I understand it.

But I don't understand how h(m||k) is subjected to collison attack, or birthday attack. Please explain?


The birthday attack can be used with every hash function. It's a simple matter of probability (see: birthday problem). However, that only means that a hash function has to generate $2n$ of output to achieve $n$ bits of security.

It's fairly obvious that $H(m||k)$ is collision-resistant provided that $H$ itself is collision-resistant, since $H(m_1||k)=H(m_2||k)$ would imply that $H(x)=H(y)$ for $x=m_1||k$ and $y=m_2||k$.

However, the big advantage of HMAC over $H(m||k)$ is that collision-resistance of the underlying hashing function is not needed. Bellare proves in New Proofs for NMAC and HMAC: Security without Collision-Resistance that HMAC is secure as long as $H$ is a pseudorandom function, which is considerably weaker than collision-resistance.

Thus, even though the once popular hashing functions $MD5$ and $SHA$ are already broken, $HMAC_{MD5}$ and $HMAC_{SHA}$ are stil considered secure.

  • $\begingroup$ OKay. I read it again. Basically, if the assumption that the hash function is not crypto-safe anymore, then we will see collision at some point. But what about H(K||X). If we use MD5, we not only experience length extension attack, but also collision attack, right? $\endgroup$
    – CppLearner
    Dec 17 '12 at 6:17
  • 1
    $\begingroup$ @CppLearner A collision attack for $H(K||X)$ with secret (short) $K$ would also lead to a collision attack on $HMAC_H(K', X)$ with a similar $K'$ (just $K$ XORed with the ipad constant). For now, there is no known way to do this. $\endgroup$ Dec 17 '12 at 8:29

The MAC algorithm you describe is called "the secret suffix method" in that paper. See the following paper, which shows how to attack the secret suffix method:

The paper describes how to use internal collisions to attack the MAC algorithm you describe. They use a birthday attack to find internal collisions, and then show how this allows attacks on the secret-suffix MAC. Crucially, almost all of the workload of the attack can be done entirely offline.

In contrast, HMAC and other good MAC algorithms are designed to make those kinds of attacks much more expensive. Yes, you can do birthday attacks on HMAC, but it has to be an online attack, and the attack requires a lot of chosen plaintext -- which makes the corresponding attacks on HMAC much harder to mount in practice. This is one reason why HMAC and other modern MAC algorithms are considered strongly preferable over "the secret suffix method", and why cryptographers recommend that no one should use the secret suffix method.


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.