# Producing existential forgery against CBC-MAC

Given the above MAC scheme, I want to ask how to form existential forgery of this scheme?

I have looked through a couple explanations on existential forgery but still struggle understanding the concept of it.

Based on the hint provided in the problem, the current method I'm working on is to

1. Start with two messages $$M_1$$ and $$M_2$$, giving known outputs $$(IV_1, T_1)$$ and $$(IV_2, T_2)$$.
2. Produce a message $$M_3$$ with output $$(IV_1, T_2)$$.
3. $$M_3$$ will be close to concatenation $$M_1||M_2$$, but with one block altered.

How can I do this? Do I need to partition $$M_1$$ and $$M_2$$ to fit into $$m_0$$ to $$m_2$$?

EDIT2

I'm thinking is this a possible solution for $$M_3$$?

• Hint : If the tag is always full side, and you can play with the IVs how can you combine $M_1$ and $M_2$. Commented May 19 at 11:36
• Hints: The drawing is shown for a message $M$ that splits into 3 blocks, but implicitly that generalizes to an arbitrary number of blocks. That's critical to the question asked. The problem statement lacks a specification of how a message $M$ is turned into blocks $m_i$. I thus suggest to assume that all messages have a size a multiple of the block size, and are merely split into block(s) in reading order. From that it follows that the concatenation of two messages is split into the concatenation of the block(s) the respective messages are split into.
– fgrieu
Commented May 19 at 11:53
• @fgrieu Thanks a lot for your hint! So can I add another sub-message in the middle of $M_1$ and $M_2$ and all together form $M_3$? Commented May 19 at 12:31
• @b1841837: Congratulations, that works when $M_2$ consists of a single block. Ideally, you should invoke the properties of XOR that you are using, and generalize to arbitrary number of blocks in $M_1$ and $M_2$. You can also write down an answer.
– fgrieu
Commented May 19 at 14:31
• Setting IV weaken it; Forge CBC-MAC given the MAC of two messages and of their concatenation Commented May 19 at 15:14