What is AES encryption and how does it work?

Published by on October 5, 2018 in Information Security

What is AES encryption and how does it work_

When it comes to cyber security, AES is one of those acronyms that you see popping up everywhere. That’s because it has become the global standard of encryption and it is used to keep a significant amount of our communications safe.

The Advanced Encryption Standard (AES) is a fast and secure form of encryption that keeps prying eyes away from our data. We see it in messaging apps like WhatsApp and Signal, programs like VeraCrypt and WinZip, in a range of hardware and a variety of other technologies that we use all of the time.

Why was AES developed?

The earliest types of encryption were simple, using techniques like changing each letter in a sentence to the one that comes after it in the alphabet. Under this kind of code, the previous sentence becomes:

encrypted text

As you can see, this simple code makes it completely unreadable. Despite the initial unreadability, if you had the time and knew it was a code and not just a bunch of characters spewed onto the page, it wouldn’t be too difficult to eventually figure out.

As people got better at cracking codes, the encryption had to become more sophisticated so that the messages could be kept secret. This arms race of coming up with more and more sophisticated methods while others poured their efforts into breaking them led to increasingly complicated techniques, such as the Enigma machine invented by the Germans in World War I.

The rise of electronic communication has also been a boon for encryption. In the 1970s, the US National Bureau of Standards (NBS) began searching for a standard means that could be used to encrypt sensitive government information. The result of their search was to adopt a symmetric key algorithm developed at IBM, which is now called the Data Encryption Standard (DES). The DES served its purpose relatively well for the next couple of decades, but in the nineties, some security concerns began to pop up.

The DES only has a 56-bit key (compared to the maximum of 256-bit in AES, but we’ll get to that later), so as technology and cracking methods improved, attacks against it started to become more practical. The first DES encrypted message to be broken open was in 1997, by the DESCHALL Project in an RSA Security-sponsored competition.

The next year, the Electronic Frontier Foundation (EFF) built a DES cracker which could brute force a key in just over two days. In 1999, the EFF and the internet’s first computing collective, distributed.net, collaborated to get that time down to under 24 hours.

Although these attacks were costly and impractical to mount, they began to show that the DES’s reign as the go-to encryption standard was coming to an end. With computing power exponentially increasing according to Moore’s law, it was only a matter of time until the DES could no longer be relied on.

The US government set out on a five year mission to evaluate a variety of different encryption methods in order to find a new standard that would be secure. The National Institute of Standards and Technology (NIST) announced that it had finally made its selection in late 2001.

Their choice was a specific subset of the Rijndael block cipher, with a fixed block-size of 128-bits and key sizes of 128, 192 and 256-bits. It was developed by Joan Daemen and Vincent Rijmen, two cryptographers from Belgium. In May of 2002, AES was approved to become the US federal standard and quickly became the standard encryption algorithm for the rest of the world as well.

Related: A beginner’s guide to cryptography

Why was this cipher chosen for AES?

With any kind of encryption, there are always trade-offs. You could easily have a standard that was exponentially more secure than AES, but it would take too long to encrypt and decrypt to be of any practical use. In the end, the Rijndael block cipher was chosen by NIST for its all-around abilities, including its performance on both hardware and software, ease of implementation and its level of security.

How does AES work?

Be aware that the following example is a simplification, but it gives you a general idea of how AES works. Unfortunately, there isn’t enough coffee in the world to make most people want to get through the more complicated aspects of AES. Normally, the process is performed in binary and there’s a lot more maths.

First, the data is divided into blocks.

Under this method of encryption, the first thing that happens is that your plaintext (which is the information that you want to be encrypted) is separated into blocks. The block size of AES is 128-bits, so it separates the data into a four-by-four column of sixteen bytes (there are eight bits in a byte and 16 x 8 = 128).

If your message was “buy me some potato chips please” the first block looks like this:

            b            m            o            p
            u            e            m            o
            y            e            t
            s            a

