0:00

In this segment, we're gonna look at the concept of deterministic encryption that

Â often comes up in practice. When I say deterministic encryption system, I mean an

Â encryption system that will always map given message to exactly the same cipher

Â text. So if we encrypt the same message three times, every time we'll get exactly

Â the same cipher text. So there are no nonces involved here. Literally this is

Â just a consistence encryption scheme that will always output the same cipher text

Â given a particular message. So let's see where this comes up in practice and in

Â particular, I want to show you the case of look-ups into an encrypted database. So

Â the settings are imagine we have a server here that is going to store information

Â inside of an encrypted database. So what it will store is records, and every record

Â has an index and some data that's stored inside of the record. Now, the first thing

Â the server's gonna do is, it's gonna encrypt this record. So here's a record

Â became encrypted and you notice that the index became encrypted with K1 and the

Â data is encrypted with K2 and then the encrypted record is sent over to the

Â database. And the same thing happens to many records so that the database overall

Â holds many, many encrypted records. Well, again, you can imagine that the index is

Â encrypted using the key K1 and then the data and the records is encrypted using

Â the key K2. Now, if encryption is deterministic, the nice thing about that

Â is that, at a later time, when the server wants to retrieve a record from the

Â database, all he needs to do is send to the database an encryption of the index

Â that the server is interested in. So here, it would send an encryption of the index,

Â Alice. That again, becomes encrypted, and the resulting cipher text is identical to

Â the cipher text that was generated when the record was first written to the

Â database. And the database can then, you know, find the record that has this

Â encrypted index in it, and then send the result back to the server. The nice thing

Â about this is that now the database is completely in the dark as to what data is

Â stored in the database and it doesn't even know what records are being retrieved by

Â the server since all it sees are basically requests for encrypted entices. And so

Â this deterministic encryption mechanism. Let's just do a quick look up in the

Â database given an encrypted index and we're guaranteed that because of the

Â deterministic encryption property that the index is going to be encrypted in exactly

Â the same way as if was when the record was created. And so this should be disturbing

Â to many of you because we previously said that deterministic encryption simply

Â cannot be chosen plain text secure. The problem is that an attacker can look at

Â different cipher text and if he sees the same cipher text twice he knows that the

Â underlying encrypted messages must also be the same. So in other words, by looking at

Â cipher text, he can learn something about the corresponding plain text because every

Â time he sees the same cipher text twice, he knows that the underlying messages are

Â equal. In practice, this leads to significant attacks, and particularly when

Â the message space is small. For example, if we're transmitting single bytes across

Â the network, such as, keystrokes that are being transmitted one keystroke at a time.

Â Then, in fact, an attacker can simply build a dictionary of all possible cipher

Â texts. If it's only single bytes, then there will only be 256 possible cipher

Â texts. And then, simply by learning what the decryptions of those cipher texts are,

Â he can actually figure out all future cipher texts, simply by looking them up,

Â in this dictionary. And so there are many cases where the message being so small,

Â where this, deterministic encryption, simply is insecure. Now concretely, in the

Â case of an encrypted database, what the attacker would see is if there are two

Â records that happen to have the same cipher text in the index position then now

Â he knows that those two records correspond to the same index. So again, even though

Â he doesn't know what the index is, he learns something about the corresponding

Â plain text. I wanted to briefly remind you that, formally, we say that deterministic

Â encryption cannot be CPA secure by describing an adversary that wins the CPA

Â game. The chosen plain text attack game, and let me quickly remind you how that

Â works. The game starts by the adversary sending two messages, M zero and M zero.

Â And remember that, in this game, the adversary is always going to be given the

Â encryption of the left message or the encryption of the right message. In this

Â case, since he used the same message in both cases, both on the left and on the

Â right, he's simply gonna get the encryption of the message M zero. In the

Â next step, he's gonna send the messages M zero, M1. And now he's either gonna get

Â the encryption of M zero, or the encryption of M1. And his goal is to tell

Â which one he got. But because the encryption is deterministic, this is very

Â easy for him to do. All he has to do is just test whether C is equal to C zero.

Â And if C is equal to C zero, then he knows that he got the encryption of M zero. If C

Â is not equal to C zero, he knows that he got the encryption of M1. So he can output

Â zero. If C is equal to C0 and output one, if C is not equal to C0 and his advantage

Â in this in this particular game would be one. So it, it would be a high, as high an

Â advantage as possible which means that he attacker completely defeats chosen

