0:00

In the last segment we defined authenticated encryption, but I didn't

really show you why authenticated encryption is the right notion of

security. In this segment I want to show you that authenticated encryption in fact

is a very natural notion of security and I'll do it by showing you that it defends

against a very powerful attack called a chosen cipher text attack. So in fact we

already saw a number of examples of a chosen cipher text attack so imagine the

adversary has some cipher text C that it wants to decrypt. And what it can do

is, for example, fool the decryption server into decrypting some cipher text

but not actually the cipher text c. So we already saw some examples of that. If you

remember in the first segment, we looked at an adversary that can submit arbitrary

cipher text, and if the plaintext happened to start with destination equals 25, then

the adversary is actually given the plaintext in the clear. So that's an

example of an adversary that can obtain the decryption of certain cipher texts but

not all cipher texts. Another example we saw is an adversary that can learn

something about the plaintext by submitting cipher texts to the decrypter.

So we have this example where the adversary submits encrypted TCP/IP packets

to the decryption server, and if the decryption server sends back an ACK, the

adversary learns that the decrypted plain text had a valid check sum. And otherwise,

the decrypted plain text didn't have a valid check sum. So this is, again, an

example of a chosen cipher text attack, where the attacker submits cipher text,

and learns something about the decryption of that cipher text. So to address this

type of threats, we're gonna define a very general notion of security, called chosen

cipher text security. So here, we're gonna give the adversary a lot of power, okay?

So he can do both chosen plain text attack, and a chosen cipher text attack.

In other words, he can obtain the encryption of arbitrary messages of his

choice. And he can decrypt any cipher text of his choice, other than some challenge

cipher texts. And as I showed you before, this is actually a fairly conservative

modeling of real life. In real life, often, the attacker can fool the, the

decrypter, into decrypting certain cipher texts for the attacker, but not all cipher

texts. So the model here is that the attacker has a certain cipher text that it

wants to decrypt. It can interact with the decrypter by issuing these chosen

cipher text queries to the decrypter. Namely, to decrypt various cipher text

other than the challenge cipher text. And then the adversary's goal is to break

semantic security of the challenge cipher text. So you notice that we're giving the

adversary a lot of power. And all we're asking you to do is break semantic

security. So it's going to be fairly difficult to design systems that are

secure against such adversaries. Nevertheless, we're going to do it. So

let's define the chosen cipher text security model more precisely. So, as

usual, we have a cipher (E, D). And we're gonna define two experiments, experiment

zero and experiment one. So this should look somewhat familiar by now. The

challenger is gonna start off by choosing a random key. And now the adversary is

gonna submit queries to this challenger. Every query can be one of two types. It

can be a chosen plain text query, or it can be a chosen cipher text query. So a

chosen plain text query, as we already know. Basically, the adversary submits two

messages, M zero and M1. They have to be the same length. And the adversary

receives the encryption of either M zero if we're in experiment zero, or M1, if we're

in experiment one. So he receives the encryption of the left or the right

depending on whether we were in experiment zero or in experiment one. The second type

of query is the more interesting one. This is where the adversary submits an arbitrary

cipher text of his choice and what he gets back is the decryption of that cipher

text. So you notice the adverary's allowed to decrypt arbitrary cipher texts of his

choice. The only restriction is that the cipher text is not one of the cipher texts

that were obtained as a result of a CPA query. And of course this wouldn't be fair

otherwise, because the attacker can simply take one cipher text that was obtained

from a CPA query. That's gonna to be either the encryption of M0 or the

encryption of M1. If he could submit a CCA query for that particular cipher text, he

will in response either obtain M0 or M1, and then he'll know whether he is in experiment

zero or experiment one. So this wouldn't be fair. So we say that the CPA cipher

texts that he received are the challenge cipher texts. And he's allowed to decrypt

any cipher texts of his choice, other than these challenge cipher texts. And as

usual, his goal is to determine whether he's in experiment zero, or in experiment

one. So I'm gonna emphasize again, that this is an extremely powerful adversary.

One that can decrypt any cipher text of his choice, other than the challenge

cipher text. And still, he can't distinguish whether he is in experiment

zero, or in experiment one. So, as usual, we say that the cipher is CCA secure,

chosen cipher text secure, if the adversary behaves the same in experiment

zero as it does in experiment one. Namely, it cannot distinguish the two experiments. So

let's start with a simple example, and show that, in fact, CBC with a random IV,

is not CCA secure, is not secure against chosen cipher text attacks. So let's see

why that's the case. So what the adversary's gonna start by doing, he's

gonna simply submit two distinct messages, M0 and M1. And let's just pretend that

these messages are one block messages. And what he's gonna get back is the CBC

encryption of either M0 or M1. You notice the cipher text only has

one block, because the plain texts were only one block long. Now what is the

attacker gonna do? Well, he's gonna modify this cipher text C that he was given into

C prime simply by changing the IV. Okay? So he just takes the IV and XORs it with

one. That's it. This gives a new cipher text, C prime, which is different from C

and as a result it's perfectly valid for the adversary to submit C prime as its

chosen cipher text query. So he asks the challenger please decrypt this C

prime for me. The challenger, because c prime is not equal to c, must decrypt c

