# 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
• Welcome to Cryptography.SE. Your question is not totally clear. The key schedule is there, there are tons of implementations. So what do you want? – kelalaka May 22 at 19:22
• Did you read en.wikipedia.org/wiki/AES_key_schedule – kelalaka May 22 at 19:36

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.

There are however two implementation variants:

1. If about 160 bytes of additional temporary RAM are available, the Round Keys can be stored as they are computed, and re-used during the decryption.
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 difficulty is the un-doubling of the Rcon; it can be implemented using a small ROM table, or as Rcon=((0x00-(Rcon&0x01))&0x8D)^(Rcon>>1). As pointed by Craig McQueen in comment, the reversal of the key schedule uses the direct AES SBox.

Hardware implementations typically do 2; both options are justifiable in software.

• Reversing the key schedule calculations on-the-fly for decryption doesn't actually need an inverse S-box. It still uses the regular S-box. – Craig McQueen Dec 22 '14 at 2:11
• @Craig McQueen: you are absolutely right! Fixed the answer accordingly. – fgrieu Dec 22 '14 at 7:55

I've implemented AES-128 with byte calculations for a small embedded systems, with optional on-the-fly key schedule calculation. See aes-min on github.

The key schedule starting point for decryption must be obtained by running the key schedule calculation forwards, calculating all the rounds of the key schedule, to get to the last round. For a particular key, that decryption key schedule starting point only needs to be done once and saved. After that, the on-the-fly-key-schedule decryption runs the key schedule calculation backwards during each decryption operation.

Reversing the key schedule calculation requires the forwards S-box, so on-the-fly-key-schedule decryption requires both the forwards and inverse S-boxes.

The simplest way to perform the AES key expansion for decryption is to do it just as for encryption, but storing the subkeys as they are generated, rather than using them. Then use them for decryption, just in the reverse of the order they where produced.

Another option, often used in hardware (much less useful in software), and relatively simple since it's AES-128, is to sequentially compute the last subkey, again just as for encryption; use it; then repeatedly walk back to the previous ones using the fact that the transformation from one subkey to the next is easily reversed. This saves RAM, trading is against computation.

Both methods use that the 11 subkeys (the first of which is the key) are the same for encryption and decryption, only used is the natural order they are produced for encryption, and the reverse order for decryption.

• So you mean that I should store the different key each round in a variable. So the inverse key expansion is the same but it will be preformed before the actual decryption. So the inverse key expansion will first create 9 different round keys and store them. Right after that the decryption process will take place with the round keys in the reverse order? – Ilay Samuelov May 22 at 19:54
• @Ilay Samuelov: there are 11 AddRoundKeys. The first one is the key itself. The last is used right after being generated, thus needs not absolutely be stored if you redo the key schedule for each block. So you can get away with storing 9 subkeys, and special-case the first (last used in decryption) and last (first used) of the 11 subkeys. Still, the simplest is to make an array with the 11 subkeys, And you need at least 10 + the initial key for speed with multiple blocks. – fgrieu May 22 at 20:00
• Hey! In x86 it can be a bit hard to do that. But I thought on a way! Maybe storing al the round keys in order i a big one array. Then taking the last 16 bits by doing: Arr[160]-arr[144] – Ilay Samuelov May 22 at 20:25
• @Ilay Samuelov: please don't make numerous separate comments, especially within the time allowance for editing these. That eats vertical space and other resources, and can raise automated alerts. The process of joining comments is largely manual, tedious, error-prone, and reserved to mods. – fgrieu May 23 at 5:17