Modes of Operation - Computerphile

well we did a video on the feistel cipher and you know hopefully people enjoyed learning about what I think is a really cool method of encryption now i actually wrote some code for this which we didn't end up putting in a video just because of time but i did put it on github and you know people as soon as you put things on github people go i can contribute to this which is a great thing and so we've added some extra modes of operation so i thought that's what we talked about today when you run a cipher you don't just run it because it's only got a certain block size so how how do you do that if you've got a fire that's two gigabytes but you've got 128 bit block then what do you do then right so we're going to talk about modes of operation we looked at the faisal network which was which is a symmetric cipher and it's a block cipher that means it takes an input of a fixed size and it outputs the same size that's how block ciphers work where they take a fixed block so that means that unless your message is exactly that's length we're going to have to do something to try and actually use this cipher for encryption right so day to day when you're sending traffic over the network the chances of it exactly being the right size for AES block is obviously quite slim so what is it we do so we're gonna look at three different modes we're going to get I guess progressively better I hope let's type with the rubbish one but perhaps the most conceptually simple and then we'll talk a little bit about padding as well because of course you might have two smaller message and then we've got to think about it so the first thing we could do is we could just naive you say well look let's just split our message into links of the book the right size and then encrypt each block at a time right now if we get to a message at the end which is too short we could Pat it in some way so this is called electronic codebook mode and it kind of harks back to when there was a little codebook for you to flick through to get the codes so we have our encryption algorithm so this could be a five store network could be AES could be something else and this is going to encrypt using some key and we're going to put in our message message block one so that isn't the whole message maybe that's just the first block of a message the first 128 the first 256 bits depending on what your message is and that's going to produce ciphertext 1 now we can just repeat this process so we can go message 2 and then finally message 3 because I've got that paper again the good thing is this is trivial to implement right if you have a cipher that works on block splitting up some bytes into blocks not very difficult and then the encryption is also quite straightforward this will have a decription so we just go back up this way so we go message one we can encrypt it to soft x1 and then we can decrypt it again back to message block one this also has the advantage but it's quite fast if you've got maybe eight cores in your PC or even more than that you could do multi-threaded versions of this where you could be doing these two at the same time and all these ones over here and so if you're decrypting things that's going to be quite quick and finally if you want something in the middle of a big file so let's say you're watching a streaming movie and you want to jump halfway through you can do that because you can jump to whatever message or ciphertext block it is that we want to look at and then the encrypt or decrypt it right then and there so that's quite helpful so this is electronic codebook or AEC be nice as that looks it's not at all secure and it's terrible so so so don't quit don't don't implement it I've already done that online for you the problem with ECB is that it gives away just a little bit too much information about our message right so the key thing here is that assuming for a minute that this block cipher is good then if we have a message that goes into this ciphertext we're not going to be able to reverse that if we don't have the key right so for now we're assuming that the cipher itself is really really good so that's good on its own but the if message one a message three are the same for instance then they're going to do the exact same encryption and we're going to get two identical cipher texts one and three so blocks of our message you're going to be identical now that might not seem like a big deal but it depends on the situation right if I send you some money let's say at regular intervals and then sometimes two of those messages are the same they know I've sent you the exact same amount of money now maybe that's not a big deal but the whole point of encryption is that you know nothing about the ciphertext and we've learned something about that ciphertext there's a really good example of this called the ECB penguin the ECB penguin is an image that's had the header removed and the pixel data has been encrypted using electronic codebook mode but the problem is that a lot of the image is the same and so the encryption is exactly the same so you can see these obvious patterns are still there and so you can basically still see the penguin right you've done nothing to hide it at all really that's an obvious example but you can imagine that same problem might rear its head in normal internet traffic maybe the the HTTP web request you put in is exactly the same every time and so someone can learn this about your traffic that's not a great idea we're gonna have to improve on this what we want to do is we want to do something a bit like this but when we have two identical messages come in we're going to have them come out of something different right and it's not clear to do that because these keys are always exactly the same so this function is the same so what we're going to do is we're going to use something called cipher block chaining or CBC mode we're gonna take this ciphertext we're gonna come back up here and we're going to XOR it with our message and then we're going to take this ciphertext and we're gonna XOR our message now what this is doing is linking the output of one block to the input of the next block essentially masking this message with some essentially pseudo-random cipher text and that means that if these two messages are the same the cipher texts are going to be different now before anyone complains in the comments I've left out the IV so we're going to have an initialization vector here which is another block of random which comes in here and is X sort of message 1 right this is so that if two message ones are ever the same you don't see that that the same ciphertext so the encryption is fairly straightforward we take message 1 we XOR it with some initialization vector which is not a secret right that just gets gets put in on the message but it does have to be random I mean clip that we take this we XOR we encrypt we take the SPX on v and we can work this way through the file right so this fixes the issue would be ECB mode pretty much now if message want a message for you're the same the IV in the ciphertext who are not going to be the same almost certainly and so these will be different and that's exactly what we wanted if you encrypt your Engram with this it will just look like random nonsense right that's exactly what we want decription on this is exactly the same as encryption basically it's just all the down arrows and our upwards so ciphertext 1 goes just straight through here is ex-ored with the IV which was sent with the message and that gets just message 1 this also comes over here and when this comes up it gets XOR to get message 2 and so on there's kind of like the exact reverse process with decryptions instead of encryptions CBC was for a long time quite well used it get used occasionally now there's a few issues with it the first is but it's pretty slow right it's pretty slow because we've lost that parallelism we had before I can't now encrypt message until I finished encrypting message to which I can't do until I finished encrypting message one if I'm watching a streaming movie and I've decided the first task pretty boring and I want to jump through sorry you can't do that because you've got to chug through the decryption of everything first right on small files that's not gonna matter but for big files that could be a big problem so it can't be paralysed very well right it's that's not very helpful the other issue is that it's got a couple of security vulnerabilities if an attacker messes around with ciphertext - let's say on the network when it comes to decrypt that's gonna impact what happens to message block three directly you're going to be able to flip bits because of this XOR that's not something you want to have happen right because that allows the attacker way too much control over what comes out in this message right now if you change ciphertext to this message - is going to be gibberish right almost certainly because it's not going to do it properly but you could make interesting effects on message block three like padding attacks and other issues like this I opened up with this kind of problem so CBC mode is should we say better than ECB but we're not it's not good enough if this is a long string of messages or parts then and you have a network problem or something like that does that mess you up for the whole thing yeah I mean so if something happens even accidentally to ciphertext one that's going to totally mess up message one it's also going to feed in and totally mess up message two it's not going to affect message three because that comes from ciphertext - and ciphertext three which theoretically wasn't messed up so you'll lose two blocks of decryption if a change happens on the ciphertext in one block - fair that's totally useless right because that we're gonna have to resend that make that message because that could be the most important part who knows that could be the bit of the movie I was trying to watch the whole time so so yeah we you know this has a few drawbacks and again it's slower right we've gotta wait for these things to finish these don't get used as much in practice anymore right if ACB almost never at all so I hope not training is used for a few things but not really what we do now is something called counter mode right and there's slightly more advanced exciting sounding version Galois counter mode which is for a different view let's talk about what counter mode is and what the benefits it has are what were the issues right one is we want the messages to encrypt or decrypt into different ciphertext right and that is because we don't want to divulge with two messages are the same the next problem we have is that we don't read we want it not to be nice and paralyzer ball and we don't want that weird attack where you can feel about with ciphertex and it will affect other blocks on the other message blocks actually the solution is surprisingly simple in terms of its design right we don't have always interconnectedness it's much easier than that what we're going to do is we're going to have our same three blocks so I think we may have talked briefly about counter mode in the crack attack well I forgot what I said so let's decide again so we've got our encryption algorithm this operates exactly the same as it did before but we're no longer encrypting our message which is kind of confusing what do you mean we're not encrypting the message what we're going to do is we're going to encrypt a counter and then we're get that's going to produce random cipher text which we're going to use as our key to XOR with our message so we're converting our block cipher into a stream cipher so we're going to take a nonce which is a number but it's going to be unique to this particular communication right and we have to use this for a nut work for a number of reasons in terms of security right so we're going to have our nonce so this could be a counter so maybe for the first message is one and the second messages - it's not private right but you mustn't reuse it and then we're going to start our counter so this is block one so we're going to have nonce plus one or maybe not so pended to one or something like that you know nonce plus two nonce plus three and that can go on obviously for as long as you've got enough bits in your counter we're going to encrypt this now what that's going to do because remember this encryption function is very very good and so the output appears essentially as random noise so this is going to produce 128 or however many bits of zeros and ones and it's going to appear pretty random even though we just put in the number one and the number two here and the nonce this is going to be the same this is going to produce some more output as 128 and this is gonna put a few some more output which is 128 bits long all we need to do now is to XOR just like with a stream cipher when we talk about stream ciphers this is what you do your key stream generator generates a huge amount of this key and then you just XOR bit by bit with the message the exact same process we're just not doing it in blocks so we're going to take message 1 this is going to come in here and be XOR and that's going to be ciphertext 1 this is going to come in here message to ciphertext to message three rubies in a different order every time there we go ciphertext of three now this has all of the properties we were hoping for from what I was just talking about so first of all because they're not the nonce is the same but the count was different for every block so even if these messages are the same different key material different ciphertext it's parallelizable you can jump straight to this one and decrypt it by just trivially calculating this nonce plus this number this is much much better it has some four backs all right we talked in when we talked about stream ciphers about how they don't protect their ciphertext because this is just X or if I start flipping bits here as an attacker bits are going to flip over here so you're gonna have to have something like a message authentication code which we also covered in a video to protect this but from actual encryption point of view this is kind of exactly what we want now a modern version of this would be something called Galois counter mode it's exactly the same it's just for as we go based on the cipher text we're calculating something called a GMAC which is enough of these messages of indication codes which is just going to stick some tag material at the end of the cipher text that just says check against this to make sure that nothing has been changed right it's going to protect that from being altered all right that's all the Galois canter mode is doing so you'll see that the majority of Internet traffic is AES and Galois counter mode and it's going to operate a lot like this the other thing about counter mode which is quite neat is how you decrypt it a bit like the firestore right we don't actually need decryption at all we just use the exact same encryption process so let's imagine I've sent you a message you calculate nonce plus 1 you encrypt it don't decrypt it you encrypt it to get the exact same key material you XOR with ciphertext 1 and message 1 pops out right because remember if your ex or something twice it undoes it it reversed itself so actually you don't even if you've got a an implementation of some cipher where the decryption is different from the encryption you don't even need to bother implementing the decryption if you can counter mode because it's just the encryption that does both things so if they're not nonce which I understand is a number that you use once is known the number is known yeah what's the secret bit the key yes this bit so this function because the good cypher will turn this very predictable nonce plus 1 into unpredictable north and ones based on this key you take the key away we can no longer perform that function it's worth noting that just like a stream cipher if you ever reuse this nonce what will happen is you've then got this issue where these bits are going to be the same for two different messages and we can do things like crib dragging attacks to trivially extract bits of message we don't want to do that right so you have to be when you're implementing something like this extremely careful about not reusing your nonce right so if you've got like a 96 bit nonce that puts the that puts a hard limit on the number of message you can send before you have to change your key on the last video actually when I talked about the farce of Safa I did actually implement a feistel cipher now I want to start off by saying but please don't use this sci-fi Society for in production code because I wrote it and I have not given very much care and attention to how securities it's a few issues but actually the actual file store network

Channel: Computerphile

Views: 146,134

Rating: 4.969305 out of 5

Keywords: computers, computerphile, computer, science, Computer Science, University of Nottingham, Dr Mike Pound, ECB

Id: Rk0NIQfEXBA

Length: 14min 15sec (855 seconds)

Published: Thu May 21 2020