0:00

Now that we understand how DES works, let's look at a few attacks on DES,

Â and we're going to start with an attack called exhaustive search.

Â So our goal here is basically that given a few input-output pairs, (mi, ci),

Â our goal is to find the key that maps these m's to the c's.

Â In other words, our goal is to find the key that maps m1, m2, m3 into c1, c2, c3,

Â and as I said, our goal is to find the key that does this mapping.

Â The first question is, how do we know that this key is unique?

Â And so, let's do a little bit of analysis to show that in fact

Â just one pair is enough to completely constrain a DES key,

Â and that's why this question makes sense.

Â OK, so let's see. So we're going to prove this simple lemma.

Â Now let's assume that DES is what's called an ideal cipher.

Â So what is an ideal cipher? Basically we're going to pretend like DES is made up of

Â random invertible functions. In other words, for every key, DES implements a random invertible function.

Â Since there are 2^56 keys in DES, we're going to pretend like DES really is a collection

Â of 2^56 functions that are invertible from {0,1}^64 to {0,1}^64. OK? So of course,

Â DES is not a collection of 2^56 random functions, but we can idealize about the cipher and pretend

Â that it is such a collection. Then what can we say?

Â Then in fact it turns out that just given one message and ciphertext, you just give me

Â one pair, message and ciphertext, there's already only one key that maps this message to that ciphertext.

Â So already just given one pair m and c, I can ask you, find me the key that maps m to c,

Â and the solution is very likely to be unique. In fact it's going to be unique with probability roughly 99.5%.

Â I should say that this statement is true for all m and c, and the probability is just over the choice

Â of the random permutations that make up the cipher.

Â So let's write a proof. This is fairly straightforward. So what we're basically asking is,

Â what's the probability that there exists some key that's not equal to k such that,

Â well, c we know is equal to DES(k, m) by defintion of c and m, but we're asking how likely is it

Â that there's this other key, k-prime, that also satisfies this equality?

Â You realize that if this is true, if such a key k-prime exists, then just given m and c,

Â you can't decide whether the right key is k or k-prime, because both of them work. OK?

Â But I want to argue that this happens with low probability.

Â Well, so what does it mean that there exists a key k-prime that satisfies this relation?

Â Well, we're asking, what's the probability that the first key, the all-zero key, satisfies it?

Â Or, the second key satisfies it. Or, the third key satisfies it. And so on and so forth.

Â So by the union bound, we can bound this probability by the sum over all keys k-prime,

Â over all 56-bit keys, of the probability that DES(k,m) is equal to DES(k-prime, m).

Â OK? So we're asking, basically, what is this probability, for a fixed key k-prime,

Â that it happens to collide with the key k at the message m? Well, let's think about this for a second.

Â Let's fix this value, let's suppose it's some fixed value. And then we're asking,

Â how likely is it that a random permutation, pi k-prime, at the point m,

Â happens to produce exactly the same output as the key k at the point m?

Â Well, it's not difficult to answer and see that in fact this is, for a single key k-prime,

Â the probability is at most one over 2^64. Right? There are 2^64 possible outputs for the permutation,

Â what's the probability that it lands exactly on this output, well, it's one over 2^64.

Â And we're summing over all 2^56 keys, so we just multiply the two,

Â we get one over 2^8, which is basically one over 256. OK? So the probability

Â that the key is not unique is one over 256, therefore the probability that it is unique

Â is one minus that, which is 99.5%. OK? So already, if you give me one plaintext-ciphertext pair,

Â the key is completely determined. There's only one key that will map that plaintext

Â to that ciphertext, and the question is just, can you find that key?

Â Now it turns out in fact if you give me two pairs, so you give me m1 and m2,

Â and their corresponding outputs, c1 and c2, the probability basically

Â â€”just do exactly the same analysis, the probability basically becomes one.

Â That there's only one such key. OK, essentially, this is very, very, very close to 1,

Â and basically it says given two pairs, it's very very likely that only one key

Â will map this pair of messages to this pair of ciphertexts, and as a result again,

Â we can ask, well, find me that unique key. And by the way, the same is true for AES,

Â if you look at AES-128, again, just given two input-output pairs,

Â there's going to be only one key with very high probability. So essentially now

