# 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? Mar 20, 2012 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? Mar 20, 2012 at 3:07
• what's $F_k$??? Mar 20, 2012 at 9:24
• Most likely a keyed hash function. Mar 22, 2012 at 3:51
• According to the problem statement (Katz-Lindell 4.4b), F is simply a pseudorandom function. Mar 26, 2012 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.