0:00

Now that we understand what is deterministic encryption, let's see some

Â constructions that provide security against deterministic chosen plaintext

Â attacks. So, first let me remind you that the deterministic encryption is needed,

Â for example, when encrypting a data base index and later we wanna look up records

Â using the encrypted index. Because the encryption is deterministic we're

Â guaranteed that when we do the lookup the encrypted index is gonna be identical to the

Â encrypted index that was sent to the database when the record was written to

Â the database. And so, this deterministic encryption allows us a very simple or fast

Â way to do lookups based on encrypted indices. The problem was that we said the

Â deterministic encryption can't possibility be secure against a general chosen

Â plaintext attack because if the attacker sees two cipher texts that are equal

Â it learns that the underlying encrypted messages are the same. So, then we defined

Â this concept of deterministic chosen plain text security which means that we have

Â security as long as the encryptor never encrypts the same message more than once

Â using a given key. In particular, this key, message pair is only used once, for

Â every encryption, either the key changes, or the message changes. And then as I

Â said, formally we define this CPA, deterministic CPA security game, and our

Â goal in this segment is to actually give constructions that are deterministic CPA

Â secure. So the first construction we're gonna look at is what's called SIV,

Â synthetic IV's. And the way this construction works is as follows. Imagine

Â we have a general CPA secure encryption system. So here's the key and here's the

Â message and we are gonna denote by R the randomness that's used by the encryption

Â algorithm. Remember that a CPA secure system that doesn't use nonsense has to be

Â randomized and so we're explicitly gonna write down this variable R to denote the

Â random string that's used by the encryption algorithm as it's doing the

Â encryption. For example if we're using randomized counter mode, r would be the

Â random IV that's used by randomized counter mode. And of course C is the resulting

Â ciphertext. Now, in addition, we're also going to need a pseudo random function, f,

Â that what it does, is it takes our arbitrary messages in the message space

Â and outputs a strings, R, that can be used as randomness for the CPA secure

Â encryption scheme. So, the little, r, over here is actually a member of the big R set. Okay.

Â And we're going to assume this is a, f is a pseudo random function that maps messages

Â to random strings. Now the way SIV works is as follows. It's going to use two keys

Â K1 and K2 to encrypt the message M. And what it does, is the first thing is going

Â to apply the pseudo random function f to the message M to derive randomness for the

Â CPA secure encryption scheme E. And then it's going to encrypt the message M using

Â the randomness that it just derived. This is going to give us a cipher text C and

Â then it's going to output this cipher text C Okay. So that's how this SIV mode works.

Â Basically it first derives the randomness from the message being encrypted, and then

Â it uses this derived randomness to actually encrypt the message to obtain the

Â cipher text. Now I'd like to point out for example, if the encryption scheme E

Â happened to be randomized counter mode. Then the randomness R would just be the

Â random IV which would actually be output along with the cipher text. So this means

Â that the cipher text is a little bit longer than the plain text. But the point

Â here isn't to generate a short cipher text. Rather the point here is to make

Â sure that the encryption scheme is deterministic, so if we encrypt the same

Â message multiple times, every time we should obtain the same cipher text. And

Â indeed every time, we'll obtain the same randomness, R, and as a result, every time

Â we'll obtain the same cipher text C. So it's fairly easy to show that this

Â encryption scheme really is semantically secure under the deterministic chosen

Â plaintext attack. The reason that's so is because we apply the pseudo random

Â function F to distinct messages. Well if we apply F to distinct messages then the

Â random string that F generates is going to look like just truly random strings. A

Â different random string for every message. And as a result the CPA secure encryption

Â scheme E is always applied using truly random strings. And that's exactly the

Â situation where it is CPA secure. So because these R's are just random

Â indistinguishable from brand new strings, the resulting system is in fact gonna be

Â CPA secure. So this is just the intuition for why this works and it's actually

Â fairly straightforward to actually formalize this into a complete proof. Now,

Â I should emphasize that this is actually well suited for messages that are more

Â than one AES block. In fact, for short messages, we're gonna see a slightly

Â different encryption scheme that's actually better suited for these short

Â messages. Okay, now the really cool thing about SIV is that, actually, we get cipher

Â text integrity for free. In fact we don't have to use a special Mac if we want to

Â add integrity. In a sense SIV already has a built in integrity mechanism. And let me

Â explain what I mean by that. First of all, our goal was to build what's called

Â deterministic authenticated encryption. Dae. Deterministic Authenticated

Â Encryption. Which basically means that deterministic CPA security and cipher text

Â integrity. Remember cipher text integrity means that the attacker gets to ask for

