Now that we've broken 4-round AES, let's try and see what we can do if we add an extra round at the end to make it a 5-round AES.

You could guess 4 bytes of the last round key to reverse the state until the end of the 4th round (second to last round). Right after XORing it with the penultimate round key. Here you could also guess 4 bytes of that last round key to continue the relevant bytes and end up by performing the same attack as the previous one. In total we have to guess 8 bytes of subkeys to start the attack, that's already a lot.

What if we could swap the penultimate round's MixColumn operation with the AddRoundKey operation? That would allow us to only guess one byte of the penultimate round key.

Well guess what. We can. Sort of.

How to do?

The MixColumns is linear with respect to the column input. This is a fancy way to mean:

\[ \begin{align*} &\text{MixColumns}(\text{state)} \oplus \text{RoundKey} \\ = &\text{MixColumns}(\text{state}) \oplus \text{MixColumns}(\text{MixColumnsInv}(\text{RoundKey})) \\ = &\text{MixColumns}(\text{state } \oplus \text{MixColumnsInv}(\text{RoundKey})) \end{align*} \]

1. The first line represented our state after the penultimate MixColumns followed by the AddRoundKey transformation.
2. The last line represent the state we wanted to achieve: the AddRoundKey transformation now happens after the MixColumns operation. It's enough to allow us to do our attack without having to guess 4 bytes of the penultimate round key, but instead only a single byte of the penultimate MixColumnsInv(RoundKey).

In total, with the four bytes of the last round key, we now have to guess 5 bytes to recover one byte of the last round key. Here's how the final attack now looks like:

This attack is taking too much computing power already. To cover 5 bytes of key you need to test \(2^{8*5} = 2^{40}\) possibilities tops. This is not impossible, just not fun as an unoptimized code and an OK machine will take too long to finish the attack.

Instead we will satisfy ourselves with these explanations, and maybe even try to understand how to extend this attack to 6-round AES in the next section.