# Breaking linear blockcipher - expanding recursive formula

I am trying to break a block cipher that can be defined as follows:

We have 12 rounds and at each round, we perform the following operation.

We split 64 bit data into 2 parts each 32-bits, $$\ x_r$$ and $$y_r$$ and compute:

$$x_{r+1} = M * (x_r \oplus y_r) \oplus k_0$$

$$y_{r+1} = M * (x_{r+1} \oplus y_r) \oplus k_1$$

Where $$k_0,k_1$$ are 32-bit keys that repeat at each round. $$M$$ is a cyclic shift matrix that is always shifting 7 to left. Encryption can be defined as $$E(x_0 || y_0,k_0,k_1) = x_{12} || y_{12}$$.

I understand that the cipher is completely linear. Therefore, it can be easily broken.

However, I am trying to find the easiest way of finding an equation that will take only $$x_{12}, y_{12}, x_0, y_0, k_0, k_1$$. Which is basically unrolling the recursiveness. After that, I can solve the equation with one plaintext/ciphertext pair and retrieve the key.

So my question is what is the best tool to perform such "unrolling" as well as the expansion. I understand that I need to do some kind of symbolic computation, such that I get 2 linear equations at the end and to solve them and retrieve the key.

• Is there any key schedule? Can you clarify the order of operations? Do you shift first and then XOR the key or vice versa? – SEJPM Mar 19 '16 at 12:04
• There us no key scheduling and yes you rotate first and then XOR it with the key. I checked the first two rounds by getting: – Maciej Żurad Mar 19 '16 at 13:50
• $x_2=M^3x_0 +M^2x_0 + M^3y_0 + Mk_0 + Mk_1 + k_0$ and it matched the implementation of the cipher at second round. – Maciej Żurad Mar 19 '16 at 13:59