We’ll skip the rest of the message for this example and just focus on what happens to the first block as it is encrypted. The “…to chips please” would normally just be added to the next block.

Key expansion

Key expansion involves taking the initial key and using it to come up with a series of other keys for each round of the encryption process. These new 128-bit round keys are derived with Rijndael’s key schedule, which is essentially a simple and fast way to produce new key ciphers. If the initial key was “keys are boring1”:

            k            i
            e            a            b            n
            y            r            o            g
            s            e            r            1

Then each of the new keys might look something like this once Rijndael’s key schedule has been used:

            14            29            1h            s5
            h9            9f            st            9f
            gt            2h            hq            73
            ks            dj            df            hb

Although they look like random characters (and the above example is just made up) each of these keys is derived from a structured process when AES encryption is actually applied. We’ll come back to what these round keys are used for later on.

Add round key

In this step, because it is the first round, our initial key is added to the block of our message:

            b            m            o            p
            u            e            m            o
            y            e            t
            s            a

+

            k            i
            e            a            b            n
            y            r            o            g
            s            e            r            1

This is done with an XOR cipher, which is an additive encryption algorithm. While it looks like you can’t actually add these things together, be aware that it is actually done in binary. The characters are just a stand-in to try and make things easier to understand. Let’s say that this mathematical operation gives us a result of:

            h3            jd            zu            7s
            s8            7d            26            2n
            dj            4b            9d            9c
            74            el            2h            hg

Substitute bytes

In this step, each byte is substituted according to a predetermined table. This is kind of like the example from the start of the article, where the sentence was coded by changing each letter to the one that comes after it in the alphabet (hello becomes ifmmp).

This system is a little bit more complicated and doesn’t necessarily have any logic to it. Instead, there is an established table that can be looked up by the algorithm, which says, for example, that h3 becomes jb, s8 becomes 9f, dj becomes 62 and so on. After this step, let’s say that the predetermined table gives us:

            jb            n3            kf           n2
            9f            jj            1h            js
            74            wh            0d            18
            hs            17            d6            px

Shift rows

Shift rows is a straightforward name, and this step is essentially what you would expect. The second row is moved one space to the left, the third row is moved two spaces to the left, and the fourth row is moved three spaces to the left. This gives us:

            jb            n3            kf            n2
            jj            1h            js            9f
            0d            18            74            wh
            px            hs            17            d6

Mix columns

This step is a little tricky to explain. To cut out most of the maths and simplify things, let’s just say that each column has a mathematical equation applied to it in order to further diffuse it. Let’s say that the operation gives us this result:

            ls            j4            2n            ma
            83            28            ke            9f
            9w            xm            3l            m4
            5b            a9            cj            ps

Add round key (again)

Remember those round keys we made at the start, using our initial key and Rijndael’s key schedule? Well, this is where we start to use them. We take the result of our mixed columns and add the first round key that we derived:

            ls            j4            2n            ma
            83            28            ke            9f
            9w            xm            3l            m4
            5b            a9            cj            ps

+

            14            29            1h            s5
            h9            9f            st            9f
            gt            2h            hq            73
            ks            dj            df            hb

Let’s say that this operation gives us the following result:

            9d            5b            28            sf
            ls            df            hf            3b
            9t            28            hp            8f
            62            7d            15            ah

Many more rounds…

If you thought that was it, we’re not even close. After the last round key was added, it goes back to the byte substitution stage, where each value is changed according to a predetermined table. Once that’s done, it’s back to shift rows and moving each row to the left by one, two or three spaces. Then it goes through the mix columns equation again. After that, another round key is added.

It doesn’t stop there either. At the start, it was mentioned that AES has key sizes of either 128, 192 or 256-bits. When a 128-bit key is used, there are nine of these rounds. When a 192-bit key is used, there are 11. When a 256-bit key is used, there are 13. So the data goes through the byte substitution, shift rows, mix columns and round key steps up to thirteen times each, being altered at every stage.

