SafeHouse

Follow

CodeX

--

Governments, militaries, banks and corporations rely on it. It’s responsible for securing most, if not all of your personal and financial data. There are special CPU instructions for it. It is the only cryptographic algorithm approved by the NSA.

We’re of course talking about the Advanced Encryption Standard (AES), the most commonplace and secure symmetric encryption algorithm yet developed.

This will be the longest article we write for the time being 😊. We’re going to take a deep dive into how this algorithm works. Modern cryptographic algorithms are by no means trivial; they use concepts from advanced mathematics to achieve a high level of security. But we don’t expect you to be a mathematician.

While there are many articles about AES, most of them are either too technical or leave out important information. With this article we hope to strike the perfect balance between comprehensiveness and accessibility. However, we must admit that this article will require some level of comfort with math, as mathematical concepts are introduced here.

It must be stated that you should not try to implement AES by yourself in a production application, or risk a side channel attack. Use the many free cryptographic libraries that offer tested implementations of whatever algorithms you need.

First, a brief refresher on what AES is.

AES is not the name of the algorithm itself, but a title awarded by the National Institute of Standards and Technology (NIST) to the algorithm they deemed to be the de facto standard for encryption. The actual name of the algorithm is Rijndael, and it was selected by the NIST over a number of algorithms to replace the former standard, known as DES (Data Encryption Standard). Rijndael was approved by the NIST in 2001 and adopted by the US government in 2002. It remains the standard cipher used by the US government and institutions across the world.

AES is a symmetric cipher, which means that a single key is used to encrypt and decrypt the same data. AES can be performed with the following key sizes: 128 bits, 196 bits and 256 bits. Generally, increasing the key size also increases the level of security. Rijndael works for any key size that is a multiple of 32 bits, but the NIST chose specific sizes (and other parameters) that balance performance and security.

It is also a block cipher, meaning that the data is divided into blocks before encryption. AES divides plaintext into blocks of 16 bytes (128 bits).

The gist of AES is this: we arrange each block of the plaintext into a 4x4 matrix and repeatedly perform a set of operations on it. We call each iteration a round, and we perform 10, 12 or 14 rounds depending on the key length (this is another parameter chosen by NIST):

For each round, we generate a round key from the main key using the Rijndael Key Schedule.

There are four operations on the 4x4 matrix that we will define:

Not every round of operations is the same; for the first round, we only add the round key, and for the last round we omit the mixColumns() step. So the pseudocode for the AES algorithm might look something like this:

blocks := divideIntoBlocks(plaintext); roundKeys = getRoundKeys(key)

This section may appear rather esoteric. We told you we would explain AES in detail and we weren’t lying. Luckily, we believe that the concepts in this section can be understood with only high-school level math and basic programming experience. Don’t let the fancy words throw you off!

Let’s introduce a concept in abstract algebra called a Galois field or finite field. A field is a set (meaning a collection of objects) with operations that act on the set and behave similarly to addition, subtraction, multiplication and division. In other words, the operations satisfy a number of properties that also hold true for addition/subtraction/multiplication/division over the rational numbers. In fact, the rational and real numbers with these four operations qualify as a field. The finite qualifier just means that the set has a finite number of elements.

We won’t go into the specific definition of a field. Just think of it as a set of numbers where addition, subtraction, multiplication and division are redefined.

AES uses a specific Galois field, which we will call Rijndael’s finite field, to perform many essential operations. In particular, it uses GF(2⁸) with irreducible polynomial x⁸ + x⁴ + x³ + x + 1. You’ll understand what this means in a bit.

The Galois field GF(pⁿ), where p is prime and n is a positive integer, denotes the field with pⁿ elements. For example, the field GF(8) (or GF(2³)) contains all integers from 0 to 7. An important property of Galois fields is that the elements of the field GF(pⁿ) are all polynomials of degree less than n with non-negative coefficients, evaluated at p. p is called the characteristic of the field.