Â we can ask this exhaustive search problem, I give you two or three pairs, and I ask you,

Â well, find me the key. So how are you going to do it? Well, you're going to do it by exhaustive search,

Â essentially by trying all possible keys, one by one, until you find the right one.

Â So this is what's known as the DES challenge. So let me explain how the DES challenge worked.

Â The challenge was issued by a company called RSA, and what they did is basically,

Â they published a number of ciphertexts, but three of the ciphertexts had known plaintexts.

Â So in particular, what they did is they took the message here: The unknown message is, colon,

Â and you can see they broke it up into blocks. If you look at these, these are basically

Â eight-byte blocks. Eight bytes, as you know, is 64 bits, right, so each of these is 64 bits.

Â And then they encrypted them using a secret key. They encrypted them all using the same

Â secret key to get three ciphertexts. So this gives us three plaintext-ciphertext pairs,

Â and then they gave us a whole bunch of other ciphertexts, you know, c4, c5, c6,

Â and the challenge was, decrypt these guys using the key that you found

Â from an exhaustive search over the first three pairs that you were given.

Â OK. So that was called the DES challenge, and let me tell you a little bit

Â about how long it took to solve it. So interestingly, in 1997, using an Internet search,

Â using distributed.net, basically, they were able to search through enough of the keyspace

Â to find the correct key in about three months. You realize the keyspace has size 2^56,

Â but on average you only have to search through half the keyspace to find the key,

Â and so it took them three months. Then, kind of a miraculous thing happened.

Â The EFF actually contracted Paul Kocher to build special-purpose hardware to break DES.

Â This was a machine called Deep Crack. It cost about 250,000 dollars, and it broke

Â the next DES challenge in only three days. Interestingly, by the way, RSA said that

Â they would pay ten thousand dollars for each solution of a challenge, so you can see

Â that this is not quite economical. They spent 250K, they got ten thousand dollars

Â for solving the challenge. The next thing that happened is in 1999,

Â RSA issued another challenge, and they said, well, I'm gonna solve it in half the time

Â of the previous solution, and so using both Deep Crack and the Internet search together,

Â they were able to break DES in 22 hours.

Â So the bottom line here is, essentially, DES is completely dead.

Â Essentially, if you forget, or you lose your DES 56-bit key, don't worryâ€”

Â within 22 hours, you can actually recover it and in fact, anyone can recover it, and so

Â DES essentially is dead and no longer secure. And just kind of a final nail in the coffin,

Â as hardware technology improved, there was another project called COPACABANA that used FPGAs,

Â just off-the-shelf FPGAs, only 120 FPGAs. It only cost 10,000 dollars. And they were able to break,

Â to do an exhaustive key search in about seven days. So very, very cheap hardware, just off the shelf,

Â you can break DES already very quickly. So the lesson from all this is essentially,

Â 56-bit ciphers are totally, totally dead. And so the question is what to do.

Â People really liked DES, it was deployed in a lot of places, there were a lot of implementations,

Â there was a lot of hardware support for it, so the question was what to do.

Â And so the first thing that came to mind is, well maybe we can take DES

Â and we can kind of artificially expand the key size, so we strengthen it against

Â this exhaustive search attack. And the first idea that comes to mind is basically,

Â well, let's iterate the block cipher a couple of times. And this is what's called Triple DES.

Â So Triple DES is a general construction. Basically it says the following.

Â Suppose you gave me a block cipher E. So here, it has a keyspace K,

Â it has a message space M, and an output space of course M as well.

Â Let's define the triple construction, which now uses three keys, and it's defined as follows,

Â basically, here, the triple construction uses three independent keys, encrypts the same

Â message block as before, and what it does is, it will encrpyt using the key k3,

Â then it will decrypt using the key k2, then it will encrypt again using the key k1.

Â OK so basically encrpyting three times, using three independent keys.

Â You might be wondering, why is it doing E, D, E, why not just do E, E, E?

Â Why do we have to have a D in the middle? Well, that's just for, uh, kind of a hack.

Â You notice what happens if you set up k1 equals k2 equals k3? What happens if all three keys

Â are the same? Well, basically, what will happen is, one E and one D would cancel,

Â and you would just get normal DES out. So it's just a hack so that if you have a hardware implementation

