0:00

In the last segment, we saw two active attacks that can completely destroy the

Â security of CPA secure encryption. In this segment, we're gonna define a new concept,

Â called authenticated encryption, that remains secure in the presence of an

Â active adversary. In later segments, we'll construct encryption schemes that satisfy

Â this new authenticated encryption concept. So what is authenticated encryption?

Â Authenticated encryption is a cipher where as usual the encryption algorithm takes a

Â key, a message and optionally a nonce and outputs a cipher text. The decryption algorithm as

Â usual outputs a message. However, here the decryption algorithm is allowed to output

Â a special symbol called bottom. When the decryption algorithm outputs the symbol

Â bottom, basically it says that the cipher text is invalid and should be ignored. The

Â only requirement is that this bottom is not in the message space so that in fact

Â it is a unique symbol that indicates that the cipher text should be rejected. Now

Â what does it mean for an authenticated encryption system to be secure? Well the

Â system has to satisfy two properties. The first property is that it has to be

Â semantically secure under a chosen plaintext attack just as before. But now

Â there's a second property which says that the system also has to satisfy what's

Â called cipher text integrity. What that means is that even though the attacker

Â gets to see a number of cipher texts, it should not be able to produce another

Â cipher text that decrypts properly. In other words, that decrypts to something

Â other than bottom. More precisely, let's look at the ciphertext integrity game.

Â So here, (E,D) is a cipher with message space M. As usual, the challenger begins

Â by choosing a random key K. And the adversary can submit messages of his

Â choice, and receive the encryptions of those messages. So here, C1 is the

Â encryption of M1, where M1 was chosen by the adversary. And the adversary can do

Â this repeatedly. In other words, he submits M2 and obtains the encryption of

Â M2, and so on and so forth. He submits many more messages up until Mq and obtains

Â the encryption of all those messages. So here the adversary obtained Q cipher texts

Â for messages of his choice. Then his goal is to produce some new cipher text that's

Â valid. So we'll say that the adversary wins the game if basically this new cipher

Â text that the adversary created decrypts correctly, in other words decrypts to

Â something other than bottom. And it's a new cipher text. In other words, it's not

Â one of the cipher texts that was given to the adversary as part of this chosen

Â plaintext attack. And then as usual we defined the adversary's advantage in the

Â cipher text integrity game as the probability that the challenger outputs

Â one at the end of the game and we'll say that the cipher has cipher text integrity

Â if in fact for all efficient adversaries the advantage in winning this game is

Â negligible. So now that we understand what cipher text integrity is we can

Â define authenticated encryption and basically we say that the cipher has

Â authenticated encryption if as we said it's semantically secure under a chosen

Â plaintext attack and it also has cipher text integrity. So just as a bad example,

Â let me mention that CBC with a random IV does not provide authenticated encryption

Â because it's very easy for the adversary to win the cipher text integrity game.

Â The adversary simply submits a random cipher text

Â and since the decryption algorithm for CBC encryption never outputs bottom,

Â it always outputs some message, the adversary just easily wins the game.

Â Any old random cipher text will decrypt to something other than bottom

Â and therefore the adversary directly wins the cipher-text integrity game. So this is just

Â a trivial example of a CPA secure cipher that does not provide authenticated encryption.

Â So I wanna mention two implications of authenticated encryption. The first I'll

Â call authenticity, which means that, basically, an attacker cannot fool the

Â recipient, Bob, into thinking that Alice sent a certain message that she didn't

Â actually send. So let's see what I mean by that. Well, here, the attacker basically

Â gets to interact with Alice, and get her to encrypt arbitrary messages of his

Â choice. So this is a chosen plain text attack. And then the attacker's goal is to

Â produce some cipher text that was not actually created by Alice. And because the

Â attacker can't win the cipher text integrity game, he can't do this. What

Â this means is, when Bob receives the cipher text that decrypts correctly under

Â the decryption algorithm, he knows that the message must have come from someone

Â who knows the secret key K. In particular, if Alice is the only one who knows K, then

Â he knows the cipher text really did come from Alice, and it's not some modification

Â that was sent by the attacker. Now the only caveat to that is that authenticated

Â encryption doesn't defend against replay attacks. In particular, the attacker

Â could've intercepted some cipher text from Alice to Bob. And could have replayed it

Â and both cipher text would look valid to Bob. So for example, Alice might send a

Â message to Bob saying transfer $100 to Charlie. Then Charlie could replay that

Â cipher text and as a result, Bob would transfer another $100 to Charlie. So in

Â fact, any encryption protocol has to defend against replay attacks and this is

Â not something that's directly prevented by authenticated encryption. And we'll come

Â back and talk about replay attacks in two segments. The second implication of

Â authenticated encryption is that it defends against a very powerful type of

Â adversary, namely an adversary that can mount what's called a chosen cipher text

Â attack. We're going to talk about that actually in the next segment.

Â