Partial key recovery from linear equations

I have searched for my question but I didn't find any relevant answer to my situation. I guess maybe it is too easy but I am a newbie in crypto and I can't figure out the answer. Here is the exercise:

An attacker mounts a partial key recovery attack on a cipher with a 128-bit key and manages to find a system of $$k$$ independent linear equations involving the secret key bits with $$k < n$$.

For example:

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

Does this info help him to attack the cipher? If yes, what would be the attacker’s gain over the complexity of an exhaustive search?

I know intuitively that this reduces the complexity because of the common $$k_1$$ in 2 of the equations and I tried using truth tables for each equation but I can't extract the answer from them. Can anyone explain how is the complexity reduced?

• @kelalaka Omg, I failed to see it but you are so right! Thank you so much! Oct 25 '19 at 10:26

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.

• Actually, we can do better than that. From the relation $k_1 \oplus k_2 \oplus k_{63} = 1$, then if we know $k_1$ and $k_2$, we immediately know $k_{63}$. Furthermore, if we flip $k_1$ xor $k_2$, then $k_{63}$ flips. So, what we do is set $k_{63}$ initially to be consistent with the initial $k_1$ and $k_2$ and iterate over all the key bits except $k_{63}$ (flipping it when necessary). By using all three equations, and skipping over the 3 bits that we can update, this reduces the number of key bits we need to iterate over to $n-3$. Oct 25 '19 at 13:34
• @poncho thanks, from this side it is much clear to see. Oct 25 '19 at 13:56