1:17

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.

Â