Â of Triple DES, you can set all three keys to be the same, and you'll get a hardware implementation

Â of single DES. Of course it'll be three times as slow as a regular impelmentation of single DES,

Â but nevertheless, it's still an option. OK, so for Triple DES now we get a key size

Â that's 3 times 56, which is 168 bits; this is, 168 bits is way too long to do an exhaustive search on.

Â That will take time 2^168, which is more than all the machines on earth working for ten years

Â would be able to do. Unfortunately, of course, the cipher is three times slower than DES.

Â So this is a real problem with Triple DES. Now I want to mention that in fact you might think

Â Triple DES has security 2^168, but in fact, there is a simple attack that runs in time 2^118,

Â and I want to show you how that attack works. OK? Soâ€” but in fact 2^118 is still a large number.

Â In fact, anything that's, kind of, bigger than 2^90 is considered sufficiently secure.

Â 2^118 is definitely sufficiently secure against exhaustive search,

Â and generally is considered a high enough level of security.

Â So clearly Triple DES is three times as slow as DES. So the question is,

Â why did they repeat the cipher three times? Why not repeat the cipher just two times,

Â or in particular, the question is, what's wrong with double DES?

Â So here we have double DES. Basically you see it uses only two keys, and it uses only

Â two applications of the block cipher, and as a result it's only going to be twice as slow as DES,

Â not three times as slow as DES. Well, the key length for double DES is 2 times 56, which is

Â 112 bits, and in fact doing exhaustive search on a space of 112 bits is too much.

Â 2^112 is too big of a number to do exhaustive search over such a large space.

Â So the question is, what's wrong with this construction. Well, it turns out

Â this construction is completely insecure, and I want to show you an attack.

Â So, suppose I'm given a bunch of inputs, say m1 to m10, and I'm given the corresponding outputs

Â c1 to c10. What's my goal? Well, my goal is basically to find keys, you know, a pair of keys k1, k2,

Â such that if I encrypt the message M using these keys, in other words if I do this encryption,

Â this double DES encryption, then I get the ciphertext vector that was given to me.

Â OK, so our goal is to solve this equation here. Now you stare at this equation a little bit,

Â and you realize, hey wait a minute, I can rewrite it in kind of an interesting way;

Â I can apply the decryption algorithm, and then what I'll get is that I'm really looking for

Â keys k1, k2 that satisfy this equation here, where basically all I did is I applied

Â the decryption algorithm using k1 to both sides. OK, now whenever you see an equation like this,

Â what just happened here is that we separated our variables into two sides,

Â the variables now appear on independent sides of the equation, and that usually means

Â that there is a faster attack than exhaustive search, and in fact this attack is called

Â a meet-in-the-middle attack, where really the meet-in-the-middle is going to somehow

Â attack this particular point in the construction. OK, so we're going to try and find a key

Â that maps m to a particular value here, and maps c to the same value.

Â OK, so let me show you how the attack works. So the first thing we're going to do is

Â we're going to build a table. Here, let me clear up some space here.

Â The first step is to build a table that for all possible values of k2,

Â encrypts m under that value. OK, so here we have this table, so you notice

Â these are all 2^56 Single DES keys, OK, so the table has 2^56 entries,

Â and what we do is basically, for each entry, we compute the encryption of m

Â under the appropriate key. So this is the encryption of m under the all-zero key,

Â the encryption of m under the one key, and at the bottom, we have the encryption of m

Â under the all-one key. OK, so there are 2^56 entries, and we sort this table based on the second column.

Â OK, so far, so good. So by the way this takes timeâ€”to build this table takes time 2^56,

Â and I guess we also want to sort, sorting takes n log n time, so it's 2^56 times log 2^56. OK.

Â So now that we have this table, we've essentially built all possible values

Â in the forward direction for this point.

Â Now what we're going to do is this meet-in-the-middle attack,

Â where now we try to go in the reverse direction with all possible keys k.

Â Essentially we compute the decryption of c under all possible keys k1.

Â OK, so now for each potential decryption, remember the table holds all possible values

Â in the midpoint, so then for each possible decrpytion, we check, hey, is the decryption in the table,

Â in the second column in the table? If it is in the table, then aha, we found the match,

Â and then what do we know? We know that essentially, well, we found the match, so we know that

