# On-the-fly computation of AES Round Keys for decryption?

The usual implementation of AES first computes all the Round Keys sequentially starting from the key, and stores them in RAM for later uses. However, when enciphering a single block with a key that will be used for that purpose only, or when RAM is very sparse, or perhaps in hardware, it is advantageous to use the Round Keys a they are being generated, rather than store them. Quoting the Rijndael submission to NIST:

The key schedule can be implemented without explicit use of the array W[Nb*(Nr+1)]. For implementations where RAM is scarce, the Round Keys can be computed on-the-fly using a buffer of Nk words with almost no computational overhead.

It is said this also works for deciphering:

The key expansion operation that generates W is defined in such a way that we can also start with the last Nk words of Round Key information and roll back to the original Cipher Key. So, calculation ’on-the-fly' of the Round Keys, starting from an “Inverse Cipher Key”, is still possible.

However, the how-to is left as an exercise to the reader. In particular: Can the last Round Key (the first used when deciphering) be computed directly, rather than sequentially?

-
I think the idea is to run the key schedule once forward to the last round key, and store this, and then for each block run it backwards to get the individual round keys. –  Paŭlo Ebermann Dec 7 '12 at 8:27
@PaŭloEbermann: I understand how what you describe can work, and might be useful if there is not enough RAM (or flip-flops) to store the Round Keys even temporarily. So the answer to "Can the last Round Key be computed directly, rather than sequentially?" would be: "No"? –  fgrieu Dec 7 '12 at 11:10
I think one can write a big formula for the last round key, but you will have to apply at least all the $f_i$ functions sequentially, so I don't think it is much faster/simpler than running the key schedule. I didn't analyze this thoroughly, though, so I'm a bit resisting to plainly answer "No". –  Paŭlo Ebermann Dec 7 '12 at 13:03

When performing AES decryption with on-the-fly computation of AES Round Keys, there is no choice beyond running the key schedule forward to the last Round Key (the first used when deciphering). The structure of the key schedule creates enough non-linearity and diffusion at each of the 10 steps that no shortcut is practicable. One step comprises 4 SubBytes transformations, 16 XORs of 8-bit quantities, some rotations of all the 16 bytes of the Round Keys, and the doubling of the byte Rcon in $\operatorname{GF}(2^8)$, in a manner such that what's produced by a byte XOR goes thru SubBytes on the next step, and non-linearly influence all the 16 bytes after 4 steps. Even halving the number of steps to reach the last Round Key would be extremely hairy, to the point of being counterproductive.
2. Otherwise (and memory is often tight in a small micro-controller, or unavailable in hardware), each of the 10 steps can easily be reversed. The only remote difficulties are inverting the SubBytes transformation and the doubling of the Rcon; but an inverse SubBytes table (or block) is a practical necessity for decryption anyway, and the de-doubling of Rcon can be implemented as Rcon=((0x00-(Rcon&0x01))&0x8D)^(Rcon>>1).