Definitions and security (16 min)

Last week, we learned a number theory
that's needed for public key encryption.

This week we're gonna put this knowledge
to work, and we're gonna construct a

number of secure public key encryption
schemes. But first, we need to define what

is public key encryption, and what does it
mean for public key encryption to be

secure? So let me remind you that in a
public key encryption scheme, there is an

encryption algorithm which is usually
denoted by E, and there's a decryption

algorithm which we denote by D. However
here, the encryption algorithm takes a

public key, while the decryption algorithm
takes a secret key. This pair is called a

key pair. And the public key is used for
encrypting messages while the secret key

is used for decrypting messages. So in
this case a message m is encrypting using

the public key and what comes out of that
is the ciphertext c. And similarly the

ciphertext is fed into the decryption
algorithm and using the secret key, what

comes out of the decryption algorithm is
the original message m. Now public key

encryption has many applications. Last
week we saw the classic application which

is session setup, namely, key exchange and
for now we're just looking at key exchange

that is secure against eavesdropping only.
And if you remember the way the protocol

works, basically Alice, what she would do
is she would generate a public key secret

pair. She would send the public key to
Bob. Bob will generate a random X, which

is gonna serve as their shared secret, and
then he sends X encrypted to Alice,

encrypted under her public key. Alice can
decrypt, recover X and now both of them

have this shared secret X which they can
use to communicate securely with one

another. The attacker, of course, all he
gets to see is just the public key, the

encryption of X under the public key, from
which he should not be able to get any

information about X. And we are going to
define that more precisely to understand

what it means to not be able to learn
anything about X. Public key encryption

actually has many other applications. For
example, it's very useful in

non-interactive applications. So think of
an email system for example. So here, Bob

wants to send mail to Alice, and as Bob
sends the email, the email passes from

mail relay to mail relay until finally it
reaches Alice, at which point Alice should

decrypt. The way the email system is set
up, is designed for kind of

non-interactive settings where Bob sends
the email. And then Alice is supposed to

receive it. And Alice should not be to
communicate with Bob in order to decrypt

the email. So in this case, because of the
non-interactivity, there's no opportunity

for setting up a shared secret between
Alice and Bob. So in this case, what would

happen is, Bob basically would, would send
the email encrypted, using Alice's, public

key. So he sends the email. Anyone in the
world can send the email encrypted to

Alice, encrypted using her public key.
When Alice receives this email, she uses

her secret key to decrypt the ciphertext and recover the plain text message.

Of course the one caveat in a system like
this is that in fact Bob needs to somehow

obtain Alice's public key So for now we
are just going to assume Bob already has

Alice's public key, but later on,
actually, when we talk about digital

signatures we're gonna see how, this can
actually be done very efficiently using what's

called public key management and as I said
we'll actually get back to that at a later

time. But the main thing I want you to
remember, is that public key encryption is

used for session setup. This is very
common on the web, where public key

encryption is used to set up a secure key
between a web browser and, and web server.

And public key encryption is also very
useful for non-interactive applications,

where anyone in the world,
non-interactively, needs to send a message

to Alice, they can encrypt the message using
Alice's public key, and Alice can decrypt

and recover the plain text. So let me
remind you in a bit more detail what a

public key encryption system is. Well,
it's made up of three algorithms G, E, and

D. G is called the key generation algorithm.
Basically what it will do is it will

generate this key pair, the public key and
the secret key. As written here, G takes

no arguments, but in real life, G actually
does take an argument called the security

parameter which specifies the size of the
keys that are generated by this key

generation algorithm. Then there are these
encryption algorithms as usual that take a

public key and a message and produce a
ciphertext in a decryption algorithm that

takes the corresponding secret key and a
ciphertext and it produces a corresponding

message. And as usual for consistency we
say that if we encrypt a message under a

given public key and then decrypt with a
corresponding secret key we should get the

original message back. Now what does it
mean for a public key encryption to be

secure? I'm going to start off by
defining, security against eavesdropping.

And then we're going to define security
against active attacks. So the way to

define security against eavesdropping is
very similar to the symmetric case we've

already this last week so we're gonna go
through this quickly just as a review.

Basically the attack game is defined as
follows. We defined these two experiments,

experiment zero and experiment one. At in
either experiment the challenger is gonna

generate a public and a secret key pair. He's gonna give the public

key to the adversary. The adversary's
gonna output two messages m0 and m1 of

equal length and then what he gets back is
either the encryption of m0 or the

encryption of m1. In experiment zero he
gets the encryption of m0. In experiment

