0:48

that comes to mind when you want to use a block cipher for encryption. What we do is

Â we take our message, we break it into blocks, each block as big as the block's

Â cipher block. So in the case of AES, we would be breaking our message into sixteen

Â byte blocks. And then we encrypt each block separately. So this mode is often

Â called electronic codebook. And, unfortunately, it's terribly insecure

Â because you realize if two blocks are equal, for example here, these two blocks

Â happen to be equal, then necessarily the resulting ciphertext is also going to be equal.

Â So an attacker who looks at the ciphertext, even though he might not know

Â what's actually written in these blocks, we'll know that these two blocks are

Â equal. And as a result, he learned something about the plaintext that he

Â shouldn't have learned. And if this isn't clear enough for you abstractly, the best

Â to explain this is using a picture. And so here's this guy here that, you know, has

Â this really dark black hair. And when we encrypt. This image, this bitmap image

Â using the electronic code book mode. You see that his hair, that contains lots of

Â ones. Basically always gets encrypted the same way, so that his silhouette,

Â actually, is completely visible, even in the encrypted data. Okay, so this is a

Â nice example of how the electronic code book mode can actually leak information

Â about the plaintext that could tell something to the attacker. So the question

Â is, how to correctly use block ciphers to encrypt long messages. And so, I just

Â want to briefly remind you of the notion we're trying to achieve, which is

Â basically semantic security using a one time key. So the adversary outputs two

Â messages, m0 and m1, and then he gets either the encryption of m0 or the

Â encryption of m1, these are two different experiments. And then our goal is to say

Â that the adversary can't distinguish between these two experiments. So you

Â can't distinguish the encryption of m0 from the encryption of m1. And the reason

Â we call this security for a one time key is that the key is only used to encrypt a

Â single message. And as a result, the adversary will ever only see one ciphertext

Â encrypted using this key. Okay, so the first thing we want to show is that in

Â fact the mode we just looked at, electronic code book, in fact, is not

Â semantically secure. And this is true as long as you're encrypting more than one

Â block. So here's an example. Suppose we encrypt two blocks using a block cipher.

Â Let me show you that in fact electronic code book will not be secure. So here's

Â what we would do. So we're the adversary. So we would output two messages, m0 and

Â m1, where, in one message, the blocks are distinct, and in the other message, the

Â blocks are the same. The two blocks are equal to one another. Well, so what is the

Â challenger gonna do? The challenger's going to encrypt either m0 or m1.

Â Either way we are gonna get two blocks back. So the ciphertext actually contains two

Â blocks. The first block is going to be an encryption of the word "Hello" and the

Â second block is gonna be either an encryption of the word "Hello" or the word

Â "World". And if the two ciphertext blocks are the same then the adversary knows that

Â he received an encryption of the message "Hello Hello" and as a difference he knows

Â that he received encryption of the message "Hello World". Okay? So, he just

Â follows a simple strategy here. And if you think about it for a second, you'll see

Â what his advantage is. So, what is the advantage? Well, this adversary when he

Â received an encryption of the message m1 he will always output 0.

Â and when he receives an encryption of the message m0 it will always output 1.

Â And because of that the advantage, basically, is 1, which means that the

Â scheme is not secure, which again shows you the electronic code book is not

Â semantically secure and should never ever be used to encrypt messages that are more

Â than one block long. So, what should we do? Well, so here's a simple example. What

Â we could do is we could use what's called a deterministic counter mode. So in a

Â deterministic counter mode, basically we build a stream cipher out of the block

Â cipher. So suppose we have a PRF, F. So again you should think of AES when I say

Â that. So AES is also a secure PRF. And what we'll do is, basically, we'll evaluate

Â AES at the point zero, at the point one, at the point two, up to the point L. This

Â will generate a pseudo random pad. And I will XOR that with all the message

Â blocks and recover the ciphertext as a result. Okay, so really this is just a

Â stream cipher that's built out of a PRF, like AES and triple DES, and it's a simple

Â way to do encryption. I wanted to just very quickly show you the security

Â theorem. In fact, we've already seen the security theorem when it applied to stream

Â ciphers using pseudo-random generators, so I'm not going to repeat this again. I'll

Â just remind you that essentially for every adversary A that's trying to attack

Â deterministic counter mode, we prove that there's an adversary B that's trying to

Â attack the PRF. And since this quantity is negligible, because the PRF is secure, we

Â obtain that this quantity is negligible. And therefore, the adversary has

Â negligible advantage in defeating deterministic counter mode. And the

Â proof in pictures is a really simple proof. So I'll just show it to you one

Â more time for completeness. So basically, what we want to show is, when the

Â adversary's given the encryption of the message m0, here, this is the encryption

Â of the message, m0. m0 XOR counter applied to the PRF, versus in giving the

Â encryption of the message, m1. We wanna argue these two distributions are

Â computationally indistinguishable. So the way we do that is basically we say, well

Â the top distribution, if instead of a PRF, we use a truly random function, namely

Â here f is a truly random function, then the adversary, because of the property of

Â the PRF, the adversary cannot distinguish these two experiments, right. A PRF is

Â indistinguishable from a truly random function, therefore when we replace the PRF

Â on the left with a truly random function on the right, the adversary is going to

Â behave the same. Basically you can't distinguish these two distributions. But

Â now because F is a truly random function, the pad here is a truly one time pad, and

Â therefore no adversary can distinguish an encryption of m0 from an encryption of m1

Â under the one time pad. So, again, these two distributions are the same. In fact,

Â here there's an actual equality. These two distributions literally are the same

Â distribution. And similarly again when we go back from a truly random function here

Â to a PRF, because the PRF is secure, the adversary can't distinguish these two

Â bottom distributions, the left from the right. And so by following these three

Â equalities, basically we have proven that the things we wanted to prove equal are

Â actually computationally indistinguishable. Okay, so that's a very

Â simply proof to show that deterministic counter mode is in fact secure and it's

Â basically the same proof as we had when we proved that a stream cipher gives us

Â semantic security. Okay. So that completes this segment and in the next segment we'll

Â talk about modes that enable us to use a key to encrypt multiple messages.

Â