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 yes yes what yeah why is a yes well why behind are they have you heard of mine doll crying 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 my AAS 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 form loads too ridiculously lows right in my opinion alright so don't worry about it if you if you find your browsers using 128 bit that's okay these were specified as part of the AES standard so and I'll 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 completing 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 byte in one byte out because it that's got to be easier to analyze and in historically of course it is instead of having a long line of bytes or bits like most ciphers might arrange things AES likes to arrange things in a grid a 4x4 grid 428 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 byte 1 and by 2 and by 3 and then 4 5 6 7 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 going to permute we're going to substitute bytes and then 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 but everything in AES happens on this 4x4 grid all right so what we're going to do remember we got the SP Network we're going to have substitution permutation and we're going to add darken as well at some point so this is our plaintext and we're going to first bring in a part of our key and we're going to perform an XOR operation we know member we put in our key intermediate between the rounds two that's all secrecy 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 around 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 the rounds except for the last one because this permutation has no effect on the last round it just pollutes the output doesn't make doesn't make any different so it's exactly like this except that this one is missing on the last round when you've got 128 bit key you have ten 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 regard though 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 scheduled in two different round keys so this would be sort of key nought perhaps so this would be key one key 2 and so on depending on which round we were in and so there'll be a key that's expanded for every round we won't talk in too much detail about that the key schedule is quite simple and effect it's just meant to be fast mainly it just takes your you're shorter key and expands it sufficiently such that you can put it in at these different rounds that's an overview of what a es does this is a much much much better version I mean I didn't 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 gonna do this over and over again until we have a ciphertext 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 XOR of course happens everywhere in cryptography but actually all of the operations within a AES are essentially mathematical operations on what we would call a finite field so Dave talked a little bit about Galois fields in his reed-solomon video and the answer is by using Galois field theory over finite fields and doing lots and lots of long divisions and additions for a finite field or Galois 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 Norton 10 for example right and you have different operations you can perform on that field so in mind our 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 elements is a is a byte all right so each element in this Galois field is just a bite so we start with naught naught naught naught naught naught naught naught we go all the way to 1 1 1 1 1 1 1 1 11 to hundred and fifty-six 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 but we never leave the field we never overflow we never under flow 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 through a different one 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 we never actually Levi bites if we've got our 4x4 by 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 140 bits or some disaster like that as well bring the diagram back and with that in mind we will talk about what each of these does SATA 2 bytes that's our substitution box is literally a lookup table it's a cleverly designed lookup table they have 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 alright so it's very nonlinear 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 couldn't we can see right so we've got our grid let's put this here we've got our grid now drawn many times this is B 0 this is B 1 all the way up to be 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 gonna do about 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 byte is substituted with itself so you don't start with a 15 and up with a 15 and there are no opposite fixed points which means all the bits flip so for example the opposite of 100 100 would be oh one o one my emphasis for the whole byte they don't exist in this it's been designed that way so this substitution box is really quite powerful 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 plaintext we put in part of our round key or s is our initial key and then at the beginning around will make some byte substitutions using our s 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 all right setting background this moves this way and this moves this way and this moves this way and this goes it goes to the end this row moves two so this goes to here this goes to here this goes round to here and so on and this moves three right which is another way of saying it moves that way but it 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 alright so we're just taking bytes and we're putting them in a different place in this grid so that brings us to mix columns which goes along with this alright 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 gonna take this column and mix these right up and this one and this one separately so this is a column wise operation so this byte has gone over to here and then we mix 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 and go through a lot of your paper today for some column let's say C naught C 1 C 2 C 3 we're going to multiply it as a vector by a matrix right now we've dealt with major applications occasionally computer file we're not going to spend too much time talking about it now but this matrix is 2 3 1 1 1 2 3 1 1 1 2 3 and 3 1 1 2 now these numbers they're big enough and jumbled enough that something interesting happens here but it's small enough that this is quite fast right on Hardware implementations and things like this if this was 50 it 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 of 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 was a reverse inverse matrix but 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 more 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 sort of leave that for someone to look into although we'll talk about it in some extra bits so so I guess like once once more from the top 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 its 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 I mean 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 landing ly producing an output when a fat actually obviously has 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 how so well it just seems to be so many stages and so many I am Sebastian if there'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 them 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 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 K have been leaked because people have not given due care to how this is implemented well never neat things about is is because it's a standard it's now in C you hardware so there are AAS instructions to perform one round and to perform a final round and things on an Intel and 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 a s on on a well-equipped CPU with the right instructions we can be talking gigabits per second of encryption which is you know pretty good 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 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 every scale wa on Wikipedia because he's fascinating did he die in a duel he died in a duel 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 that this is a guy

Channel: Computerphile

Views: 698,519

Rating: 4.9468641 out of 5

Keywords: computers, computerphile, computer, science, AES, Encryption, InfoSec, University of Nottingham, Dr Mike Pound, Galois Fields

Id: O4xNJsjtN6E

Length: 14min 14sec (854 seconds)

Published: Fri Nov 22 2019

Reddit Comments

[u/libeeterianprince]

My favourite YouTube channel

[u/john_alan]

Dr Pound has a great knack of explaining things.

[u/alexgand]

Thanks, wonderful channel!