Â say for example a decryption using a particular key k1 happened to match this entry in the table,

Â say, k2 or more generally ki, then we know that the encryption of m under ki

Â is equal to the decryption of c under k. OK, so we kind of build this meet-in-the-middle,

Â where the two sides, you know, the encryption of m under ki and the decryption of c under k,

Â collided, but if they collided, then we know that in fact this pair, ki and k, is equal to

Â the pair that we're looking for. And so we've just solved our challenge.

Â So now let's look at what's the running time of this? Well, we had to build a table,

Â and sort it, and then for all possible decryptions, we had to do a search through the table.

Â So there were 2^56 possible decryptions, each search in a sorted table takes log(2^56) time,

Â if you just work it out this turns out to be 2^63, which is way, way, way, way, way smaller

Â than 2^112. OK, so this is a serious attack, it's probably doable today, that runs in a total time

Â of 2^63, which is about the same time as the exhaustive search attack on DES.

Â So really, double DES really didn't solve the exhaustive search problem,

Â because, well, there's an attack on it that runs in about the same time

Â as exhaustive search on single DES. Now someone might complain

Â that in fact this algorithm, well, we have to store this big table,

Â so it takes up a lot of space, but you know, so be it. Nevertheless, the running time

Â is still quite small or significantly smaller than 2^112.

Â Now you notice, by the way, this same attack applies to Triple DES.

Â What you would do is you would implement the meet-in-the-middle attack against this point,

Â you would build a table of size 2^56 of all possible encryptions of m,

Â and then you would try to decrypt with all 2^112 keys until you find a collision,

Â and when you find a collision, you have basically found k1, k2, k3.

Â OK, so even Triple DES has an attack that basically explores only 2^112 possible keys.

Â But 2^112 is a large enough number, so Triple DES in fact, as far as we know,

Â is sufficiently secure. I should mention that Triple DES is actually a NIST standard,

Â and so Triple DES is actually used quite a bit, and in fact DES should never ever ever be used,

Â if for some reason you're forced to use some version of DES, use Triple DES, not DES.

Â OK, I want to mention one more method for strengthening DES against exhaustive search attacks.

Â This method actually is not standardized by NIST, because it doesn't defend against

Â more subtle attacks on DES, but nevertheless if all you're worried about is exhaustive search,

Â and you don't want to pay the performance penalties of Triple DES, then this is an interesting idea.

Â So let me show you how it works. So let E be a block cipher that operates on n-bit blocks.

Â We're going to define the EX construction, and for DES we're going to get DESX, to be the following.

Â So we use three keys, k1, k2, k3, and then basically before encrpytion, we XOR with k3,

Â then we encrypt using k2, and then after encryption we XOR with k1. That's it.

Â That's the whole construction. So basically, you'll notice it doesn't slow the block cipher much,

Â because all we did is we applied the cipher plus two additional XORs, which are super fast.

Â The key length for this is in fact, well, we got two keys that are as long as the block size,

Â and we got one key that's as long as the key size, so the total is 184 bits.

Â Now, it turns out actually the best attack that's known is actually an attack that takes time 2^120,

Â and this is actually fairly simple. So it's a generic attack on EX, it will always take time basically

Â block size plus the key size, and it's a simple homework problem

Â for you to try to figure out this attack. I think this is a good exercise.

Â OK, in fact there is some analysis to show that there is no exhaustive search attack

Â on this type of construction, so it's a fine construction against exhaustive search,

Â but there are more subtle attacks on DES that we'll talk about in the next segment,

Â that basically this construction will not prevent.

Â One thing that I want to point out, unfortunately I found this mistake in a number of products,

Â is if you just decide to XOR on the outside, or if you just decide to XOR on the inside,

Â as opposed to XOR-ing on both sides, which is what DESX does,

Â you notice DESX XORs both on the outside and on the inside,

Â If you just do one of them, then basically this construction does nothing

Â to secure your cipher. It'll still be as vulnerable to exhaustive search

Â as the original block cipher E. OK, so this is another homework problem,

Â and actually you'll see that as part of our homeworks. OK.

Â So this basically concludes our discussion of exhaustive search attacks,

Â and next we'll talk about more sophisticated attacks on DES.

Â