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.
