AES Explained (Advanced Encryption Standard) - Computerphile

let's delve into aes and talk about you know what's good about it how it works and why it was judged good enough to be the advanced encryption standard so why aes is a yes what yeah why is aes well why ryan diaz have you heard of reindoll ryan doll no no okay so in that perhaps slightly infuriating way i managed to not say anything about how it works in the last video at all let's start with a few numbers that we briefly mentioned in the last video right aes is a 128-bit symmetric block cipher that

means it takes 128 bits of message and it encrypts it into 128 bits of ciphertext with some key now that key can either be 128 192 or 256 bits and that gives you just varying amounts of security right from loads to ridiculously lows right in my opinion all right so don't worry about it if you if you find your browser's using 128 bit that's okay these were specified as part of the aas standard so random had to adhere to this but just think that we're taking 16 bytes that's 128 bits and we're doing something to

it that turns it into some ciphertext and because this is an sp network we're going to be doing some amount of substitution or bringing in some confusion and some amount of permutation moving things around to add diffusion you don't want just like the enigma machine you don't want to have one bite in one bite out because that's got to be easier to analyze and in historically of course it is instead of having a long line of of bytes or bits like most ciphers might arrange things aes likes to arrange things in a grid a 4x4

grid for 128 bit so we have our message which is 128 bit that's 16 bytes as a 4x4 grid every time i try and draw a grid it always goes wrong so byte naught is going to be in 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're going to start doing 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 what the message 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 all right so what we're going to do remember we've got the sp network we're going to have substitution permutation and we're going to add our key in as well at some point so this is our plain text and we're going to first bring in a part of our key and we're going to

perform an xor operation right we remember we put in our key intermediate between the rounds to um that's our secrecy right the rest of the algorithm is fully published in public then we're going to do our round so that's going to be substitute bytes then we're going to shift rows and then finally we're going to mix columns and this is going to be our substitution and this is going to be our permutation and finally at the end of each round we're going to add our key add our round key like this and then this is

going to be one round and the only thing to mention is that the mixed columns is in all arounds except for the last one because this permutation has no effect on the last round it just promotes the output doesn't make doesn't make any difference so it's exactly like this except for this one is missing on the last round when you've got 128-bit key you have 10 of these rounds when you have 192-bit key you have 12 of these rounds and when you have a 256-bit key you have 14 of these rounds but in all other

regard they're exactly the same so this is also an xor down here add round key we don't put the same key in every time what we do is we take the original key and as i mentioned in the sp network video we expand it using something called a key schedule into different round keys so this would be sort of key naught perhaps this would be key one key two and so on depending on which round we were in and so there'll be a key that's expanded for every round um we won't talk in too much

detail about the key schedule it's quite simple uh an effect it's just meant to be fast mainly it just takes your your shorter key and expands it sufficiently such that you can put it in at these different rounds that's an overview of what aes does this is a much much much better version i mean i can't stress this enough a much much better version than the one i designed or showed in my sp network video right we're substituting and then we're going to permute and then we're going to mix in our round key and we're

going to do this over and over again until we have a cipher text so i guess the question then becomes what happens here here and here of interest what's particularly nifty for me about aes is that it doesn't use the same kind of operations that you might expect so exor of course happens everywhere in cryptography but actually all of the operations within aes are essentially mathematical operations 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 by using galwa field

theory over finite fields and doing lots and lots of long divisions and additions so a finite field or galway field which are interchangeable names they what you have in a field is you have some some number of elements so let's say all the numbers between naught and ten for example right and you have different operations you can perform on that field so in reindeer we have a galois field of two to the eight elements and then in this field we can do addition subtraction multiplication and division or x to the minus one inversion the important

thing to remember about a finite field if we don't go any further with the math at all is that two to the eight elements is a is a byte right so each element in this galwa field is just a byte so we start with naught naught naught naught naught naught naught we go all the way to one one one one one one one and so there are 256 of these elements in this particular finite field and the one take-home message you need to know about this even if you don't ever look at it again is

that whichever of these operations we do we produce another element in this field right we never leave the field we never overflow we never underflow and go you know into negative numbers or anything there's no float representation or anything like this if we take one of these numbers and we add them to another one we find a different one and if we multiply them or inverse invert them or divide we go to a different one right which makes it quite nice for implementing a cipher because a lot of these have an opposite so for example

addition and subtraction undo each other multiplication and inversion or dividing they undo each other and we can move around this field but we never actually leave our eight bytes if we've got our four by four byte representation of our data path in aes this is our 128-bit block we can perform operations on here within this finite field and by the end we'll still be in the finite field we won't have gone over to 130 bits or 140 bits or some disaster like that all right so we'll bring the diagram back and with that in mind

we will talk about what each of these does substitute bytes fatsar substitution box is literally a lookup table it's a cleverly designed lookup table they haven't just made this up each byte is mapped to a different byte based on a function in this field but most importantly there's a few there's a few things that they've done to try and design it to be as complicated as possible right so it's very non-linear so it's very difficult to kind of represent this as a mathematical function exactly what it is that it does in fact let's just do

