I'm working on some cryptography problems, found this and I'm not sure how to solve it:
Modify CBC-MAC so that all blocks $t_1,\dots,t_l$ are output rather than just $t_l$ and prove it is not secure.
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.Sign up to join this community
Consider the following chosen-plaintext attack on the modified CBC-MAC function:
Send $m_1$, $m_2$, $m_3$, receive $t_1$, $t_2$, $t_3$.
Send $m_1$, $m'_2$, $m'_3$, receive $t'_1$, $t'_2$, $t'_3$.
Send $t'_2 \oplus m''_3$, $m''_2$, $m''_3$, receive $E_k(t'_2 \oplus m''_3)$, $t''_2$, $t''_3$.
Then you know the following (message, tag) pair will verify:
Send $m_1$, $m'_2$, $m''_3$: the tag will be the concatenation of values you have previously queried for: $t_1$, $t'_2$, $E_k(t'_2 \oplus m''_3)$. Therefore you can generate a valid (message, tag) pair that has not yet been sent through the modified CBC-MAC algorithm. This can be generalized for any number of blocks.
Recall what we mean when we talk about security of a MAC.
While MAC functions are similar to cryptographic hash functions, they possess different security requirements. To be considered secure, a MAC function must resist existential forgery under chosen-plaintext attacks. This means that even if an attacker has access to an oracle which possesses the secret key and generates MACs for messages of the attacker's choosing, the attacker cannot guess the MAC for other messages (which were not used to query the oracle) without performing infeasible amounts of computation.
So, you are given oracle access to something that you give it a message $m$ and it gives you the MAC. Your goal is to compute a valid MAC of some $m'\neq m$. How would you do that in this modified MAC?
Think about this, let's say I sent the message
I EOS, give all my worldly belongings to mikeazo. Just kidding. to the oracle. Given the MAC of that message, can I generate a MAC for the message
I EOS, give all my worldly belongings to mikeazo.?
In practice you will have to deal with block boundaries and padding, but both of those things are entirely deterministic and known to the attacker. In other words, they aren't much of a hurdle.