0:00

There is an immense literature on attacking block ciphers.

In this segment, I just want to give you a taste for what these attacks look like.

And I hope I'll convince you that you should never ever design your own block cipher,

and just stick to the standards like Triple DES and AES.

The first set of attacks that I want to talk about

are attacks on the implementation of the block cipher.

As an example, imagine you have a smart card that's implementing a block cipher.

So the smart card, for example, could be used for credit card payments. It might have a

secret key inside of it to authenticate your credit card payments as you stick the

card into a payment terminal, say. So now, if an attacker obtains your smart card,

what he could do is he could actually take the smart card to a lab, and then run the

card, and measure very precisely how much time the card took to do encryption and

decryption. Now, if the amount of time that the implementation took to do

encryption depends on bits of the secret key, then by measuring the time, the

attacker will learn something about your secret key and in fact, he might be able

to completely extract your secret key. And there are many examples of implementations

that simply by measuring the time very precisely for many operations of

encryption algorithms, you can completely extract the secret key. Another example is,

rather than just measuring the time, you can actually measure the power consumption

of the card as it's operating. So, literally, you can connect it to a device

that will measure the current that the card is drawing and then graph the

currents very, very precisely. Now, these cards are not very fast, and as a result,

you can actually measure the exact amount of power consumed at every clock cycle as

the card was executing. When you do that, you actually get graphs of this form.

So this is an example of a smart card operating, while it's doing the

DES computation. So you can see very clearly, here's when it was doing

the initial permutation. Here's when it's doing the final permutation. And then,

here, you can count. There are actually sixteen hills and troughs

corresponding to the sixteen rounds. And essentially when you zoom in on a graph

like this, you can basically read the key bits off one by one, just by looking at

how much power the card consumed as it was doing the different operations. It turns out

that, even cards that take steps to mask this type of information, are still

vulnerable. There's an attack called differential power analysis, where

basically, you measure the power consumed by the card over many, many, many, runs of

the encryption algorithm. And as long as there's any even small dependence between

the amount of current consumed and the bits of the secret key, basically that

dependence will show up after enough runs of the encryption algorithm. And as a

result you'll be able to completely extract the secret key. Okay, so these

attacks were actually discovered by Paul Kocher and his colleagues up at

Cryptography Research and there's actually a fairly large industry devoted to just

defending against these power attacks. As far as timing attacks are concerned,

I want to mention that these are real. They're not just about smart cards.

For example, you can imagine a multicore processor where the encryption algorithm

is running on one core and the attacker code happens to be running on another

core. Now these cores actually share the same cache. And as a result, an attacker

can actually measure or can actually look at the exact cache misses that the

encryption algorithm incurred. It turns out that by looking at cache misses, you

can completely figure out the secret key used by the algorithms. So, one core can

essentially extract information from the other core, just by looking at cache misses.

So implementing these block ciphers is actually quite subtle

because you have to make sure that the side channel attacks don't leak

information about your secret key. Another type of attack that's been discussed in

the literature is what's called a fault attack. So here, basically, if you're

attacking a smart card, you can actually cause the smart card to malfunction,

perhaps by overclocking it, perhaps by warming it up. Essentially, you can cause

the processor to, malfunction, and output erroneous data. It turns out that, if,

during encryption, there are errors in the last round of the encryption process, the

resulting ciphertexts that are produced are enough to actually expose the secret key K.

That's quite an interesting result that in fact if you have any errors, if you ever

output a wrong result, that actually could completely compromise your secret key.

So, of course, the defense against this means that before you output the result of your

algorithm, you should check to make sure that the correct result was computed.

Now of course that's nontrivial, because how do you know that the error didn't happen

in your checking algorithm. But there are known ways around that. So basically you

can actually compute something three or four times, take the majority over all those

results, and be assured that the output really is correct as long as not too many

faults occurred inside of your computation. These are attacks on the implementation.

I hope these examples can assure you that not only should you not

invent your own block ciphers, you should never even implement these crypto

primitives yourself. Because A, you have to make sure there are no side channel

attachments on your implementation and B, you have to make sure that the

implementation is secure against fault attacks. Okay so, instead you should just

use standard libraries like the ones available in OpenSSL and many other

libraries out there. So don't implement these primitives yourself, just use

existing libraries. All right, so now I want to turn to kind of more sophisticated

attacks on block ciphers and I'll particularly talk about how these attacks apply to DES.

Okay so these attacks were discovered by Biham and Shamir back in 1989, and I'll

