33
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ As I remember the AES reasoning, for the last round this MixColumns step would not add any security, and thus it was omitted. I'll have to look more thoroughly, though ... I just did take the "Design of Rijndael" book from the library, but now I've got to go to sleep. $\endgroup$ Nov 28, 2011 at 23:56
  • 1
    $\begingroup$ Try to google for "Influence of the final round" (with quotation marks). The only hit I get is page 152 of the book "The Design of Rijndael" where Joan and Vincent explain their reasons. $\endgroup$
    – j.p.
    Nov 29, 2011 at 13:24
  • 3
    $\begingroup$ Sorry, I should have read your question more carefully instead of reading the answers/comments. My last comment gives the reasons why it is secure to emit the final MixColumn. For your first question google for rijndael "graphical representation of the algorithm" (with quotation marks). The symbols of the upper line stand for AddRoundKey, SubBytes, ShiftRows, MixColumns, AddRoundKey, ShiftRows, SubBytes and AddRoundKey (using the names from en.wikipedia.org/wiki/Advanced_Encryption_Standard). $\endgroup$
    – j.p.
    Nov 29, 2011 at 13:52
  • 1
    $\begingroup$ I removed my answer, which was plain wrong, because I misplaced the hypothetical MixColumns. The justification on page 152 of "The Design of Rijndael" is much more complex than I had stated; it only concludes "that the removal of the MixColumns step in the final round does not weaken Rijndael with respect to the four-round saturation attack". $\endgroup$
    – fgrieu
    Nov 29, 2011 at 16:04

2 Answers 2

22
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ I feel this answer is not answering the question (even if accepted). Let me reformulate what I would like to know: If our goal is to make all rounds in the encryption/decryption equal (I stress that the round function will be different in enc/dec), what is the problem of adding MixColumns in the last round? As far as I can see, AES-ENC would then simply become: 1. AddKey 2. repeat RoundFunc 10 times. And for AES-DEC we get: 1. AddKey (last RndKey) 2. repeat InvRoundFunc' 10 times, where InvRoundFunc' = 1. InvMixColumns 2. InvShift 3. InvSubBytes 4. AddRndKey. Why is this not possible? $\endgroup$
    – hakoja
    Jan 22, 2013 at 12:37
  • $\begingroup$ Of course this would be possible. The idea is that with the ommission one can use a InvRoundFunc which is structurally similar to RoundFunc, and as such can share code (in Software) or chip area (in hardware) with the original RoundFunc. $\endgroup$ Jan 23, 2013 at 8:28
  • $\begingroup$ Ok, fair enough. I will remove my downvote when the timeout has passed. Still, since many modes of operation allows you get away with only the encryption direction, I don't understand why an equal RoundFunction wouldn't be preferable for all rounds (Ref. Fixee's comment about the hassle's of the last round omission, in his answer to PulpSpy's answer) $\endgroup$
    – hakoja
    Jan 23, 2013 at 11:38
  • $\begingroup$ Ah, apparently my vote has been locked in, so I'm unfortunately not able to change my downvote. Sorry about that :( $\endgroup$
    – hakoja
    Jan 23, 2013 at 11:40
  • 2
    $\begingroup$ While there are some modes of operation which only need the forward direction (and I think they don't even need a random permutation, just a random function), many of them (including the "default-like" CBC) need both directions, and this was even more usual at the time of the AES competition. $\endgroup$ Jan 23, 2013 at 20:50
10
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ Thanks for your response, PulpSpy. 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?" For the latter, I have always found it a pain to implement this special-case in AES where you have to omit MixColumns in the final round: for example, you can't use the precomputed tables. $\endgroup$
    – Fixee
    Nov 29, 2011 at 17:01
  • $\begingroup$ Oh sorry — I answered a tangental question. I'm not sure the answer to that. $\endgroup$
    – PulpSpy
    Nov 29, 2011 at 18:27
  • $\begingroup$ @Fixee Actually, you can use the precomputed tables for the final round too, you just use them a bit differently. $\endgroup$ Jan 23, 2013 at 20:52
  • $\begingroup$ @PaŭloEbermann Yes, but you need a separate set of precomputed table just for the final round. This is onerous in environments where memory is tight. $\endgroup$
    – Fixee
    Jan 24, 2013 at 0:30
  • $\begingroup$ @Fixee I seem to recall that a part of the same table set can be used, but I don't remember the details. I'll have to look it up. $\endgroup$ Jan 25, 2013 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.