Solve System of Equations including XOR and Modular Addition A Dummy cipher is shown in figure below. Plaintext is 16 bits ($X_1$ and $X_2$ are 8 bit each). Ciphertext is computed after two rounds using two round keys $K_1$ and $K_2$. Can the round keys $K_1$ and $K_2$ be found by solving the system of equations, which involves XOR and Modular Addition?



$\boxplus $ = addition modulo $2^8$

$\oplus$ = XOR

$X_1$, $X_2$, $Y_1$, $Y_2$ are 8-bit. $i=1,2$.

I am confused on how to solve such system of equation which involves XOR and modular addition. How many PT-CT pairs are required to solve such system of equations? How many linear, non-linear/quadratic terms will there be in the system of equations?
Ok, this would appear to be homework, so I won't give the full answer; I'll get you started.

First thing to do (with this attack approach) is to write out the full equations of the system, as in:

$$T_0 = P_0 \oplus K_0$$

$$T_1 = P_1 \boxplus T_0$$

$$T_2 = T_0 \oplus T_1$$

$$T_3 = T_2 \oplus K_1$$

$$C_1 = T_3 \boxplus T_1$$

$$C_0 = T_3 \oplus C_1$$

where you know $P_0, P_1$ (the plaintext), $C_0, C_1$ (the ciphertext), and you don't know $K_0, K_1$ (the keys) or $T_0, T_1, T_2, T_3$ (the internal states of the cipher at various points).  And, we'll assume that we have a single plaintext/ciphertext pair (that will turn out to be sufficient against this cipher).

Where to do go from here?  Well, the first obvious step is to notice the last relation $C_0 = T_3 \oplus C_1$; we know $C_0, C_1$, and so we can deduce the value $T_3 = C_0 \oplus C_1$.  Then, we notice the relation $C_1 = T_3 \boxplus T_1$, we know $C_1$ and $T_3$, and so we can deduce the value $T_1 = C_1 \boxminus T_3 = C_1 \boxminus (C_0 \oplus C_1)$.  Where do we go next?

Now, this approach takes apart this two round cipher quite nicely; however it doesn't scale very well; adding a third round to this toy cipher will break the relations this depends on.  On the other hand, I suppose it might be a start in learning how to think about how to attack a cipher, although you will need to find other ways to attack less trivial ciphers. fgrieu's suggestion about looking at the lower-order bits first is a more general approach that'll work in cases where this won't.