# 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

## 1 Answer

The usual meaning of "secure" for a MAC means that an attacker has no chance to forge a message not originally sent by the sender, without knowing the private key.

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.

Thus, in the formal sense this proposed MAC scheme is not secure. Whether it is a problem in practice depends on what kind of data you are sending. If each block is a sub-message which makes sense of it own independent on the order of the blocks, then it might still be enough.

But as there are better MAC schemes which actually take the order of the blocks into account, use these instead.