Modes of operation: many time key (CBC) (16 min)

Now that we understand chosen plaintext
security, let's build encryption schemes

that are chosen plaintext secure. And the
first such encryption scheme is going to

be called cipher bock chaining. So here
is how cipher block chaining works.

Cipher block chaining is a way of using a
block cipher to get chosen plaintext

security. In particular, we are going to
look at a mode called cipher block chaining

with a random IV. CBC stands for cipher
block chaning. So suppose we have a block

cipher, so EB is a block cipher. So now
let's define CBC to be the following

encryption scheme. So the encryption
algorithm when it's asked to encrypt a

message m, the first thing it's going to do
is it's going to choose a random IV that's

exactly one block of the block
cipher. So IV is one cypher block.

So in the case of AES the IV
would be 16 bytes. And then we're

gonna run through the algorithm here, the
IV basically that we chose is gonna be XORed

to the first plain text
block. And then the result is gonna be

encrypted using the block cipher and
output of the first block of the ciphertext.

And now comes the chaining part
where we actually use the first block of

the ciphertext to kind of mask the second
block of the plaintext. So we XOR

the two together and the encryption of
that becomes the second ciphertext block.

And so on, and so on, and so forth. So
this is cIpher block chaining, you can

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.