0:00:00.000,0:00:04.152
Now that we understand chosen plaintext[br]security, let's build encryption schemes

0:00:04.152,0:00:08.515
that are chosen plaintext secure. And the[br]first such encryption scheme is going to

0:00:08.515,0:00:12.510
be called cipher bock chaining. So here[br]is how cipher block chaining works.

0:00:12.510,0:00:16.610
Cipher block chaining is a way of using a[br]block cipher to get chosen plaintext

0:00:16.610,0:00:20.868
security. In particular, we are going to[br]look at a mode called cipher block chaining

0:00:20.868,0:00:25.021
with a random IV. CBC stands for cipher[br]block chaning. So suppose we have a block

0:00:25.021,0:00:28.963
cipher, so EB is a block cipher. So now[br]let's define CBC to be the following

0:00:28.963,0:00:33.248
encryption scheme. So the encryption[br]algorithm when it's asked to encrypt a

0:00:33.248,0:00:37.991
message m, the first thing it's going to do[br]is it's going to choose a random IV that's

0:00:37.991,0:00:41.958
exactly one block of the block[br]cipher. So IV is one cypher block.

0:00:41.958,0:00:46.035
So in the case of AES the IV[br]would be 16 bytes. And then we're

0:00:46.035,0:00:50.649
gonna run through the algorithm here, the[br]IV basically that we chose is gonna be XORed

0:00:50.649,0:00:54.726
to the first plain text[br]block. And then the result is gonna be

0:00:54.726,0:00:58.857
encrypted using the block cipher and[br]output of the first block of the ciphertext.

0:00:58.857,0:01:03.041
And now comes the chaining part[br]where we actually use the first block of

0:01:03.041,0:01:07.436
the ciphertext to kind of mask the second[br]block of the plaintext. So we XOR

0:01:07.436,0:01:11.588
the two together and the encryption of[br]that becomes the second ciphertext block.

0:01:11.588,0:01:15.535
And so on, and so on, and so forth. So[br]this is cIpher block chaining, you can

0:01:17.559,0:01:19.584
see that each cIpher block is chained and[br]XORed into the next plaintext

0:01:19.584,0:01:24.118
block, and the final ciphertext is going to[br]be essentially the IV, the initial IV

0:01:24.118,0:01:30.024
that we chose along with all the ciphertext blocks. I should say that IV stands

0:01:30.024,0:01:35.795
for Initialization Vector. And we're going to[br]be seeing that term used quite a bit,

0:01:35.795,0:01:39.717
every time we need to pick something at[br]random at the beginning of the encryption

0:01:39.717,0:01:43.543
scheme typically we'll call that an IV[br]for initialization vector. So you notice

0:01:43.543,0:01:47.322
that the cIphertext is a little bit[br]longer than the plain text because we had

0:01:47.322,0:01:51.149
to include this IV in the cIphertexts[br]which basically captures the randomness

0:01:51.149,0:01:55.450
that was used during encryption. So the[br]first question is how do we decrypt the

0:01:55.450,0:02:00.226
results of CBC encryption, and so[br]let me remind you again that if when we

0:02:00.226,0:02:04.470
encrypt the first message block we[br]XOR it with the IV, encrypt the

0:02:04.470,0:02:09.187
result and that becomes the first ciphertext[br]block. So let me ask you how would

0:02:09.187,0:02:13.667
you decrypt that? So given the first[br]ciphertext block, how would you recover

0:02:13.667,0:02:17.915
the original first plaintext block? So[br]decryption is actually very similar to

0:02:17.915,0:02:21.660
encryption, here I wrote down the[br]decryption circuit, you can see basically

0:02:21.660,0:02:25.961
it's almost the same thing except the XOR[br]is on the bottom, instead of on the top, and

0:02:25.961,0:02:29.605
again you realize that essentially we[br]chopped off the IV as part of the

0:02:29.605,0:02:33.754
decryption process and we only output the[br]original message back, the IV is dropped