Â plain text security. Okay so, this is just a formal way of saying that the attacker

Â basically learns more information about the plain text than he should. So, the

Â question is, what do we do? And it turns out the solution is basically to restrict

Â the type of messages that can be encrypted under a single key. And so, the idea is to

Â say that suppose the encryptor never ever, ever encrypts the same message under a

Â single key. In other words the message key pair is always different and never

Â repeats. So that for every single encryption, either the message changes, or

Â the key changes, but, or both change. But it can't be that we encrypt the same

Â message twice under the same key. So why would this ever happen? Well it turns out

Â there are very natural cases where this happens. For example, if the messages

Â happen to be random. Say you, the encryptors encrypting keys and those keys,

Â you know, say are 128 the keys so, they'll never actually with very high

Â probability, they'll never repeat. In this case when we're encrypting keys, in fact,

Â is very likely that all the messages that are encrypted under one master key are

Â always distinct because, again, these keys are very unlikely to ever repeat. The

Â other reason why messages would never repeat is simply because of some structure

Â in the message space. For example, if all we're encrypting are unique user IDs. So

Â imagine, in the database example, the index corresponds to a unique user ID. And

Â if there's exactly one record in the database for each user, that says that

Â every encrypted record basically contains an encrypted index, where the index is

Â distinct for all records in the database. Okay so these are two reasons why messages

Â might never repeat. And this is a fairly reasonable thing that actually does happen

Â quite often in practice. So now if the messages never repeat, now maybe we can

Â actually define security and actually give constructions to satisfy our definitions.

Â So this motivates the concept of deterministic chosen plain text attacks and

Â let me explain what they mean. So as usual we have a cipher defined as an encryption

Â on a decryption algorithm. So we have a key space, a message space and a cipher

Â text space and we're gonna define security just as normal using two experiments.

Â Experiment zero and experiment one. And the game actually looks very similar, it's

Â almost an identical game to the standard chosen playing test attack game where

Â basically the attacker issues queries, so you can see these queries consist of pairs

Â of messages, M0 and M1. They, as usual they have to be the same length and for

Â each query the attacker either gets the encryption of M0 or the encryption of M1

Â and the attacker can do this again and again. He can do this Q times, and at the

Â end of the game he's supposed to say whether he got the encryptions of the left

Â messages or the encryptions of the right messages. So this is the standard chosen

Â plain text attack game, but now there's one extra caveat. Which is to say that, if

Â the bit is equal to zero, if B is equal to zero. In other words, the attacker always

Â sees the encryption of the left messages, then it so happens that the left messages

Â must all be distinct. In other words, he will never get to see the encryption of

Â the same message twice, because these left messages are always distinct. So if the

Â bit B is equal to zero, again, he'll never see. The same message encrypted under the

Â same key. Because, again, these zero messages, M1 zero to MQ zero, are all

Â distinct. Similarly, we require that all the one messages are also distinct. And so

Â that, again, if B happens to be equal to one, the attacker will never see two

Â messages encrypted under the same key. Okay? So this requirement that the, all

Â these messages are distinct, and similarly, all these Q messages are

Â distinct. Basically captures this use case that the encryptor will never encrypt the

Â same message multiple times using one particular key. And as a result, the

Â attacker simply can't ask for, the encryption of the same message multiple

Â times using the same key. Now, I should point out as you go back to our, to the

Â original attack, here. So, here we go back to our CPA attack on deterministic

Â encryption, you notice that here, in fact, this is not a deterministic CPA game,

Â because, here, the attacker did ask for the same message m0 to be encrypted twice.

Â So, in fact, this attack would be an illegal attack under the deterministic CPA

Â game. And by ruling out this attack we actually make it plausible that we might

Â be able to give constructions that are deterministic CPA secure. And so as usual

Â we say if the adversary cannot distinguish experiment zero, when he's given the

Â encryption of the left messages, from experiment one, when he's given the

Â encryption of the right messages, then the scheme is semantically secure. Under a

Â deterministic CPA attack. Okay. So as usual, we ask for what's the probability

Â that the adversary outputs one in experiment zero? What's the probability

Â that the outputs one in experiment one? Then if these probabilities are close then

Â his advantage in attacking the scheme is negligible. And if that's true for all

Â efficient adversaries then we say that the scheme is semantically secure under

Â deterministic CPA attack. So the first thing I want to do is show you the cipher

Â block training with a fixed IV, in fact, not deterministic CPA secure. And this a

Â common mistake that's used in practice. There are many products that should be

