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?

  • $\begingroup$ Does the key $k$ is fixed? Also, in your solution, how do you access the internal values? $\endgroup$
    – kelalaka
    Feb 13 at 17:28
  • $\begingroup$ 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. $\endgroup$ Feb 13 at 20:43


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.