Why is MixColumns omitted from the last round of AES?

Question

All rounds of AES (and Rijndael) have a MixColumns step, save the last round which omits it. DES has a similar feature where the last round differs slightly. The rationale, if I recall correctly, was to "make the cipher appear similar in reverse as it does in the forward direction."

Why does this make AES$^{-1}$ look similar to AES? And how does this help in implementing the block cipher?

Answer 1

Having taken The Design of Rijndael from the library just yesterday, I had a look on this problem, too. Fixee wrote in a comment:

However, my question is not so much about security implications, but rather "how does omissions of MixColumns make the inverse cipher similar to the cipher?" and "how does this help in implementing the cipher?"

The encryption has these steps in each round (List 3.2, page 34), with an additional AddRoundKey at the beginning and a shorter round at the end:

Round(State, ExpandedKey[i]) {
    SubBytes(State);
    ShiftRows(State);
    MixColumns(State);
    AddRoundKey(State, ExpandedKey[i]);
}

The decryption looks this way, when done in a straightforward way (List 3.5, page 47) (with a shorter initial round):

InvRound(State, ExpandedKey[i]) {
    AddRoundKey(State, ExpandedKey[i]);
    InvMixColumns(State);
    InvShiftRows(State);
    InvSubBytes(State);
}

---

As mentioned in a comment, without the omission of the one MixColumns step all 10 rounds would be identical (like the ones above), and we could do the total encryption and decryption as

AddRoundKey(ExpandedKey[0])
for i = 1 .. 10:
    Round(State, ExpandedKey[i])

for i = 10 .. 1:
    InvRound(State, ExpandedKey[i])
AddRoundKey(ExpandedKey[0])

If we move the AddRoundKey to the end of the inverse function, it would look like this:

InvRound'(State, ExpandedKey[i]) {
    InvMixColumns(State);
    InvShiftRows(State);
    InvSubBytes(State);
    AddRoundKey(State, ExpandedKey[i]);
}

AddRoundKey(ExpandedKey[10])
for i = 9 .. 0:
    InvRound'(State, ExpandedKey[i])

In this form, we would have a similar global structure of the encryption and function, but the round functions for encryption and decryption are still structurally different. We (as hypothetical re-inventors of Rijndael) can do better.

---

Back to our (naive) inverse round function:

InvRound(State, ExpandedKey[i]) {
    AddRoundKey(State, ExpandedKey[i]);
    InvMixColumns(State);
    InvShiftRows(State);
    InvSubBytes(State);
}

By swapping InvMixColumns and AddRoundKey with a modified ExpandedKey) and also swapping InvShiftRows and InvSubBytes (as one of them works on each byte individually, and the other one just transposes whole bytes), we see this is equivalent to this one:

InvRound(State, ExpandedKey[i]) {
    InvMixColumns(State);
    AddRoundKey(State, InvMixColumns(ExpandedKey[i]));
    InvSubBytes(State);
    InvShiftRows(State);
}

(We still have a shorter group at the beginning, and a final AddRoundKey at the end.)

Now by using a grouping that uses both InvMixColums and AddRoundKey at the end of the round, we will swap the positions of InvSubBytes with InvShiftRows and swap the positions of InvMixColumns with AddRoundKey to get this equivalent description instead (List 3.8, page 49), with again a shorter last round, and an initial AddRoundKey:

EqRound (State, EqExpandedKey[i]) {
    InvSubBytes(State);
    InvShiftRows(State);
    InvMixColumns(State);
    AddRoundKey(State, EqExpandedKey[i]);
}

But as it stands, this round structure, combined with the initial AddRoundKey, is not the inverse of the encryption. The last MixColumns of encryption has no corresponding InvMixColumns, and the last InvMixColumns of decryption has no corresponding MixColumns. We will solve this by omitting the MixColumns step from the last encryption round and the InvMixColums step from the last decryption round. With that change, since both encryption and decryption omit of the MixColumns / InvMixColumns step of the last round, their round structure remains the same and decryption is the inverse of encryption.

This combination of substitution, row-shifting and column-mixing (in this order) looks quite similar to the operation sequence for encrypting, and is now assumed to be more efficiently implemented than the inverse sequence used in the straightforward inversion.

Also, we can share some of the code (for software implementations) or chip area (for hardware implementations) for encryption and decryption.

Of course, we now need a tweak to the key schedule for decryption: apply InvMixColumns on each round key, other than the first and last. As the key schedule is only done once for many blocks, this is not a big overhead.

On 32-bit (or larger) processors with some fast cache (or ROM), one can implement this sequence of substitution, row-shifting and column-mixing (which is independent of any key) for each 32-bit column by looking up four 32-bit values (depending on different bytes in the old state) in four 1kB lookup tables and XORing these together. By using different rotations after the lookup, we can use just one of those tables (1 kB). (Details are in section 4.2, pages 58/59 in the book.) A part of this table can be used for the final round, too (where there is no column mixing).

Here we can use the same code with different (sets of) tables for both decryption and encryption. (These tables don't change with different keys, so we put them in ROM, or calculate them when first needed.)

(These lookup tables open the way to timing attacks if they don't fit completely in the processor cache, and/or are removed from the cache by other programs running concurrently.)

Answer 2

According to the Rijndael design document (top of page 7):

In order to make the cipher and its inverse more similar in structure, the linear mixing layer of the last round is different from the mixing layer in the other rounds. It can be shown that this does not improve or reduce the security of the cipher in any way. This is similar to the absence of the swap operation in the last round of the DES.

In a normal AES round, MixColumns precedes the AddRoundKey operation. However it is possible to swap the order of these operations. By performing a slight modification of the AddRoundKey operation first and then MixColumns second, you can receive the same result. Therefore, it was thought that the final MixColumns does not add any security since it is an unkeyed, reversible operation that can be made to be the last step in the final round.

However if theoretically you could do the following attack, there are security consequences. Consider the AES variant where MixColumns is performed in the final round of encryption. To attack the decryption function, the adversary may swap the order of MixColumns and AddRoundKey so she can undo MixColumns for free. Now suppose she were able (somehow) to recover some information about the round key used in AddRoundKey. Because she swapped the operations, what she recovers is not actually information about the round key as spit out by the key schedule, rather it is information about the round key with an inverted MixColumns applied to it.

In short, it is harder to use what information she knows about the last round key to determine information about the second-to-last round key if the information is actually about a transformed version of the last round key. (This attack was linked to by @Samuel Neves in a now deleted comment so credit to him.)