Â using a cipher that's deterministic CPA secure, but instead, they just use CBC

Â with a fixed IV and assume that's a secure mechanism. And in fact, it's not and I

Â want to show you why. So suppose we have a PRP that happens to operate on N bits

Â blocks. And we're going to use this PRP in CBC mode. So, you know, if there are five

Â blocks in the message then this PRP E will be called five times to encrypt each one

Â of those blocks. Okay. So here's how the attack's going to work. Well, the first

Â thing the adversary is going to do is he's going to ask for the encryption of the

Â message as 0N, 1N. In other words, the first block is all zeros and the second

Â block is all ones. So the left message is equal to the right message here which

Â means that he just wants the encryption of this 0N, one to the N message. So let's

Â see what the cipher text looks like. Well, for completeness I'm gonna write the IV,

Â the fixed IV, as the first element in the ciphertext. And if you think about how

Â CBC works and the second element in the ciphertext is gonna be basically the

Â encryption of the IV XOR the first block of the message. Well in our case the

Â first block of the message is all zeros so really all we're encrypting is just a

Â fixed IV. So the second block of the ciphertext is simply gonna be the

Â encryption of this fixed IV. So next, what the adversary's gonna do is, now he's

Â gonna output two messages that are a single block. So the first message is

Â gonna be, the message on the left is gonna be the all zeroes block. And the message

Â on the right is gonna be all ones block. So observe that this is a valid query,

Â because messages on the left are all distinct. And the messages on the right

Â are also all distinct. So these are all valid deterministic CPA queries. Now, what

Â does the attacker get in response? Well, what he'll get in response is the

Â following. If he gets the encryption of the message on the left. Then, well,

Â what's the encryption of the one block message, zero to the N? It's simply the

Â encryption of the fixed IV, just as we saw before. However, if he's getting the

Â encryption of the message on the right, well, that's gonna be the encryption of 1 XOR

Â the fixed IV. That's the definition of, CBC encryption. So know, you can see

Â basically how the attack is going to proceed. You notice, if I, here I'll use a

Â different color here. You notice if these two blocks happen to be the same, then we

Â know that he received the encryption of the message on the left, in other words B

Â is equal to zero. If they're not the same then he knows that B is equal to one Okay,

Â so he's gonna output zero if, you know, C of one, which is this block, is equal to

Â C1 of one, which is this block, and he's gonna output one otherwise. So this

Â basically shows that CBC with a fixed IV is completely insecure. Basically the

Â first block can be very easily attacked. And, in fact, if the messages are short

Â you can again build dictionaries and completely break systems that kind

Â of view CBC with a fixed IV hoping that it's gonna be a deterministic CPA secure.

Â So don't do that. We're actually gonna see secure deterministic CPA constructions in

Â the next segment. So I'll say one more time, if you need to encrypt the database

Â index in a consistent manner, don't use CBC with a fixed IV to do it. Use the

Â schemes that I'm gonna show you in the next segment. And so let me ask you the

Â same question about counter mode with a fixed IV. Is this gonna be a deterministic

Â CPA secure system or not? And here, I'm reminding you what counter mode with a

Â fixed IV is. Basically, we concatenate the fixed IV. Fixed IV plus one, Fixed IV plus

Â L. We encrypt all these counters. We concatenate the results, we encrypt the

Â message to get the cipher text. So if you think this is gonna be deterministic CPA

Â secure. So I hope everybody said no, because basically this is a onetime

Â padding encryption, and if we use this one time pad to encrypt distinct messages,

Â basically we'll be getting a two time pad. And to see more precisely, here I wrote

Â down the, deterministic CPA game. So, you notice what the attacker will do is he

Â would start off by asking for the encryption of the message m. So he would

Â get here the message m XOR the encryption of the fixed iv and then he's gonna ask

Â for some two distinct messages m0 and m1 that's different from m. So, m, m0 and m1

Â are a three are all three are distinct messages. And then what he'll get is the

Â encryption of mb and now he can simply mount the standard, kinda two time pad

Â attack. And if this equality here of c XOR c prime is equal to m XOR m zero, he

Â knows that c prime is the encryption of m zero. And otherwise he knows it's the

Â encryption of M1. So, again, he will completely win this game with advantage

Â equals to one. Okay, so again deterministic CPA with a fixed IV is also

Â completely insecure as a deterministic CPA cipher. So, don't use any of those

Â schemes, instead let's use the schemes I'm going to describe in the next segment.

Â