Consequences of AES without any one of its operations

Question

Suppose AES-$128$. There are $4$ operations in AES's encryption, they are SubByte, Shift Row, MixColumns and AddRoundKey.

Question: If I remove one of the following opearations, what will happen to the AES? SubByte, Shift Row, MixColumns

If Shift Row is removed, then attacker can treat input block ($128$ bits) as $4$ independent $32$ bits block. Hence, attacker can attack these $4$ blocks one by one to recover key.

If MixColumn is removed, then attacker can treat input block ($128$ bits) as $16$ independent $8$ bits block. Hence, attacker can attack these $16$ blocks separately.

If SubByte is removed, then the non-linearity of AES is gone. But I don't know how an attacker can attack the AES?

Can anyone give some hint?

Answer 1

As poncho notes in the comments above, viewing the input block as a 128-element vector over ${\rm GF}(2)$, the AES ShiftRows and MixColumns operations are both linear transformations, and AddRoundKey is just vector addition.

Both linear transformations and addition of a constant are kinds of affine transformations, and since the composition of any two affine transformations is itself an affine transformation, it follows that, if the non-affine SubBytes step is removed from AES, the whole cipher becomes affine.

In particular, every affine transformation can be represented in the form $c = Ap + k$, where $p$ is the plaintext input (a vector of 128 bits), $c$ is the corresponding ciphertext output, $k$ is a constant vector and $A$ is a 128 × 128 bit matrix. Furthermore, the inverse of this transformation is then simply $p = A^{-1}(c - k)$, where $A^{-1}$ is the matrix inverse of $A$, and (for vectors over ${\rm GF}(2)$) both vector addition "$+$" and subtraction "$-$" simply mean bitwise XOR.

The constant $k$ obviously depends on the key, but the matrix $A$ actually does not — it is fully determined by the ShiftRows and MixColumns steps, neither of which are key-dependent. Thus, you can precalculate it e.g. by implementing this affine AES variant yourself, leaving out the AddRoundKey step as well to make it linear, and using this to encrypt (or decrypt) all the 128 blocks with a single bit set to one and all other bits zero, which will directly give you the columns of $A$ (or of its inverse $A^{-1}$).

Once you've precalculated $A$, even just a single known plaintext/ciphertext block pair $(p,c)$ encrypted using the actual affine cipher will let you determine the key-dependent the additive constant $k = c - Ap$. Knowing $A$ and $k$ will then let you encrypt (or decrypt, using $A^{-1}$) any arbitrary plaintext (or ciphertext) block.

Answer 2

Every block cipher is a proper mixture of substitution and permutation operations which these proper mixtures,in entire rounds unanimously gives the algorithm resistance against different crypt-analytic analysis.

In AES cipher, which it is arranged in SP structure, Round function is consist of substitution operation("Sub Byte") and permutation operation("Mix Column" , "Shift Row"). But we should consider that the Round function itself in One Round is not giving enough strength to the structure. In fact the right number of proper arrangement of Round functions make the structure resistance against cryptographic attacks.

Besides, "Sub Byte" in AES does not let the attacker to run the cipher in reverse,means able to reach the Plain-text from reverse running the cipher from the cipher-text and get the keys(because Sboxes are resistance against Linear and Differential attack).

Moreover, other magic which gives stamina to the cipher is using Galois Field(Finite Field) in its arithmetic. Finite fields are abstract algebra structures that used in this cipher and we can model them with polynomials. Whenever you want to encrypt a plain-text, this plain-text converts to GF(2^8) and then the arithmetic in round functions is done based on that. Even "Sub Byte" in AES, which is a SBox, is built based on this Abstract Algebra. In conclusion, proper mixture of Linear elements ("Mix Column" , "Shift Row") and nonlinear element("Sub Bytes") together in 10 rounds alongside "Finite Fields in GF(2^8)" makes it strengthen.

If we want to explain GF(2^8) in simple: a byte(8 bits) which every bit can have 0 or 1 in it. But when we want to do arithmetic on them like sum or multiplication, the arithmetic rules are different from our conventional way and are based on Galois Field arithmetic rules.