AES Explained (Advanced Encryption Standard) - Computerphile

Let's dive deeper into AES and talk about you know what's good about it, how it works, and why it was considered good enough to be the

advanced

encryption

standard

. So why aes is a yes, what yes, why is aes and why ryan diaz, have you heard of reindoll ryan? doll, no, no, okay, so in that maybe a little infuriating way I managed to not say anything about how it works in the last video. Let's start with some numbers that we briefly mentioned in the last video. Aes is a 128-bit symmetric block.

encryption

, that means you take 128 bits of message and encrypt it into 128 bits of ciphertext with some key, now that key can be 128, 192 or 256 bits and that gives you varying amounts of security, from loads to ridiculously low, just In my opinion very good, so don't worry if you find that your browser uses 128 bits, that's fine, these were specified as part of the aas

standard

, so chance had to comply with this, but think that we are taking 16 bytes , that is, 128 bits and we are doing something to it that turns it into a ciphertext and because this is an sp network, we are going to do some amount of substitution or generate some confusion and a certain amount of permutation, moving things around to add diffusion. you don't want like the enigma machine, you don't want to have a bite in a bite because that has to be easier to parse and historically of course it is rather than having a long line of bytes or bits like most ciphers can organize things.

Aes likes to organize things in a grid, a 128-bit 4x4 grid, so we have our message, which is 128 bits, which is 16 bytes like a 4x4 grid. Every time I try to draw a grid it always goes wrong, so the byte is zero. It's going to be here and by one and by two and by three and then four five six seven says column major order so actually what we're doing is we're taking our 128 bit message and we're just laying it out in this order like this and then we'll start to make our sp network, we're going to permute, we're going to substitute bytes and then we're going to transform this into some way where an attacker can't read the message.

It used to be so there are a few different operations that aes will do, but remember that everything in aes happens on this 4x4 grid, so what we're going to do, remember we have the sp grid, we're going to have substitution. permutation and we will also add our key at some point, so this is our plain text and first we will bring in a part of our key and perform an xor operation, just as we remember. put our intermediate key in between the rounds for um that's our secret the rest of the algorithm is completely published in public then we're going to do our round so it's going to be surrogate bytes then we're going to shift the rows and then finally we're going to shuffle columns and this will be our substitution and this will be our permutation and finally at the end of each round we will add our key, add our round key like this and then this is There's going to be a round and the only thing to mention is that the mixed columns are in all the rounds except the last one because this permutation has no effect on the last round, it only promotes the exit, it doesn't make any difference. so it's exactly like that except this one is missing in the last round when you have a 128 bit key you have 10 of these rounds when you have a 192 bit key you have 12 of these rounds and when you have a 256 bit key bit key you have 14 of these rounds, but in all other respects they are exactly the same, so this is also an xor down here, add round key, we don't put the same key every time, what we do is take the original key. and as I mentioned in the sp network video, we expanded it using something called key program into different round keys, so this would be some kind of null key, maybe it would be key one, key two, etc. depending on What round are we in?

There will be a key that will expand for each round. We will not talk in too much detail about the key program. It's pretty simple. An effect that is meant to be quick. It mainly just takes your shortest key and expands it enough. that you can put it in these different rounds. That's an overview of what AES does. This is a much, much better version. I mean, I can't emphasize this enough. It's a much better version than the one I designed or showed on my SP network. right video, we're substituting and then we're going to permute and then we're going to shuffle our round key and we're going to do this over and over again until we have a ciphertext, so I guess the question is then.

It becomes interesting what happens here and here. What's particularly clever to me about aes is that it doesn't use the same type of operations that you might expect, so of course it happens everywhere in crypto, but actually all operations within aes are essentially operations mathematics on what we would call a finite field, so Dave talked a little bit about Galway fields in his Reed Solomon video and the answer is to use Galwa field theory on finite fields and do a lot of division and long addition to get a finite field. or Galway field, which are interchangeable names, what you have in a field is that you have a certain number of elements, so let's say all the numbers between zero and ten, for example, right, and you have different operations that you can perform on that field, so in reindeer we have a Galois field of two to eight elements and then in this field we can do addition subtraction multiplication and division or x to minus one inversion the important thing that we must remember about a finite field if we do not go further with the mathematics at all is that two to eight elements is one byte, so each element in this galwa field is just one byte, so we start with nothing nothing nothing nothing nothing nothing nothing we go up to one one one one one one one and then there are 256 of these elements in this particular finite field and the message that you need to know about this, even if you never look at it again, is that any of these operations that we do will produce another element in this field, we never leave the field, We never overflow, we never overflow and go, you know, to negative numbers or anything, there's no float representation or anything like that.

If we take one of these numbers and add them to another, we find a different one. and if we multiply them or invert them or divide them, we go to a different one, which makes it quite good for implementing a cipher because many of these have an opposite, for example, addition and subtraction undo each other, multiplication and investment or division. We get rid of each other and we can move around this field, but we never really get out of our eight bytes if we have our four by four byte representation of our data path in aes.

This is our 128-bit block that we can perform operations on here inside of it. finite field and in the end we will still be in the finite field, we will not have gone to 130 bits or 140 bits or some disaster like that, so we will recover the diagram and with that in mind talk about what each of these substitution bytes does. fatsar substitution table is literally a lookup table. It is a smartly designed lookup table. They haven't just invented it. Each byte maps to a different byte based on a function in this field, but the most important thing is that there are some, there are some things that they have done to try to design it to be as complicated as possible, so it is very non-linear, so which is very difficult to represent this as a mathematical function, exactly what it does.