one he gets the encryption of m1. And then
the adversary is supposed to say which one

did he get. Did he get the encryption of
m0 or did he get the encryption of m1? So

in this game, the attacker only gets one
ciphertext. This corresponds to an

eavesdropping attack where he simply
eavesdropped on that ciphertext C. And now

his goal is to tell whether the ciphertext
C i s the encryption of M0 or M1. No

tampering on the ciphertext C is allowed
just yet. And as usual we say that the

public key encryption scheme is
semantically secure if the attacker cannot

distinguish experiment zero from
experiment one. In other words he cannot

tell whether he got the encryption of M0,
or the encryption of M1. Before we move on

to active attacks, I want to mention a
quick relation between the definition we

just saw, And the definition of, of
eavesdropping security for symmetric

ciphers. If you remember, when we talked
about eavesdropping security for symmetric

ciphers, we distinguished between the case
where the key is used once, and the case

where the key is used multiple times. And,
in fact we saw that, there's a clear

separation. For example, the onetime pad.
Is secure if the key is used to encrypt a

single message, but is completely insecure
if the key is used to encrypt multiple

messages. And in fact we had two different
definitions if you remember we had a

definition for one-time security, and then
we had a separate definition, which was

stronger, when the key was used multiple
times. The definition that I showed you on

the previous slide's very similar to the
definition of one time security for

symmetric ciphers. And in fact, it turns
out that for public key encryption, if a

system is secure under a onetime key, in a
sense, it's also secure for a many time

key. So in other words, we don't have to
explicitly give the attacker the ability

to, request encryptions of messages of his
choice. Because he could just create those

encryptions all by himself. He is given
the public key, and therefore he can by

himself encrypt any message he likes. As a
result any public key secret pair in some

sense inherently is used to encrypt
multiple messages because the attacker

could have just encrypted many, many
messages of his choice using the given

public key that we just gave him in the
first step. And so, as a result in fact,

the definition of one time security is
enough to imply many time security and

that's why we refer to the concept as
indistinguishability under a chosen plain

text attach. So this is just a minor point
to explain why the settings of public

encryption, we don't need a more
complicated definition to capture

eavesdropping security. Now that we
understand eavesdropping security, let's

look at more powerful adversaries that can
actually mount active attacks. So, in

particular, let's look at the email
example. So here, we have our friend Bob

who wants to send mail to his friend
Caroline. And Caroline happens to have, an

account at Gmail. And the way this works
is basically, the email is sent to the

Gmail server, encrypted. The Gmail server
decrypts the email, looks at the, intended

recipients. And then, if it's, the
intended recipient is Caroline, it

forwards the email to Caroline. If the
intended recipient is the attacker, it

forwards the email to the attacker. This
is similar to how Gmail actually works

because the sender would send the email
encrypted over SSL to the Gmail server.

The Gmail server would terminate the SSL
and then forward the email to the

appropriate recipients. Now suppose Bob
encrypts the email using a system that

allows the adversary to tamper with the
ciphertext without being detected. For

example, imagine this email is encrypted
using Counter Mode, or something like

that. Then when the attacker intercepts
this email, he can change the recipient,

so that now the recipient says
[e-mail], and we know that for

Counter Mode, for example, this is quite
easy to do. The attacker knows that the

email is intended for Caroline, he is just
interested in the email body. So he can

easily change the email recipient to
[e-mail] and now when the server

receives the email, he will decrypt it,
see that the recipient is supposed to be

attacker, and forward the body to the
attacker. And now the attacker was able to

read the body of the email that was
intended for Caroline. So this is a

classic example of an active attack, and
you notice what the attacker could do

here, is it could decrypt any ciphertext
where the intended recipient is to:

attacker. So any ciphertext where the plain
text begins with the words "to: attacker". So our goal is

to design public key systems that are
secure, even if the attacker can tamper

with ciphertext and possibly decrypt
certain cyphertexts. And again, I want to

emphasize that here the attacker's goal
was to get the message body. The attacker

already knew that the email is intended
for Caroline. And all he had to do was

just change the, intended recipient. So
this tampering attack motivates the

definition of chosen ciphertext security.
And in fact this is the standard notion of

security for public key encryption. So let
me explain how the attack [here procedes] and as I

said our goal is to build systems that are
secure under this very, very conservative

notion of encryption. So we have an
encryption scheme (G, E, D). And let's say

that's defined over a message space and
a ciphertext (M, C) and as usual we're

gonna define two experiments, experiment
zero, and experiment one. So 'b' here

says whether the challenger is
implementing experiment zero or experiment