0:02:33.754,0:02:38.438
by the decryption algorithm. Okay, so the[br]following theorem is going to show that in

0:02:38.438,0:02:43.762
fact CBC mode encryption with a random IV[br]is in fact semantically secure under a

0:02:43.762,0:02:48.956
chosen plaintext attack, and so let's[br]take that more precisely, basically if we

0:02:48.956,0:02:54.083
start with a PRP, in other words, our[br]block cipher E, that is defined over a

0:02:54.083,0:02:59.079
space X, then we are gonna to end up with[br]a encryption algorithm Ecbc that takes

0:02:59.079,0:03:03.944
messages of length L and outputs[br]ciphertexts of length L+1. And then

0:03:03.944,0:03:09.324
suppose we have an adversary that makes q[br]chosen plaintext queries. Then we can

0:03:09.324,0:03:15.024
state the following security fact, that[br]for every such adversary that's attacking

0:03:15.024,0:03:20.184
Ecbc, to exist an adversary that's[br]attacking the PRP, the block cipher, with

0:03:20.184,0:03:24.926
the following relation between the two[br]algorithms, in other words, the advantage

0:03:24.926,0:03:29.851
of algorithm A against the encryption scheme[br]is less than the advantage of algorithm B

0:03:29.851,0:03:35.080
against the original PRP plus some noise[br]term. So let me interpret this theorem for

0:03:35.080,0:03:40.005
you as usual, so what this means is that[br]essentially since E is a secure PRP this

0:03:40.005,0:03:45.051
quantity here is negligible, and our goal[br]is to say that adversary A's advantage is

0:03:45.051,0:03:49.794
also negligible. However, here we are[br]prevented from saying that because we got

0:03:49.794,0:03:54.630
this extra error term. This is often[br]called an error term and to argue that CBC

0:03:54.630,0:03:59.676
is secure we have to make sure that the[br]error term is also negligible. Because if

0:03:59.676,0:04:04.474
both of these terms on the right are[br]negligible, there sum is negligible and

0:04:04.474,0:04:09.458
therefore the advantage of A against Ecbc[br]would also be negligible. So this says

0:04:09.458,0:04:14.565
that in fact for Ecbc to be secure it has better[br]be the case that q squared L squared Is

0:04:14.565,0:04:19.564
much, much, much smaller than the value X,[br]so let me remind you what q and L are, so

0:04:19.564,0:04:24.566
L is simply the length of the messages[br]that we're encrypting. Okay, so L could be

0:04:24.566,0:04:29.902
like say a 1000, which means that we are[br]encrypting messages that are at most 1000

0:04:29.902,0:04:35.303
AES blocks. q is the number of ciphertexts[br]that the adversary gets to see under the

0:04:35.303,0:04:40.770
CPA attack, but in real life what q is, is[br]basically the number of times that we have

0:04:40.770,0:04:46.041
used the key K to encrypt messages, in other[br]words if we use a particular AES key to

0:04:46.041,0:04:51.052
encrypt 100 messages, Q would be 100.[br]It is because the adversary would then see

0:04:51.052,0:04:56.224
at most 100 messages encrypted under this key K. Okay[br]so lets see what this means in the real

0:04:56.224,0:05:00.866
world. So here I've rewrote the error[br]balance from the theorem. And just to remind

0:05:00.866,0:05:05.093
you to use the messages encrypted with K[br]and L with the lengths of the messages and so

0:05:05.093,0:05:09.370
suppose we want the adversary's advantage[br]to be less than one over two to the thirty

0:05:09.370,0:05:13.346
two. This means that the error term had[br]better be less than one over two to the

0:05:13.346,0:05:17.853
thirty two. Okay, so let's look at AES and see[br]what this mean. For AES, AES of course uses

0:05:17.853,0:05:22.300
128 bit blocks, so X is going to be two[br]to the 128, the

0:05:22.300,0:05:26.363
size of X is going to be 2 to the[br]128, and if you