In fact, let's just do one and then we can see okay, so we have our grid, let's put this here. We have our grid that I have drawn many times. This is b0, this is b1 until we get there. b 15. Now what we're going to do is take this byte, look it up in our table and replace it with a different one, so our replaced byte looks like this. and we'll do it individually for each of these to make this feature more confusing. It has been designed in such a way that there are no fixed points, which means that no bit is substituted for itself so that you don't start with a 15 and end with a 15 and there are no opposing fixed points, which means that all the bits are they invert, so for example the opposite of 101.0 would be 0101 correct and this is for a full byte, they don't exist in this, it's been designed that way, so this substitution box is actually quite powerful and it's a of the reasons why this is a really good algorithm, because it turns out it's also just a lookup table, so it's nice and fast, that's the first thing, so we've substituted our bytes, we've taken our text without Format. we put in part of our round key or this is our initial key and then at the beginning we're going to do some bite substitutions using the OS box, then we're going to change the rows, this is really simple so we're just going to take the first row and don't do anything to it, we're going to take the second row, we're going to move it one to the left so that b1 comes back here to the right, so we go around this and it moves this way and this way. moves this way and this moves this way and this obviously goes to the end this row moves two so this goes to here this goes to here this goes back to here and so on and this moves three to the right , which is another way of saying it moves that way, but you know, this one goes here, this one goes here and so on, remember that this is going to be an iterative process and what we want to do is move these things and permute them in different ways. so If this is our data path with our columns by sharing bytes around the different columns, when we combine it with the mixed column step that we will do in a minute, you will see that we are actually mixing everything into just one pair. of rounds everything is very, very confusing and that's obviously a really good thing because it's going to be a lot harder to break it right, so we're just taking bites and we're putting them in a different place on this grid, which brings us to mixed columns that go along with this now that we've moved things to different columns, what we're going to do is take this column here and we're going to mix them together.

I'm going to take this column and mix them and this and this separately, so this is a column operation, so this bite went up to here and then mixed into this column, this one went up to here and mixed into this column, so these two operations together, you know they're doing a good job of mixing everything properly, will be my technical way of putting it. This will be done using a matrix multiplication, so let's turn it off. We reviewed much of your article today for some column, let's say c zero c one c two c three let's multiply it as a vector by a matrix right now we've dealt with important multiplications occasionally computer file we're not going to spend too much time talking about it now, but this matrix is ​​two, three, one, one, two, three, one, one, two, three and three, one, two.

Now these numbers are big enough and mixed up enough that something interesting is going to happen here, but they are small. It's enough that this is pretty fast in harder implementations and things like this, if it was 50, you made your algorithm slower, so if you remember from some kind of linear algebra, a matrix multiplication will produce another vector, so it will replace this column with another and it will be a combination of all of these, so this by this plus this by this plus this by this plus this by this and then we repeat this process for each of the values, so we are taking bits and bytes from all of these in this column, mixing them, moving them changing them and there is an inverse matrix that does exactly the opposite when you want to decrypt as well, so although this is doing a good job of mixing everything there in reality we can also undo it, the only thing to mention Of course, is that this is not normal multiplication in the sense that we are inside this finite field, so our addition operation is an xor and our multiplication operation is a multiplication inside this finite field. field on the right, which is modulo a polynomial and you know, we'll leave that for someone to investigate or we'll talk about it in some additional snippets, so I guess once again from the top, we take our plain text and we xorate it with the first part of our expanded key and then we'll repeat this process over and over again, so we'll replace some bytes using our very well designed s box that we're going to shift. the rows and then we will shuffle all the columns so we will substitute and then we will permute our data in this grid and then each time we will add the round key which in this case is xor and then We are going to repeat this process except in the last round where we don't bother in shuffling the columns because it doesn't really help us and then at the end we add our final round key and that's the end and it comes out. the 128 bit block of total gibberish, this can be described as a kind of random permutation, i.e. it takes some input and performs what appears to be completely random, producing an output when in reality it has obviously had a lot to do . with this key, if you have the key, you can undo it.

Each of these steps has an exactly opposite step by which we canundo this whole process again. Does this ever go wrong? You mean how good it seems to be? so many stages and so many oh yeah, that's true, so that's a very good question because I guess there are two answers to that question, one is technically no, because they have what we would call test vectors, which are all zeros when you enter this with this key, this is what you should get so you can test your algorithm quite a bit before you put it into production, um, but in terms of kind of security issues, actually yeah, right, so if you mess up in this implementation, you can somehow undermine the security of all this encryption.

There have been things like cache sync attacks and side channel attacks where key fragments have been leaked because people haven't done it. If you pay close attention to how this is implemented, one of the interesting things about AES is that because it is a standard, it is now in the CPU hardware, so there are AES instructions to do a round to do a final round and stuff on an Intel and AMD chip etc. others and are immune to these types of attacks and are also ridiculously fast, so if you are using a well-equipped CPU with the right instructions, we can be talking about gigabits per second of encryption, which is pretty good.

Uh, that's why something like Bitlocker or some kind of encryption on the disk you won't notice, you click on a file, it's already decrypted and it shows it to you before you can even realize what happened and it's because of the speed from this. Well, maybe let's talk a little bit more about the Galois fields because I mean, I like the name, so first of all, look up Galois Everest Galwa on Wikipedia because it's fascinating, didn't he die in a jewel he died in? a gem, for having published three historical papers on finite fields and polynomials and stuff like that, I mean, I'm not a mathematician, so I don't know the whole story, but this is a guy.