> For the complete documentation index, see [llms.txt](https://luminousxlb.gitbook.io/cryptography/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://luminousxlb.gitbook.io/cryptography/chapter-4-message-authentication-codes/exercise-4.15.md).

# Exercise 4.15

### Problem

Show that appending the message length to the end of the message before applying basic CBC-MAC does not result in a secure MAC for arbitrary-length messages.

### Solution

Query

* $$m\_1 = B\_0 || B\_1$$, $$t\_1 = MAC\_k(m\_1 || \langle |m\_1| \rangle)$$
* $$m^*\_1 = B^*\_0 || B^*\_1$$,  $$t^*\_1 = MAC\_k(m^*\_1 || \langle |m^*\_1| \rangle)$$
  * $$|m^\*\_1| = |m\_1|$$
* $$m\_2 = m\_1 || \langle |m\_1| \rangle || B\_2 || B\_3$$, $$t\_2 = MAC(m\_2 || \langle |m\_2| \rangle)$$

To be specific, the process of computing $$t\_2$$ for message $$m\_2$$ is listed below:

* $$c\_0=F\_k(B\_0)$$
* $$c\_1=F\_k(c\_0 \oplus B\_1)$$
* $$t\_1=F\_k(c\_1 \oplus \langle |m\_1| \rangle)$$
* $$c\_3=F\_k(t\_1 \oplus B\_2)$$
* $$c\_4=F\_k(c\_3 \oplus B\_3)$$
* $$t=F\_k(c\_4 \oplus \langle | m\_2 | \rangle)$$

Hence, if we change $$m\_1$$ to $$m^\*\_1$$,

* $$c^*\_0=F\_k(B^*\_0)$$
* $$c^*\_1=F\_k(c^*\_0 \oplus B^\*\_1)$$
* $$t^*\_1=F\_k(c^*\_1 \oplus \langle |m^\*\_1| \rangle)$$

In order to keep the result of MAC, it must hold that $$t\_1 \oplus B\_2 = t\_1^\* \oplus B^\*\_2$$. Thus

$$
B^*\_2 = t\_1 \oplus B\_2 \oplus  t\_1^*
$$

Therefore

* $$c^*\_3=F\_k(t^*\_1 \oplus B^*\_2) = F\_k(t^*\_1 \oplus  t\_1 \oplus B\_2 \oplus  t\_1^\*) = F\_k(t\_1 \oplus B\_2) = c\_3$$
* $$c^*\_4 = F\_k(c^*\_3 \oplus B\_3) = F\_k(c\_3 \oplus B\_3) = c\_4$$
* $$t^\* = F\_k(c^*\_4 \oplus \langle | m^*\_2 | \rangle)  = F\_k(c\_4 \oplus \langle | m\_2 | \rangle) =t$$
  * $$|m^*\_2|=|m\_2|$$ can be easily get since $$|m^*\_1| = |m\_1|$$

Hence we get a message and its valid tag $$\langle m^*, t^* \rangle$$ where

$$
m^\* := m^*\_1 || \langle | m^*\_1| \rangle || t\_1 \oplus B\_2 \oplus  t\_1^\* || B\_3 \\
t^\* = t
$$