Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
7  
Explain why we should do your homework. –  owlstead Nov 13 '12 at 1:37
1  
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
add comment

3 Answers

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.

share|improve this answer
    
Assuming we have another message P,which consist of blocks p1,p2...p3. what u get when u XOR message blocks p1,p2...pn will differ from XORing message blocks m1,m2...mn right? so how do u mean MAC of 2 different messages will be the same –  Aisha Nov 13 '12 at 13:24
    
@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
4  
Order would be the least of my worries. The attacker can completely choose all but 1 message. –  CodesInChaos Nov 19 '12 at 20:53
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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