Let’s look at GF(8), or GF(2³), again. GF(2³) contains {0, 1, 2, 3, 4, 5, 6, 7}, which can be equivalently represented as {0, 1, 2, 2 + 1, 2², 2²+ 1, 2²+ 2, 2²+ 2 + 1}, or {0, 1, x, x+ 1, x², x² + 1, x² + x, x² + x+ 1} where x = 2.

With this notation out of the way, we can now explain how addition/subtraction/multiplication/division works with Galois fields.

Suppose we want to add elements a and b of GF(pⁿ). First, convert them to their polynomial forms, that is, write them as sums of powers of p. Then we add the polynomials together, but with a caveat: for each coefficient a_k in a(p), b_k in b(p), the resulting coefficient c_k is equal to a_k + b_k mod p. For subtraction, the formula is c_k = a_k — b_k mod p.

We apologize for Medium’s lack of support for mathematical expressions. Here are the formulas again in LaTeX:

“mod” of course stands for modulo, which in most programming languages is written as “%”. Let’s look at an example:

74 + 26 in GF(3⁴) = (2 * 3³ + 2 * 3² + 2 * 1) + (2 * 3² + 2 * 3 + 2 * 1)

= (2 * 3³ + 4 * 3² + 2 * 3 + 4 * 1) = (2 * 3³ + 3² + 6 + 1) = 70

Notice that 4 * 3² became 3² and 4 * 1 became 1 because of the modulo operation on the coefficients.

The Rijndael field GF(2⁸), as well as all fields with characteristic 2, share a property that makes them well suited for computers: addition and subtraction are equivalent to the bitwise exclusive or (XOR/⊕) operation. This works because each term in the polynomial represents a bit. Here is another example to demonstrate this fact:

15 + 12 in GF(2⁴) = (2³ + 2² + 2 + 1) + (2³ + 2²)

= (2 * 2³ + 2 * 2² + 2 + 1) = (2 + 1) = 3

15 ⊕ 12 = 0b1111 ⊕ 0b1100 = 0b0011 = 3

Addition in Galois fields is often referred to as “carryless addition.” We add each set of digits independently modulo p. Note that in the example above, the first set of digits adds to 2 mod 2 = 0, while the second set adds to 7 mod 2 = 3.

In order to multiply two polynomials a(p) and b(p) in GF(pⁿ), we need to chose a third polynomial m(p) that cannot be factored and has a degree of at least n. We call m(p) the irreducible polynomial.

To multiply a(p) and b(p) in GF(pⁿ) we perform the following steps:

The final step can be performed using polynomial long division. However, this is no ordinary division. Every arithmetic operation we perform during the process must be the finite field’s version. In the case of GF(2⁸), every time we perform “subtraction”, we actually perform the XOR operation. Representing the polynomials as binary strings will be helpful for this step.

Let’s perform 193 * 56 in GF(2⁸) and with m(p) = x⁸ + x⁴ + x³ + x + 1 (Rijndael’s field):

If multiplication in finite fields seems complicated, don’t worry! With Rijndael’s field, the multiplication algorithm can be greatly optimized beyond what is described above. Below is a pseudocode implementation:

