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.)