The Advanced Encryption Standard (AES)

- [Instructor] Hello and welcome to this course on symmetric cryptography. In the previous video in this course, we talked generally about block ciphers and block cipher modes of operation and how block ciphers are designed to encrypt plain text and decrypt cipher text and fixed size chunks. In this video, we're going to talk about one of the most famous block ciphers out there, the Advanced Encryption Standard. And so moving on to the next slide, AES is a symmetric block cipher and is currently the official encryption algorithm of the US government. How AES was selected or how a certain cipher was chosen as the official Advanced Encryption Standard was through open competition run by the National Institute of Standards and Technology. And that competition was considered by everyone involved to be extraordinarily well run. The choice was a good one in the opinion of many people, and AES was endorsed to the point where it's actually approved for use and encryption of classified US data. So at least they're implying that they have a certain level of trust in the algorithm since they're using it to protect their classified data. And so when you talk about AES, you're actually talking about a family of three different but related ciphers. There's AES-128, which has 128-bit key, AES-192, which has 192-bit key, and AES-256 with a 256-bit key. And so now let's dive into the history of the AES on the next slide. And so, as I mentioned, AES was chosen through a contest. So in 1997, the Data Encryption Standard, which was the previous encryption standard of the US government, was starting to grow stale. Essentially, it had a very short key length, which made it vulnerable to a brute force attack. If an attacker tried to guess the secret key of DES, it was actually possible to identify the encryption key used in a particular DES instance with modern technology at the time. And so NIST wanted to replace DES. And so they started the AES contest in 1997, and their criteria were that the ciphers should have 128-bit block size and they should have three different key lengths, 128, 192, and 256 bits. So what happened was 15 different ciphers were submitted from around the world. Rijndael was created by Belgian cryptographers Vincent Rijmen and Joan Daemen. And so this contest went on for a couple different years and they had conferences a couple of different times where they discussed how much they'd liked certain cipher. So between the different conferences, cryptographers would work on breaking different ciphers, determining how efficient they are, et cetera. They'd meet at the conferences. And eventually in October, 2000, Rijndael became the official Advanced Encryption Standard. And so the AES contest really underscores the importance of Kerckhoffs' principle that we talked about in a previous course in this learning path. If you don't recall, the principle says that the only thing that should be secret in a cipher is the secret key. And this was really demonstrated by the AES contest because several of the submitted ciphers were broken before the first AES conference. And so that demonstrated the importance of getting peer review, more eyes on the cipher because if those ciphers had been used in operations and someone had learned enough about them, they could have broken them. And so AES survived the contest. Rijndael was chosen as the official AES, and it's still in use today. And so moving on to the next slide, let's take a brief look at the structure of AES. So as we mentioned, AES has three different key lengths and each one has their own key derivation structure and the number of encryption rounds. Remember, in a previous course, we talked about the fact that a split encryption structure and key schedule was a common structure in cryptography. AES follows that structure. So AES-128 has 128-bit key, 10 rounds of encryption. AES-192 bumps up to 12 rounds of encryption. And AES-256 requires 256 round, or sorry, 14 rounds of encryption. And so what is a round of encryption? We see this on the next slide. And so in that same section where we talked about the structure of cryptography, we talked about Feistel networks and how they were useful because they made it so that you did not have to have a reversible algorithm. AES does not use a Feistel network. DES, its predecessor, does. AES uses only reversible operations. And so looking at this round of encryption, there are four main functions that occur. So starting at the state at the beginning, we first move on to SubBytes. And so in this SubBytes stage, there is some Galois Field arithmetic going on, which is complicated math, don't need to understand it. And how this stage of the operations is typically implemented is as a look-up table, 256 possible inputs, 256 possible outputs. And that way, each one is matched one-to-one, and it's just a substitution box or an S-box. And so that is the SubByte stage of a round of AES. And so with our updated stage or state, we move on to ShiftRow, which we talked about in a previous course with the mathematics of cryptography about bit shifting. And so that's what occurs in ShiftRow. It moves the information in the state around, as we see demonstrated by the arrows in this ShiftRow image. So this just mixes up where things are located within the state of the cipher. After that ShiftRow stage, we enter MixColumns, which is a mathematical function that mixes each column. And when they're talking about rows and columns here, typically, AES's internal state is represented as a four-by-four grid. And so that four-by-four grid, you have four rows, which are what are shifting sideways in ShiftRows, and you have four columns, which are what are mixed together in the MixColumn stage. And then, finally, our last stage in our round of encryption is AddRoundKey. And so here we use the exclusive or operation we talked about previously. And so from the key schedule, each round gets its own round key and this is XOR in with the state to produce the final output of the round. AES also has a couple of operations out of a common round, there's an additional AddRoundKey, but this is the main meat of the AES algorithm. And so, all of these operations are also completely reversible. AddRoundKey is an exclusive or, and so you can XOR in the same round key to undo that. MixColumns, ShiftRows, and the S-boxes are all reversible operations, which is what enables decryption of AES. And so like I said, this is not a Feistel network. Every part of the encryption algorithm has to be fully reversible. And so moving on to the next slide, let's talk briefly about the security of AES. And so full-round AES is currently considered to be secure. And so what I mean by full-round AES is if you're using AES-128, it's using all 10 rounds of encryption. There have been attacks against reduced round variations of AES. So for example, maybe with AES-128, if there were only six rounds of encryption, it's possible to break, but nobody's found a useful or usable attack against the entire 10-round version. And so currently, the best known attack against the full AES, so essentially all of the rounds for whichever version, is four times faster than a brute force attack. And so what this means is that it requires either 2 to the 126.2, 2 to the 190.2, or 2 to the 254.5 operations to crack AES-128, 192, and 256. So essentially, your effective key lengths are 126.2, 190.2, and 254.5. And so cracking key lengths of that length is already impossible on modern hardware. It's far beyond what we can do on modern technology, especially since 190.2 and 254.5, even though they're not the key length that they're intended to be, are still greater than the minimum key length of 128. Also, these attacks require storage of 9,007 terabytes of data, which is quite a lot, and dealing with storage indexing, addressing of that would also add overhead to the attack. And so right now, AES is considered secure. That doesn't mean that tomorrow some cryptographer might not come up with a brilliant idea on how to break it, find a way to tear it apart and render it completely useless. However, it's received a lot of scrutiny to date and has stood up to it pretty well. And so this is an example of a modern block cipher, like I said, the official encryption algorithm of the US government and one that has gone through a great deal of analysis by cryptographers trying to break it. Next video, we're going to switch gears from block ciphers to stream ciphers. Thank you.