How does birthday attack on message authentication work?

In Cryptography Engineering:

2.7.1 Birthday Attacks

Birthday attacks are named after the birthday paradox. If you have 23 people in a room, the chance that two of them will have the same birthday exceeds 50%. That is a surprisingly large probability, given that there are 365 possible birthdays.

So what is a birthday attack? It is an attack that depends on the fact that duplicate values, also called collisions, appear much faster than you would expect. Suppose a system for secure financial transactions uses a fresh 64-bit authentication key for each transaction. (For simplicity, we assume that no encryption is used.) There are $2^{64}$ ($=18\cdot 10^{18}$ , or eighteen billion billion) possible key values, so this should be quite difficult to break, right? Wrong! After seeing about $2^{32}$ ($=4\cdot 10^9$ , or four billion) transactions, the attacker can expect that two transactions use the same key. Suppose the first authenticated message is always the same "Are you ready to receive a transaction?" message. If two transactions use the same authentication key, then the MAC values on their first messages will also be the same, which is easy to detect for the attacker. By knowing that the two keys are the same, the attacker can now insert the messages from the older transaction into the newer transaction while it is going on. As they are authenticated by the correct key, these bogus messages will be accepted, which is a clear break of the financial transaction system.

What bad does this do:

By knowing that the two keys are the same, the attacker can now insert the messages from the older transaction into the newer transaction while it is going on.

?

Suppose the two transactions have the same MAC, which implies the same authentication key.

Isn't the message from the older transaction the same as the message in the newer transaction? So the replacement does not change?

In this context, a transaction $t_i$ contains many messages $m_i^t$ where each message is MAC'ed with the transaction key $k_i$.

Now assume that the MAC key of each transaction is generated uniformly randomly[1]. Then after around $2^{32}$ transactions, we expect a key occurs again with 50% percentage probability by the birthday paradox. This is the collision part. Assume $t_i$ and $t_j$ have the same MAC key $k_i$.

As mentioned in the paragraph if the first messages of the transactions are the same, then an attacker storing the transactions can see that a key is reused - key from transaction $t_i$ is used on the transaction $t_j$.

Attacker stores

| (m10,MAC(m10) |(m11,MAC(m11) | ... | (m1N1,MAC(m1N1)|
| (m20,MAC(m20) |(m21,MAC(m21) | ... | (m2N1,MAC(m2N2)|
....
| (mi0,MAC(mi0) |(mi1,MAC(mi1) | ... | (miNi,MAC(miNi)|
....
| (mj0,MAC(mj0) |(mj1,MAC(mj1) | ... | (mjNi,MAC(mjNi)|

and observes :  MAC(mi0) = MAC(mj0)
and may send

| (mj0,MAC(mj0) |(mi1,MAC(mi1) | ... | (miNi,MAC(miNi)|

Now, they simply take messages $m_i^t$ from the $t_i$, and insert them into a current transaction that uses the same key. So the new transaction contains $m_j^t$ messages and the insert $m_i^t$ messages on the advantage of the attacker. The attacker may delete all of the $m_j^t$ messages of the transaction and can send $m_i^t$'s, too, depending on their advantage.

As a result, the replacement changes the messages on the transaction.

[1] This is an important part of the collision part and the security, too.

As noted by kelalaka, there seems to be an implicit assumption that a "transaction" contains multiple separately authenticated messages, and that the messages are not chained in any way (e.g. by including the previous message's MAC token in the input to the next message's MAC calculation).

It's worth noting that such a scheme does not protect transaction integrity anyway — an MITM attacker could reorder, remove or replay messages within a single transaction without being caught by the MAC. The birthday attack, as described, only gives the attacker the additional freedom of replaying messages from one transaction to another one using the same MAC key, which is not much of an extension of the (already pretty bad) vulnerability to MITM attacks the scheme would have even with longer MAC keys.

In principle, birthday attacks can affect even otherwise well designed multi-message authentication schemes, if the MAC key and/or tokens are too short. The details, however, depend a lot on the scheme, and usually such attacks will require more than just a short key.

For example, let's assume that the $i$-th message in transaction $t$ is authenticated by the tag $$\tau_{i,t} = \operatorname{MAC}_{K_t}(\tau_{i-1,t} \mathbin\| i \mathbin\| m_{i,t}),$$ where $K_t$ is the per-transaction MAC key, $\tau_{i-1,t}$ is the MAC tag for the previous message in the transaction, $i$ is the message number (padded to a fixed length or otherwise unambiguously separated from the other MAC inputs) and $m_{i,t}$ is the message to be authenticated.

Then, to be able to replace the tagged message $(m_{i,t}, \tau_{i,t})$ with a previously intercepted one $(m_{i',t'}, \tau_{i',t'})$ from another transaction $t'$ and have it pass MAC validation, the attacker needs not just $K_t = K_{t'}$, but also $i = i'$ and $\tau_{i-1,t} = \tau_{i-1,t'}$. This could happen by chance, if the combined length of the key, the tag and (typical values of) the message counter was low enough, but it's a lot less likely than just two keys colliding. In practice, it would also require the tag (or the key!) to be short enough that it would be directly vulnerable to brute force forgery attacks even without exploiting the birthday effect.

Thus, while the overall point the book is trying to get across — that keys should be long enough to avoid birthday collisions — is a good principle to follow in general, I'm not convinced that the actual attack they present is a practical one, at least not against any schemes that aren't already vulnerable to much worse attacks anyway.