# Known message attack on ENC-MAC with AES encryption

The assignment I have is as follows:

Let $$l=2^{128}$$ and let $$x$$ be a random integer satisfying $$0\le x \le l$$

Let $$\oplus$$ be the XOR operator and $$E_k$$ an AES encryption with $$key=k$$

Let the signature of a string $$M=m_{1}||m_{2}\dots||m_{n}$$ where $$||$$ denotes concatenation of strings where $$m_i$$ is a binary string of $$128$$ bits

Now assume the signature $$S\left(x,M\right)=\left\langle x,\sum_{i=1}^{n}E_{k}\left(m_{i}\oplus E_{k}\left(i+x\right)\right)\mod l\right\rangle$$

Design an known message attack to forge signatures.

Using brute force to break down AES is impossible so there must be some clever trick. I tried using $$n=2$$ and using the known message $$S\left(x,M\right)=\left\langle x,E_{k}\left(m_{1}\oplus\left(E_{k}\left(x+1\right)\right)\right)+E_{k}\left(m_{2}\oplus\left(E_{k}\left(x+2\right)\right)\right)\right\rangle$$

We can construct another string $$T=t_{1}||t_{2}$$ and we want the parameters inside $$E_k$$ to be equal: $$m_{1}\oplus\left(E_{k}\left(x+1\right)\right)=t_{2}\oplus\left(E_{k}\left(x+2\right)\right)\Rightarrow \\t_{2}=m_{1}\oplus\left(E_{k}\left(x+1\right)\right)\oplus\left(E_{k}\left(x+2\right)\right) \\\\$$ With the same logic we can deduce $$t_{1}=m_{2}\oplus\left(E_{k}\left(x+2\right)\right)\oplus\left(E_{k}\left(x+1\right)\right)$$ obviously if $$t_1=m_1 , t_2=m_2$$ it will satisfy the equations, but is there any way to find other $$t_1,t_2$$ that satisfy the conditions if we don't know $$E_k(x+1)$$ or $$E_k(x+2)$$ ? Is there perhaps another method to find an attack on this signature?

• Does the key $k$ is fixed? Also, in your solution, how do you access the internal values? Feb 13 at 17:28
• Yes, $k$ is a fixed(unknown to atyacker) 128 bit key. One can't access the internal values, only a few messages and their signatures. Feb 13 at 20:43