Security for many-time key (23 min)

In this segment we will look at how to use
block ciphers to encrypt multiple messages

using the same key. This comes up in
practice for example in file systems where

the same key's used to encrypt multiple
files. It comes up in networking protocols

where the same key is used to encrypt
multiple packets. So let's see how to do

it. The first thing we need to do is to
define what is mean for a cipher to be

secure when the same key is used to
encrypt multiple messages. When we use the

key more than once the result of that is
that the adversary gets to see many cyber

text encrypted using the same key. As a
result, when we define security, we're

gonna allow the adversary to mount what's
called a chosen plain text attack. In

other words, the adversary can obtain the
encryption of arbitrary messages of his

choice. So, for example, if the
adversary's interacting with Alice. The

adversary can ask Alice to encrypt
arbitrary messages of the adversary's

choosing. And Alice will go ahead and
encrypt those messages and give the

adversary the resulting cipher texts. You
might wonder why would Alice ever do this.

How could this possibly happen in real
life? But it turns out this is actually

very common in real life. And in fact,
this modeling is quite a conservative

modeling of real life. For example, the
adversary might send Alice an email. When

Alice receives the email, the writes it to
her encrypted disk, thereby encrypting the

adversary's email using her secret key. If
later the adversary steals this disc, then

he obtains the encryption of an email that
he sent Alice under Alice's secret key. So

that's an example of a chosen plain text
attack, where the adversary provided Alice

with a message and she encrypted that
message using her own key. And then later

the attacker was able to obtain the
resulting cipher text. So that's the

adversary's power. And then the
adversary's goal is basically to break

semantic security. So let's define this
more precisely. As usual, we're gonna

define semantic security under a chosen
plain text attack using two experiments,

experiment zero and experiment one, that
are modeled as a game between a challenger

and an adversary. When the game begins,
the challenger is gonna choose a random

key K. And now the adversary basically
gets to query the challenger. So the

adversary now begins by submitting a
semantic security query, namely, he

submits two messages, M zero and M one. I
added another index, but let me ignore

that extra index for a while. So the
adversary submits two messages, M zero and

M one, that happen to be of the same
length. And then the adversary receives

the encryption of one of those messages,
either of M zero or of M one. In

experiment zero, he receives the
encryption of M zero. In experiment one,

he receives the encryption of M one. So,
so far this would look familiar this looks

exactly like a standard semantic security
[inaudible]. However, plain text attack

the adversary can now repeat this query
again. So now you can issue a query with

two other plain texts, again of the same
length, and again you would receive the

encryption of one of them. In experiment
zero you would receive the encryption of M

zero. In experiment one you would receive
the encryption of M one. And the attacker

can continue issuing queries like this. In
fact we'll say that he can issue up to Q

queries of this type. And then, remember,
every time he issues a pair of messages.

That happen to be of the same length and
every time he either gets the encryption

of the left side or the right side again
in experiment zero he will always get the

encryption of the left message in
experiment one he will always get the

encryption of the left message. And, then
adversary's goal is, basically, to figure

out whether he's in experimental zero or
in experiment one. In other words, whether

he was constantly receiving the encryption
of the left message or the encryption of

the right message. So, in some sense, this
is a standard semantic security game just

iterated over many queries that the
attacker can issue to adaptively one after

the other. Now the chosen plain text
attack is captured by the fact that if the

attacker wants the encryption of a
particular message m. What he could do is,

for example, use query J for sum J, where
in this query J he'll set both the zero

message and the one message to be the
exactly same message M. In other words,

both the left message and the right
message are the same, and both are set to

the message M. In this case, what he will
receive, since both messages are the same,

he knows that he's gonna receive the
encryption of this message M that he was

interested in. So this is exactly what we
meant by a chosen [inaudible] attack.

Where the advisory can submit a message m
and receive the encryption of that

particular message m of his choice. So
some of his queries might be of this chose

plain text flavor where the message on the
left is equal to the message on the right,

but some of the queries might be standard
semantic security queries where the two

messages are distinct and that actually
gives him information on whether he's in

experiment zero or in experiment one. Now
by now you should be used to this

definition where we say that the system is
semantically secure under a chosen plain

text attack. If, for all efficient
adversaries, they cannot distinguish

experiment zero from experiment one. In
other words, the probability that, at the

end, the output, B Prime, which we're
gonna denote by the output of experiment

B. This output will be the same whether
[inaudible] experiment zero or experiment

one. So the attacker couldn't distinguish
between always receiving encryptions of

the left messages, versus always receiving
encryptions of the right messages. So in

your mind, I'd like you to be thinking of
an adversary that is able to mount a

chosen plaintext attack, namely, be given
the encryption of arbitrary messages of

