# 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? Nov 23, 2013 at 15:57
• Nov 23, 2013 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. Nov 23, 2013 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}$
– user991
Nov 23, 2013 at 21:49

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