one and then we can we can see right so we've got our grid let's put this here uh we've got our grid which i've now drawn many times this is b0 this is b1 all the way up to b 15. now what we're going to do is we're going to take this byte we're going to look it up in our table and we're going to replace it with a different one right so our substituted byte like that and we're going to do that individually for each of these to make this function more confusing it's been

designed such that there are no fixed points that means no bite is substituted with itself so you don't start with a 15 and end up with a 15 and there are no opposite fixed points which means all the bits flip so for example the opposite of 101.0 would be 0101 right and this is for a whole byte they don't exist in this it's been designed that way so this substitution box is really quite powerful and and it's one of the reasons why this is a really good algorithm as it happens also it's just a lookup

table so it's nice and quick that's the first thing what so we've substituted our bytes we've taken our plain text we put in part of our round key or this is our initial key and then at the beginning around we'll make some bite substitutions using os box then we're going to shift the rows this is really straightforward so we're just going to take the first row and do nothing to it we're going to take the second row we're going to move it one to the left so b1 goes all the way back over to here

right so we wrap around this moves this way and this 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 round back to here and so on and this moves three right which is another way of saying it moves that way but you know so this one goes all the way over to here this one goes over to here and so and so on remember this is going to be an iterative process and what we want

to do is move these things around and permute them 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 which we'll do in a minute you'll see that actually we're mixing everything up so within just a couple of rounds everything is very very jumbled up and that's obviously a really good thing because it's going to be much much harder to break right so we're just taking bites and we're putting them in a different place in this grid so that brings

us to mixed columns which goes along with this right so now that we've moved things into different columns what we're going to do is we're going to take this column here and we're going to mix these right up we're going to take this column and mix these right up and this one and this one separately so this is a column wise operation so this bite has gone over to here and then been mixed into this column this one has gone over to here and been mixed into this column so these two operations together are you

know they're doing a good job of jumbling everything up right will be my technical way of putting it this is going to be done using a matrix multiplication so let's just turn it off i'm going through a lot of your paper today for some column let's say c naught c one c two c three we're going to multiply it as a vector by a matrix right now we've dealt with major multiplications occasionally computer file we're not gonna spend too much time talking about it now but this matrix is two three one one one two three

one one one two three and three one one two now these numbers they're big enough and jumbled enough that something interesting happens here but they're small enough that this is quite fast right on harder implementations and things like this if this was 50 you made your algorithm slower so if you remember from sort of linear algebra a matrix multiplication is going to produce another vector out so it's going to replace this column with another one and it's going to be a combination of all of these so this one times this one plus this one times

this one plus this one times this one plus this one times this one and then we repeat this process for each of the values so we're taking bits and bytes from all of these in this column jumbling them up moving them around shifting them and there is a reverse inverse matrix that does the exact opposite when you want to decrypt as well so although this is doing a good job of jumbling everything up we can actually also undo it the only thing to mention of course is this is not a normal multiplication in the sense

that we're inside this finite field so our add operation is an xor and our multiplication operation is a multiplication inside this finite field right which is modulo a polynomial and you know we'll we'll sort of leave that for someone to look into or we'll talk about it in some extra bits so so i guess like once once more from the top um we take our plain text and we xor it with the first part of our expanded key and then we're going to repeat this process over and over again so we're going to substitute some

bytes using our nicely designed s box we're going to shift the rows along and then we're going to mix all the columns up so we're going to substitute and then permute our data in this grid then each time we're going to add the round key which in this case is xor and then we're going to repeat this process except for the last round where we don't bother to mix the columns because it doesn't really help us and then at the end we add in our final round key and that's the end and out comes the

128-bit block of total gibberish this can be described as kind of a random permutation that is to say it takes some input and it performs what appears to be complete randomly producing an output when in fact actually obviously it's had quite a lot to do with this key if you have the key you can then undo it each of these steps has an exact opposite step that we can go back up through to undo this whole process does this ever go wrong you mean uh how so well it just 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's two answers to that question one is technically no because they have what we would call um test vectors which are this is all zeros when you put this in with this key this is what you should get so you can test your algorithm quite a lot before you would put it into production um but in terms of sort of security issues actually yes right so if you get this implementation wrong you can kind of undermine the security of this

whole cipher there have been things like cache timing attacks and side channel attacks where bits of key have been leaked because people have not given due care to how this is implemented one of the neat things about aes is because it's a standard it's now in cpu hardware so there are aes instructions to perform one round to perform a final round and things on an intel and an amd chip and on others and they are impervious to these kind of attacks and they're also ridiculously fast so if you're using as on a well-equipped cpu with

the right instructions we can be talking gigabits per second of encryption um which is you know pretty good uh so that's why something like bitlocker or some kind of on-disk encryption you won't notice it you click a file it's already decrypted it and shown it to you before you can sort of realize what's happened and it's because of the speed of this kind of stuff well perhaps we'll talk a little bit more about galois fields because i mean i like the name so first first of all please look up galois everest galwa on wikipedia because

he's fascinating didn't he die in a jewel he died in a jewel right having published three landmark papers on finite fields and polynomials and things right so i mean i'm not a mathematician so i don't know the whole history but this is this is a guy