# Why is H(k || m || k) secure against birthday attack?

I don't know if my opinion is correct. I think that H(k || m || k) (I mean using Merkle and Damgard algorithm where k is a secret key shared by two parties and m is the message sent) is a good keyed hash function with respect to birthday attack because:

1. if the attacker finds another message m' different from m such that h(m') = h(m) this doesn't guarantee that the prefix of m' is equal to the prefix of m, so with high probability H(k || m' || k) will be very different from H(k || m || k).
2. if the attacker wants to append extra bits to H(k || m || k) and compute another step of Merkle and Damgard algorithm he/she can't because he/she doesn't know the last block (that is the key), he/she only knows message blocks sent during the communication.
3. if the attacker finds with birthday attack a message m' such that h(m') = h(k || m || k), he/she cannot verify if that authentication tag is correct because he/she doesn't know the key k. So the attacker to find a message m' such that h(m') = h(k || m || k) generates all possible hashes (considering the rule of birthday bound) in order to find the same value of H(k || m || k).

I'm not sure about this statements, above all the third. Can anyone confirm me the correctness of this statements and eventually explain me possible mistakes? Thanks!

• Define "secure against birthday attack" for a MAC. The reasoning of 1 is flawed, because the adversary looking for collisions can force the colliding messages to start with the same prefix for the length of $k$. In fact, all the messages colliding for SHA-1 have been (are still? ) sharing the same long prefix. Flawed reasoning does not imply invalid conclusion. [re-posted with correction] – fgrieu Feb 12 '18 at 15:02
• Keyed hashes are in general not vulnerable to the birthday attack. If the attacker does not know the key then they are unable to evaluate the same PRF that the participants would use. Further, your description seems to me to talk about preimage resistance whereas the birthday problem is about generating collisions. – bmm6o Feb 13 '18 at 18:19
• Maybe think some more on what exactly your threat model is and what precisely you want to ask, and focus less on trying to provide your own answer. Asking good questions is hard enough! – bmm6o Feb 13 '18 at 18:21

1. if the attacker finds another message m' different from m such that h(m') = h(m) this doesn't guarantee that the prefix of m' is equal to the prefix of m, so with high probability H(k || m' || k) will be very different from H(k || m || k).

Correct: an adversary can't do a collision search offline because the adversary can't even evaluate the function $$m \mapsto H(k \mathbin\| m \mathbin\| k)$$.

1. if the attacker wants to append extra bits to H(k || m || k) and compute another step of Merkle and Damgard algorithm he/she can't because he/she doesn't know the last block (that is the key), he/she only knows message blocks sent during the communication.

Correct: although if given $$h = H(k \mathbin\| m \mathbin\| k)$$ the adversary could compute $$H(k \mathbin\| m \mathbin\| k \mathbin\| m')$$ for some suffixes $$m'$$, that is of no consequence unless by luck $$m'$$ happens to end with $$k$$, which is completely improbable.

1. if the attacker finds with birthday attack a message m' such that h(m') = h(k || m || k), he/she cannot verify if that authentication tag is correct because he/she doesn't know the key k. So the attacker to find a message m' such that h(m') = h(k || m || k) generates all possible hashes (considering the rule of birthday bound) in order to find the same value of H(k || m || k).

I don't really understand what you're getting at here, because $$H(m')$$ is not relevant to the authentication system.

All that said: The birthday paradox is nevertheless relevant even if the adversary can't perform an offline collision search!

Suppose you're using a 128-bit hash like MD5, and you learn the authentication tag $$H(k \mathbin\| m_i \mathbin\| k)$$ for a whopping $$2^{64}$$ messages $$m_1, m_2, \dots, m_{2^{64}}$$. Suppose for simplicity that $$k$$ and the $$m_i$$ are all at least one full block long—at least 512 bits, for MD5. With high probability, there will be a pair of messages $$m_i \ne m_j$$ with $$H(k \mathbin\| m_i) = H(k \mathbin\| m_j)$$, which means not only that $$H(k \mathbin\| m_i \mathbin\| k) = H(k \mathbin\| m_j \mathbin\| k)$$ but also $$H(k \mathbin\| m_i \mathbin\| m' \mathbin\| k) = H(k \mathbin\| m_j \mathbin\| m' \mathbin\| k)$$ for any common suffix $$m'$$, enabling forgery of many additional messages! This is why for an iterated hash with an $$n$$-bit state, you should use it only for $${\lll}2^{n/2}$$ messages.

To my knowledge, this was first described by Preneel and van Oorschot in their 1995 MDx-MAC paper. It is a general attack on any hash of this sort with an $$n$$-bit state; the same idea applies to HMAC too even though HMAC had not yet been invented and Preneel and van Oorschot sensibly chose not to disrupt the natural flow of time by describing how it applies to HMAC.