Partial key recovery from linear equations

Firstly consider the simple case where we know that there is only a simple x-or relation between two key bits. $k_i \oplus k_j = 1$ and $i \neq j$ and call it $R1$. If we consider the x-or table we will see that only half of the rows for $k_i$ and $k_j$ will satisfies this equation.

\begin{array}{cc|c} k_i & k_j & k_i\oplus k_j \\ \hline 0 & 0 & \color{blue}{0} \\ 0 & 1 & \color{red}{1} \\ 1 & 0 & \color{red}{1} \\ 1 & 1 & \color{blue}{0} \\ \end{array}

An equation with equal to $0$ has the same result, i.e. x-or splits the table into half.

Now, lets look at a key search by brute-force.

   for key in possible_keys
       if ciphertext = Enc(key,m)
            return key

Clearly, this will take $\mathcal{O}(2^n)$-time for n-bit cipher.

Now using the relation update this key search

   for key in possible_keys
       if the key doesn't satisfy R1
           continue
       if ciphertext = Enc(key,m)
            return key

What is the gain here? For half of the keys, the loop will not compute the Enc this means that the keyspace is reduced by one-bit due to the R1.

One might say that we are still looping as the number of all possible keys. The cost of an Enc is not considered in the $\mathcal{O}(2^n)$-time. If you add it then you will see that, you will get an approximately a double speed up. It might possible to design an iterator that only loops valid keys, however, that is a software issue. There is a another approach for this see, below.

A relation having more than two key bits will have the same result. Half of the time we don't need to calculate the Encryption.

If we have more than one relation for the speed up calculation we will use fixing bits by equations. Lets look at your your equations to see this:

$k_{1} \oplus k_2 \oplus k_{63} = 1$

$k_{1} \oplus k_3 \oplus k_{17} = 1$

$k_{43} \oplus k_{56} \oplus k_{60} = 0$

While iterating we if we know $k_1$ and $k_2$ than the value of $k_{63}$ is fixed. Even if one of $k_1$ and $k_2$'s is flipped $k_{63}$ is also flipped. So, you iterate overall, expect the $k_{63}$ since it is fixed. To benefit this you can use a permutation on the keys for better iteration.

Similarly, for your second and third equations. So, you have fixed three keys depending on the relation. This can result in a 3-bit key search advantage. Roughly, we can say, $l$ equations gives $l$-bit advantage.

Solved by user18298 (43,386 )
Oct 25, 2019 at 13:25