After these nine, 11 or 13 rounds, there is one additional round in which the data is only processed by the byte substitution, shift rows and add round key steps, but not the mix columns step. The mix columns step is taken out because at this stage, it would just be eating up processing power without altering the data, which would make the encryption method less efficient.

To make things clearer, the entire AES encryption process goes:

Key expansion

Add round key

 

Byte substitution

Shift rows

Mix columns

Add round key          

x 9, 11 or 13 times, depending on whether the key is 128, 192 or 256-bit

 

Byte substitution

Shift rows

Add round key

 

Once the data has gone through this complex process, your original “buy me some potato chips please” comes out looking something like “ok23b8a0i3j 293uivnfqf98vs87a”. It seems like a completely random string of characters, but as you can see from these examples, it is actually the result of many different mathematical operations being applied to it again and again.

What’s the point of each of these steps?

A lot of things happen when our data is encrypted and it’s important to understand why. Key expansion is a critical step, because it gives us our keys for the later rounds. Otherwise, the same key would be added in each round, which would make AES easier to crack. In the first round, the initial key is added in order to begin the alteration of the plain text.

The byte substitution step, where each of the data points is changed according to a predetermined table, also performs an essential role. It alters the data in a non-linear way, in order to apply confusion to the information. Confusion is a process that helps to hide the relationship between the encrypted data and the original message.

Shift rows is also critical, performing what is known as diffusion. In cryptography, diffusion essentially means to transpose the data to add complication. By shifting the rows, the data is moved from its original position, further helping to obscure it. Mix columns acts in a similar way, altering the data vertically rather than horizontally.

At the end of a round, a new round key that was derived from the initial key is added. This adds greater confusion to the data.

Why are there so many rounds?

The processes of adding round keys, byte substitution, shifting rows and mixing columns alters the data, but it can still be cracked by cryptanalysis, which is a way of studying the cryptographic algorithm in order to break it.

Shortcut attacks are one of the key threats. These are attacks that can crack the encryption with less effort than brute-forcing. When AES was being designed, shortcut attacks were found for up to six rounds of its process. Because of this, an extra four rounds were added for the minimum of 128-bit AES as a security margin. The resulting 10 rounds give the encryption method enough legroom to prevent shortcut attacks under today’s techniques and technology.

Why don’t we add more rounds to beef up the security?

With most things in security, there needs to be a compromise between pure defensive strength, usability, and performance. If you put ten steel doors with deadbolts at each of the entry points to your house, it would surely make it more secure. It would also take an unreasonable amount of time to get in and out, which is why we never see anyone do it.

It’s the same when it comes to encryption. We could make it more secure by adding more rounds, but it would also be slower and much less efficient. The 10, 12 and 14 rounds of AES have been settled on because they provide a good compromise between these competing aspects, at least in the current technological landscape.

Decrypting AES

If you’ve managed to get your head around the encryption process explained above, decryption is relatively simple. To go from the ciphertext back to the plaintext of the original message, everything is done in reverse.

If we start with our encrypted result of “ok23b8a0i3j 293uivnfqf98vs87a” and apply the inverse of each encryption step, it starts with the inverse round key, then the inverse shift rows, and the inverse byte substitution, before going into the inverse of the 9, 11 or 13 rounds. It looks like this:

“ok23b8a0i3j 293uivnfqf98vs87a”

Inverse add round key

Inverse shift rows

Inverse byte substitution

 

Inverse add round key

Inverse mix columns

Inverse shift rows

Inverse byte substitution         

x 9, 11 or 13 times, depending on whether the key is 128,192 or 256-bit

 

Inverse add round key

 

After this decryption process, we end up with our original message again: “buy me some potato chips please”

128 vs 192 vs 256-bit AES

AES has three different key lengths. The main difference is the number of rounds that the data goes through in the encryption process, 10, 12 and 14 respectively. In essence, 192-bit and 256-bit provide a greater security margin than 128-bit.