his choice, and his goal is to break
semantic security for some other challenge

cipher texts. And as I said in this
[inaudible] model of the real world the

attacker is able to fool Alice into
encrypting for him messages of his choice

and then the attacker's goal is to somehow
break some challenge cypher text. So I

claim that all the ciphers that we've seen
up until now, namely deterministic counter

mode or the one time pad, are insecure
under a chosen plain text attack. More

generally, suppose we have an encryption
scheme that always outputs the same cipher

text for a particular message M. In other
words, if I ask the encryption scheme to

encrypt the message M once. And then I ask
the encryption scheme to encrypt the

message m again. If in both cases the
encryption scheme outputs the same cypher

text, then that system cannot possibly be
secure under a chosen plain text attack.

And both deterministic counter mode and
the one time pad were of that flavor. They

always output the same cipher text, given
the same message. And so let's see why

that cannot be chosen plain text secure.
And the attack is fairly simple, what the

attacker is gonna do, is he's gonna output
the same message twice. This just says.

That he really wants the encryption of M0.
So here the attacker is given C0 which is

the encryption of M0. So this was his
chosen plain text query where he actually

received the encryption of the message M0
of his choice. And now he's going to break

semantic security. So what he does is he
outputs two messages, M0 and M1 of the

same length, and he's going to be given
the encryption of MB. But low and behold,

we said that the encryption system. Always
outputs the same cipher text when its

encrypting the message, M0. Therefore, if
B is=to zero, we know that C, this

challenged cipher text, is simply=to CO,
because it's the encryption of M0.

However, if B is=to one. Then we know that
this challenge cypher text is the

encryption of M1 which is something other
than C zero so all the attacker does is he

just checks his C is = to C0 the output's
zero in other words he outputs one. So, in

this case, the attacker is able to
perfectly guess this bit B, so he knows

exactly [inaudible] given the encryption
of M0, or the encryption of M1. And as a

result, his advantage in winning this game
is one. Meaning that the system cannot

possibly be CPA secure. One is not a
negligible number. So this shows that the

deterministic encryption schemes cannot
possibly be CPA-secure, but you might

wonder well, what does this mean in
practice? Well in practice this means

again that every message is always
encrypted to the same cipher text. What

this means is if you're encrypting files
on disk, and you happen to be encrypting

two files that happen to be the same, they
will result in the same cipher text and

then the attacker by looking at the
encrypted disk, will learn that these two

files actually contain the same content.
The attacker might not learn what the

content is, but he will learn that these
two encrypted files are an encryption of

the same content and he shouldn't be able
to learn that. Similarly, if you send two

encrypted packets on the network that
happen to be the same, the attacker will

not learn the content of those packets,
but he will learn that those two packets

actually contain the same information.
Think for example of an encrypted voice

conversation. Every time there's quiet on
the line, the system will be sending

encryptions of zero. But since encryption
of zero are always mapped to the same

cypher text. An attacker looking at the
network will be able to identify exactly

the points in the conversation where
there's quiet because he will always see

those exact same cypher text every time.
So these are examples where deterministic

encryption cannot possibly be secure. And
as I say formerly we say that the

terministic encryption can not be
semantically secure under a chosen plain

text attack. So what do we do, well the
lesson here is if the secret keys gonna be

used to encrypt multiple messages, it had
better be the case that given the same

plain text to encrypt twice. The
encryption algorithm must produce

different cipher texts. And so there are
two ways to do that. The first method is

what's called randomized encryption. Here,
the encryption algorithm itself is going

to choose some random string during the
encryption process and it is going to

encrypt the message M using that random
string. So what this means is that a

particular message, M0 for example, isn't
just going to be mapped to one cipher text

but it's going to be mapped to a whole
ball of cipher texts. Whereon every

encryption, basically, we output one point
in this ball. So every time we encrypt, the

encryption algorithm chooses a random
string, and that random string leads to

one point in this ball. Of course, the
decryption algorithm, when it takes any

point in this ball, will always map the
result to M zero. Similarly cipher text M

one will be mapped to a ball, and every
time we encrypt M one, we basically output

one point in this ball. And these balls
have to be disjoint, so that the

encryption algorithm, when it obtains a
point in the ball corresponding to M one,

will always output the message M one. In
this way, since the encryption algorithm

uses randomness, if we encrypt the same
message twice, with high probability we'll

get different cipher texts. Unfortunately
this means that the cipher text

necessarily has to be longer than the
plain text because somehow the randomness

that was used to generate the cipher text
is now encoded somehow in the cipher text.

So the cipher text takes more space. And
roughly speaking, the cipher text size is

going to be larger than the plain text. By
basically the number of random bits that

were used during encryption. So if the
plain texts are very big, if the plain