particularly describe a version of the attack discovered by Matsui in 1993.

So the goal here is basically given many, many input-output pairs, can we actually

recover the key better than exhaustive search? So anything that runs better than

exhaustive search already counts as an attack on the block cipher. Okay, so the

example I want to give you is what's called linear cryptanalysis. And here imagine it

so happens that, you know, c is the encryption of m using key k, and

suppose it so happens that if I look at random key and a random message, somehow

there's a dependence between the message, ciphertext, and the key bits. In

particular, if I XOR a subset of the message bits, so this is just a

subset of the message bits, if I XOR that with a certain subset of the ciphertext

bits. —So these two the attacker sees. The attacker has the message and the

attacker has the ciphertext. And then you compare that to an XOR of a subset of

the key bits. Now if the two were completely independent which is what you'd

like, you definitely don't want your message and your ciphertext to somehow

predict your key bits, if the two are like, completely independent, then this

equality will hold with probability exactly one-half. But suppose it so

happens that there's a bias and this probability holds with probability half

plus epsilon for some small epsilon. It so happens that, in fact, for DES, there is

such a relation. The relation holds specifically because of a bug in the design

of the fifth S-box. It turns out the fifth S-box happens to be too close to a linear

function. And that linear function, basically, as it propagates through the

entire DES circuit, generates a relation of this type. You notice, this is

basically a linear relation that's being computed here. So, this small tiny, tiny

linearity in the fifth S-box generates this relation over the entire circuit,

where the epsilon is tiny. Epsilon is one over 2^21, and I wrote down what

that is. So the bias is really, really, really small. But nevertheless, there is a

bias using these particular subsets of bits. Now, I'm not going to show you how to

derive this relation, or I'm not going to show you even what it is. I'll just tell you

how to use a relation like this once you find it. Okay. So here's our relation

that we have. And the question is how to use it. So with a little bit of statistics

you can actually use an equation like this to determine some of the key bits. And

here's you do it. Suppose you were given one over epsilon squared message-ciphertext pairs.

And these have to be independently random messages and the

corresponding ciphertexts. What you would do is you would use the formula above. In

fact you would use the left-hand side of the formula above to compute this relation

between the message and ciphertext for all the pairs you were given. Now what do

you know? You know that for half plus epsilon of these values, you know that

these things will be equal to an XOR of the key bits. So if you

take majority over all the values you've computed, it turns out it's not so

difficult to see that in fact you'll get the correct prediction for the XOR of the

key bits with a probability of 97.7%. In other words, if this relation happens to

be correct more than half the time, then the majority will be right. And because

there's a bias, there's an epsilon bias, the probability that you will be correct

more than half the time is, in fact, 97.7%. In which case, the majority, in

fact, will give you the correct XOR of the key bits. Okay? So this is kinda cool.

Within one over epsilon squared time, you can figure out an XOR of a bunch of key

bits. So now, let's apply this to DES. So, for DES, we have epsilon, which is one

over 2^21. Which means that if you give me 2^42 input-output pairs, I can

figure out an XOR of the key bits. And now, it turns out, I'm not gonna exactly show

you how, roughly speaking, using this method, you don't just get one key bit. In

fact, you get two key bits. You can kind of use this relation. One's going in a

forward direction and one's going in a backwards direction. So that gives you two

XORs of bits of the secret key. Okay, so that's two bits of information about the

secret key. And then it turns out you can get twelve more bits, because,

essentially, you can figure out what the inputs are to the fifth S-box. Okay, so,

I'm not going to exactly show you how. But it turns out you can get twelve more bits,

which is a total of fourteen bits overall. So now, using this method, you've

recovered fourteen bits of the secret key. And of course, it took you time 2^42.

Okay, so then, what do you do? Well, so the rest of it is easy. Now what

you're going to do is you're going to do exhaustive search on the remaining bits.

Well how many remaining bits are there? Well, there are 42 remaining bits, so

the exhaustive search will take you time 2^42. So what's the total attack time?

Well, the first step of the algorithm to determine the fourteen bits took 2^42 time,

and the remaining brute force search also took 2^42 time.

So overall, the attack took two to the 43 time. Okay? So now, this is much better

than exhaustive search. Within two to the 43 time, we broke DES. But of course, this

required two to the 42 random input-output pairs whereas exhaustive search only

required three pairs. Okay, so this is a fairly large number of input-output

pairs that are needed, but given such a large number, you can actually recover the

key faster than exhaustive search. Okay, so what's the lesson in all this?

