# Why is this MAC based on secure PRF with ordering and randomization insecure?

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.

-
I don't understand how that would work. Could you develop your argument? –  gregorias Nov 23 '13 at 15:57
–  CodesInChaos Nov 23 '13 at 16:03
I was aware of those. Attacks presented there are not applicable here, since there's ordering added to message text preventing simple swapping of message chunks. Also we can't enlarge the message with something of 0 XOR value since every tag we get from oracle is a result of XOR with unknown random number $F_k(r)$, where $r$ is arbitrary. –  gregorias Nov 23 '13 at 16:28
Could they be just referring to the fact that for every way of padding messages whose length is not $\hspace{.44 in}$ a multiple of $n$ to strings whose length is a multiple of $n$, the resulting algorithm will be insecure? $\hspace{.6 in}$ –  Ricky Demer Nov 23 '13 at 21:49

$\langle \langle 1\rangle || m_1, 0^n \rangle$ is a valid tag on $m = m_1$