texts are gigabytes long, the number of
random bits is going to be on the order of

128. So maybe this extra space doesn't
really matter. But if the plain texts are

very short, maybe they themselves are 128
bits, then adding an extra 128 bits to

every cipher text is going to double the
total cipher text size. And that could be

quite expensive. So as I say randomized
encryption is a fine solution but in some

cases it actually introduces quite a bit
of costs. So let's look at a simple example.

So imagine we have a pseudorandom
function that takes inputs in a certain

space r which is gonna be called a nonce
space. And outputs, outputs in the message

space. And, now, let's define the
following randomize encryption scheme

where we want to encrypt the message m
with the encryption of whatever it's gonna

do is first it's gonna generate a random r
in this nonce space R. And then it's going

to open a cypher text that consist of two
components, the first component is going

to be this value R and the second
component is going to be an evaluation of

the pseudo-random function at the point R
XOR with the message M. And my question to

you is, is this encryption system
semantically secure under a chosen plain

text attack. So the correct answer is yes.
But only if the nonce space R is large

enough so that little R never repeats with
very, very high probability. And let's

quickly argue why that's true. So first of
all, because F is a secure pseudo-random

function, we might as well replace it with
a truly random function. In other words,

this is indistinguishable from the case
where we encrypt the message M, using the

truly random function little F, evaluated
to point R, and then XOR with M.

But since this little r never repeats every
cypher text uses a different little r what

this means is that the values of F(r)
are random uniform independent strings

every time. So every time we encrypt a
message, we encrypt it essentially using a

new uniform random one time pad. And since
XORing a uniform string with any string

simply generates a new uniform string, the
resulting cipher text is distributed as

simply two random uniform strings. I'll
call them r and r prime. And so both in

experiment zero and in experiment one, all
the attacker gets to see are truly uniform

random strings r, r', and since in both
experiments the attacker is seeing the same

distribution, he cannot distinguish the
two distributions. And so since security

holds completely when we're using a truly
random function it's also gonna hold when

we're using a pseudorandom function. Okay,
so this is a nice example of how we use

the fact that the pseudo random function
behaves like a random function to argue

security of this particular encryption
scheme. Okay, so now we have a nice

example of randomized encryption. The
other approach to building chosen plain

text secure encryption schemes is what's
called a nonce based encryption. Now, in

a non-spaced encryption system, the
encryption algorithm actually takes three

inputs rather than two. As usual it takes
the key and the message. But it also takes

an additional input called a nonce. And
similarly, the decryption algorithm also

takes the nonce as input, and then produces
the resulting decrypted plain text. And

what is this nonce value n. This nonce is
a public value. It does not need to be

hidden from the adversary but the only
requirement is that the pair (k,n)

is only used to encrypt a single
message. In other words, this pair (k,n)

must change from message to message. And
there are two ways to change it. One way

to change it is by choosing a new random
key for every message. And the other way

is to keep using the same key all the time
but then we must choose a new nonce for

every message. And, and as I said, I wanna
emphasize again, this nonce need not

be secret, and it need not be random. The
only requirement is the nonce is unique.

And in fact, we're gonna use this
term throughout the course. A nonce

for us, means a unique value that doesn't
repeat. It does not have to be random. So

let's look at some examples of choosing an
nonce, well the simplest option is

simply to make the nonce of the
accounter so for example the networking

protocol you can imagine the nonce
being a packet counter that's incremented

every time a packet is sent by a sender or
received by the receiver this means that

the encrypter has to keep state from
message to message mainly that he has to

keep this counter around and increment it
after every message is transmitted.

Interestingly, if the decrypter actually
has the same state then there is no need

to include the nuance in the cipher text
since the nuance is implicit. Let's look

at an example. The https protocol is run
over a reliable transport mechanism which

means that packets sent by the sender are
assumed to be received in order at a

recipient. So if the sender sends packet #5 and then packet #6, the recipient

will receive packet #5 and then
packet #6 in that order. This

means that if the sender maintains a
packet counter, the recipient can also

maintain a packet counter and two counters
basically increment in sync. In this case

there is no reason to include the
nonce in the packets because the

nonce is implicit between the two
sides. However, in other protocols, for

example, in IPsec, IPsec has a protocol
designed to encrypt the IP layer. The IP

layer does not guarantee in order
delivery. And so the sender might send

packet #5 and then packet #6, but
those will be received in reverse order at

the recipient. In this case it's still
fine to use a packet counter as a nonce

but now the nonce has to be included in
the packet so that the recipient knows

which nonce to use to decrypt the
received packet. So as I say, nonce based

encryption is a very efficient way to
achieve CPA security. In particular if the

nonce is implicit, it doesn't even
increase the cipher text length. Of course

