Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
Jean-Philippe Aumasson' "Serious Cryptography" says: "Without MixColumns, changes in a byte would not affect any other bytes of the state. A chosen-plaintext attacker could then decrypt any ciphertext after storing 16 lookup tables of 256 bytes each that hold the encrypted values of each possible value of a byte."
What would that attack look like? I can't beat the fact that SubBytes in non-linear.
From what I understand, he is basically saying that without MixColumns AES reduces to be a byte by byte cipher. So an attacker that can encrypt arbitrary plaintexts (that's the meaning of a chosen plaintext attack) can just request the encryption oracle to encrypt 16 byte blocks, while iterating each of the 256 possible byte values from 0x00-0xFF (==256 possibilities for each byte), thus obtaining as said 16 lookup tables, one for each byte of the block. This will basically expose the entirety of this "degenerate AES" cipher, under this specific key.
(Just to be clear: It doesn't matter that the S-boxes are not linear, they still operate on each byte independently, which is why the MixColumns step is so crucial, it does more than only "mix the columns!!" :)).
