# 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?

• Note of the editor: I kept the original notation, but find it disastrous. I suggest to first change $X_1$ to $L_i$, $X_2$ to $R_i$, $Y_1$ to $L_{i+1}$, $Y_2$ to $L_{i+1}$. Then define $P=L_0\mathbin\|R_0$, $C=L_k\mathbin\|R_k$ with $k=2$ the number of rounds. Then number individual bits and start finding boolean equations; some enlightening may ensue. – fgrieu Apr 6 '18 at 12:28
• if i write the complete system in equations, then how can i solve it because + and Xor seems confusing. – khan Apr 6 '18 at 12:36
• Addition modulo $2^n$ of two $n$-bit quantities can be expressed as $2n-1$ XOR, $2n-3$ AND, $n-2$ OR of individual Boolean variables, using the well-known ripple carry adder construction. In the end, the whole block cipher boils down to Boolean equations. Hint: start with the equations involving the low-order bit of each 8-bit quantity. Prove that you can find the low-order bit of $K_1$ and $K_2$ from the the low-order bit of each halves of a single $P/C$ pair. Then move on to higher-order bits. – fgrieu Apr 6 '18 at 13:06
• @fgrieu: actually, the problem can be solved a lot easier than that; you can keep the modular add (and xor) as group operations, and find a fairly simple solution that way. Yes, your approach would work better if you extended the cipher past two rounds; for just two rounds, it's overkill – poncho Apr 6 '18 at 14:11
• @fgrieu What about multiplication? how many Xor, AND & OR boolean variables it involve? – khan Apr 7 '18 at 6:46

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.

• How to proceed for more than 2 rounds, like 5 or 10? – khan Apr 7 '18 at 6:46