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.