AES Encryption

9 min readJan 11, 2021

Since becoming a security engineer, I’ve been working my way through the Cryptopals challenges and writing about them. If you’ve been following along, we’re just starting to get to challenges that start to use AES encryption. For this article, I’m going to take a break from actually solving any challenges and do a deep dive on how AES-128 encryption works. It’s definitely not necessary to solve the upcoming challenges, so if it seems boring to you feel free to skip it, but I don’t like things to be a black box, so I wanted to know what was actually happening when applied AES encryption.

What is AES?

AES stands for Advanced Encryption Standard. If you take a look at a lot of user agreements, a bunch of them will tell you that your data is encrypted using some form of AES. AES is a block cipher encryption method, meaning that the plaintext is split into blocks of a specified size, and the encryption method is applied to each block.

Based on the key size, the plaintext will go through a series of rounds of encryption.

128 bit key — 10 rounds
192 bit key — 12 rounds
256 bit key — 14 rounds

Important Concepts

Hex Encoding

We’re going to be breaking strings down into bytes, and it can be a little easier on the eyes to deal with hex than raw bits.

XOR

We’re going to be using XOR against two bytes a lot in the process of breaking down AES, so it’s a good idea to know how that works.

The High Level

Key Expansion — each round of encryption needs it’s own key, so based on our key size we’re going to need between 10 and 14 keys. To do this, we’ll go through a process called key expansion on our initial given key.
The encryption rounds (10–14 rounds based on key size)
a. Substitute Bytes: Based on a lookup table we will switch bytes
b. Shift Rows: Bytes are organized onto a table, and bytes are shifted a number of columns based on what row they are in
c. Mix Columns: Columns in the created table are multiplied against a constant table(not done in the last round).
d. Add Round Key: XOR against the key for the round.
DONE!

Key Expansion

The first thing that we need to do is expand our key. For this example, we’re going to use the key: YELLOW SUBMARINE . Because that key is 128 bits (16 bytes), we are going to go through 10 rounds of applying the encryption algorithm. Each round needs its own key, so we need a way to get 10 keys out of 1. We do this by a process called key expansion.

For the next step, I’m going to convert the key to hex: 59454c4c4f57205355424d4152494e45 . We’re going to take this hex and break it into a 4x4 table, filling columns first.

As you can see in the table above, each 4 byte column is referred to as a word and we’ve split our 16 byte key into 4 words. This is going to be key 0, and we are going to generate keys 1–10.

1. Rotate Word 3

Word 3 starts out as 52 49 4e 45 in our example. For the first step, we’re going to take the first byte, move it the end and shift everything to left, so we end up with 49 4e 45 52 .

2. Replace Word 3 Bytes with S-Box

For this next part, we’re going to reference a chart called the S-Box. For each byte we will find the replacement byte on this table. So for our first byte 49, we look up 40 on the x-axis, and reference it to 9 on the y-axis, and see that we have 3b

S-Box

After our byte replacement, we end up with 3b 2f 6e 00

3. XOR Result with round constant

Next we need to XOR the result with a constant based on the round we are on. The constants (in hex) are

So when we XOR our 3b2f6e00 against 01000000 we get 3a2f6e00

4. XOR result with Word 0

This is going to create Word 4 (the first part of our next key). We will XOR the result of the previous steps with Word 0, and this will give us Word 4.

3a2f6e00 ^ 59454c4c = 636a224c

5. More XOR

Now we just have a bunch more XORing to do.
Word 1 ^ Word 4 = Word 5
Word 2 ^ Word 5 = Word 6
Word 3 ^ Word 6 = Word 7

4f572053 ^ 636a224c = 2c3d021f (Word 5) 
55424d41 ^ 2c3d021f = 797f4f5e (Word 6)
52494e45 ^ 797f4f5e = 2b36011b (Word 7)

6. Repeat!

Words 4–7 are our key for round 1 of encryption, but we have ten rounds, so we need nine more keys! The process is repeated again with the round one key to generate the round 2 key, and then on the round 2 key to generate the round 3 key, and so on until we have 10 rounds worth of keys.

Key expansion

The Encryption!

We have our key YELLOW SUBMARINE , and we’re going to use it to encrypt the plaintext Yay cryptography since it fits our 16 byte block size. I’ll go ahead and convert that into hex, since that’s what we’ve been using so far: 5961792063727970746f677261706879 .

When the encryption is done, we should end up with the hex string e13c11fa5ed5c460f17bfe872e8a37d9 .

0. XOR Plaintext

Before we start the 10 rounds of encryption, the plaintext is XOR’d against our initial key. This gives us the result

0024356c2c255923212d2a333339263c

which we will put into a 4x4 table

+--------+--------+--------+--------+
| Word 0 | Word 1 | Word 2 | Word 3 |
+--------+--------+--------+--------+
| 00     | 2c     | 21     | 33     |
| 24     | 25     | 2d     | 39     |
| 35     | 59     | 2a     | 26     |
| 6c     | 23     | 33     | 3c     |
+--------+--------+--------+--------+

1. Byte Substitution

For this step we’re going to use the same s-box we used in key expansion to substitute the bytes. Here’s the table again

S-Box

After subbing out our bytes using the table, we end up with

+--------+--------+--------+--------+
| Word 0 | Word 1 | Word 2 | Word 3 |
+--------+--------+--------+--------+
|     63 | 71     | fd     | c3     |
|     36 | 3f     | d8     | 12     |
|     96 | cb     | e5     | f7     |
|     50 | 26     | c3     | eb     |
+--------+--------+--------+--------+

2. Shift Rows

Now that we’ve done our byte substitution, each row rotates a number of times based on which row it is. The first row stays the same, the second row rotates left once, the third row rotates twice, and the last row rotates 3 times. So we will end up with this