0:05:26.363,0:05:30.865
plug this into the expression you see that[br]basically the product q times L had

0:05:30.865,0:05:35.477
better be less than two to the forty eight.[br]This means that after we use a particular

0:05:35.477,0:05:40.014
key to encrypt 2 to the 48 AES[br]blocks we have to change the key. Okay, so

0:05:40.014,0:05:46.966
essentially CBC stops being secure after[br]the key is used to encrypt 2 to the 48 different AES blocks.

0:05:46.966,0:05:49.572
So its[br]kinda nice that the security theorem tells

0:05:49.572,0:05:54.499
you exactly how long the key can be used[br]and then how frequently, essentially, you have to

0:05:54.499,0:05:59.575
replace the key. Now interestingly if you[br]apply the same analogy to the 3DES it

0:05:59.575,0:06:04.909
actually has a much shorter block, maybe[br]only 64 bits, you see the key has to be

0:06:04.909,0:06:10.485
changed much more frequently, maybe after every[br]65 thousand DES blocks, essentially you need to generate a new key. So

0:06:10.485,0:06:15.275
this is one of the reasons why AES has a[br]larger block size so that in fact modes

0:06:15.275,0:06:20.240
like CBC would be more secure and one can[br]use the keys for a longer period of time, before having

0:06:20.240,0:06:24.796
to replace it. What this means is having[br]to replace two to the sixteen blocks,

0:06:24.796,0:06:29.586
each block of course is 8 bytes, so[br]after you encrypt about half a megabyte of

0:06:29.586,0:06:33.868
data you would have to change the DES key[br]which is actually quite low. And you

0:06:33.868,0:06:37.645
notice with AES you can encrypt quite a[br]bit more data before you have to change the

0:06:37.645,0:06:42.604
key. So I want to warn you about a very[br]common mistake that people have made when

0:06:42.604,0:06:47.627
using CBC with a random IV. That is that[br]the minute that the attacker can predict

0:06:47.627,0:06:52.712
the IV that you're going to be using for[br]encrypting a particular message decipher

0:06:52.712,0:06:57.797
this Ecbc is no longer CPA secure. So when[br]using CBC with a random IV like we've

0:06:57.797,0:07:02.246
just shown It's crucial that the IV is not[br]predictable. But lets see an attack. So

0:07:02.246,0:07:06.282
suppose it so happens that given a[br]particular encryption in a message that

0:07:06.282,0:07:10.695
attacker can actually predict that IV that[br]will be used for the next message. Well

0:07:10.695,0:07:14.839
let's show that in fact the resulting[br]system is not CPA secure. So the first thing the

0:07:14.839,0:07:19.197
adversary is going to do is, he is going[br]to ask for the encryption of a one block

0:07:19.197,0:07:23.449
message. In particular that one block is[br]going to be zero. So what the adversary

0:07:23.449,0:07:27.592
gets back is the encryption of one[br]block, which namely is the encryption of

0:07:27.592,0:07:31.748
the message namely zero, XOR the IV. Okay[br]and of course the adversary also gets the

0:07:31.748,0:07:35.877
IV. Okay so now the adversary by[br]assumption can predict the IV that's gonna

0:07:35.877,0:07:40.196
be used for the next encryption. Okay so[br]let's say that IV is called, well IV. So

0:07:40.196,0:07:44.460
next the adversary is going to issue his[br]semantic security challenge and the

0:07:44.460,0:07:49.167
message m0 is going to be the predicted IV[br]XOR IV1 which was used in the encryption

0:07:49.167,0:07:53.707
of c1. And the, the message of m1 is just[br]going to be some other message, it doesn't

0:07:53.707,0:07:58.248
really matter what it is. So now let's see[br]what happens when the adversary receives

0:07:58.248,0:08:02.346
the result of the semantic security[br]challenge. Well, he is going to get the

0:08:02.346,0:08:06.470
encryption of m0 or m1. So when the[br]adversary receives the encryption of m0,