The lesson is, firstly, any tiny bit of linearity, basically, in this— in the

fifth S-box, which was not designed as well as the other S-boxes, basically led

to an attack on the algorithm. Okay. A tiny beat of linearity already introduced this

linear attack. And I want to emphasize again that this is not the sort of thing

you would think of when you design a cipher. And so again, the conclusion here is,

there are very subtle attacks on block ciphers, ones which you will not be able to

find yourself. And so just stick to the standards. Don't ever, ever, ever, ever

design your block cipher. Okay, so that's all I want to say about sophisticated

attacks. Now let's move on to the last type of attack that I want to mention, which

I'll call quantum attacks, which are again— these are generic attacks on

all block ciphers. So let me explain what I mean by this.

So first of all, let's look at a generic problem, a generic search problem. Suppose I have a function

on some large domain X, that happens to be two outputs, either zero or one.

And it so happens that this function is mostly zero. And there's, like, maybe one input

where the function happens to evaluate to one. And your goal is basically, you know,

find me the inputs where the function happens to be one. Maybe there's only one

such input. But your goal is to find it. Well, so on a classical computer, what can

you do? The function is given to you. It's given to you as a black box. So the best

you can do is just try all possible inputs. So this is gonna take time which

in linear in the size of the domain. Now, it turns out there's an absolutely magical

result that says that if you build a computer that's based on quantum physics

as opposed to classical physics, you can solve this problem faster. So let me

explain what I mean by this. So first of all in the 70s and 80s it was observed, I

think it was actually Richard Feynman who observed this initially, that said

that it turns out to be very difficult to simulate quantum experiments on a

classical computer. So Feynman said, if that's the case, maybe these quantum

experiments are computing things that a classical computer can't compute.

So they're somehow able to compute very quickly things that are very difficult to

do classically. And that turned out to be correct. And in fact, the example I want

to show you is one of these amazing things that in fact, if you could build a

quantum computer that's using quantum physics, then it's, in fact, you can solve

this search problem not in time X but in time square root of X. So somehow, even

though the computer doesn't know anything about the function F, it's treating it as

a black box, nevertheless, it's able to find a point where the function is one, in

time square root of X. I'm not going to explain this here, but, at the end of the

class, we're gonna have an advanced topics lecture. And if you'd like me to explain

how this algorithm works, I can explain it in that advanced topics lecture.

It's actually quite interesting, and, in fact, quantum computers have quite an impact on

crypto. And again, as I said, I can explain this in the very last lecture.

All right. So what does this have to do with breaking block cyphers? So far it's just a

generic search problem. Well, oh actually I should say before I show you the

application, I should mention that, well, you might be wondering, well, can someone

build a quantum computer. And this is still completely unknown. At this point,

nobody really knows if we can build large enough quantum computers to actually

take advantage of this beautiful algorithm due to Grover. Alright, so what does this

have to do with block ciphers? Well, so suppose I give you a message-ciphertext pair.

Just one or just a few. We can define a function as follows. It's a

function on K, it's a function on, the key space. And the function will basically

output one if it so happens that the encryption of m with k maps to c, and it

will output zero otherwise. Now we argue that basically this is exactly the type of

function that's one at one point in the key space and that's it. So by Grover's

algorithm, we can actually find the secret key in time square root of K.

So what does that mean? For DES, this would totally destroy DES. This would say

that in time 2^28, you could find a key. 2^28 is about 200 million.

So 200 million steps which is, you know, just takes a millisecond on a modern computer.

This would totally destroy DES. But even AES with 128-bit keys,

you would be able to find the secret key in time, roughly 2^64.

And 2^64 is these days, considered insecure. That's within the realm of

exhaustive search. And so, basically, if somebody was able to build a quantum

computer, we would then say that AES-128 is no longer secure. Instead, if somebody,

you know, if tomorrow, you open up the newspaper, and you read an article that

says, you know, so-and-so built a quantum computer, the conclusion, the

consequence of all that is that you should immediately move to block ciphers that use

256 bits, because then the running time of Grover's algorithm is 2^128,

which is more time than we consider feasible, and the, basically there are

example ciphers with 256 bits, for example, AES-256. This is one of the

reasons why AES was designed with 256 bits in mind. But to be honest, this is

not the only reason. There are other reasons why you want it to have larger key sizes.

Okay, so this is, as I said, just a taste of the different attacks on block ciphers,

and I'm gonna leave it at that. If we decide on quantum for the last

topic of the course, then we'll recover that in the very last lecture.