MAC scheme

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$?


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

enter image description here

  • $\begingroup$ Hint : If the tag is always full side, and you can play with the IVs how can you combine $M_1$ and $M_2$. $\endgroup$
    – kelalaka
    Commented May 19 at 11:36
  • $\begingroup$ 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. $\endgroup$
    – fgrieu
    Commented May 19 at 11:53
  • $\begingroup$ @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$? $\endgroup$
    – b1841837
    Commented May 19 at 12:31
  • 3
    $\begingroup$ @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. $\endgroup$
    – fgrieu
    Commented May 19 at 14:31
  • 1
    $\begingroup$ Setting IV weaken it; Forge CBC-MAC given the MAC of two messages and of their concatenation $\endgroup$
    – kelalaka
    Commented May 19 at 15:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.