0:08:06.470,0:08:10.800
tell me what is the actual plain text[br]that is encrypted in the ciphertext c?

0:08:11.260,0:08:17.368
Well so the answer is that what is[br]actually encrypted is the message which is

0:08:17.368,0:08:22.826
IV XOR IV1 XOR the IV that's used to[br]encrypt that message which happens to be

0:08:22.826,0:08:28.301
IV and this of course is IV1. So when the[br]adversary receives the encryption of m0,

0:08:28.301,0:08:33.167
he is actually receiving the block cipher[br]encryption of IV1. And lo and behold,

0:08:33.167,0:08:38.440
you'll notice that he already has that[br]value from his chosen plaintext query.

0:08:38.440,0:08:42.800
And then, when he is receiving the[br]encryption of message m1, he just received

0:08:42.800,0:08:47.825
a normal CBC encryption of the message m1.[br]So you realize that now he has a simple

0:08:47.825,0:08:53.057
way of breaking the scheme, namely what[br]he'll do is he'll say, he's gonna ask, "Is the second

0:08:53.057,0:08:58.354
block of the ciphertext c equal to the[br]value that I received in my CPA query?" If

0:08:58.354,0:09:03.843
so I'll say that I received the encryption[br]of m0, otherwise I'll say that I received

0:09:03.843,0:09:09.209
the encryption of m1. So really his test[br]is c1 he refers to the second block

0:09:09.209,0:09:14.441
of c and c11 refers to the second block of[br]c1, if the two are equal he says zero,

0:09:14.441,0:09:20.095
otherwise he says one. So the advantage of[br]this adversary is going to be 1 and as a

0:09:20.095,0:09:25.650
result, he completely breaks CPA security[br]of this CBC encryption. So the lesson here

0:09:25.650,0:09:30.334
is, if the IV is predictable then, in[br]fact, there is no CPA security and

0:09:30.334,0:09:35.621
unfortunately, this is actually a very[br]common mistake in practice. In particular

0:09:35.621,0:09:41.339
even in SSL protocol and in TLS 1.1, it turns[br]out that IV for record number I is in fact

0:09:41.339,0:09:46.363
the last ciphertext block of record I-1. That means that exactly given

0:09:46.363,0:09:51.579
the encryption of record I-1, the[br]adversary knows exactly what IV is going

0:09:51.579,0:09:56.031
to be used as record number I. Very[br]recently, just last summer, this was

0:09:56.031,0:10:00.737
actually converted into a pretty[br]devastating attack on SSL. We'll describe

0:10:00.737,0:10:06.016
that attack once we talk about SSL in more[br]detail, but for now I wanted to make sure

0:10:06.016,0:10:12.371
you understand than when you use CBC encryption,[br]its absolutely crucial that the IV be random.

0:10:12.371,0:10:16.372
Okay, so now I going to show you the nonce based version of CBC encryption

0:10:16.372,0:10:21.443
So in this mode the IV is replaced by non random but unique nonce

0:10:21.443,0:10:23.928
for example the numbers 1,2,3,4,5, could all be used as a nonce, and now, the appeal of this mode

0:10:23.928,0:10:25.246
is that if the recipient actually knows[br]what the nonce is supposed to be

0:10:25.246,0:10:25.880
then there's no reason to include the nonce[br]in the ciphertext, in which case, the ciphertext

0:10:25.880,0:10:26.197
is exactly the same length as the plaintext,[br]unlike CBC with the random IV,

0:10:26.197,0:10:26.276
where we had to expand the ciphertext to include the IV, here, if the nonce is already known to the recipient,

0:10:26.276,0:10:26.315
there's no reason to include it in the ciphertext, and[br]the ciphertext is exactly the same length as the plaintext.

0:10:26.315,0:10:26.335
So it's perfectly fine to use a non-random but unique nonce. However, it's absolutely crucial to know that,