another method to generate a unique nonce
is simply to pick the nonce at random

assuming the nonce space is sufficiently
large so that with high probability the

nonce will never repeat for the life of
the key. Now in this case, nonce

based encryption simply reduces to
randomized encryption. However, the

benefit here is that the sender does not
need to maintain any state from message to

message. So this is very useful for
example if encryption happens to take

place on multiple devices. For example, I
might have both a laptop and a smart

phone. They might both use the same key.
But in this case if I require state full

encryption, then my laptop and the
smartphone would have to coordinate to

make sure that they never reuse the same
nonces. Whereas if both of them simply take

nonces at random, they don't need to
coordinate because it was very high

probability they'll simply never choose
the same nonce. Again assuming the nonce

space is big enough. So there are some
cases where stateless encryption is quite

important, in particular where the same
key is used by multiple machines. So I

wanted to find, more precisely, what
security means for nonce based

encryption. And in particular, I want to
emphasize that the system must remain

secure when the nonce are chosen by
the adversary. The reason it's important

to allow the adversary to choose the
nonces is because the adversary can

choose which cipher text it wants to
attack. So imagine the nonce happens to

be a counter and it so happens that when
the couter hits the value fifteen, maybe

at that point it's easy for the adversary
to break semantic security. So the

adversary will wait until the fifteenth
packet is sent and only then he will ask

to break semantic security. So when we
talk about nonce based encryption, we

generally allow the adversary to choose
the nonce and the system should remain

secure even under those settings. So let's
define the CPA game in this case and it's

actually very similar to the game before.
Basically the attacker gets to submit

pairs of messages MI, MI0, and MI1.
Obviously they both have to be of the same

length. And he gets to supply the nonce.
And in response, the adversary is given

the encryption of either MI0, or MI1. But
using the nonce that the adversary

chose. And of course, as usual, the
adversary's goal is to tell whether he was

given the encryption of the left plain
text or the right plain text. And as

before the adversary gets to iterate these
queries and he can issue as, as many

queries as he wants, we usually let q
denote the number of queries that the

adversary issues. Now the only restriction
of course, which is crucial, is that

although the adversary gets to choose the
nonces, he's restricted to choosing

distinct nonces. The reason we force him
to choose distinct nonces is because

that's the requirement in practice. Even
if the adversary fools Alice into

encrypting multiple messages for him,
Alice will never use the same nonce

again. As a result, the adversary will
never see messages encrypted using the

same nonce and therefore, even in the
game, we require that all nonce be

distinct. And then as usual we say that
the system is a nonce based encryption

system that's, semantically secure under a
chosen plain text attack if the adversary

cannot distinguish experiment zero where
he's given encryptions of the left

messages from experiment one where he's
given encryptions of the right messages.

So let's look at an example of a nonce
based encryption system. As before, we

have a secure PRF that takes inputs in the
nonce space R and outputs strings in the

message space M. Now when a new key is
chosen, we're going to reset our counter R

to be zero. And now we encrypt the
particular message M, what we will do is

we will increment our counter R, and then
encrypt the message M using the

pseudorandom function applied to this
value R. And as before, the cipher text is

going to contain two components, our
current value of the counter and then the

one time pad encryption of the message M.
And so my question to you is whether this

is a secure, non-spaced encryption system.
So the answer as before is yes, but only

if the nuance space is large enough. So as
we increment the counter R, it will never

cycle back to zero so that the nuances
will always, always be unique. We argue

security the same way as before. Because
the PRF is secure, we know that this

encryption system is indistinguishable
from using a truly random function. In

other words, if we apply a truly random
function to the counter and XOR the

results with, the plain text M. But now
since the nuance R never repeats, every

time we compute this F of R, we get a
truly random uniform and independent

string so that we're actually encrypting
every message using the one time pad. And

as a result, all the adversary gets to see
in both experiments are basically just a

pair of random strings. So both the
experiment zero and experiment one the

adversary get's to see exactly the same
distribution, namely, the responses to all

this chosen plain text queries are just
pairs of strings that are just uniformly

distributed and this is basically the same
in experiment zero and experiment one and,

therefore, the attacker cannot distinguish
the two experiments. And since he cannot

win the semantic security game with a
truly random function he, also, cannot win

the semantics security game with the
secure PRF, and, therefore, the scheme is

secure. So now we understand what it means
for a symmetric system to be secure when

the keys used to encrypt multiple messages
the requirement is that it be secure under

a chosen plan of attack. And we said that
basically, the only way to be secure under

a chosen plain text attack is either to
use randomized encryption, or to use, use

nonce spaced encryption where the
nonce never repeats. And then in the

next two segments, we're gonna build two
classic encryption systems that are secure

when the key is used multiple times.