Exhaustive search attacks (20 min)

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.