0:10:26.335,0:10:26.345
if you do this, there's one more step that you have[br]to do before you use the nonce in the CBC chain.

0:10:26.345,0:10:26.355
In particular, in this mode now we're going to[br]be using two independent keys, k and k1.

0:10:26.355,0:10:26.434
The key k is, as before, going to be used to[br]encrypt the individual message blocks,

0:10:26.434,0:10:26.474
However, this key k1 is going to be used to[br]encrypt the non-random but unique nonce,

0:10:26.474,0:10:26.494
so that the output is going to be a random IV,[br]which is then used in the CBC chain.

0:10:26.494,0:10:26.504
So this extra step here, encrypting the nonce[br]with the key k1, is absolutely crucial.

0:10:26.504,0:10:26.509
Without it, CBC mode encryption would not be secure.

0:10:26.509,0:10:26.514
[br]However it if is going to be a counter you

0:10:26.514,0:10:32.046
need to do one more step. Before actually[br]encryption CBC and in particular you have

0:10:32.046,0:10:37.380
to actually encrypt the notes to obtain[br]the IV that will actually be used for

0:10:37.380,0:10:42.919
encryption. The notes on CBC is similar to[br]a random IV, the difference is that the

0:10:42.919,0:10:48.047
notes is first encrypted and the results[br]is that the IV is used in the CBC

0:10:48.047,0:10:52.728
encryption Now the beauty of this mode is[br]that the Nance doesn't necessarily have to

0:10:52.728,0:10:56.975
be included in the cipher text. It only[br]needs to be in there if its unknowns are

0:10:56.975,0:11:01.116
the decrypter but it if the decrypter[br]happens to already know the value of the

0:11:01.116,0:11:05.310
counter by some other means then in fact[br]the cipher text is only as big as the

0:11:05.310,0:11:09.291
plain text. There's no extra value[br]transmitted in the cipher text. And again,

0:11:09.291,0:11:13.591
I warn that when you're using non spaced[br]encryption, it's absolutely crucial that

0:11:13.591,0:11:17.679
the key common Nance spare is only used[br]for one message so for every message,

0:11:17.679,0:11:22.028
either the Nance has changed or the key[br]has changed. Okay, so here emphasize the

0:11:22.028,0:11:26.499
fact that you need to do this extra[br]encryption step before actual using the

0:11:26.499,0:11:31.088
Nance. This is very common mistake that[br]actually forgotten in practice and for

0:11:31.088,0:11:35.795
example in TLS, this was not done and as a[br]result there was a significant attack

0:11:35.795,0:11:40.282
against CBC encryption in TLS. Remember[br]the reason that this is so important to

0:11:40.282,0:11:44.950
know is that in fact many crypto APIs are[br]set up to almost deliberately mislead the

0:11:44.950,0:11:49.451
user to using CBC incorrectly. So let's[br]look to see how CBC implemented inside of

0:11:49.451,0:11:53.840
open SSL. So here are the arguments of the[br]function. Basically this is the plain

0:11:53.840,0:11:58.119
text, this is the place where the cipher[br]text will get written to. This is the

0:11:58.119,0:12:02.760
length of the plain text. This is a, a Yes[br]key Finally there is an argument here that

0:12:02.760,0:12:06.438
says whether you are crypting or[br]decrypting. And the most important

0:12:06.438,0:12:10.884
parameter that I wanted to point out here[br]is the actual IV and unfortunately, the

0:12:10.884,0:12:15.330
user is asked to supply this IV and the[br]function uses the IV directly in the CBC

0:12:15.330,0:12:19.831
encryption mechanism. It doesn't encrypt[br]the IV before using it and as a result, if

0:12:19.831,0:12:24.332
you ever call this function using a non[br]random IV, the resulting encryption system

0:12:24.332,0:12:28.816
won't be CPA secure. Okay, so it's very[br]important to know that when calling

0:12:28.816,0:12:33.960
functions like this. Cbc encryption or[br]open SSL either supply a truly random IV

