see that each cIpher block is chained and XORed into the next plaintext

block, and the final ciphertext is going to be essentially the IV, the initial IV

that we chose along with all the ciphertext blocks. I should say that IV stands

for Initialization Vector. And we're going to be seeing that term used quite a bit,

every time we need to pick something at random at the beginning of the encryption

scheme typically we'll call that an IV for initialization vector. So you notice

that the cIphertext is a little bit longer than the plain text because we had

to include this IV in the cIphertexts which basically captures the randomness

that was used during encryption. So the first question is how do we decrypt the

results of CBC encryption, and so let me remind you again that if when we

encrypt the first message block we XOR it with the IV, encrypt the

result and that becomes the first ciphertext block. So let me ask you how would

you decrypt that? So given the first ciphertext block, how would you recover

the original first plaintext block? So decryption is actually very similar to

encryption, here I wrote down the decryption circuit, you can see basically

it's almost the same thing except the XOR is on the bottom, instead of on the top, and

again you realize that essentially we chopped off the IV as part of the

decryption process and we only output the original message back, the IV is dropped

by the decryption algorithm. Okay, so the following theorem is going to show that in

fact CBC mode encryption with a random IV is in fact semantically secure under a

chosen plaintext attack, and so let's take that more precisely, basically if we

start with a PRP, in other words, our block cipher E, that is defined over a

space X, then we are gonna to end up with a encryption algorithm Ecbc that takes

messages of length L and outputs ciphertexts of length L+1. And then

suppose we have an adversary that makes q chosen plaintext queries. Then we can

state the following security fact, that for every such adversary that's attacking

Ecbc, to exist an adversary that's attacking the PRP, the block cipher, with

the following relation between the two algorithms, in other words, the advantage

of algorithm A against the encryption scheme is less than the advantage of algorithm B

against the original PRP plus some noise term. So let me interpret this theorem for

you as usual, so what this means is that essentially since E is a secure PRP this

quantity here is negligible, and our goal is to say that adversary A's advantage is

also negligible. However, here we are prevented from saying that because we got

this extra error term. This is often called an error term and to argue that CBC

is secure we have to make sure that the error term is also negligible. Because if

both of these terms on the right are negligible, there sum is negligible and

therefore the advantage of A against Ecbc would also be negligible. So this says

that in fact for Ecbc to be secure it has better be the case that q squared L squared Is

much, much, much smaller than the value X, so let me remind you what q and L are, so

L is simply the length of the messages that we're encrypting. Okay, so L could be

like say a 1000, which means that we are encrypting messages that are at most 1000

AES blocks. q is the number of ciphertexts that the adversary gets to see under the

CPA attack, but in real life what q is, is basically the number of times that we have

used the key K to encrypt messages, in other words if we use a particular AES key to

encrypt 100 messages, Q would be 100. It is because the adversary would then see

at most 100 messages encrypted under this key K. Okay so lets see what this means in the real

world. So here I've rewrote the error balance from the theorem. And just to remind

you to use the messages encrypted with K and L with the lengths of the messages and so

suppose we want the adversary's advantage to be less than one over two to the thirty

two. This means that the error term had better be less than one over two to the

thirty two. Okay, so let's look at AES and see what this mean. For AES, AES of course uses

128 bit blocks, so X is going to be two to the 128, the

size of X is going to be 2 to the 128, and if you

plug this into the expression you see that basically the product q times L had

better be less than two to the forty eight. This means that after we use a particular

key to encrypt 2 to the 48 AES blocks we have to change the key. Okay, so

essentially CBC stops being secure after the key is used to encrypt 2 to the 48 different AES blocks.

So its kinda nice that the security theorem tells

you exactly how long the key can be used and then how frequently, essentially, you have to

replace the key. Now interestingly if you apply the same analogy to the 3DES it

actually has a much shorter block, maybe only 64 bits, you see the key has to be

changed much more frequently, maybe after every 65 thousand DES blocks, essentially you need to generate a new key. So

this is one of the reasons why AES has a larger block size so that in fact modes

like CBC would be more secure and one can use the keys for a longer period of time, before having