+--------+--------+--------+--------+
| Word 0 | Word 1 | Word 2 | Word 3 |
+--------+--------+--------+--------+
| 63     | 71     | fd     | c3     | // No Change
| 3f     | d8     | 12     | 36     | // Shift left 1 time
| e5     | f7     | 96     | cb     | // Shift left 2 times
| eb     | 50     | 26     | c3     | // Shift left 3 times
+--------+--------+--------+--------+

3. Mix Columns

This step is skipped in the last round

Fair warning, this step get pretty mathy, and I’m not a mathematician by any stretch of the imagination, so apologies if some of the terminology is off, I hope I can at least get the point across of what we’re doing. For this step, we’re going to multiply our 4x4 matrix with a constant 4x4 matrix provided below

+----+----+----+----+
| 02 | 03 | 01 | 01 |
+----+----+----+----+
| 01 | 02 | 03 | 01 |
+----+----+----+----+
| 01 | 01 | 02 | 03 |
+----+----+----+----+
| 03 | 01 | 01 | 02 |
+----+----+----+----+

and we’re going to populate this

+----+----+-----+-----+
| r1 | r5 | r9  | r13 |
+----+----+-----+-----+
| r2 | r6 | r10 | r14 |
+----+----+-----+-----+
| r3 | r7 | r11 | r15 |
+----+----+-----+-----+
| r4 | r8 | r12 | r16 |
+----+----+-----+-----+

To get the result for r1 of our result table, we’re going to have to multiply row 1 of our constant table against column 1 of our current cipher text. To get r2, we’ll multiply row 2 of our constant table against column 1 of our cipher text. r5 will be row 1 of our constant table against column 2 of our cipher text and so on. To do all this multiplication we’re going to need to use finite field arithmetic in GF(2⁸). That’s a bunch of math terms, so I’m going to break it down as best as I can.

r1 = (02 * 63) + (03 * 3f) + (01 * e5) + (01 * eb)

We’re going to break these values down to binary, and convert them into polynomials. As an example, if we had ff as our hex value, then it would be 11111111 in binary. If we convert that to a polynomial, it would be x⁷+x⁶+x⁵+x⁴+x³+x²+x+1

The hex value 63 in binary is going to be 01100011 , and in polynomial form it will be x⁶+x⁵+x+1 and the hex value of 02 is going to be 00000010 in binary and x in polynomial. So 02 * 63 = x(x⁶ + x⁵ + x + 1) . Simplified down is x⁷ + x⁶ + x² + x .

3f in binary is going to be 00111111 and 03 is 00000011 . So 03 * 3f expressed in polynomial is going to be x+1(x⁵+x⁴+x³+x²+x+1) . That simplified down is x⁶ + x⁵ + x⁴+ x³ + x² + x + x⁵ + x⁴ + x³ + x² + x + 1 . The last two elements are just multiplied by one, so our expression broken down into polynomials will be

x⁷ + x⁶ +                x² + x     +
     x⁶ + x⁵ + x⁴ + x³ + x² + x     + 
          x⁵ + x⁴ + x³ + x² + x + 1 + 
x⁷ + x⁶ + x⁵ +           x² +     1 + 
x⁷ + x⁶ + x⁵ +      x³ +      x + 1

When we do this finite field arithmetic, we cancel out two matching values. For example, since we have 3 values of x⁷ , 2 cancel out, and we are left with just one x⁷ , and we have 4 values of x⁶ , so they all cancel each other out and we have none. After doing this we are left with x⁷ + x³ + 1 . If we convert that to binary it’s 10001001 . That converted over to hex is 89. So r1 = 89 . This is repeated for all 16 squares of our matrix.

There is one more step to this you might have to do. To illustrate it, I’m going to find the value of r11 .

r11 = (01 * fd) + (01 * 12) + (02 * 96) + (03 * 26)     x⁷ + x⁶ + x⁵ + x⁴ + x³ + x² +     1 + 
                    x⁴ +           x     + 
x⁸ +           x⁵ +      x³ + x²         + 
          x⁶ +           x³ + x²         +
               x⁵ +           x² + x

If we simplify this down, we’re left with x⁸ + x⁷ + x⁵ + x³ + 1 . There’s a problem with this though. x⁸ is too big to fit into a byte. When this happens, we have to XOR our result with an irreducible polynomial, which is
x⁸ + x⁴ + x³ + x + 1 . So our result for r11 is going to be

110101001 ^ 
100011011
----------
010110010 -- Binary value
b2        -- Hex Value

So our value for r11 will be b2.

After doing this with each value in our matrix we end up with

+----+----+----+----+
| 89 | 36 | 67 | cf |
+----+----+----+----+
| c2 | 88 | 5e | 2a |
+----+----+----+----+
| ab | ac | b2 | 26 |
+----+----+----+----+
| b2 | 1c | d4 | 3e |
+----+----+----+----+

4. Add Round Key

In this step, we’re going to take the corresponding key for the round, and XOR that key with our matrix, similar to what we did before round 1.

The key for round 1 is 636a224c2c3d021f797f4f5e2b36011b , and our text is 89c2abb23688ac1c675eb2d4cf2a263e .

636a224c2c3d021f797f4f5e2b36011b ^
89c2abb23688ac1c675eb2d4cf2a263e
---------------------------------
eaa889fe1ab5ae031e21fd8ae41c2725 ---- RESULT OF ROUND 1!

With that we have the result of round 1! We just need to do that 9 more times (leaving out mix columns on the final round).

References and Digging Further

If this interests you and you want to do some more research, or you are having trouble following my examples, then I recommend checking out these sources.

https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.197.pdf