Is this MAC secure:
To authenticate a message $m=m_1||\ldots||m_l$ where $m_i \in \{0,1\}^{n/2}$, choose $r \leftarrow \{0,1\}^n$ at random, compute $$t:=F_k(r)\oplus F_k(\langle 1\rangle || m_1) \oplus \ldots \oplus F_k(\langle l\rangle ||m_l)$$
(where $\langle i \rangle$ is $\frac{n}{2}$ bit encoding of the integer $i$) and send $\langle r, t\rangle$. $F$ is a pseudorandom function.
The question comes from "Introduction to Modern Cryptography" (4.4c) where it is asked to prove that it is insecure, however I'm not sure it is. Here is my intuition (I understand that it is very weak):
The problem comes from the fact that $\langle i \rangle$ is $n/2$ bit encoded. Therefore there is only negligible chance that any r will be of form: $\langle i \rangle || m$ where $i$ is of polynomial size. If this was only $\log n$ bit encoded then we can do something.
So each message xor $F_k(\langle 1\rangle || m_1) \oplus \ldots \oplus F_k(\langle l\rangle ||m_l)$ is XORed with $F_k(r)$ which is basically a random bit string (since $F$ is PRF) that has negligible chance of occuring twice. Therefore each tag is independent from each other.
I tried to prove that it is secure by simulating what would happen if it was breakable, but i was unable to prove that any fraudulent tag would have a unique $F_k(\langle i \rangle || m_i)$ that we haven't sent already during the simulation.
