I recently started the cryptopals challenge and had to re-study how AES works to implement it in Go. I decided to publish my notes on the AES algorithm to help my future self and anyone here get started or get re-acquainted with the cryptographic standard.
This article is not a copy-paste of the AES specification. I wanted to write an introduction that helps the reader understand the basics of the AES key schedule. At the end of this article you should know enough to read the actual AES specification with ease and implement the key schedule yourself.
Let's start with a quick recap. The Advanced Encryption Standard is a symmetric cipher, which means that you need a secret key to encrypt a plaintext and the same key to decrypt the ciphertext. The key can be
256 bits. In the rest of this article I assume that we are working with AES-128 that uses a key of 128 bits.
But AES is also a block cipher, which means that it encrypts blocks of 128 bits in multiple rounds before outputting the final ciphertext.
Since there are multiple rounds of encryption for one block, do we use the same key every time ?
No we don't do that because it would expose us to slide attacks: a cryptanalysis technique relying on the fact that we use the same key every round.
To avoid using the same key every round, we derive new keys (called Round Keys) from the original one. This is called a key schedule:
A key schedule is an algorithm that calculates all the round keys from the key.
In this article I will use the same notation found in the original specification. Let's start by defining some constants. We write:
Since there are 10 rounds, we have to produce 10 round keys. Each round key is then used in the corresponding round:
The AES key schedule generates a total of 11 subkeys of 128 bits each (even in AES-192 and AES-256).
11 subkeys? But there are only 10 rounds !
That's because first key is XOR'd with the plaintext before the first round. Check out my post explaining AES for more info.
The operations are done on 32-bit words so we adapt our notation to work with this: the result of the key schedule is an array of 32-bit words denoted , where .
Consider the cipher key composed of 128 bits. We split the key in 32-bit words denoted :
See how I used the notation ? This is because the cipher key is actually the first round key : .
is only applicable for AES-128.
Then each new subkey depends on the previous subkey. To compute the algorithm is the following:
The general rule is that:
For instance .
The exception occurs when we have to compute a new and . Here we want to compute and . In this case, the previous word undergoes some transformation with the functions
Rcon (more on this later).
To compute , we apply the same algorithm to . In total this is repeated 10 times.
Independently of the size of the cipher key you are using (
AES-256), the length of the Round Key is always the size of the state. In other words, the size of the Round Key is the size of a block.
RotWord is quite simple. It takes a 4-byte word and returns .
Here each is a byte composed of 8 bits.
SubWord is a little bit more complex. It takes a 4-byte word and applies the AES S-Box to each of the bytes to produce a new 4-byte word .
The S-box is a substitution table also used in the encryption algorithm.
Think of it as a big lookup table that maps an 8-bit input to an 8-bit output.
b3 is mapped to
For an input there is a way to compute the output . You start by computing the multiplicative inverse of in , we name it .
Then you can compute using the affine transformation - source wikipedia:
In practice, it's easier to implement the S-box as a constant lookup table. I give some complementary information in my post about the AES algorithm.
Rcon is a round constant word array. For each round, you get 4-byte word.
For your convenience here are the values of noted as , in hexadecimal:
This is it, you now know enough to implement the AES key schedule on your own (with the official specification as a reference of course). One last thing, you might not have noticed that an attacker who managed to retrieve a round key , is able to determine all the other round keys as well as the cipher key by reversing the algorithm. An attacker could retrieve a round key thanks to a side channel attack.
I wrote two other posts about AES: