# Is there an alternative AES schedule?

I'm currently reversing an AES implementation for disk encryption. The odd thing I'm stumbled about is a key schedule where the encryption round keys are not the same as the decryption round keys (in "reversed order"). Altough the first 4 bytes, i.e. the first round key for the encryption, and the last 4 bytes, i.e. the last round key for the decryption, are the same. The other round keys are totally different.

Is there an optimization that requires the round keys to be computed in a different manner?

• Are you saying that for decrypting, the round keys are in reversed order, or that they aren't (e.g. maybe in some random pattern)? – Jonathan Nov 28 '14 at 16:26
• As per Thomas Pornin's answer, what you are seeing is called the "equivalent inverse cipher" and is the most common implementation of AES, as it is faster for decrypt – Richie Frame Nov 29 '14 at 8:37

If you look at the algorithm description, you see that, at a high-level, the encryption algorithm looks like this:

            addRoundKey(0);
for (int i = 1; i < rounds; i ++) {
subBytes();
shiftRows();
mixColumns();
}
subBytes();
shiftRows();


The decryption algorithm will then look like this:

            addRoundKey(rounds);
for (i = 1; i < rounds; i ++) {
invShiftRows();
invSubBytes();
invMixColumns();
}
invShiftRows();
invSubBytes();


Now, if you view the 16-byte state as a vector in space (Z2)128, then the ShiftRows() and MixColumns() transforms are linear, and so is the addition of a round key (addRoundKey() -- really, a bitwise XOR). Moreover, the ShiftRows() is byte-oriented, therefore it can commute with SubBytes() (since SubBytes() works on each state byte independently). Therefore, it is customary for AES implementations to combine SubBytes(), ShiftRows() and MixColumns() into a single step with 8->32 lookup tables (you need four of them, for a total of 4 kB of tables). This optimization is what the Wikipedia page alludes to.

If you try to do that with decryption, in the loop above, you will see that the addRoundKey() step happens between invSubBytes() and invMixColumns(), which is inconvenient. The solution is to move the addRoundKey() one step down, but then the round key must be modified to account for the move (in simple words, if you add the round key after the invMixColumns(), then you must add a round key that has been already "invMixColumnsed"; it works because of linearity).

In that case, decryption becomes:

            addRoundKey(rounds);
for (i = 1; i < rounds; i ++) {
invShiftRows();
invSubBytes();
invMixColumns();
}
invShiftRows();
invSubBytes();