Â the encryptions of messages of his choice and then he shouldn't be able to produce

Â another cipher text that decrypts to a valid message. Okay, so I want to claim

Â that in fact SIV automatically gives a cipher text integrity without the need for

Â an embedded MAC or anything else. So let's see why. In particular, let's look at a

Â special case of SIV when the underlying encryption scheme is randomized counter

Â mode. Okay, so we'll call this SIV-CTR again to denote SIV where we're using

Â randomized counter mode. Alright. So let me remind you again how SIV works in this

Â case. Well, so we take our message, here, we take our message, and then we apply a

Â PRF to it. And that derives an IV. And then that IV is going to be used to

Â encrypt the message using randomized counter mode. Okay. So in particular,

Â we're gonna use this PRF FTCRr for F counter, for randomized counter mode and

Â essentially evaluate this FCTR at Iv, IV plus one up to IV plus L. And, then, we

Â had sorta that with the message. And that gives us the final ciphertext. Okay. So,

Â this is SIV with a randomized counter mode. Now, let's see how decryption is

Â gonna work. And during decryption we're gonna add one more check, and that's

Â going to provide ciphertext integrity. So let's see how decryption is going to work. So here

Â we have our input cipher text that contains the IV and the cipher text. Well,

Â the first thing we're going to do is we're going to decrypt the cipher text using the

Â given IV, and that will give us candidate plain text. Now we're gonna reapply the

Â PRF F from the definition of SIV to this message. Now if a message is valid, we

Â should be getting the same IV that the [adversary??] supplied as part of the cipher

Â text. If we get a different IV, then we know that this message is not a valid

Â message and we simply reject the cipher text. So this is really cute. It's a very

Â simple kinda built in check to make sure that the cipher text is valid, right. We

Â simply check that after decryption if we re-derive the IV we would actually get

Â the correct IV. And if not we reject the message. And I claim that this simple check

Â during decryption is enough to [actually??] provide ciphertext integrity. And therefore,

Â deterministic authenticated encryption. So I'll state this in a simple theorem.

Â Basically to say, that if F is a secure PRF, and in counter mode that's derived

Â from FCTR is CPA secure, then the result is in fact a deterministic authenticated

Â encryption system. Now the proof for this is not too difficult. In two sentences,

Â let me just show you the rough intuition for why this is true. So, all we have to

Â argue is just cipher text integrity. So we already argued before that the system has

Â deterministic CPA security, all we have to argue is just cipher text integrity. So to

Â argue that the system has cipher text integrity, let's think again how the

Â cipher text integrity game works. Adversary asks for the encryption of a

Â bunch of messages of his choice. And he gets the resulting cipher text. Then, his

Â goal is to produce a new valid cipher text. Well, if that valid cipher text upon

Â decryption, decrypts to some completely new message. Then when we plug this new

Â message into the PRF F, we're just going to get some random IV and it's very unlikely

Â to hit the IV that the adversary supplied in the cipher text that he output. So

Â therefore that says that when the advisory outputs his forged cipher text, the

Â message in that forged cipher text basically should be equal to one of the

Â messages in his chosen message queries. Otherwise, again the IV that you get is

Â simply not gonna be equal to the IV in the forged safe index with very high

Â probability. But if the message is equal to one of the messages that the adversary

Â queried us on, well then, the cipher text that we're gonna get is also gonna be

Â equal to one of the cipher texts that we supplied to the adversary. But then his

Â forgery is simply one of the cipher texts that we gave to him. And therefore, this

Â is not a valid forgery. He has to give us a new cipher text to win the cipher text

Â integrity game. But he gave us one of our old cipher texts. So, this is the rough

Â intuition. I hope, I kinda went through it quickly. I hope it kinda makes sense. If

Â it doesn't then it's not the end of the world. I'm gonna reference the paper that

Â describes SIV at the end of the module. And if you wanna see this in more detail

Â you can read and take a look inside of that paper. But, regardless, this is a

Â very cute idea that I wanted to show you where kinda the fact that we derive the

Â randomness for deterministic counter mode using a PRF. Also, gives us an integrity

Â check when we actually do the decryption. Okay. So this SIV is a good mode for doing

Â deterministic encryption when you need to, particularly if the messages are long. If

Â the messages are very short, say they're less than sixteen bytes, in fact there's a

Â better way to do it, and that's the method that I wanna show you now. So the second

Â construction is actually trivial. All we're gonna do is we're gonna use a PRP

Â directly. So here's what we do. So suppose (E, D) is a secure PRP. So E will encrypt, and

Â D will decrypt. And I claim that if we use E directly, that already gives us