prime. And now let's see, what happens when he decrypts c prime? Well, what's the

decryption of c prime, let me ask you. So you probably remember from the first

segment that if we xor the IV by one, that simply xors the plaintext by one. So now

that adversary received M0 xor one, or M1 xor one, and now he can perfectly tell

whether he's in experiment zero and, or in experiment one. So the advantage of this

adversary is basically one, because he can very easily tell which experiment he's in.

And as a result he can win the chosen cipher text security game. So if you think

about it for a second, you'll see that this attack game exactly captured the first

active attack that we saw, where the adversary slightly changed the cipher text

that he was given. And then he got the decrypter to decrypt it for him. And

therefore, he was able to eavesdrop on messages that were not intended for the

adversary. So I wanna emphasize again that this chosen cipher text game really does

come up in real life, where the adversary can submit cipher texts to the decrypter

and the decrypter can reveal information about the plain text, or it can give the

plain text outright to the adversary for certain cipher texts but not others. So

this is a very natural notion of security, and the question is, how do we design

crypto-systems that are CCA secure? So I claim that this authenticated encryption

notion that we defined before actually implies chosen cipher text security, and

this is why authenticated encryption is such a natural concept. Okay? So the

theorem basically says, well, if you give me a cipher that provides authenticated

encryption, the cipher can withstand chosen cipher text attacks. And more

precisely, the theorem says the following. If we have an adversary that issues Q

queries, in other words, at most, q CPA queries and q chosen cipher text queries,

then there are two efficient adversaries, B1 and B2, that satisfy this inequality

here. So since the scheme has authenticated encryption, we know that

this quantity is negligible because it's CPA secure. And we know that this

quantity is negligible because the encryption scheme has cipher text

integrity. And as a result, since both terms are negligible we know that

adversary's advantage in winning the CCA game is also negligible. So let's prove

this theorem. It's actually a very simple theorem to prove. And so let's just do it

as proof by pictures. Okay, so here we have two copies of the CCA game, so this

would be experiment zero. And the bottom one is experiment one. You can see the

adversary's issuing CPA queries, and he's issuing CCA queries, and at the end he

outputs, you know, a certain guess b, let's call it b prime, and our goal is to

show that this b prime is indistinguishable in both cases. In other

words, probability that b prime is equal to one in the top game is the same as the

probability that b prime is equal to one in the bottom game. Okay, so the way we're

gonna do it is the following. Well, first of all, we're gonna change the challenger

a little bit, so that instead of actually outputting the decryption of CCA queries,

the challenger is just gonna always output bottom. So every time the adversary

submits a CCA query, the challenger says bottom. And I claim that these two

games are, in fact, indistinguishable. In other words, the adversary can't

distinguish these two games, for the simple reason that, because the scheme has

cipher text integrity, the adversary simply cannot create a cipher text that's

not in C1 to CI-1 that decrypts to anything other than bottom. That is the

definition of cipher text integrity. And as a result, again, because of cipher text

integrity, it must be the case that every chosen cipher text query that the

adversary issues results in bottom. If the adversary, in fact, could distinguish

between the left game and the right game, that would mean that at some point he

issued a query that decrypted to something other than bottom. And that we could use

to then break cipher text integrity of the scheme. And since the scheme has

cipher-text integrity, these left and right games are indistinguishable. Okay,

so that's kind of a cute argument that shows that it's very easy to respond to

chosen cipher-text queries when you have cipher-text integrity. And the same thing

exactly applies on the bottom, where we can simply replace the chosen cipher-text

responses by just always saying bottom. Okay, very good. But now, since the chosen

cipher text queries always respond in the same way, they're not giving the adversary

any information. The adversary always knows that we're always gonna just respond

with bottom. So we might as well just remove these queries, 'cause they don't

contribute any information to the adversary. But now, once we remove these

queries, the resulting game should look fairly familiar. The top right game, and

the [bottom right] game are basically the two games that come up in the definition of

CPA security. And as a result, because the scheme is CPA secure, we know that the

adversary can't distinguish the top from the bottom. And so now, by this change of

reasoning, we've proven that all of these games are equivalent. And in particular,

the original two games that we started with are also equivalent, and therefore,

the adversary can't distinguish the top left from the bottom left. And therefore,

the scheme is CCA secure. So this gives you the intuition as to why authenticated

encryption is such a cool concept. Because primarily it implies security against

chosen cipher test attacks. Okay, so as we said authenticated encryption

ensures confidentiality. Even if the adversary can decrypt a subset of the

cipher text, and more generally, even if he can mount a general chosen cipher text attack,

he still is not going to be able to break semantic security of the system. However,

it is important to remember the two limitations. First of all, it does not

prevent replay attacks on its own. We're going to have to do something in addition

to defend against replay attacks. We're going to see several examples where if the

decryption engine reveals more information about why a cipher text is rejected, it

doesn't just output bottom, but it actually outputs more information, say, by

timing attacks. And that explains why the cipher text is rejected. Then in fact that

can completely destroy security of the authenticated encryption system. So we'll

see some cute attacks like this in a later segment. Okay. So, in the next segment

we're gonna turn to constructing authenticated encryption systems.