I was studying Rijndael AES proposal, and its cryptanalysis. I started with writing code to break AES reduced to 2 rounds. I am using 128 bit key size and 128 bit block size. 2 round AES means the following sequence of steps:
$AR \to BS \to SR \to MC \to AR \to BS \to SR \to AR$
where
AR = AddRoundKey
BS = ByteSub
SR = ShiftRows
MC = MixedColumn
One of the way of breaking the algorithm can be generating inputs following a particular pattern and analyzing the output. Following are patterns I consider:
$P:$ All values are distinct
$Z:$ Sum of all values in zero
$X:$ Any other pattern
I give 256 blocks of input to the algorithm at a time. The blocks follow the following pattern:
$$ \begin{matrix} P & P & P & P \\ P & P & P & P \\ P & P & P & P \\ P & P & P & P \\ \end{matrix} $$
i.e. all the elements at same position in 256 blocks are distinct. I will denote this matrix as $[P]$ for simplicity.
After applying the above AES steps following is the fate of these matrices:
$[P] -AR \to [P] -BS \to [P] -SR \to [P] -MC \to [Z] -AR \to [Z] -BS,SR,AR \to [X]$
The last $BS$ operation destroys the structure of the matrix.
We can consider the last 4 steps $AR, BS, SR, AR$ to be a map (say $f$) from 256 inputs at each matrix position to outputs and try to obtain this map using the fact that the input has pattern $Z$. There will be 16 such maps. We can solve it in following way:
Lets consider we want to find the map $f_{00}$ i.e. for the first element in the matrix. We know what all outputs we are getting for the 256 inputs we have taken. Lets say they are:
$u_i, 0 \le i < 256 $
Lets denote:
$x_{u_i} = f_{00}^{-1}(u_i)$
Since the input has pattern $Z$, we can write the following equation:
$$\sum_{i=0}^{255} x_{u_i} = 0$$
This is a liner equation in 256 variables. We can take another set of 256 blocks of input of pattern $[P]$ and generate another equation. We can generate 256 of these equations and solve them to find $f_{00}$. Same we can do for other positions as well. Once we get all the maps. We can easily get the key of encryption.
However my problem is this: No matter how many equations I generate, I always get at max 247 equations that are linearly independent. This means they don't have a unique solution. But according to me they should get a unique solution. Where am I going wrong? Why only 247 equations?