What are the implications of a birthday attack on a HMAC?

Question

After collecting approximately $2^{n/2}$ message-tag pairs a collision can be observed. So two different messages (m1 and m2) will have the same tag.

This paper states:

Then, for any string x, (m1,x) and (m2,x) have the same tags (with high probability in the case of HMAC, and with certainty in the case of CMAC). The attacker can then request for the tag of (m1,x), thereby also obtaining the tag if (m2,x).

Does this mean that it is possible to attach any string x on m1 and the tag of it will be the same as the tag for x attached to m2?

If my assumption is true could this be considered as a length extension attack?

Answer 1

This is like stating that $H(C_1|m_1|x|C_2) = H(C_1|m_2|x|C_2)$ if $H(C_1|m_1|C_2) = H(C_1|m_2|C_2)$ for HMAC.

That is probably correct if $H$ is a hash function based on Merkle–Damgård construction (such as SHA-1 and SHA-2) and if $m_1$ and $m_2$ end on block boundaries.

$H(C_1|m_1|C_2) = H(C_1|m_2|C_2)$ implies that the state after hashing $C_1$ and $m_1$ is identical to hashing $C_1$ and $m_2$. So adding any data to either one will result in the same hash.

If however $m$ doesn't end on a block boundary then changing the data coming after $m$ will still alter the state after the block has been hashed; it is extremely unlikely that the result will be the same for $m_1$ and $m_2$ (if $m_1$ and $m_2$ differ for the last block of course). If $m_1$ and $m_2$ can be chosen freely then this situation can be avoided.

---

The situation for CMAC (and CBC-MAC) will be more or less identical. CBC is however explicit while Merkle–Damgård isn't. So this seems indeed more true for CMAC.

---

If my assumption is true could this be considered as a length extension attack?

You could call this a length extension attack, it's at least pretty similar to one. With additional data coming after it it's more a kind of insertion attack, but the principles are the same.

Note that this is only applicable to the insertion of $x$, not the rest of the attack.

Answer 2

Does this mean that it is possible to attach any string x on m1 and the tag of it will be the same as the tag for x attached to m2?

Yes. If using HMAC, then with high probability, the tag on (m1, x) will be the same as the tag on (m2, x). With CMAC, the attack works with probability 1.

If my assumption is true could this be considered as a length extension attack?

I wouldn't call it a length extension attack. Length extension attacks are typically seen when discussing a MAC of the form $H(k||m)$. Due to the way some hash functions operate, computing a MAC of this form can allow an attacker to get a valid MAC on a message $m||m'$.

So here are some differences between length extension and this birthday-style attack:

1. A length extension attack only requires one query from the bad MAC function. The birthday-style attack requires many. Thus, even for a secure hash function, the traditional length extension will work, but this attack is infeasible for a good hash function.
2. Length extension works with probability 1; this attack works with "high probability" for HMAC, but less than 1.
3. After the initial query, a length extension attack requires no additional queries. After the initial collision, this attack requires one additional query.