to replace it. What this means is having to replace two to the sixteen blocks,

each block of course is 8 bytes, so after you encrypt about half a megabyte of

data you would have to change the DES key which is actually quite low. And you

notice with AES you can encrypt quite a bit more data before you have to change the

key. So I want to warn you about a very common mistake that people have made when

using CBC with a random IV. That is that the minute that the attacker can predict

the IV that you're going to be using for encrypting a particular message decipher

this Ecbc is no longer CPA secure. So when using CBC with a random IV like we've

just shown It's crucial that the IV is not predictable. But lets see an attack. So

suppose it so happens that given a particular encryption in a message that

attacker can actually predict that IV that will be used for the next message. Well

let's show that in fact the resulting system is not CPA secure. So the first thing the

adversary is going to do is, he is going to ask for the encryption of a one block

message. In particular that one block is going to be zero. So what the adversary

gets back is the encryption of one block, which namely is the encryption of

the message namely zero, XOR the IV. Okay and of course the adversary also gets the

IV. Okay so now the adversary by assumption can predict the IV that's gonna

be used for the next encryption. Okay so let's say that IV is called, well IV. So

next the adversary is going to issue his semantic security challenge and the

message m0 is going to be the predicted IV XOR IV1 which was used in the encryption

of c1. And the, the message of m1 is just going to be some other message, it doesn't

really matter what it is. So now let's see what happens when the adversary receives

the result of the semantic security challenge. Well, he is going to get the

encryption of m0 or m1. So when the adversary receives the encryption of m0,

tell me what is the actual plain text that is encrypted in the ciphertext c?

Well so the answer is that what is actually encrypted is the message which is

IV XOR IV1 XOR the IV that's used to encrypt that message which happens to be

IV and this of course is IV1. So when the adversary receives the encryption of m0,

he is actually receiving the block cipher encryption of IV1. And lo and behold,

you'll notice that he already has that value from his chosen plaintext query.

And then, when he is receiving the encryption of message m1, he just received

a normal CBC encryption of the message m1. So you realize that now he has a simple

way of breaking the scheme, namely what he'll do is he'll say, he's gonna ask, "Is the second

block of the ciphertext c equal to the value that I received in my CPA query?" If

so I'll say that I received the encryption of m0, otherwise I'll say that I received

the encryption of m1. So really his test is c1 he refers to the second block

of c and c11 refers to the second block of c1, if the two are equal he says zero,

otherwise he says one. So the advantage of this adversary is going to be 1 and as a

result, he completely breaks CPA security of this CBC encryption. So the lesson here

is, if the IV is predictable then, in fact, there is no CPA security and

unfortunately, this is actually a very common mistake in practice. In particular

even in SSL protocol and in TLS 1.1, it turns out that IV for record number I is in fact

the last ciphertext block of record I-1. That means that exactly given

the encryption of record I-1, the adversary knows exactly what IV is going

to be used as record number I. Very recently, just last summer, this was

actually converted into a pretty devastating attack on SSL. We'll describe

that attack once we talk about SSL in more detail, but for now I wanted to make sure

you understand than when you use CBC encryption, its absolutely crucial that the IV be random.

Okay, so now I going to show you the nonce based version of CBC encryption

So in this mode the IV is replaced by non random but unique nonce

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

is that if the recipient actually knows what the nonce is supposed to be

then there's no reason to include the nonce in the ciphertext, in which case, the ciphertext

is exactly the same length as the plaintext, unlike CBC with the random IV,

where we had to expand the ciphertext to include the IV, here, if the nonce is already known to the recipient,

there's no reason to include it in the ciphertext, and the ciphertext is exactly the same length as the plaintext.

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

if you do this, there's one more step that you have to do before you use the nonce in the CBC chain.

In particular, in this mode now we're going to be using two independent keys, k and k1.

The key k is, as before, going to be used to encrypt the individual message blocks,

However, this key k1 is going to be used to encrypt the non-random but unique nonce,

so that the output is going to be a random IV, which is then used in the CBC chain.

So this extra step here, encrypting the nonce with the key k1, is absolutely crucial.

