# Attacking multi block MAC constructions

For variable-length messages, there are three different ways to generate the tags.

1. $Tag = MAC_k(\Sigma_i m_i)$.

2. $t_i = MAC_k(m_i)$ and $Tag = (t_1, ..., t_l)$.

3. $t_i = MAC_k(i||m_i)$ where $i$ is a sequence number and $Tag = (t_1, ..., t_l)$.

Find an attack for each case.

Problem comes from Communication Systems Security, by Chen and Gong, page 179

I have been looking for various attacks for the above question. Can anyone help me with the answer?

• You should explain what you have tried and where, specifically, you are stuck. – mikeazo Feb 10 '15 at 18:07
• @xxx I have deleted my comment mentioning your original name. But please refrain from vandalizing the question or my answer. You asked the question and can't take it back. – CodesInChaos Feb 11 '15 at 20:39
• @xxx you may be interested in this: meta.stackexchange.com/questions/18221/… – mikeazo Feb 11 '15 at 22:39

1. $Tag = MAC_k(\Sigma_i m_i)$.

Too many attacks to enumerate. As long as the sum over the blocks remains the same, the tag remains valid. If the sum is reduced modulo $2^{\mathrm{blocksize}}$ at the end, the attacker can choose the whole message, apart from a single block used to balance the sum.

2. $t_i = MAC_k(m_i)$ and $Tag = (t_1, ..., t_l)$.

Reordering message blocks and tag blocks in the same way results in a valid (message,tag pair). You can duplicate blocks. In general, the attacker can compose a message from any block that has appeared in a valid authenticated message.

3. $t_i = MAC_k(i||m_i)$ where $i$ is a sequence number and $Tag = (t_1, ..., t_l)$.

Reordering is not possible. If you authenticate several messages an attacker can pick each block from a different messages.

Another attack is simply truncating both message and tag to $l^\prime<l$ blocks.