# Block ordering and security in a MAC?

To authenticate a message $m = m_1 \,\|\, \dots \,\|\,m_n$ the tag $t := F_k(r) \oplus F_k(m_1) \oplus \dotsb \oplus F_k(m_n)$ is used, where r is uniform random number $(0,1)^n$ and $m=(0,1)^n$. Even though the random number is prepended to the sequence there is still a chance of reordering the message blocks which makes it insecure.

I am confused whether the blocks changed by an attacker make it insecure or not?

-
Is this problem 4.4b of Katz-Lindell? If so, think about how the authenticating party would verify the MAC. What information would they need? How would they get it? – pg1989 Mar 20 '12 at 1:29
Hint: suppose an attacker saw the value message $r||m_1||m_2||m_3||t$, and modified it into the message $r||m_2||m_1||m_3||t$; would the modified message still have a valid tag? – poncho Mar 20 '12 at 3:07
what's $F_k$??? – Vineet Menon Mar 20 '12 at 9:24
Most likely a keyed hash function. – pg1989 Mar 22 '12 at 3:51
According to the problem statement (Katz-Lindell 4.4b), F is simply a pseudorandom function. – MartinSuecia Mar 26 '12 at 14:43

So, assume there is a message $ABCDE$ (where each letter corresponds to one $n$-bit block). This will be sent as $rABCDEt$. If an attacker captures this message, she can reorder the blocks to create a second message $rBDCEAt$, and if you look at your formula, the tag for $BDCEA$ is exactly the same as the one for $ABCDE$, thus this mangled message will still validate as authentic.