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.

Â