One Encryption Standard to Rule Them All! - Computerphile

let's start with a question right have you heard of reindeer ryan doll no no okay so some people watching will have heard of ryan dahl i'm going to talk about what that is today it's the algorithm behind the advanced encryption standard it's everywhere absolutely everywhere so it's being used to encrypt this video it's being used to encrypt the connection from to the server that's producing the video and so on it's being used if you're using bitlocker to encrypt your hard disk and so on and so forth the list goes on it's being used everywhere why is this one algorithm everywhere uh why are we not using lots of different algorithms and some are good and some are bad you know you know we we talk about algorithms from time to time director and stuff director dijkstra's good at certain jobs and not other jobs why is it that everyone's using this one in the let's say 80s and early 90s there was an algorithm called des or the data encryption standard now this was written by ibm and we could talk about this in a different video but dez had a few problems the mo the biggest of which was that it only had a 56-bit key you know you might guess the key about halfway through the search on average so if you're doing it at random so that's maybe two to the 55 operations now in the 80s that was probably quite difficult to do but it became easier and actually des got broken a few times by clusters of computers and large um dedicated circuits and things like this so for a while what happened was we used a process called triple des right which is where it's three times with this um where instead of using one 56-bit key you use three and you do des three times right that's another thing we can talk about another time um but it's three times slower right so yeah it solved the problem with the short key it didn't solve the problem with the fact that actually it's quite slow so what we needed was you know the internet was coming on board right things were happening uh encryption was getting more and more important we need something faster right so so in 1997 the national institute of standards and technologies in america put out a call and said we want a new encryption standard so instead of des the data encryption standard we're going to go for the advanced encryption standard i mean the name says it all it's better it's going to be better right now there were a few things that they wanted so support for different for a specific block length of 128 bits different key sizes and things but the main thing they said was we want it to be as secure as triple this but much much quicker right and quicker on not just your fast pentium but also on your smart card and on your mobile phone not the mobile phones was a particularly big deal back then but you know on your nokia 3310 or whatever it was you can imagine but this in a cryptographic community went down quite well they want to be they want to produce cool ciphers they want to test out each other's cyphers and generate new algorithms and so it was going to be a competition an open competition des was written by ibm and the with help from the nsa shall we say and was just announced as a standard this was going to be a different process we're going to have a proper competition anyone i mean i was quite young at the time so not me but anyone who wanted to could um submit an algorithm it would be sort of scrutinized and if it was judged to be the best among all the others then it would be made into the advanced encryption standard and it would become you know fips accredited and it would get a lot of use now at that time it would get sort of local use in america but as as we've seen now you know worldwide use the initial submission was closed in may 1998 that was when the 15 submissions uh were sort of finalized um and then we had a an evaluation period where cryptographers from all over the world could try and attack these ciphers work out if they had vulnerabilities how fast they were and there were a number of different criteria they were looking for right because just not being able to break the cipher is actually not that it's only one part of it right there's lots of things so for example low memory footprint efficient so not you know using up too much electricity too many cpu cycles fast obviously because that's got to help the ability to deploy in hardware if your algorithm is totally unusable when you try and make a hardware dedicated chip to do it no one can do that and that doesn't make any sense so in march 1999 they had another conference where they looked at what they'd found out so far so they had people talking about whether these algorithms were secure and how fast they were and people had tried implementing them on hardware and reported how that had gone five of them um issues were found with their security such they were not secure enough so five of them were discounted and then another five were discounted because of you know various other issues like they had the same security as one of the others but were slower right and things like this and so in the end this got narrowed down to five right so there was reindeer serpent which was written in part by ross anderson who's been on computer file before mars written by ibm rc6 written by the rsa organization who also developed rsa encryption and two fish written by bruce schneier and others niels ferguson and so on it came down not just to which is more secure um and so it wasn't that we picked the most secure one there were lots of things to be thought about so for example um ryan dial performed very well on lots of different devices so that was a real positive serpent was probably the most secure in sort of a strict sense of it it had the fewest attacks make any progress on it at all and but it was just a little bit slower than ryan dart for example in software so lots of decisions in the end a vote was taken and it was somewhere around 80 something votes for ryan dahl and then 50 for serpent ish and then some for the others so reindeer won ryandahl was written by two belgian cryptographers so joanne darman and vincent ryman they were obviously in in the cryptographic community but you know we had big hitters like um ibm uh in in this competition so it was in some sense a little bit of a coup but that they won but you know one of the nice things about academia is that if you perform good work people will notice that work and hopefully you know it'll it'll see some use right even if you're just starting out or you're not as established as some other researchers so i quite i quite like that the nice thing about aes is that it is an sp network we already talked about sp networks in a previous video and so in some sense aes is actually quite similar now there are some differences and we'll talk about those in another video but in general what we've got is we've got a series of confusing substitutions that make our life difficult of tracking back what we had before and some permutations where we're moving bytes and bits around so that it's difficult to keep track of where the key was and where the message was and you do this a few times until the output bears no resemblance to the input at all the way that ryan die works is actually it can have different block sizes so it can have 128 bit block sizes or 256 bit block sizes for example the aes specification only allows for 128 bit blocks with 128 or 192 or 256 bit keys right and that that's what everyone had to adhere to so in some sense aes is a subset of ryandale but they're now interchangeable right one is the other so when we talk about aes we're talking about the algorithm that was named ryan darling has now become the advanced encryption standard is that job done then i mean we've chosen this surely you know computers get faster there'll be a point where maybe this is broken will there have to be another advanced advanced encryption statement well i mean maybe eventually the so there's a few that's an interesting question because so each of these algorithms had what we would call a security margin which was i guess how much better are we going to have to get at attacking these things to break them and we were a long way off as far as i can tell right there are some obscure attacks on things like related keys and where and but the amount of i mean some of some of them will require petabytes of data and and of encryptions and decryptions to even slightly be brute force right so none of these are practical you know there's no issue of breaking anytime soon to brute force a key on even 128-bit machine is totally out of reach 2-128 operations is huge so it would take some 100 trillion years for the world's fastest supercomputer i think i calculated as a while ago i could be out of date now you get papers and other ciphers that come along so for example there's another cipher called char char 20 which is arguably slightly faster on very low cost devices right so there are algorithms that perhaps weren't in this competition that could see some use but there's a good reason to have standards they get attacked the most they get tested the most they get implemented the most so you you soon realize what the problems are and then you can rely on libraries like open ssl that have a very very good implementation for your needs so in some sense something would have to really go wrong for us to want to change our algorithm because of how established it is and you know don't reinvent the wheel if we're taking our 128-bit message and we're just laying it out in this order like this um and then we're going to start using doing our sp networks yeah 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

Channel: Computerphile

Views: 426,647

Keywords: computers, computerphile, computer, science, Rijndael, AES, Encryption, University of Nottingham, Dr Mike Pound

Id: VYech-c5Dic

Length: 9min 10sec (550 seconds)

Published: Wed Nov 20 2019