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 basicly 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