2
$\begingroup$

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?

One Round

$\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?

|improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – fgrieu Apr 6 '18 at 12:28
  • $\begingroup$ if i write the complete system in equations, then how can i solve it because + and Xor seems confusing. $\endgroup$ – khan Apr 6 '18 at 12:36
  • $\begingroup$ 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. $\endgroup$ – fgrieu Apr 6 '18 at 13:06
  • $\begingroup$ @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 $\endgroup$ – poncho Apr 6 '18 at 14:11
  • $\begingroup$ @fgrieu What about multiplication? how many Xor, AND & OR boolean variables it involve? $\endgroup$ – khan Apr 7 '18 at 6:46
1
$\begingroup$

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.

|improve this answer
$\endgroup$
  • $\begingroup$ How to proceed for more than 2 rounds, like 5 or 10? $\endgroup$ – khan Apr 7 '18 at 6:46

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.