Meet-in-the-Middle Attack on Double Block Cipher

so let's just illustrate the concepts for this cipher we have a five bit plaintext block coming in a five bit painting ciphertext block coming out and a three bit key so we could draw that and just draw it up the top saying that our simple cipher can someone give it a name give our cipher a name Bob okay plain text comes in and our cipher I need some space sorry Bob that's the name of our site it's not des it takes a key in and produces ciphertext that comes out the length of those in our case are five bits the key is three bits and the ciphertext is five bits it's the single version of our cipher Bob that's the normal operation from the perspective of a brute-force attack what's the worst-case time to break Bob so we do a brute force what's the worst-case number of operations I need to break this 8y 8 ^ 3 o our key is three bits we have 8 possible values ^ three possible values what if I replace Bob with deaths on our Drori but let's say we just checked change the algorithm remember the key lengths or the effective key lengths in in deaths the effective key lengths 56 the actual key that you choose is 64 bits but a or 8 of the bits are unused in encryption so we'll say 56 bits here because in practice the brute the attacker needs to try and find those 56 bits only so with 56 bits with des a brute-force worst case to ^ 56 that's a 6 we'll just keep track of both of them we'll go through the simple example and compare so that's the normal case of course our simple cipher is subject to a brute-force attack and in fact guest today is considered subject to a brute-force attack 56 bits is not long enough so the concept of a double cipher double encryption we take our plain text in we apply our cipher we use one key to encrypt that will get a value that comes out will denote as X some intermediate value and then we take that encrypt that again but this time using a different key same cipher a different key and get ciphertext out still same lengths for our simple cipher Bob five bits of plaintext X value will also be five bits C is five bits the keys each are three bits so just apply the cipher twice note if we take a plaintext we get some X that comes out X should be random with respect to the plaintext that's the idea of the encryption that is we'll get a different value out then we encrypt that different value we should get another random value output so we'll get a secure cipher text now we use two different keys the chooser chooses those two keys so if effectively the user chooses a six bit key they choose a six bit random value the first three bits will be used for the first step the second three bits use for the second step let's call this double Bob we've complied Bob twice brute-force what's a brute-force attack on double-bond bank two to the power of six operations again the attacker has to guess both values of k1 and k2 if they want to do a brute force so six bits to guess two to the power of six operations similar with double deaths how many bits well we expand our key from 56 up to 112 bits we'll just use two different keys or two random keys with double des a brute force would take two to the power of hundred and twelve operations and if you look up if you go back to that table we gave some example times for brute force attacks you'll see that with computers today that's probably not possible yeah well if we try to do calculations of how fast computers are if you had thousands of computers it's still going to take many years to do a brute-force attack so that's the idea make a brute force attack not possible let's see why we can try a different attack to still defeat double deaths and the attack is called meet in the middle what we will do we will assume that the attacker has a pair of plaintext ciphertext that is this attack requires the attacker to have a little bit of extra information to work the assumption is that the attacker knows from some past encryption by the user they know a plaintext and the corresponding ciphertext so knowing a ciphertext is easy intercept and you learn the ciphertext but we also assume that they know what was the plaintext for that case they don't know the key but they know one pair of plaintext ciphertext where the ciphertext was obtained using the Bob encryption algorithm using the some secret key K 1 and K 2 we want to find K 1 and K 2 how can our user or our attacker know a pair of ciphertext and plaintext without knowing the key what we need is somehow that let's say we've we can learn ciphertext easy intercept how do we learn the plaintext well the idea of encryption is we can't learn the plaintext if we don't have the key we don't have the key how can we assume that your attacker knows the plaintext well it may be some in some cases possible sometimes the ciphertext is encrypted and only needs to stay encrypted for a certain period of time maybe the plaintext is released publicly later okay so let's say I encrypt a message I send it the ciphertext to someone the message only makes sense for one day after two days it doesn't matter if someone knows what the plaintext message is so the attacker may discover this old ciphertext corresponds with this plaintext value a simple example of that let's say the plaintext message is the coordinates of the military is going to bomb someplace okay so the headquarters of the military send the exact GPS coordinates you need to bomb this location they send it to the plane that's going to bomb them and they bomb that location the attack eh of course they don't send their coordinates in plain text they send them encrypted so that if someone intercepts they can't learn where they're going to bomb that location so the attacker sees the ciphertext they can't find the plaintext fine but tomorrow after they know that that location was bombed they know the ciphertext and they know the coordinates of where it was bombed because it was actually bombed so now they know the corresponding plaintext with that ciphertext because that information was only really valid for up until the time that the bomb was hit the ground so that's an extreme example but there's other cases where it's possible for the attacker to learn the plaintext even if they don't have the key so let's assume that they do and I'll give you a pair it's we'll use our table to do the encryption our meet in the middle attack this attack assumes that the attacker knows of a plaintext ciphertext pair and I'll give you one and in fact in practice when we apply this attack to real dear students usually not just one pair that they have to know they may need to know a set of pairs more than one and at the end we'll analyze and see or how many let's give you a second one just in case we need it this is known by the attacker another pair what that means is that the attacker knows that when p1 is encrypted we get c1 when we use keys k1 and k2 but we don't know the keys k1 and k2 the goal of the attack is to find the keys k1 and k2 they also know using those same two key values encrypting the value of P 2 gives c2 so this is learnt by the attacker in advance they need this to be successful given that now they start the meet in the middle attack and it's quite simple what they do given one of the pairs that they know say with the first pair they take the plane to XP 1 and they do a brute force on that plaintext using the single version of the cipher Bob and find all possible potential values that come out of that that is what they're going to do in the picture is they know p1 they're going to encrypt p1 with every possible key they don't know k1 so let's try all possible values will get multiple values of X coming out potential values not necessarily the correct one but possible values and we'll store them and then what we'll do is we'll take the known ciphertext C 1 and go backwards that is we know what C 1 is we know what p1 was that we started with we don't know K 1 or K 2 after we try for all possible values of k1 on P we get potential values of X then with the ciphertext C 1 we decrypt that with possible values of K 2 and the idea is that if we know that p1 produce C 1 as output if you encrypt p1 with the correct key you'll get some x value and if you decrypt C 1 with the correct key you'll get the same x value it must be the same because otherwise they wouldn't have produced that correct hair so what we do is once we know the potential values of the X in one direction we work backwards and see if we find a matching X from the ciphertext if we do then that's a potential key pair if it's not a match then it's definitely not the correct keys so we'll try that the first step a brute-force attack on p1 using our cipher Bob and the key k1 is three bits so we need to try eight possible keys so the meet in the middle attack we're going to start with t1 and encrypt with the 8 possible keys I'll list them we know what they are and we're going to get eight intermediate values of X so look up in the table given plaintext 0 1 1 0 1 key 0 0 0 what comes out for our cipher Bob as simply a look up in the table write it down and then do it for the other kids so we need to try for all possible keys here this is a brute-force on the single version of our cycle a quick won't take long to find the other 8 values of X how do they know the plaintext we set an example there are some examples where this this text is owned and because the message was a secret for a short period of time then maybe the plaintext is released later maybe the plaintext was a message to say bye-bye these stocks in this KN Apple buy a thousand shares of Apple at this time at this price that was encrypted once they're bought the next day then it's no longer to stay encrypted because if someone sees that you've bought them after you've already bought them you may not want to keep them secret you want to keep it secret before you buy them so that someone doesn't know you're going to purchase stocks for example so some information the plaintext is only need to be secret for a short period of time if that's the case then the attacker may discover that plantings what do you get write down your values look up your table and find out the values of X which is just the ciphertext that comes out of our a bit block cipher eight keys what was L plaintext 0 1 1 0 1 0 1 1 here's our plaintext encrypt with the first key and we get this values output the second key that the next column and so on so we just get these eight values as an output here let's write them down and I'll give them values I'll say it's X the first value of x1 one we'll give these eight potential values of X this will call x.18 keep track of how many operations we do because at the end we need to count how many operations do we do in total or in a typical case and compare it to brute-force attack here we've encrypted our our plain text 8 times so the number of operations is 8 or 2 to the power of 3 it depends upon the key length here now we give these 8 values we store them in memory so we have to save them and then the next step is that with the corresponding ciphertext C 1 we decrypt that with potential key values we know c1 will each it was given to us five ones so decrypt with the potential keys see what we get this was x1 we're going to get a another x-value here x2 what we do is we take this ciphertext decrypt with our first possible key we don't know what the value of the key is we try this one what do we get look up the table five ones decrypted with key zero zero zero we did it before so decrypt those values as you go find the cipher page one owes and decrypt the vet 1 1 1 with the key 0 0 what do we get for the first value of x 1 0 0 0 1 we did that before let's just check that the key was 3 zeros the ciphertext 5 1 which is here decrypt this and you get 1 0 0 0 1 and then we do that for the next key this is the the x value x 2 1 will denote as and you keep keep going with the other keys you'll you'll tell me if we I write down any errors this is our last value so the first stage encrypt the plaintext with all possible keys the second stage take the corresponding known ciphertext for that plaintext that we started with c1 and decrypt that with what we did with all possible keys we'll come back later and sometimes we may not need to do all possible keys in the second phase but we will do that so in our block model what we did p1 encrypted with 8 keys get potential values of x x 1 so X 1 1 X 1 2 up to X 1 8 with C 1 decrypt with all possible keys K 2 and get X 2 X 2 1 X 2 2 and so on and we know if we've got the correct K 1 and K 2 then the X values should match X 1 should equal X 2 because we know that X is the intermediate value when we encrypt to get the ciphertext so this tells us what our potential values of K 1 and K 2 and it's quite easy to see we look at the values where the X are the same on both sides does this value x11 match any of these find see if you'd find this value in this set actually we'll do it the other way we'll try with x2 first because that's what's done in practice does one zero zero zero one appear in the first set of X values no it's not there okay so the next value does this appear in the first set check carefully no it's not there the third one no fourth one are we unlucky today fifth one yes that's there somewhere there's a match there we know that if we've used the right keys of k1 and k2 when the potential values of k1 are those that we used when we obtained x1 and the potential values of k2 are those values of the key were used when we obtained x2 so we know if we've used the correct values of x of k1 and k2 the x-values must match here we find a match any other matches which ones the last value of x2 matches matches two different places and that's possible ok all the others don't match which means that the potential values of k1 and k2 well there are three potential values three pairs k1 could be the value we use to get x1 2 0 0 1 and K 2 could be the value we use to get x2 5 which was 1 0 0 so that's a potential key pair we're actually looking for the entire six bits but I'll write it down as I keep a pair of keys k1 k2 we're trying to find the first potential values are 0 0 1 and 1 0 0 but there's other potential values 0 1 1 with 1 1 1 and the last one 1 0 0 1 1 1 so the attacker now knows that the keys used by the the user are one of those three pairs we want to know exactly which one how do we find out try print anew message well in fact I gave you a second one because I knew that's what we would need here if the attacker has a second plaintext ciphertext pair like the one given here they can check which of those three potential key values if we take our plain text to 1 1 0 0 1 encrypt with potential value of K 1 you get X encrypt that with a potential value of K 2 if you get this ciphertext value then you're very confident that it's the correct one maybe not for sure if you don't get it you know it's not the correct key try see which of the these three potential values are correct or which are incorrect if there's only one left over that's the correct value that is encrypt P 2 with k1 and k2 0 1 0 0 1 0 and then potential value try to look up start with 1 1 0 0 1 p2 and we'll try this first potential values of the keys if we use K 1 as 0 0 1 what does the value of X become encrypt this value of the plaintext with this key what's X if you look up in the table all zero is five zeros good now take that x value and encrypt it with the value of K 2 1 1 what's K 2 is the other value in the pair we're using this pair first we'll try that and when we do that we get cipher texts and 1 1 o 1 1 does that match the expected value of ciphertext yes it does so this key pair that we just tried is a potential correct key pair we don't know for sure maybe there's still others that are also potentially correct one way to find out is to try the others so do the same with the second key pair 0 1 1 get a value of X and then the second one of three ones and to be complete we'll try with the last one all we're doing here is encrypting using our lookup table using the table of the five bit block cipher we know the plaintext in we know the key find the output and then take that as the plaintext in the next step with the key find the output and see what you get and then check whether the ciphertext values you get out match the known correct value the known correct value was given in our pair we know c2 should be this value or we got it here here we get 1 0 1 1 1 out we try key 1 1 1 and you get 1 0 1 0 0 out this is the wrong key pair we know for sure now that this key pair is not the correct one because it doesn't give us the right ciphertext value and we try the last one and we get a ciphertext value that also doesn't match and that gets us to the end we now of those three potential key pairs of k1 and k2 we tried them all using our second known plaintext ciphertext pair and we found that two of them don't work only one of them works and that tells us that the correct values of k1 and k2 are the first pair k1 is 0 0 1 and K 2 is 1 0 0 let the answer we've found the key for the the double version of our cipher Bob count the number of operations we did with a single version of Bob how many encrypts or decrypts did we do count them in the first phase we did a brute-force attack on the key we did eight operations two to the power of three the next phase we actually did another eight operations this time decrypt but generally with ciphers encrypt and decrypt take about the same time with block ciphers so we count them as an eight operations so we've got sixteen operations and then in the last set of checks we did one two three four five six and other six operations another six encrypts or decrypts just to check those three paths so a total of 22 operations in this case we have to do these eight we have to do a brute force here two to the power of three we did it again but going backwards another two to the power of three and in this case we have three potential pairs so we need to do another six to check we won't always get three potential pairs sometimes we'll get just one and therefore we don't check we've already found the correct key sometimes we'll get more than one so we will need to check so the main contribution to the number of operations is doing the first two steps we have to do the brute force here to the power of three always what we can do when we look at the real desk is that we don't even need to do all two to the power of three here sometimes what we may do is if we find let's say in this case if we found the first matching pair after five operations then check that with another pair and the probabilities work when you have a large number of keys like des when there's many possible values the probability that the key pair that we find works for two or even three plaintext cipher taxpayers is very very low if it's incorrect that is if we find a match very high chance we've got the correct one here because there's only eight to choose from it's possible to get different possible values but with DES the chance of getting multiple and then doing it again and getting moldable is very very low so we can actually cut down the number of operations by stopping once we find a correct pair even if you do them all two to the power of 3 plus 2 to the power 3 plus another 6 here so we've got 2 to the power 3 2 times at least this meet in the middle attack let's write down some of the numbers to compare with brute force on our version of double bulb in that case it took us 2 to the power 3 plus another 2 to the power 3 plus in our case another 622 in that case our brute force on double Bob would have took 32 so we've done better than doing a brute force attack brute force all 32 keys 2 to the power of 6 64 well done 2 to the power of 5 is 32 it even better the force requires 2 to the power of 6 operation C for operations we did it in 22 we only checked when we have multiple potential values of the key like in this case we had 3 potential values so we did 2 to the power of 3 we did another 2 to the power of 3 operations now we have three possible values so we check those three only and other six operations we'll come back to that in a moment let's summarize the numbers so with a brute force on double Bob you would have took 64 operations here meet-in-the-middle in our specific case took 22 we're about three times faster than a brute force attack 1/3 of the number of operations so that's good that's where this attack is better than brute force because we can find the key in less time in double DES we must do a brute-force attack on the single version so there's two to the power of 56 and then worst case we need to do another two to the power of 56 similar here we did two to the power of three of n encrypts from one direction two to the power of three of decrypts from the other direction so we do two brute-force attacks plus some others in the same here we had plus six how many do we plus here depends upon how many matches we get here we had six there are three matches if we have a thousand matches here we have plus two thousand but compared to two to the fifty six two to the power of 56 is billions and billions so the number that we plus on in the Andes in most cases or almost zero so small plus something which is approximately if this is very small compared to two the power of 56 what do we get if this is 0 so 2 to the power of 56 plus 2 to the power of 56 2 to the power of 57 2 times 2 to the power of 56 brute force on single deaths takes two to the power of 56 operations brute force on double deaths takes two to the power of 112 operations group meet in the middle attack on double death takes about two to the power of 57 operations it's about two times slower than breaking single deaths in other words if you can break single s in one day you can break double deaths use a meat meat in the middle attack in two days which is insignificant from the attackers perspective right if I can break something in one day then if I want to break double deaths in two in one day as well I just spend twice as much money on my computer's so that's well we say that the double death is not much more secure than single deaths it's about the same two times better so that's why double deaths or double encryption in general it's not just for deaths double encryption like this is not a good approach it doesn't help well it doesn't help by much so the meat in the middle attack means that we shouldn't just do double encryption to extend the key length you can try triple encryption one then another than another and it turns out that that does make it harder for the attack and because you can't go back from other endpoints because there's two x-values in the middle so first let's summarize on meat in the middle attack in terms of number operations what we do a brute force on the first key value k1 and then a brute force on the second key value so equivalent to to brute force attacks and then possibly a few other operations to check but very small number compared to a brute force attack so it takes about two times as time to break as a brute force attack on deaths using a meat in in the middle attack now there's some ways to improve that the brute force attack on k2 a game with DES you usually don't have to try all 256 because as soon as you find a match you can confirm that match with another pair and you very high probability that you've got the correct key pair so in fact usually it's closer to us to ^ 5060 coming back to our specific example what's the problem with our meet in the middle attack from the attackers perspective what do we need to know or what do we need to do to make this attack work we we know that the user hasn't changed his key so so that's okay and we assume that the attacker the the normal user is using the same key for every plain text that they encrypt we'll come back to that later a good policy therefore is to change your key but here they're using the same key what's the problem from the attackers perspective for this tool the attacker needed to know a pair of plaintext cipher texts they had needed to know to in our case so there's one issue somehow they must discover this plaintext ciphertext pair in advance so this attack depends upon the attacker knowing some information in advance so that's one limitation another maybe more practical limitation is that when they do first brute-force on k1 they give these eight values of X what they must do is they store those eight values because when they're doing the next brute-force they compare the generator value of x to with those eight values of x one go through and check see which ones matched and if you do get a match you've got a potential key pair with DES the number of X values how many X one how many do we need to store with Bob we stored two to the power of three values of x one that first column with DES we'd have two to the power of 56 values of X 1 so with DES we'd need to store two to the power of 56 values of X 1 then when we go through to find X 2 we compare with those two to the power of 56 values next one compare and find the possible matches the limitation here's the storage to ^ fifty six values how many bytes store to ^ 56 in desc how big would XP and our cipher X was 5 bits a 5 bit block in DES it uses a 64-bit block 2 to the power of 56 64-bit blocks we need to store them on disk or in memory 64-bits is eight bytes times two to the power of 56 that's the number of bytes that we need megabytes gigabytes terabytes only 576 thousand terabytes what above terabytes petabytes isn't it P I think above T but a hard disk we measure in terabytes so we need about half a million hard disks all right one gigabyte one terabyte hard disk to store this information in an attack here's a practical limitation of the meat in the middle attack you need a lot of storage space to store that first set of answers and then compare against them approximately and we must know multiple usually multiple plaintext ciphertext pads so for the attack to be successful the number of operations is twice as many as a single desk brute-force attack but we must store a lot of information to do the attack and we must know multiple plaintext cipher taxpayers in advance to be successful even though that storage space may consider not practical today there may be ways to reduce it or to cut down on how much we store and this is the the double des is not considered a good design because of the meeting the middle attack and this was known and people therefore designed Triple DES encrypt encrypt encrypt three times and you can't take the plaintext and the cipher text and go back to get the same point so you can't meet in the middle in that case so Triple DES is considered secure