for (8 rounds) {

//true if the high bit of a is seth : bool = (a & 0x80) != 0;

The multiplicative inverse of a polynomial a(p) is the polynomial b(p) such that a(p) * b(p) mod m(p) = 1. Multiplicative inverses can be found by applying the inverse of the algorithm above. Division is simply a matter of multiplying the first operand by the multiplicative inverse of the second.

Why does AES borrow concepts from finite field theory. The main reason is performance. Remember that “addition” in GF(2⁸) is the same as the XOR operation. Also consider that there is no need to worry about overflow/underflow, because the inputs and outputs of the operations are restricted to the numbers 0–255.

Multiplication is less complicated than it looks. To put things in perspective, consider how computers perform normal multiplication at the lowest level: through repeated bit shifts and additions (of course, we don’t have special circuitry to perform GF(2⁸) arithmetic). Finally, multiplication by 2 and 3 is very easy to optimize. This will become important later.

The gist of the algorithm is this: generally, each word is the previous word XOR’ed with the word N places behind it. But every N words, we perform various GF(2⁸) operations on the word N places behind before the XOR-ing takes place.

In this section we will take you through an entire AES round. Remember that the first round only contains the addRoundKey() step. We will be going over every step, so imagine that the first round has already passed and that we are now on the second round.

Let’s say we want to encrypt the following message:

The quick brown fox jumped over the lazy dog

We will look only how the first block is encrypted, containing “The quick brown ”. Rearranged into a 4x4 matrix, the block looks like this:

And here it is again in hexadecimal:

This is the first step in the AES round. We perform the sbox() operation on each byte in the matrix (see the Key Expansion section for details).

For this step, we rotate each row to the left a number of spaces corresponding to the row number. The first row is shifted zero spaces, the second is shifted one space, and so on.

Now we multiply each column by the following matrix using GF(2⁸) arithmetic (gmul() and XOR instead of normal addition and multiplication):

The entire transformation looks like this:

Notice that this transformation involves many multiplications by 2 and by 3. This is where the optimizations mentioned at the end of the “Mathematical Background” section come into play.

In our example applying the transformation to each column looks like this:

Both the shiftRows() and mixColumns() steps add diffusion to the cipher in that they allow small changes in the plaintext to affect the entirety of the ciphertext.

This is the easiest step. We XOR each byte in the block with its respective byte in the round key. Let’s assume that the round key for this round is:

abcdefghijklmnop

In hexadecimal this is:

61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f 70

Keep in mind that this is a very unrealistic scenario. The round key should be pseudorandom, as well as the cipher key.

The result of addRoundKey() in our example looks like this:

Converted back to ASCII the result of a single AES round looks like this:

€1SFÒ½”Ë%Èm¸P«¯

As you can see, the original message is already ridiculously scrambled. Magnify this by as much as fourteen times and make sure the keys are random, and you have a level of security that not even the best computers can crack.

So we have our encrypted message. How to we reverse the long and complicated process that is AES? One of the great things about AES is that every action has its inverse.

Decryption works like this: we generate the round keys using the same process. Then we perform the encryption algorithm in reverse using the inverses of the various operations.

The addKeys() step is it’s own inverse. XOR-ing string A with string B twice simply results in A. We just have to remember to use the final encryption round key as the first decryption round key, the second-to-last as the second, and so on.

For the mixColums() step, we apply the inverse of the matrix described above to all of the columns. The transformation looks like this:

For the shiftRows() step, we simply rotate the rows in the opposite direction. Or alternatively, rotate each row in the same direction a different number of spaces. If a byte is in row two, it will be rotated 1 space to the left during encryption, and 1 space to the right/3 spaces to the left during decryption.

Finally, for the subBytes() step, we apply the inverse of the sbox() operation. Remember that we usually use a lookup table for sbox(). We can also use a lookup table for the inverse, which looks like this:

One last thing: we need to remember that not all of the rounds are the same. Because we perform just addRoundKey() during the first round of encryption, we do the same for the final round of decryption. Because we omit mixColumns() from the final round of encryption, we must do so for the first round of decryption.

The pseudocode for the entire decryption process looks like this:

blocks := divideIntoBlocks(ciphertext); roundKeys = getRoundKeys(key)

We’re done! We’ve explained basically everything. With this knowledge you should be able to implement AES yourself, although we highly discourage it.

We at SafeHouse believe that cybersecurity is for everyone, so we’re glad to present info like this in an accessible manner. The cybersec industry is ignoring small businesses and we want to take a stand.

If you found what you read informative, consider checking us out at https://safehouse.dev/.