0:12:33.960,0:12:38.836
or if you want the IV to be a counter than[br]you have to encrypt a counter using AAS

0:12:38.836,0:12:43.668
before you actually call a CBC encrypt and[br]you have to that yourself. So again, it's

0:12:43.668,0:12:48.340
very important that the programmer knows[br]that it needs to be done otherwise the CBC

0:12:48.340,0:12:52.456
encryption is insecure. One last[br]technicality about CBC is what to do when

0:12:52.456,0:12:57.183
the message is not a multiple of the block[br]cipher block length? That is what do we do

0:12:57.183,0:13:01.689
if the last message block is shorter than[br]the block length of AES, for example? So

0:13:01.689,0:13:06.281
the last message block is less than[br]sixteen bytes. And the answer is if we add

0:13:06.281,0:13:11.586
a pad to the last block so it becomes as[br]long as sixteen bytes, as long as the AES

0:13:11.586,0:13:16.633
block size. And this pad, of course, if[br]going to be removed during encryption. So

0:13:16.633,0:13:21.873
here is a typical path, this is the path[br]that is used in TLS. Basically a pad with

0:13:21.873,0:13:26.919
N bytes then essentially what you do is[br]you write the number N, N times. So for

0:13:26.919,0:13:32.036
example if you pad with five bytes, you[br]pad with the string 555555. So five bytes

0:13:32.036,0:13:37.175
where each byte is the value five. And the[br]key thing about this pad is basically when

0:13:37.175,0:13:42.012
the decrypter receives the message, what[br]he does is he looks at the last byte of

0:13:42.012,0:13:46.970
the last block. So suppose that value is[br]five, then he simply removes the last five

0:13:46.970,0:13:51.818
bytes of the message. Now the question is[br]what do we do if in fact the message is a

0:13:51.818,0:13:56.262
multiple of sixteen bytes so in fact no[br]pad is needed? If we don't pad at all,

0:13:56.262,0:14:00.476
well that's a problem because the[br]decrypter is going to look at the very

0:14:00.476,0:14:05.267
last byte of the last block which is not[br]part of the actual message and he's going

0:14:05.267,0:14:10.000
to remove that many bytes from the plain[br]text. So that actually would be a problem.

0:14:10.000,0:14:15.363
So the solution is, if in fact there is no[br]pad that's needed, nevertheless we still

0:14:15.363,0:14:20.662
have to add a dummy block. And since we[br]add the dummy block this would be a block

0:14:20.662,0:14:25.830
that's basically contains sixteen bytes[br]each one containing the number sixteen.

0:14:25.830,0:14:30.042
Okay, so we add essentially sixteen dummy[br]blocks. The decrypter, that when he's

0:14:30.042,0:14:34.473
decrypting, he looks at the last byte of[br]the last block, he sees that the value is

0:14:34.473,0:14:38.823
sixteen, therefore he removes the entire[br]block. And whatever's left is the actual

0:14:38.823,0:14:42.975
plain text. So it's a bit unfortunate that[br]in fact if you're encrypting short

0:14:42.975,0:14:47.019
messages with CBC and the messages happen[br]to be, say, 32 bytes, so they are a

0:14:47.019,0:14:51.387
multiple of sixteen bytes, then you have[br]to add one more block and make all these

0:14:51.387,0:14:55.108
ciphertexts be 48 bytes just to[br]accommodate the CBC padding. I should

0:14:55.108,0:14:59.584
mention there's a variant of CBC called[br]CBC with ciphertext stealing that actually

0:14:59.584,0:15:03.790
avoids this problem, but I'm not gonna[br]describe that here. If you're interested

0:15:03.790,0:15:07.907
you can look that up online. Okay, so[br]that's the end of our discussion of CBC

0:15:07.907,0:15:12.198
and in the next segment we'll see how to[br]use counter modes to encrypt multiple

0:15:12.198,0:15:13.720
messages using a single key.