Without it, CBC mode encryption would not be secure.

However it if is going to be a counter you

need to do one more step. Before actually encryption CBC and in particular you have

to actually encrypt the notes to obtain the IV that will actually be used for

encryption. The notes on CBC is similar to a random IV, the difference is that the

notes is first encrypted and the results is that the IV is used in the CBC

encryption Now the beauty of this mode is that the Nance doesn't necessarily have to

be included in the cipher text. It only needs to be in there if its unknowns are

the decrypter but it if the decrypter happens to already know the value of the

counter by some other means then in fact the cipher text is only as big as the

plain text. There's no extra value transmitted in the cipher text. And again,

I warn that when you're using non spaced encryption, it's absolutely crucial that

the key common Nance spare is only used for one message so for every message,

either the Nance has changed or the key has changed. Okay, so here emphasize the

fact that you need to do this extra encryption step before actual using the

Nance. This is very common mistake that actually forgotten in practice and for

example in TLS, this was not done and as a result there was a significant attack

against CBC encryption in TLS. Remember the reason that this is so important to

know is that in fact many crypto APIs are set up to almost deliberately mislead the

user to using CBC incorrectly. So let's look to see how CBC implemented inside of

open SSL. So here are the arguments of the function. Basically this is the plain

text, this is the place where the cipher text will get written to. This is the

length of the plain text. This is a, a Yes key Finally there is an argument here that

says whether you are crypting or decrypting. And the most important

parameter that I wanted to point out here is the actual IV and unfortunately, the

user is asked to supply this IV and the function uses the IV directly in the CBC

encryption mechanism. It doesn't encrypt the IV before using it and as a result, if

you ever call this function using a non random IV, the resulting encryption system

won't be CPA secure. Okay, so it's very important to know that when calling

functions like this. Cbc encryption or open SSL either supply a truly random IV

or if you want the IV to be a counter than you have to encrypt a counter using AAS

before you actually call a CBC encrypt and you have to that yourself. So again, it's

very important that the programmer knows that it needs to be done otherwise the CBC

encryption is insecure. One last technicality about CBC is what to do when

the message is not a multiple of the block cipher block length? That is what do we do

if the last message block is shorter than the block length of AES, for example? So

the last message block is less than sixteen bytes. And the answer is if we add

a pad to the last block so it becomes as long as sixteen bytes, as long as the AES

block size. And this pad, of course, if going to be removed during encryption. So

here is a typical path, this is the path that is used in TLS. Basically a pad with

N bytes then essentially what you do is you write the number N, N times. So for

example if you pad with five bytes, you pad with the string 555555. So five bytes

where each byte is the value five. And the key thing about this pad is basically when

the decrypter receives the message, what he does is he looks at the last byte of

the last block. So suppose that value is five, then he simply removes the last five

bytes of the message. Now the question is what do we do if in fact the message is a

multiple of sixteen bytes so in fact no pad is needed? If we don't pad at all,

well that's a problem because the decrypter is going to look at the very

last byte of the last block which is not part of the actual message and he's going

to remove that many bytes from the plain text. So that actually would be a problem.

So the solution is, if in fact there is no pad that's needed, nevertheless we still

have to add a dummy block. And since we add the dummy block this would be a block

that's basically contains sixteen bytes each one containing the number sixteen.

Okay, so we add essentially sixteen dummy blocks. The decrypter, that when he's

decrypting, he looks at the last byte of the last block, he sees that the value is

sixteen, therefore he removes the entire block. And whatever's left is the actual

plain text. So it's a bit unfortunate that in fact if you're encrypting short

messages with CBC and the messages happen to be, say, 32 bytes, so they are a

multiple of sixteen bytes, then you have to add one more block and make all these

ciphertexts be 48 bytes just to accommodate the CBC padding. I should

mention there's a variant of CBC called CBC with ciphertext stealing that actually

avoids this problem, but I'm not gonna describe that here. If you're interested

you can look that up online. Okay, so that's the end of our discussion of CBC

and in the next segment we'll see how to use counter modes to encrypt multiple

messages using a single key.