Lecture 8: Advanced Encryption Standard (AES) - Christof Paar

[00:00:16]okay um welcome everybody to the um second Super exciting lecture on AES so so what we did last week we um did only mathematics which is kind of unusual for this course any typically we try to do some crypto and some mathematics there some other New Concept but last week we only did Galla fields and um in case you were wondering why do we really need that you will see that today so today we're going to talk about the advanced encryption standard and we're going to need G Fields eventually today um maybe one one question which uh um we're going to use a lot of um Graphics today Graphics from the book would you like to have the graphics in Blackboard to so that you can print them out and glue in your lecture notes or is that a stupid thing yes okay we're going to do that doesn't cost anything okay so re if I don't do it today reminds remind me or remind deun so what you're going to do today first I give give you an introduction what is as and it's actually it's a pretty cool story as is a good story um then we talk a little bit on a higher level about the structure of as and then we go into the nasty details of as and then toward the end we we talk about decryption okay and it's going to be a pretty packed lecture contents wise so pay attention buckle up don't talk okay okay except the first one okay so you don't have to pay attention actually the beginning is just history okay that's unimportant so F first 10 minutes you can sleep okay still don't talk but sleep okay so so okay intro duction okay to as okay so the um um very very brief history and I think this is one thing that makes cryptography fun it's a really young discipline you know this all the stuff 10 years ago when you were in school you know not in the 1920s like you know some other subject that you're learning here so this is very real and if you go to a big crypto conference and those of you who stay here for Masters or PhD you will eventually go to crypto conferences people are young you know they're my age so it's relatively speaking okay so there very few people over 60s and many many people in the 30s and 40s okay so very brief history um in 1997 and if if if you remember very very well what we did two weeks ago at the end of the DS lecture we talked about the attacks and what happened in 9798 death was seriously being attacked so death was dying right and and by this time the US government said we need a new encryption algorithm so this was really directly triggered by the fact that death has become unsecure okay so in 1997 there was a call an out Shing you would say in Germany a call for for the as which stands for advanced encryption standard you know DS was the data encryption standard AES is the advanced encryption standard called for our as by what's called nist which is the National Institute of Stander and Technology we mentioned that before so direct translation would be the dean in Germany Do's Institute for norong but they end up to do I think they more probably more active than the dean Institute here in um one and a half years later or so in uh uh in um the summer of 1998 was a deadline and they got 15 algorithm submissions which always surprises me I would would have thought they get 50 submissions but they only only got 15 I thought more people would do that but it's they didn't um then one years one year later in August 1999 they reduce this field of um of 15 candidates down to five so-called finalist I I uppercase as finalist algorithms are selected so out of the 15 algorithms that kicked 10 out and five are left these are the as finalist and they're all more or less famous in quotation mark so they're all around they're all very secure but only one out of the five became the is was be became the as was the winner of this process okay so we went to 15 to five and then it took another two years namely on October 2nd 2000 which happens to be the birthday of our sonan NOA okay October 2nd um one of the algorithm which was called and that's not that's not on the exam okay so um rindal which was one of the name of the algorithms right there were five algorithms one world called rindal that's an made up word by Belgium that's a Belgium Cipher rindal um was chosen as the as which was very interesting is that there were the other four algorithms there were some really big prominent names behind it there was one was by bun there were um Ron reest had an algorithm in the field most noticeably there was an algorithm by IBM and if you you might recall that that DS was developed by IBM by IBM research in New York and so IBM had a cipher in that so I think most people assumed one of the other four algorithms would win but it turned out reindel won but two young Belgium cryptographers so that was pretty uh spectacular and I guess everybody was very very happy the Belgium are very proud and it was an excellent um piece of work the um let me see what what else what data is of interest to you um let's continue here [Music] um the designers just that we have the names you know for it's alamine building you know everybody everybody um should know that so that was John Damon D and Vincent Ryman and we in touch with Vincent is still at in in in at the University of Len in Belgium and we we we in touch with them oh actually we have a very active Exchange program with them so if you're you know in your fifth semester if you want to go abroad and study there you're welcome to go to the university of Len in Belgium or do your Bachelor CES this there or your master CES this um so that's a little bit you know boring fact um now we want to start to look a little bit more at the algorithm with a very very high level view so a as is of course is a block Cipher with input output and a key right this is what you know we've seen these type of of of uh uh drawings before um what is of Interest are the the the bit lengths so this is 128 bit or 16 bytes 16 bytes is going to be an important thing for this lecture does anyone remember how many bits were at DS what was the bit the bit Qui here the block size anybody remember 64 so this is twice as big this is not that critical what is very very interesting is the key length you remember death has 56 bits which is really which is the reason why death is unsecure the key space is too small here we have three key key lengths and I I showed that last week namely and that was part of the nist requirements it was part of of the of the call was part of the said we need a block SI for 128 bit bit length and you have to support three key length which was I think at least back then kind of unusual um what is also unusual is that the um number of rounds depend on the key length that means if you look at the three key lengths that exist which is 128 192 and 256 the number of rounds right you remember death round and death had 16 rounds and that's it there was 16 and as has different number of rounds so this is number of rounds is for 128 bit which is the Z standard bit size for the vast majority of commercial application you have 10 Rounds if you want to have something more secure more secure for whatever reason you switch to 192 a stays the same but you iterate not 10 times but 12 times if you go to 256 you have to iterate 14 times okay so this was not a requirement by n this is what the Yan and and Vincent did right they said if in order for the cipher to be secure you have to increase the number of rounds if you go with the long key length Okay means whatever happens inside here you know the number of rounds is key dependent um so and before we go into the more technical stuff there I want to have I want to give a few final remarks the first one is is maybe the most important one also for your motivation um as is uh by now the most important symmetric algorithm in the world I don't have any numbers it's really hard to get numbers but I'm I'm pretty sure that more than 50% of all data that being encrypted at least for new products a products that came out the last five or 10 years use as you know so this is that's it this is super super super important in in super important algorithm in terms of of of practical impact what what you learn in this two in this in this two semesters is as is number one this is the most widely used algorithm at at the moment very very super super important right it's in it's not in cell phones that's bad but isn't in every web browser right in wifi connection vean all you know a million application use as okay um second thing I want to mention is um when you look at at this diagram of this process you know there was this call for algorithm and there was a selection process and I was very exciting and and we I started doing crypto in 1995 so we were like a little little puzzle piece in in in this process so we looked at implementing all these candidates so there's still some research papers by us where we implemented these five algorithms in hardware and on DSP processor so I you know it was again a little tiny uh uh uh piece in this whole um evaluation process my question is another one did we have a was there a similar timeline for the D selection 99 903 uh 7 1973 7475 did we have these dates for D no and why not what I want to hear what was the difference how was death selected and how was as selected what's it it was done by IBM and top secret remember that there was IBM M probably with input from NSA developed the algorithm and then after a few years they said oh here's the algorithm okay this was different there was a public call people submitted the algorithm and which what I didn't write down there people were encouraged offed a MCT to analyze the algorithm that means everybody in the world every crypto person in the world they tried to break those submissions they tried to break those crypto algorithm that was was a really fun time back then right so that was a very super open review process which is exactly the difference that what what happened with the S okay what is also interesting is that um um the NSA which which is a little known fact but I think it's it's very very telling in terms of the evolution of of modern cryptography the NSA the National Security Agency what they did until a few years ago they only use their own algorithm and pretty much the rest of the world does it too that mean obviously the intelligence agencies the they uh infoset agencies they say they have their own algorithm and they only use them so they have their own algorithm they don't use public algorithm but what NS and NSA did the same but what NSA said in um now is NSA allows as for um classified the as as time GED for classified data up to you know they this is this is like cheap Hollywood movies right but this the real classification they secret and top secret and confidential and it's up to and this is always an uppercase lad so G bab up to Top Secret with um but you have to choose the longer key so with 192 or 256bit key okay again this is a little known fact what I think is interesting is NSA which is this huge agency which has very smart cryptographers employed they probably think ases is pretty secure okay it means if if if if Obama communicates with the US Embassy in Berlin they encrypt with as and of course you can find it on Wikileaks later anyway so you know um nevertheless it's really hard to break it right so if there's no wikileak it's really hard to break if if there's wikileak you you know you can read it online okay so um but still this just the fact that the a big intelligence agency said we trust as this is what it says I think is is a pretty strong endorsement for the algorithm okay so this was all right for getting getting started um and it's already the just have to squeeze it in so we're done with number two okay I told you you could sleep this is over now you have to wake up okay now it's getting interesting here so now we look at the structure of as so this is um chapter number two of today structure of as um the first statement is let's do a little bit you know stepping back in time by three weeks H what what was the structure of DS can here I told you wake up wake up and don't talk when we looked at how DS worked internally on on on the on the the the general type of algorithm was that it was a FIS Network right so this has roughly this structure here right this is the main main this is the main kind of viewpoint main how would you call it main something rather so that's the main structure of death right this is a fisal network right this is f EG DS and there a whole bunch of other block ciphers that look s that are FAL Networks have the structure as not as is not a FAL Network okay but a is not a FAL Cipher okay so it's it's quite different which actually makes it very nice that we first introduce the s because many ciphers are F still and now we introduce the different different type of ciphers um and one one specific feature of f networks is that you per round you only encrypt one half of the data path right we call this the data path here right and here in the case of death we had 64 bits but only per round we only encrypt 32 bits namely those the other ones are copied over right to the next round and this is not what as does as um as encrypts all 128 bits of the data path in one round okay so this is not super exciting but it's a little bit exciting um so let's look at a um diagram that's not the right that's not what I want to show okay Graphics no it's not the right one oh okay I know where it is so and now I give you this is figure 4.2 this is my book electronically getting close okay here that's the graphic I wanted to show you so okay so this is the you know very high level View can can can you read that and in the no not really I'll try to blow that up a little bit okay it's better is it better can you read that the last row bilan PL yeah okay good so um this is [Music] um this oh yeah so I get everything on here so um see figure 4.2 in the textbook so this is very important so this is the equivalence of the Des F thing right so this is pretty important it's to some extent it's easier you know that was a little complicated what we have here we just have this difference the call it layers sh there different layers which um you know repeat repeat themselves eles um and now I want to talk and I don't want to copy that right now I I'll put that on blackboard so you can print that out and if you want you can put that in your lecture notes right you can glue that in or put that in in in your ring bind or in your ring boo okay or you can just say look in the book but we'll put this very graphic I'm going to put on blackboard okay so some um remarks about this figure there about what you see up there there okay um first a little bit um what is the most important thing we was start um yeah the most important thing is probably let's start here okay each round if you look up there what I really want to show you is this here you know this is round one this is round let's say for for as with [Music] um with 128bit key we have 10 Rounds so this would be round one round two this would be round nine and this is round 10 right and the first the first nine rounds are identical so we do four things here we do bite substitution then we have what's called shift row here right shift row then we do third mix column that's the third layer and then we have a key addition layer this is one round okay and then you do that nine times so let's just write that down each round consists of four layers where do we start by substitution it's sometimes just abbreviated at bite sub by substitution secondly um shift row sometimes theyve written in in in one word abbreviated not shift row but shift row without a l SI and without a blank um mix column or mix call sometimes and fourthly key addition okay so and now there are two things that are a little bit irregular namely in the last round to see the last round you see that here right if you look at the last row we have bite substitution we have shift row and we have key Edition what what is missing here does anyone see that here mix column for whatever reason reason so the last round is always a little bit special last round does not have does not have the um mixed column layer okay so to maybe maybe to start to motivate it a little bit in in in uh uh terms of theory of functionality what do the layers do and this is you know obviously a large part of the lecture um you might vaguely remember um when we talked about DS we also talked about um diffusion and confusion very you remember a little bit and this direct map for that here the bite sub provides confusion does anyone remember what was the confusion element in DS which part of DS provided confusion does anyone know anyone and pun in their closure yeah yeah no I meus point okay so no I'm kidding um anyone what's that very good the sboxes so was the sboxes and bite sub is the sbox layer okay so this looks almost like this this is is a s box there's nothing mysterious about it okay then um other person said permutation but permutation in DS don't provide confusion but what is the other thing there's confusion and diffusion so these two layers together provide diffusion and then key addition is something else okay so again it's it's similar to death that you can can you know pinpoint this part of the algorithm that provides this these two principles um what is also which did not exist in um in Des but which is a trend in modern Block ciphers in what you did in death we we just had the FIS rounds what modern block ciphers often often do the first thing that H what happen what is the first thing that happens to the pl text the pl text comes in you know the 128 bit and say Hey I want to be encrypted so the first thing what you do here you add a sub key okay so you do that that at the very beginning and interestingly you also do that at the very end okay and this is called key widening and this is a general principle that didn't exist in in in 1975 When Death was uh um proposed but nowadays a lot of ciphers do that this is called key whitening I just want to write that down so that you've heard the term um so it would be you know you you should continue underneath here um um at the end near at the beginning of as and at the end or at the very end the guns I'm ending at the very end a sub key is added and in in in quotation marks this is called key whitening I don't think they will really be an question on the exam about that but if you stay in cryptography you're going to to hear the term key whitening more often okay so this all looks very interesting um but the real exciting stuff hasn't happened so far I mean the big question obviously at this point is big big question at this point is what happens inside the layers okay which is going to be may maybe probably the main part of this lecture here okay which brings us to so we done with the structure so what we did so far essentially we talked about this figure that you see up there the projected figure and um we talked a little bit about it so now the and we call this the structure of as now the real interesting thing is what what what what we call the internals is we want to look what happens to the bits I mean this is still very high level you know you just have a rectangular bar there and say you know there's some manipulation happening with the bits what how do we manipulate the beds here okay so this is um the third section okay and now comes kind of the most important now I'm going to do a pretty big drawing so if if you want to copy that I think you need probably one third of a page or half a page but also you don't have to copy it at all because it's in in in the book okay so but just if if if you if you're copying if if you take lecture notes and the mid you need probably at least one third of a page now okay the um the figure number is the figure number is very good question it's um um Fe Fe 4.3 okay figure 4.3 so what what you're going to see is essentially a modified version of 4.3 I just wanted that slowly develop that figure for you which 4.3 is probably the most important figure which is in case you're wondering this here okay so this is what happens inside around but I wanted I could say this this is this is how these are the internals and you know let's do RSA but we're not doing that okay so we're spending about whatever 30 minutes on this picture here okay so what I want to do now this is one round and what I want to explain to you what is the what is the relationship of this drawing to this drawing okay so but I want to stay with this for one more SEC for for one more minute so um note um the 128bit data path is split into 16 bytes so this is a bite oriented side for so all almost all I think all oper I think all operations in DS operate on a bite level on eight bits which is very very different from DS DS was a bit oriented one in particular you did bit permutation you had small s boxes everything everything in as is always in in chunks of eight B of eight bits okay 16 bytes you know we know 16 * 8 is 128 so you take 128 you split it in bites you get the 16 out there okay so and now what I want to do I want to start with one round um and I call the input to one r that call a you know which is a 128 bit vector or 16 bytes then just what what you see up there the first thing that we're doing is is bite substitution so that's a bite sub layer deide Subs um and then we have the three other ones which are which are quite interesting and you should keep some space here you know okay so and then we get the the first sub player which is called shift row then you get mix column mix call and then the fourth and last layer is key at okay and then you get the output okay so this is one round here just to make it clear this is one there's one round and so far nothing is new it's just what we had before and what I want to do now is I want to look into each of these layers what's happening inside with the bit that we put in there okay um the first bite substitution is very similar in principle what we do to um DS so you um what I do now is it takes this you know a split a up in bies but there 16 bytes but these 16 bytes are again grouped so I always look at four bytes four bytes four bytes and four bytes okay I look at groups of four bytes this is a Zer up to A3 this would be you know the next four bites I don't don't want to put all the the names in here this is the next three bytes and here are the last four bytes sorry the last four bites which range from um a15 15 right in 12 up to a12 okay a12 okay so these are the input bites um so what you do simply and it's very similar to to this you take your bite here you put that in your SBX which is and I use circles here which is maybe not that great okay so you have you have an S boox here and the input to the SBX is 8 Bits And The out output is 8 Bits okay you do that 16 times so that means you have 16 sboxes and they're all running in parallel and just what what we do we call this here the output we call B but this isn't this is not something that standardized this is just what what we do in this lecture you know we call the input a these are the a byes and after the sbox layer get the B bytes out so this is B 0 and that's the very end you get B5 out right okay so conceptionally this is very simple this is simp and again remember s stands for substitution that means replacement as so you simply replace eight bits that come in here with a certain value by another value that's it and this has something to do with gal fields we going to see that in in 15 minutes okay we're going to talk about how what happens there in in more detail so what is the next thing that's happening and now I want to um I I do want to switch to this full this here okay that's pretty visible what the next thing which is called shift row layer sounds really fancy as though we were doing something really complicated what this really is this is just a bite permutation so you just reordering the bites okay you remember in in Des we had a lot of permutations but they were also always on the bit level so individual bits were cross-wired what you do here you keep the spite structure intact so always takes this one bite and now you put the this bite somewhere okay and the rule for that you see up there okay so this goes into the um mixed column box we're going to talk about this and there's a kind of a fun yeah and the but the the actual shift row is this here and what what I meant to do is because I like color um I think colors are helpful so um okay this is that um the actual the cross wiring is What's called the shift row layer this is just a per bite permutation it's nothing it's it's nothing complicated um and this happens to be a value that we do have here you know the last one is coming from B15 and you do that four times so you have four mixed column boxes here and and Fe okay so you have four mixed column boxes and each of that has some certain input pattern here okay and each mixed column has 16 B of input okay and now I think I can sure yeah I'll do that at this point so so you know what what I did so far I just explained a block Cipher and I didn't give much motivation why we're doing that and now I want to start to motivate it a little bit okay one of the big features and very important features of modern block ciphers is we want to have diffusion on on an algorithm level what what was that diffusion on the algorithm level means if I provide an input X zero let's called it X1 let's like X1 okay so 128 bits let's say all zero bits okay there's a certain key what you get out is some Cipher text y one you know it looks pretty random what we do now again imagine we have 128 Bit Zero 128 zeros now you flip one single bit okay so instead of 0000 Z you do one 000000 Z okay let's do X2 okay what you do not want to happen is that Y2 looks pretty similar to y1 okay you I mean the worst thing that can happen is that there would only one bit that flips in y1 right you don't want to want that to happen so what when you have what you want to have is a y 2 which again looks completely uncorrelated to y1 which this looks this should look like a random number and this should look like a random number and there should be no relationship as that you can exploit as an attacker there should be no relationship so this is called diffusion on the algorithm level and let's start with this diffusion thing I think it's a fun part to do and it's fun thing to do and I think it's good for understanding um um crypto algorithms symmetric algorithms so let's imagine you put one input in here you know 128 bit and they run through the algorithm what we do now you flip one bit at this point here let's say first you had eight zeros and now you have a one and seven zeros one 0 0 z0 z0 okay you put that in the sbox what probably even we don't know that yet but probably they will be bit flipsy at the output right and as you can imagine there actually quite a few bits that flip here okay so you have you know you go in with one bit flip you go out with a few bit flips maybe three or four bits have flipped okay this goes into here here this goes into here but all the other you know that means there's one bite with where a few bits have flipped all the other 15 bits are unaffected everybody with me so right now this is very local right one bit flips here a few flip here but it's really in the left hand corner of the algorithm what we now want to do we want to achieve you see that in in Orange provides diffusion we want to get diffusion that means we want we want to make sure that this you know there may be three or four bits that have flipped here that they spread over more than one bite right and what this mixed column does is the mixed column has four outputs and what this mixed column makes sure is that these this bit flips which which are local which are only you know one bite affect all four output bytes okay that's the idea and if everything works out we get the following Behavior you flip one bit here you flip you after we don't know for sure it depends on the details but on average you have like four bits or so flip here at this point you have four bit flips here but suddenly because this is this is bites this is eight suddenly 32 output bytes are affected can can can you roughly follow so this is very strong diffusion you flip one bit here and suddenly you have 32 bits affected that means within one round one quarter and FAL of the whole data pass is affected here so this is a very powerful property of a that you have extremely strong diffusion here okay and so and that is the role of mix colum and again in 15 minutes we going to talk what happens inside but this is a motivation after the mix colum which is color number three okay oh by the way this is really it sounds really complicated you do a matrix multiplication this is whatever 11th grade high school 11 over fa yeah this is not this is not really very hard how to do the mix column here so the key Edition works exactly as you would imagine you have 128 bits right you have 32 32 32 and 32 you have 128 bits coming out the sub keys that you don't the subkey Ki which you see here right this is the sub key Ki I can't highlight I can highlight that okay the sub key k a the eye is gone okay that's bad so you know what I mean okay this sub key there this is 128 bits and you do a bitwise Exel very simple so if you wish at this point you're bit oriented so what we do here you do an X or and you know with key bit Ki number one and it's a little bit too it's hard to draw here so k i number two and I'm not drawing all one all I I I'm sorry now this is not this is bite this is bite no no no no this is Ki this is this is one bite this is the first bite of you can call it ka1 I guess this is the first bite of the sub key and so forth and at the end here this would be Ki comma 16 right so this is last bite last bite of sub key okay so that's it four layers so um again if you look at the way we are we we we are learning about as so we started at this very high level said this is a box with input and output bits then the next thing we saw is which we didn't draw because it's too much of a pain to draw that we've seen this here say this is like this layered approach here right so this getting a little bit this is much more detailed than the Box you see over there where you just have one rectangular and now the next level of detail was this here right okay and this is what you see on this on the Blackboard but we're not really done because this is still very vishy vashy everything right so now what a the next thing that we do is we have to look inside the sboxes we want to talk a little bit how how is this permutation happening and then we want to look into the mix colum okay so but this is still all part of of uh section number three here of the core of today okay how do we proceed so so what we do we we start with with the with the first layer which is the bite substitution layer so this is [Music] um called it 3A bite substitution layer I think it would be less confusing if people would have called it the sbox layer but they didn't so this is the sbox layer and what the sbox layer does you you you substitute on a bite level so you know if if you look exactly at the drawing up there what happening you go in with some input B bit AI you know a zero A1 A2 up to a15 you apply the S function to it the the uh substitution function what you get out is bit um bite bi um what one thing which is quite different from uh a from DS is all 16 s boxes are identical okay again this is different from DS you have we had S1 S2 S3 up to S8 and there were eight different tables you know that from the homework assignment this is different here again okay um so what about the tables here the tables look um the table look different namely okay okay so this is the on no no no no this is I'm just looking for an sbox table here is the s table okay okay this is similar you know it's bigger because there more input and more outputs right it was was smaller in the case of DS so um this is a um this is table 4.3 in the textbook in our book okay and first I give you an example how to read that table this is just a question of notation example let's assume our input AI has a value and this is now written in hexa decimal notation is C2 right in in HEX now in order to read the table oh yeah and of course we we which which we you know now we get X and Y the first the first hex hex digit is X and the second is y so this gives you the x and y coordinate here so if x what did I say x is C it means we're in this row here okay everybody with me okay and what is the Y value Y is two here so Y is here so we get and that means the output is here you see where I'm with the cursor the 25 okay so that means bi is s of AI is this is you know table what did I say 25 okay so so for so so this is the way you read the table it's actually E I think it's easier than the way you read the DS tables um and of course we can look at that also on the bit level which is an an Andes we only only talked about bits and you can do that here too so for instance we look at the binary representation of C you know C is the 12 right binary 12 so this is 1 1 0 0 Let's see C and now the two is okay so if this is the input to the SBX 1 1 0 0 0 then the output here now we we rewriting B is n n I null this is two and five is n i n i so this is the decimal five or hexad decimal five okay means you go in with this bit Vector with this bite you get this bite out okay so this is how that works um does anyone remember in the case of DS so we go back in time by two weeks we had you know we had a similar looking table it was a smaller table but we had a table here for DS maybe I should show that let's look at I just want to want to um look at the death table again where's the death table oh we getting close yeah yeah so that's the death table here right this here I'm sure it's fine okay so um in the in the lower left hand corner you see this is the sbox table S1 for death right does anyone remember and the the eight of them this S1 S2 S3 Does anyone remember how they were constructed where they were coming from that was kind of the big secret that didn't tell us right and it turned out these you have to choose them in in a very spe specific way to make them resistant against differential C analysis um but how they were constructed essentially they had requirements and then they chose random table and they looked whether the requirements were fulfilled but this was early 1970s so 40 years ago almost from today when as was designed about 12 years ago people were smarter and they knew much much more about sboxes and now what happens is that the um sbox has a lot of mathematical structure which was not true for as this is kind of the for DS that's the point I wanted to make there's a lot of mathematical structure and actually a rather simple one um and this is what uh what we want to want to show now so now I want to go back to here so it it might be sufficient and it pro yeah uh Pro probably for the exam it's sufficient just to think if when you think about sbox as you think about this table right now if you want to understand a little bit more advanced crypto now I'm going to explain to you where this sbox is coming from which I couldn't do for DS this was really complicated it turns out this sbox the as sbox is constructed in a very specific specific way and again this is only people who are interested in in somewhat more advanced stuff okay um the um question is how is the sbox table constructed okay so what you do what we've just seen here the input is the bite of course can be viewed as a bit Vector okay and now finally we use galwa Fields you know something we spend a whole week on what you do now for the sboxes you say well this is the input bite then you say okay so this is also a bit vector and now you say this bit Vector is a polinomial in the Galla field it's an element of the Galla field okay so what you do is consider AI element of gf2 to the8 it means in this um and that means this becomes a polinomial I give you an example in in a second consider a um element of G of 2 to the 8 and compute its inverse multi multiplicative invers okay so you you know you do one divided by AI um so let's look at an example and I really I made a mistake with this blackboards I switch to the so I do an example now and I but I switch to the uh to this here please you know notes just just continue writing so AI was this value right and now we may kind of and I think this is is conceptually this is kind of a funny thing that's happening these are really bits and what you and what we say now is well this can also be polinomial that means you call this now ai of X and this is you know the zero coefficient x to the one x to the 2 x to the 3r and so forth so this becomes the polinomial X to the 7 + x to the 6 Plus X okay so this is a mapping bit string to polinomial in a very easy way so there's nothing complicated what you do now you have to compute the inverse okay it turns out that b of X you know the output is X to the 5th + x² xad + 1 which is exactly this bit Vector so now if you want to go transform that into bits you get again this get again this here okay so this is some kind of transformation or you know change of representation maybe and now comes the important thing so this was easy here what what what is the math behind is the math behind it this is the inverse here so this is a exus one and how is the inverse defined the inverse is if you take the original element a a ofx if you multiply that with the inverse which is X 5th + X2 + 1 which is B of X which is the inverse what do I have to write down here $64,000 Question this is equal to what excellent but what happens if you if if you multiply this out you get a polinomial of degree 12 right so this is one but under what else is missing here what do I have to do model reduction very good mod and now it's the question module of which polom and I don't know you might have forgotten that but we talked about Gallow Fields every gal Fields say there are several irreducible polinomial out there so for G gf2 to the8 there are a few dozen I don't know there are 30 or 40 irreducible polinomial and there's one specific one which is part of the as standard which which I gave you last week actually which is X to the 8 plus x 4 + x CU + x + 1 one okay so this is the and I think I called it I called it that even so this is the as irreducible polinomial okay oh oh ah I was I made a mistake I made a mistake okay so be be bear with me bear with me okay so I made a mistake I made a mistake okay this is not the whole SBX okay so what happens in the S the s box are two parts I'm really really sorry so you go in with AI and you compute little gf2 to the 8 inverse this is what we just did okay what you get out of here and what you get out of here is um it's not bi but bi Prime okay so and actually what I yeah I I was wrong what I told um is that wrong yeah this is this is this is this is not true here I don't have be this is wrong okay so this is wrong that's embarrassing okay so um is this wrong is this wrong I have to look in my book I have to look yeah this is wrong so what I get out here is this is different this is so this is X to the 5 this is um first thing so what happens here you have to do something else you do the a what's called a fine mapping a up building and this is bi so this is like intermediate value in vid okay I'm sorry and this intermediate value is so this is B Prime here this is X to the 5 plus spere plus X3 x² x + 1 and this is the inverse I'm really sorry okay so now here you have to multiply this [Music] by I'm sorry for the MTH okay X 5th + x Cub + x² + x + 1 and then you get one out okay so so this is the first part what what I did so far this is the first part of the SBX okay and actually the main part so I don't I don't feel quite as bad but it's it's it's the main part um yeah yeah good good super yeah so and this is B Prime again B Prime okay um again I'm sorry so and now you but this is b a prime and what you want to do with so you do this because you get very nice cryptographic properties out here um and but on the other hand you don't want to have an sbox that has this very nice mathematical description because that could lead to an attack so what we do next you this is followed by another transformation which kind of destroys this this mathematical property which I don't want to which I just want to show you oh which should I only have in my book you see this picture here so now what I want to show you what happens here in this fine mapping here what happens the fine mapping is this here you see this bi this is all eight bits right what you do is you take those eight bits here which are called you know b0 up to B7 right these are a variable these are the prime variables here at this point okay and now you multiply that with this fixed Matrix here so this is again this Matrix here which I which I'm highlighting at the moment this is part of the as standard you multiply this is just module 2 everything everything is module 2 and you add a constant vector and the output of that is the actual sbox output Okay so let's maybe go back here so what happens within you know we what are we talking about talking about one of these circles here right very very small atomic component of as so what happens 8 bit go in the inverse is being computed then you do this funny bit level Matrix mapping you know multiplying by matrix adding a vector you get an output Okay so and I'm I'm I'm I'm hesitant even to explain that because what the incorrect impression people might get if I Implement as what happens is that every time I'm implementing as here here back here I have to do this really complicated galwa field multiplication inversion and all the other stuff and now it's the question why don't I have to do that here every time I mean you can do that but why why why is that maybe not a good idea what is faster yeah you calculate it once because it's fixed right I mean it's well it depends on the input but there only 256 inputs so you calculate it for all 256 inputs and that's it and it's even better you don't have to calculate it it's in the book right and it's on Wikipedia and everywhere right so you know this is what I here this table that you see there that was constructed in this really complicated way here okay that's why I said it's only for people who are really interested a little bit in the background in the case of death there was just this god-given table right wasn't god-given was given by Don copper Smith or whatever right but here it's um this is really complicated in a very clear mathematical way and even better if you're interested in Hardware implementation which is one of the thing my my my group is is doing for a living in Hardware it's often actually better to compute that because in Hardware it's sometimes not that easy to put small table a lot of small tables somewhere so in Hardware often you actually do this G field computation okay so this took a long time but it was was the hardest part probably we I'm with spite substitution now we want look at the next function which is shift row and I actually I can do that here so this becomes section um 3B is shift Row the shift row layer to be exact rows plural what do we do here if you look at this diagram if again if you look at this at this uh as round this looks pretty wild right I'm talking about this here that's you know you see what I'm high what I'm putting in the Box here right you see this here this looks pretty wild um but it's very systematic it looks very unsystematic and wild like the death permutation and some of them are pretty hard to understand but here there's a lot of system behind it what happens here is that you um very systematic if and you have to do the follow you have to know the following trick if you if you look at this in kind of in a linear fashion what we do right we we the data path is kind of written in this way which is actually the literature doesn't do that this is only only us who are doing it this way in the literature what they do is they take these 16 bytes very systematic if we write the state and what is the state IE that's bed the 16 um bite of the data path so this I should should have maybe I should have introduced it before so when we talk a really fancy way of saying the 128 bits insert insert as is to call that the state the tant okay so these 16 bytes 128 bits they called the state so the shift Rose layer becomes very systematic if you write the state as a 4x4 Matrix okay so what does this mean rather than writing that in a long line here put that in a matrix and I'll show you I'll show you what H what's happening what happens then is yeah okay so this this is this is um this is on the internet right this is an on textbook.com Crypt textbook.com so this is the input b0 B1 B2 B3 B4 so these are those 16 bytes okay and what you do now you take the first row and you don't do anything to it you take the second row and you shift that one position to the left oh it should be here you take this and shift that by one position to the left right like this you get this you see this is the shifted version of this here by one position is can can you follow is it two it's not complicated right same here now this for the next row you take this row B2 B6 B10 b14 and you shift it by two positions to the left 1 2 and the last row surprise surprise you shift by one two three and of course this is cyclical okay if you do that if you do this shifting here and then you you kind of roll that you get which is hardly visible which is what what you see there right and I'll show you this you know which I put in this box here right which I put is it too big yeah this big box here this box here we see here you what what I put in this thing this is kind of the graphical you know spread out representation what you see in this Matrix here okay this very so this is just a bite permutation in a very systematic manner okay and it's not you know like like everything in in in cryptography almost everything there's a um reason for doing that one nice thing is for instance these four bites here know B 0 to B3 here you see they are influencing if you follow the lines they're influencing all the other mixed columns so this one bite is going here right B 0 B2 where B2 is going B2 is going all the way to this here oops don't understand that okay what's Happening Here so B 0 was going here B1 is going here B2 is going to this box and B3 is going to this box that means potentially B 0 up to B3 which is here in the right hand corner these four bites this they're connecting to exactly one of the other ones that means they are spreading already over the data path but this is not only true for this here it's also true for this here these four bytes are also every B is connected to one mcallum box so this is connected to this one B4 goes here B5 goes here B6 goes here and B7 goes at this point okay that means each of these four groups of four bites is always connecting to exactly one other bite at the output okay which we need for diffusion purposes okay so the last thing that's left the last non-trivial thing that's left we have to talk talk about mixed color okay so and let's go back to this gunkan experiment we had before right where we said we have a we flip one bit here yeah we have to be quiet for a few more minutes we flip one bit here there only a few bit flips at this point you know maybe one bit flip here maybe four bit flips here flip here we have only four bit flip here and again then the goal and this the mixed column is a very very important element now we want to make sure that if you have a change at this point here this is eight bits right the few bits flip here that all of these are somehow affected and what you do for that you do a relatively easy thing scum um let's look at an example example is the first mix column box what I mind mean by first is a left most here the gun Linker here okay mix colum box so you have mixed column your input your four bytes input which again if if you look here what happen is it's coming from b0 the next one is B5 and then B10 and B 15 which is also um here oh yeah here we can look you know we we just looked at the shifting you know after the shift this Vector here this becomes the input of the to here okay so these four bytes and then the output we call in our notation here we call that c0 1 2 and three and another the question how do we compute that and inside the mix colum you just have a you just no you just have a matrix multiplication with a fixed Matrix so outputs these are the outputs The Matrix I can also show you here this is a matrix there you know there's nothing particular mysterious about that this is a matrix here okay um but I show you a way of again this's is system behind this is o03 O2 o11 and now every every row of this Matrix is a is a shifted version of the next one so this is 203 what you do here you write o23 then I shift it again2 or3 and I shift it again I get O2 O3 would be here but unfortunately the end of The Matrix so we wrap around what about the rest all the rest are ones okay or zero wants to be exact and this constant Matrix is multiplied by B 0 B5 B10 B5 okay and now now it's not clear how do we multiply what does multiplication mean I mean this these are the first remark here is remark all bi CI and constants are bites okay so all of that is eight bit right each each thing is a bit okay abide and now um and now we have to do computation with that so let's maybe look from from linear algebra how do we do that and as an example we look at C zero okay and we we just you know multiply that according to matrix multiplication right this is O2 * B 0 plus O3 * B5 plus o1 * B10 + o1 * B15 okay again this is like C cluster right this is matrix multiplication okay so and what we would like and and each of that is a bite so this is 8 bit this is 8bit and even that is 8 bit in hexadecimal notation okay any ERS how should we multiply what do we do here how do we multiply why is is that integer multiplication no we would get 16 bits out right namely probably which French mathematician am I waiting for whose name polomia the scal field stuff so again we do this thing these eight bits become we say this is a polom this is a polom well you multiply the pols into do M reduction in the scal field that means it's very very important that this this is GF 2 to the 8 multiply and this is gf2 to the8 add addition okay so the the question that may arise here is what are o1 O2 and O3 which are the cons which are part of this Matrix here right but this is answer we just follow our convention saying these These are bites in heximal notation it means if if you put them if you put them in uh in a by in a bit oriented writing so this is this is a bit representation so this is gf2 to the8 representation I don't know with it you know this is some kind of mapping so this is a simply a one this is one of the G of field okay or two is getting a little bit more interesting this becomes X and O3 is probably the most interesting one even though it's still pretty simple x + one okay so these are three pols you know admittedly one is kind of a very spec very you know simple type of polom this is polinomial this is polom so what you do here you do polinomial multiplication 1 2 3 four times you do for polinomial multiplication followed by m reduction of course right it's here with this this is as polinomial x to the 8 blah blah blah and then you do polinomial addition and you get one bite out and it's C zero okay so to wrap up the last last statement um for today is again we had the thing some bits flip here how can we assure that many outputs are affected this happens through here because you know if if there's a if there's a bit flip at B zero well the bit flip occurs here here here and here okay that means c0 C1 C2 and C3 they all depend on this bite here okay and that's why you have bit flip suddenly in all outputs same here let's say we have a bit flip at B5 B5 you know is multiplied by this by these constants here and suddenly again all four output bytes are affected okay so because this is a square structure input chain any if only one bit change is here or all output bites all 32 output bits are affected so um this is one of the few times I misjudged the time so that means um we only do the first three things and decryption is being done in the ubu thank you very much [Music]