Â deterministic CPA security. So let me show you very quickly why. So suppose F is a truly random invertible function from X

Â to X. Okay. So remember a PRP is indistinguishable from a truly random

Â invertible function, so let's pretend that we actually do have a truly random

Â invertible function. Now in experiment zero what the attacker is gonna see while

Â he submits a bunch of messages, you know the messages on the left. And what he's

Â gonna see is basically the evaluation of f on the messages on the left that he

Â supplied. Well, in the deterministic CPA game, all these messages are distinct, and

Â so all he's gonna get back are just q distinct random values in X. That's all he

Â sees. Yes, there's Q distinct random values in X. Now let's think about

Â experiment one. In experiment one, he gets to see the encryptions of messages on the

Â right, okay, the M11 to MQ1. Well, again, all these messages are all distinct so all

Â he gets to see are just Q random distinct values in X. Well these two distributions,

Â in experiment zero and experiment one, therefore are identical. Basically, in

Â both cases what he gets to see are just Q distinct random values in X. And as a

Â result, he can't distinguish experiment zero from experiment one. And since he

Â can't do this for a truly random function, he also can't do this for the PRP. Ok,

Â so that explains why directly encrypting with a PRP already gives us a CPA secure

Â system very, very, very simple to use. That says that if all we wanna do is

Â encrypt short messages, say, less than sixteen bytes, then all we need to do is

Â to directly encrypt them using AES and the result will, in fact, be deterministic CPA

Â secure. So, if your indices are less than sixteen bytes directly using AES is a fine

Â thing to do. Notice however, that's not gonna provide any integrity. And we're

Â gonna see how to add integrity in just a minute. But the question for you is, what

Â do we do if we have longer than sixteen byte messages? Well, one option is to use

Â SIV. But what if we actually wanted to use this construction too. It's actually an

Â interesting question. Can we construct PRP's that have message spaces that are

Â bigger than just sixteen bytes? If you remember in the past we constructed PRFs

Â on that had large message spaces from PRFs that had small message spaces. Here,

Â we're going to construct PRPs with large message spaces from PRFs that have small

Â message spaces. So, here's how we do it. So suppose E D is a secure PRP that

Â operates on N bit blocks. There's a standard mode called EME that actually

Â will construct a PRP that operates on capital N bit blocks, where capital N is

Â much, much bigger than little n. So this would allow us to do deterministic

Â encryption on much larger messages than just sixteen bytes. In fact it could be as

Â long as we want. So let's see how EME works. It's a bit daunting at first but

Â it's not a difficult construction. So, let's see how it works. So, EME uses two

Â keys, K and L, and in fact in the real EME L is derived from K. But for our purposes,

Â let's just pretend that K and L are two distinct keys. The first thing we do, is

Â we take our message X and we break it up into blocks. And then we XOR each block

Â with a certain padding function, okay? So we use the secret key L to derive a pad

Â using this, you know function P that I'm not gonna explain here. We derive a

Â different pad for each one of the blocks and we XOR that pad. Into the block. The

Â next thing we do is we apply the PRP E using the Key K, to each of these blocks,

Â and we're gonna call these outputs PP0, PP1, and PP2. The next thing we do is we

Â XOR all these ppp's together and we call the result MP. Actually this XOR

Â doesn't need to be there. We call the result of the XOR MP. The next thing we

Â do we XOR all these ppp's together and we call the result MP. We encrypt this MP

Â using E and the key K. We call the outputs of this encryption MC. Okay. So then we use

Â the XOR MP and MC and this gives us another PM, which we use to derive one

Â more pad, and then we XOR this output of this pad with all the PPP's to get

Â these CCC's, [laugh], and then we XOR all these C C C's together that gives us

Â a value of C C C zero, which we then encrypt one more time with all these E's,

Â we do one more padding with all these P's and that actually finally gives us the

Â output of EME. Okay, so like I said, this may look a little daunting, but in

Â fact there's a theorem that shows that if the underlying block cipher E is a secure

Â PRP, then in fact. This construction, EME, is a secure PRP on this larger block, you

Â know, zero, one to the capital N. The nice thing about this construction is you

Â notice that it's very parallel and actually that's why it's a little

Â complicated. Counted every block. It's encrypted in parallel, so if you have a

Â multi-core processor, you can use all your cores to encrypt all the blocks at the

Â same time and then there would be one kind of sequential step to compute this, check

Â sum of, all the outputs and then one more parallel around to encrypt one more time

Â and then finally you get the outputs. These function Ps, by the way, that

Â generate the pads, are very, very simple functions. They take constant time so

Â we're just going to ignore them in terms of performance. So the bottom line is

