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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.