# Why shouldn't one build a MAC by XORing multiple message blocks?

I found this simple proposal for a MAC algorithm:

Let the MAC of message M (which consists of message blocks $M_1$,$M_2$, ..., $M_n$) be the AES encryption with key K of the XOR of all the message blocks. In other words: $$MAC_K(M)=E_K(M_1 \oplus M_2 \oplus\cdots\oplus M_n.$$

Why is this a bad idea?

-
Explain why we should do your homework. –  owlstead Nov 13 '12 at 1:37
Assuming this is a homework question, we do accept them on this site, but " If you have just written out your assignment, it is highly likely your question will be closed". I'm quoting from the FAQ. –  mikeazo Nov 13 '12 at 14:05

I give you an example. Assume you are using AES in CTR mode with XOR-based MAC. An attacker can XOR the same value to the different blocks. As the result, text is corrupted but MAC is still correct. So it doesn't provide a message authentication service.

-

One of the goals of MAC is to detect/avoid message tampering.

Bellare, Canetti and Krawczyk defined 1996 formally: "The adversary sees a sequence $(m_1,a_1),(m_2,a_2),\dots,(m_q,a_q)$ of pairs of messages and tags ... and breaks MAC if she can find $m$ not included among $m_1,m_2,\dots,m_q$" and the corresponding valid tag $a = MAC_k(m)$.

However, you can not fulfill that requirement, as you can easily modify an message by adding additional blocks of all 0 at any position. Even worse, you can add a number of arbitrary blocks, as long as their total XOR results in all 0.

Thus, you can take a message/tag pair $(m_1,a_1)$, and modify the message to $m_2$. The formal definition does not require the tag to be new, pair of $(m_2,a_1)$ is a valid forgery.

-
Swap two blocks and what happens in the XOR? It is still the same. In other words, $M_1 \oplus M_2 \oplus \cdots \oplus M_n\equiv M_2 \oplus M_1 \oplus \cdots \oplus M_n$, so the MAC for the two different messages will be the same.
@Aisha, $M_1|M_2|\cdots|M_n\neq M_2|M_1|\cdots|M_n$. Where $|$ is concatenation. So let $M=M_1|M_2|\cdots|M_n$ and $M'=M_2|M_1|\cdots|M_n$. Note that $M\neq M'$ but that $MAC_k(M)=MAC_k(M')$. –  mikeazo Nov 13 '12 at 14:02