What would happen to AES if we replaced MixColumns with ShiftColumns?

Question

I have this as a question in an assignment and I guess I don't fully understand the steps. I understand that if we omit MixColumns, then every byte of the ciphertext would not depend on every byte of the plaintext. But if we insert a new operation, ShiftColumns, which is like ShiftRows, but operates on columns, wouldn't this, combined with ShiftRows, provide a solution?

Answer 1

If MixColumns is omitted, the following happens:

The cipher essentially becomes a group of 8-bit block ciphers, that work only by subkey addition and s-box transformation. After every 3 rounds, the original bytes will shift back to their original locations, in the following pattern:

Original state
a b c d
e f g h
i j l k
m n o p

After round 1
a g i o
f k n d
l m c e
p b h j

After round 2
a n l h
k e b o
c p i f
j g d m

After round 3
a b c d
e f g h
i j k l
m n o p

With AES-128, 10 rounds would equal a single round shift, and with AES-256, 14 rounds would equal a double round shift. An optimized version of the cipher would exist where only the final byte repositioning occurs, and the subkeys themselves get the shifts during the key schedule.

The entire cipher can then be re-described as 16 8-bit block ciphers, all with different key schedules that do not use every bit of key material for each round, and a final position change. The 8-bit ciphers will not be secure. Only a maximum of 16 times the data should be required to attack it compared to an 8-bit cipher, which recovers the entire code page for that key.

Key recovery is substantially more likely with a chosen plaintext attack due to the way the key schedule is broken up across each 8-bit group than would be with a pure 8-bit cipher, and the fact that you have 16 of them to work with.