# Consequences of AES without any one of its operations

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?

• Hint: what does linearity mean? If $AES(x) \oplus AES(y) = AES(x \oplus y) \oplus c$, for any $x$ and $y$ (and a fixed, key-dependent $c$), how could this be exploited? – poncho Nov 13 '14 at 16:39
• So after $10$ rounds, the ciphertext is a linear combination of shift row, mix column and addroundkey. If we have a pair of plaintext and ciphertext, then the key can be recovered and hence all ciphertext can be decrypted. Is this correct? – Idonknow Nov 14 '14 at 6:11
• Suppose you knew the plaintexts the correspond to the ciphertexts 1000...00, 0100...00, 0010...00, ..., 0000...001, and finally 0000...00 (all zeros). How could you use that to decrypt an arbitrary ciphertext? Extra credit question: how could you use that technique if you were given 129+ random plaintext/ciphertext pairs? – poncho Nov 14 '14 at 16:24
• Yup, except for one glitch; the cipher is affine rather than linear (hence, there's this constant c sitting in the relationship); this is actually pretty easy to workaround; one way is adding an extra implied bit to each plaintext/ciphertext, which is set on every plaintext/ciphertext you have, and solve it as a set of GF(2) linear equations over 129 variables. – poncho Nov 14 '14 at 17:43
• @poncho: That looks like an answer to me. Want to make it one? – Ilmari Karonen Nov 17 '14 at 11:07