Cryptanalysis of modified AES algorithm with no shift-rows, and no key-expansion

Question

I came across an answer about consequences of AES without any of its operation In the question in the given link, it is mentioned that "if Shift Row is removed, then an attacker can treat input block ($128$ bits) as $4$ independent $32$ bits block. Hence, the attacker can attack these $4$ blocks one by one to recover the key." I did not understand this statement. I request the community to please help me understand this question.

Since AES is a block cipher, we have to encrypt each 16byte block at once, but how can we divide that 16byte into blocks of 4 bytes? If I have a plaintext-ciphertext pair of 16bytes, will it be enough to recover the key? If yes, then how?

Answer 1

AES works by operating on the 16 input bytes as a 4x4 matrix of values. The state looks like:

$$\begin{bmatrix} x_{1} & x_{5} & x_{9} & x_{13} \\ x_{2} & x_{6} & x_{10} & x_{14} \\ x_{3} & x_{7} & x_{11} & x_{15}\\ x_{4} & x_{8} & x_{12} & x_{16} \end{bmatrix}$$

Sub Bytes

The subBytes operation operates on one entry of the state at a time, and it replaces the value of each entry $x_{n}$ with another value.

Mix Columns

The mixColumns operation operates on a column at a time, independently:

$$\begin{bmatrix} x_{1}\\ x_{2}\\ x_{3}\\ x_{4} \end{bmatrix} \begin{bmatrix} x_{5}\\ x_{6}\\ x_{7}\\ x_{8} \end{bmatrix} \begin{bmatrix} x_{9}\\ x_{10}\\ x_{11}\\ x_{12} \end{bmatrix} \begin{bmatrix} x_{13}\\ x_{14}\\ x_{15}\\ x_{16} \end{bmatrix} $$

and it outputs a new column such that each entry in the column depends on all of the entries in the column.

Shift Rows

The shiftRows operation transposes individual entries from each column so that each output column consists of 1 entry from each input column:

$$ \begin{bmatrix} x_{1} & x_{5} & x_{9} & x_{13} \\ x_{2} & x_{6} & x_{10} & x_{14} \\ x_{3} & x_{7} & x_{11} & x_{15}\\ x_{4} & x_{8} & x_{12} & x_{16} \end{bmatrix} \rightarrow \begin{bmatrix} x_{1} & x_{5} & x_{9} & x_{13} \\ x_{14} & x_{2} & x_{6} & x_{10} \\ x_{11} & x_{15} & x_{3} & x_{7}\\ x_{8} & x_{12} & x_{16} & x_{4} \end{bmatrix} $$

Removing Shift Rows

If you don't use the shiftRows operation, then there is no mixing of values between columns of the state. The state would effectively consist of four separate columns that do not influence each other.

Since there are four 8-bit bytes in each column, each column would effectively become a 32-bit permutation, instead of the 128-bit permutation that AES is supposed to be.

Breaking it

32-bits is easily within the range of brute force, and is usually considered small enough to be amenable to a lookup table. While you would have to perform 4 separate 32-bit brute force attacks to recover the key, this does not take nearly as much time as a single 128-bit brute force attack. This is because each column can be attacked independently and in parallel.