one. The challenger begins by generating a
public key and a secret key, and then gives

the public key to the adversary. Now the
adversary can say, "Well, here are a bunch

of ciphertexts, please decrypt them for
me." So here the adversary submits

ciphertext C1 and he gets the decryption
of ciphertext C1, namely M1. And he gets

to do this again and again, so he submits
ciphertext C2, and he gets the decryption,

which is M2, ciphertext C3, and he gets
the decryption M3, and so on and so forth.

Finally, the adversary says, "This
squaring phase is over," and now he

submits basically two equal length
messages, M0 and M1 as normal, and he

receives in response the challenge
ciphertext C, Which is the encryption of M

zero or the encryption of M one. Depending
on whether we're in experiment zero or

experiment one. Now, the adversary can
continue to issue these ciphertext

queries. So he can continue to issue,
decryption requests. So he submits a

ciphertext, and he gets a decryption of
that ciphertext, but of course, now, there

has to be a caveat. If the attacker could
submit arbitrary ciphertext of his choice,

of course, he could break the challenge.
What he would do is he would submit the

challenge ciphertext C as a decryption
query. And then he would be told whether

in the challenge phase he was given the
encryption of M0 or the encryption of M1.

As a result we put this limitation here,
that says that he can in fact submit any

ciphertext of his choice except. For the
challenge ciphertext. So the attacker

could ask for the decryption of any
ciphertext of his choice other than the

challenge ciphertext. And even though he
was given all these decryptions, he still

shouldn't be able to tell whether he was
given the encryption of M0 or the

encryption of M1. So you notice this is a
very conservative definition. It gives the

attacker more power than what we saw in
the previous slide. On the previous slide,

the attacker could only decrypt messages
where the plain text began with the words

"to: attacker". Here, we're saying the attacker
can decrypt any ciphertext of his choice,

as long as it's different from the
challenge ciphertext C. Okay? And then his

goal is to say whether the challenge
ciphertext is the encryption of M0 or the

encryption of M1. And as usual, if he
can't do that, in other words, his

behavior in experiment zero is basically
the same as his behavior in experiment

one, so he wasn't able to distinguish the
encryption of M0 from the encryption of

M1, even though he had all this power Then
we say that the system is chosen

ciphertext secure, CCA secure. And
sometimes there is an acronym, the acronym

for this is indistinguishability under a
chosen ciphertext attack, but I'm just

gonna say CCA secured. So let's see how
this captures, the email example we saw

before. So suppose the encryption system
being used is such that just given the

encryption of a message the attacker can
change the intended recipient from to

Alice say to, to Charlie. Then here's how
we would win the CCA game. Well in the

first step he's given the public key of
course. And then what the attacker will do

is he would issue two equal length
messages, namely in the first message, the

body is zero. In the second message the
body is one. But both messages are

intended for Alice. And in response, he
would be given the challenge ciphertext C.

Okay, so now here we have our challenge
ciphertext C. Now what the attacker is

gonna do is he's gonna use his, his
ability here to modify the intended

recipient. And he's gonna send back a
ciphertext C', where C' is the encryption

of the message to Charlie with body being
the challenge body b. So if you remember is

either zero or one. Now, because the plain
text is different, we know that the

ciphertext must also be different. So in
particular, C prime must be different from

the challenge ciphertext C, yeah? So the
C prime here must be different from C. And

as a result, the poor challenger now has
to decrypt by definition of the CCA game.

The challenger must decrypt any ciphertext
that's not equal to a challenge

ciphertext. So the challenger decrypts
give the adversary M prime. Basically he

gave the adversary B, and now the
adversary can output the challenge B and

he wins the game with advantage one. So
he's advantage with this particular scheme

is one. So, simply because the attacker
was able to change the challenge ciphertext

from one recipient to another that
allows him to, to win the CCA game with

advantage one. So as I said, chosen
ciphertext security turns out actually is

the correct notion of security for public
key encryption systems. And it's a very,

very interesting concept, right? Basically, somehow
even though the attacker has this ability

to decrypt anything he wants. Other than
the challenge ciphertext, still he can't

learn what the challenge ciphertext is.
And so the goal for the remainder of this module

and actually the next module as well, is
to construct CCA secure systems. It's

actually quite remarkable that this is
achievable and I'm going to show you

exactly how to do it. And in fact those
CCA secure systems that we build are the

ones that are used in the real world. And
every time a system has tried to deploy

a public key encryption mechanism that's not
CCA secure someone has come up with an

attack and was able to break it. And we're
going to see some of these example attacks

actually in the next few segments.