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?

  • 3
    $\begingroup$ 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? $\endgroup$
    – pg1989
    Commented Mar 20, 2012 at 1:29
  • 5
    $\begingroup$ 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? $\endgroup$
    – poncho
    Commented Mar 20, 2012 at 3:07
  • 1
    $\begingroup$ what's $F_k$??? $\endgroup$ Commented Mar 20, 2012 at 9:24
  • $\begingroup$ Most likely a keyed hash function. $\endgroup$
    – pg1989
    Commented Mar 22, 2012 at 3:51
  • 3
    $\begingroup$ According to the problem statement (Katz-Lindell 4.4b), F is simply a pseudorandom function. $\endgroup$ Commented Mar 26, 2012 at 14:43

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.