In the current technological landscape, 128-bit AES is enough for most practical purposes. Highly sensitive data handled by those with an extreme threat level, such as TOP SECRET documents controlled by the military, should probably be processed with either 192 or 256-bit AES.

If you are paranoid, you might prefer using 192 or 256-bit encryption wherever possible. This is fine if it makes it easier for you to sleep at night, but it’s really not necessary in most situations. It’s not without its costs either, with the extra four rounds of 256-bit encryption making it about 40 percent less efficient.

AES security issues

Cryptographers are constantly probing AES for weaknesses, trying to come up with new techniques and harnessing the technology that comes their way. This is essential, because if it wasn’t being thoroughly tested by academics, then criminals or nation states could eventually find a way to crack it without the rest of the world knowing. So far, researchers have only uncovered theoretical breaks and side channel attacks.

Related-key attack

In 2009, a series of related-key attacks were discovered. These are a type of cryptanalysis that involves observing how a cipher operates under different keys. The related-key attacks that researchers discovered aren’t of any great concern; they are only possible against protocols that aren’t implemented properly.

Known-key distinguishing attack

Again in 2009, there was a known-key distinguishing attack against an eight round version of AES-128. These attacks use a key that is already known in order to figure out the inherent structure of the cipher. As this attack was only against an eight round version, it isn’t too much to worry about for everyday users of AES-128.

Side-channel attack

There have been several other theoretical attacks, but under current technology they would still take billions of years to crack. This means that AES itself is essentially unbreakable at the moment. Despite this, AES can still be vulnerable if it hasn’t been implemented properly, in what’s known as a side-channel attack.

Side-channel attacks occur when a system is leaking information. The attacker listens in to the sound, timing information, electromagnetic information or the power consumption in order to gather inferences from the algorithm which can then be used to break it.

If AES is implemented carefully, these attacks can be prevented by either removing the source of the data leak, or by ensuring that there is no apparent relationship between the leaked data and the algorithmic processes.

The last weakness is more general than AES specific, but users need to be aware that AES doesn’t automatically make their data safe. Even AES-256 is vulnerable if an attacker can access a user’s key. This is why AES is just one aspect of keeping data secure. Effective password management, firewalls, virus detection and education against social engineering attacks are just as critical in their own ways.

Is AES enough?

In the current age, we all transmit so much of our sensitive data online, AES has become an essential part of our security. Although it’s been around since 2001, it’s repetitive process of adding keys, byte substitution, shifting rows and mixing columns has proved to stand the test of time.

Despite the current theoretical attacks and any potential side-channel attacks, AES itself remains secure. It’s an excellent standard for securing our electronic communication and can be applied in many situations where sensitive information needs to be protected. Judging by the current level of technology and attack techniques, you should feel confident using it well into the foreseeable future.

Why do we need encryption?

Now that we’ve gone through the technical details of AES, it’s important to discuss why encryption is important. At its most basic level, encryption allows us to encode information so that only those who have access to the key can decrypt the data. Without the key, it looks like gibberish. With the key, the jumble of seemingly random characters turns back into its original message.

Encryption has been used by governments and militaries for millennia to keep sensitive information from falling into the wrong hands. Over the years it has crept more and more into everyday life, especially since such a large portion of our personal, social and work dealings have now migrated to the online world.

Just think about all of the data you enter into your devices: passwords, bank details, your private messages and much more. Without any kind of encryption, this information would be much easier for anyone to intercept, whether they be criminals, crazy stalkers or the government.

So much of our information is valuable or sensitive, so it’s clear that it needs to be protected in a way so that only ourselves and those that we authorize can access it. That’s why we need encryption. Without it, the online world just couldn’t function. We would be stripped completely of any privacy and security, sending our online lives into absolute chaos.

See also:
Password generator tool
Encryption Resources: A Big List of Tools and Guides
Famous codes and ciphers through history
Cyber security statistics & facts

“Hacking, cybercrime” by jaydeep_ licensed under CC0

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.