Â performance here. You notice it requires two applications of E per input block. And

Â it turns out this can actually be slower than SIV, if SIV is implemented properly

Â with a very fast PRF to derive the randomness. Then in fact SIV can be twice

Â as fast, as this particular mode of operation. For this reason I say that the

Â PRP construction is very good for short messages, whereas SIV is good if you h, if

Â you want to encrypt longer messages in a deterministic fashion. But now what if we

Â wanted to add integrity to this PRP-based mechanism? So, can we achieve

Â deterministic authenticated encryption using the PRP mechanism where we directly

Â encrypt the message using a PRP? And it turns out the answer is yes and it's

Â actually again, a very simple encryption scheme that you should know

Â about. Basically what we're going to do is we're going to take our message and we're

Â going to append a bunch of zeros to this message and then we're going to apply the

Â PRP and that's it. And that's going to give us the cipher text. Now, very, very

Â simple. Just append zeros and encrypt using a PRP. When we decrypt, we're going

Â to look at these least significant bits of the resulting plain text and if they're

Â not equal to zero, we're just going to reject the cipher text. And if they are

Â equal to zero, we're going to output the message as valid. Okay, so that's it,

Â that's the whole system, very, very simple. Simply append zeroes during

Â encryption, and then check that the zeroes are there when you decrypt. And I claim

Â that this very simple mechanism actually provides deterministic authenticated

Â encryption, assuming, of course, that you've appended enough zeroes. And in

Â particular, if you append N zeroes, you need one over two to the N to be

Â negligible. And if so, then, in fact, this direct PRP based encryption, in fact,

Â provides deterministic authenticated encryption. So let me see why. Well, we

Â already argued that the system is CPA secure, so all we have to argue is that it

Â provides cipher text integrity. And again, that's easy to see. Let's look at the

Â cipher text game. So the adversary is gonna choose let's say a truly random

Â permutation. So a truly random, invertible function, on the input space. In this case

Â the input space is the message space and the N zero bits. Now what does the

Â adversary get to do? Well he gets to submit q messages, and then he receives

Â the encryption of those Q messages. Mainly he receives the PRP at his chosen points

Â concatenated with N zeros. Okay, that's what it basically it means to query the

Â CPA challenger. So in case of a random permutation, he simply gets to see, the

Â value of this permutation at Q points of his choice, but only concatenated with N

Â zeroes. And now, what's his goal in the cipher text integrity game? Well, his goal

Â is to produce some new cipher text that's different from the cipher text that he was

Â given, that's gonna decrypt properly. Well, what does it mean that it decrypts

Â properly? It means that if, when we apply, Pi inverse To the cipher text C, it had

Â better be the case that the N least significant bytes of C are all zeros. And

Â the question is how likely is that to happen? Well, so let's think about this.

Â So basically we have a truly random permutation and the adversary got to see

Â the value of this permutation as Q points. How likely is he to produce a new point

Â that, when inverted, happens to have N zeroes as the least significant bits? What we're

Â doing here is basically we're evaluating the permutation Pi inverse at the point c.

Â And since Pi inverse is a random permutation, how likely is it to have its

Â n least significant bits be equal to zero? So it isn't hard to see that the answer

Â is, is, at most, the probability's at most, one over two to the N. Because,

Â again, basically, the permutation is gonna output a random element inside of, X times

Â 0 1 to the N. And that element is gonna end with N zeroes, but basically

Â with the probability one over two to the N. And as a result, the adversary wins the

Â game with negligible probability, Because, this value is negligible. So that's the

Â end of this segment. I wanted you to see these two very cute deterministic

Â authenticated encryption schemes. The first one we called SIV, where I said you

Â would use randomized counter mode and you just arrived at randomness for randomized

Â counter mode from a PRF applied to the message. And the very cute idea here is

Â that during decryption you can simply recompute the IV from the, from the decrypted

Â message and verify that that IV is what's given to you in the cipher text. And that

Â simple check is actually enough to guarantee authenticated encryption or

Â rather deterministic authenticated encryption. So this mode is, is the way

Â you would encrypt an index in a database if the index was large. If the index

Â happens to be short, maybe say, its eight bytes if it's an 8-byte user ID, then you

Â can directly use a PRP and the way you would do is, is you would append zeros to

Â those eight bytes. And then those zeros will be used as an integrity check when

Â you decrypt and again if you append, are able to append enough zeros, then in fact

Â this also provides deterministic authenticated encryption. As an aside, I

Â showed you that there's a way to build the wide block PRP from a narrow PRP and that

Â particular mode of operation is called EME. So we're gonna refer EME

Â actually in the next segment.

Â