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

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?

• I would think that this is only true for HMAC if a Merkle-Damgård hash function is used – mikeazo Jul 23 '15 at 16:47
• @mikeazo I'm not sure if it is only true for Merkle-Damgård hash functions, but some kind of linearity in the way the input is treated seems required. – Maarten Bodewes Jul 23 '15 at 20:54

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.

• It's probably true for most hash functions, especially if they are linear in nature, but it would be possible to construct one that isn't. – Maarten Bodewes Jul 23 '15 at 17:11
• I would say it's an application of a length extension attack on the underlying hash function. – otus Jul 23 '15 at 19:31
• @otus Changed my mind on it. Would you agree with the current definition? – Maarten Bodewes Jul 23 '15 at 20:58

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.