Information theoretic security and the one time pad (19 min)

Now that we've seen a few examples of
historic ciphers, all of which are badly

broken, we're going to switch gears and
talk about ciphers that are much better

designed. But before we do that, I want to,
first of all, define more precisely what a

cipher is. So first of all, a cipher is
actually, remember a cipher is made up of

two algorithms. There's an encryption
algorithm and a decryption algorithm. But

in fact, a cipher is defined over a
triple. So the set of all possible keys,

which I'm going to denote by script K, and
sometimes I'll call this the key space,

it's the set of all possible keys. There's
this set of all possible messages and this

set of all possible ciphertexts. Okay, so
this triple in some sense defines the

environment over which the cipher is
defined. And then the cipher itself is a

pair of efficient algorithms E and D. E is
the encryption algorithm; D is the

decryption algorithm. Of course, E takes
keys and messages. And outputs ciphertexts.

And the decryption algorithm takes
keys and ciphertexts. Then outputs messages.

And the only requirements is that these
algorithms are consistent. They satisfy

what's called the correctness property. So
for every message in the message space.

And every key. In the key space, it had
better be the case that if I encrypt the

message with the key K and then I decrypt
using the same key K I had better get back

the original message that I started with.
So this equation here is what's called the

consistency equation and every cipher has
to satisfy it in order to be a cipher

otherwise it's not possible to decrypt.
One thing I wanted to point out is that I

put the word efficient here in quotes. And
the reason I do that is because efficient

means different things to different
people. If you're more inclined towards

theory, efficient means runs in polynomial
time. So algorithms E and D have to run in

polynomial time in the size of their
inputs. If you're more practically

inclined, efficient means runs within a
certain time period. So for example,

algorithm E might be required to take
under a minute to encrypt a gigabyte of

data. Now either way, the word efficient
kind of captures both notions and you can

interpret it in your head whichever way
you'd like. I'm just going to keep

referring to it as efficient and put
quotes in it as I said if you're theory

inclined think of it as polynomial time,
otherwise think of it as

concrete time constraints. Another comment
I want to make is in fact algorithm E.

It's often a randomized algorithm. What
that means is that as your encrypting

messages, algorithm E is gonna generate
random bits for itself, and it's going to

use those random bits to actually encrypt
the messages that are given to it. On the

other hand the decrypting algorithm is
always deterministic. In other words given

the key and the ciphertext output is
always the same. Doesn't depend on any

randomness that's used by the algorithm.
Okay, so now that we understand what a

cipher is better, I want to kind of show
you the first example of a secure cipher.

It's called a one time pad It was designed
by Vernam back at the beginning of the

twentieth century. Before I actually
explain what the cipher is, let's just

state it in the terminology that we've
just seen. So the message space for the

Vernam cipher for the one-time pad is the
same as the ciphertext space which is

just the set of all ended binary strings.
This, this just means all sequences of

bits, of zero one characters. The key
space is basically the same as the message

space which is again simply the embed of
all binary strings. So a key in the one

time pad is simply a random big string,
it's a random sequence of bits. That's as

long as the message to be encrypted, as
long as the message. Okay, now that we've

specified kind of what's the cipher's
defined over we can actually specify how

the cipher works and it's actually really
simple. So essentially the ciphertexts.

Which is the result of encrypting a
message with a particular key, is simply

the XOR of the two. Simply K XOR M. [inaudible] see a quick example of

this. Remember that XOR, this plus
with a circle. XOR means addition

modulo two. So if I take a particular
message, say, 0110111. And it take a

particular key, say 1011001. When I
compute the encryption of the message

using this key, all I do is I
compute the XOR of these two

strings. In other words, I do addition
module or two bit by bit. So I get one,

one, zero, one, one, one, zero. That's a
ciphertext. And then how do I decrypt? I

guess they could do kind of the same
thing. So they decrypt a cipher text using

a particular key. What I do is I XOR the
key and the ciphertext again. And so all

we have to verify is that it satisfies the
consistency requirements. And I'm going to

do this slowly once and then from now on
I'm going to assume this is all, simple to

you. So we're gonna make, we're gonna have
to make sure that if I decrypt a cipher

text, that was encrypted using a
particular key, I had better get. Back the

message M. So what happens here? Well,
let's see. So if I look at the encryption

of k and m, this is just k XOR m by
definition. What's the decryption of k XOR

m using k? That's just k XOR (k XOR
m). And so since I said that XOR is

addition modulo two, addition is
associative, so this is the same as (k XOR k)

XOR m, which is simply as you know k XOR k is a zero, and zero XOR anything

is simply m. Okay, so this actually shows
that the one-time pad is in fact a cipher,

but it doesn't say anything about the
security of the cipher. And we'll talk

about security of the cipher in just a
minute. First of all, let me quickly ask

you a question, just to make sure we're
all in sync. Suppose you are given a

message m and the encryption of that
message using the one time pad. So all

you're given is the message and the cipher
text. My question to you is, given this

pair m and c, can you actually figure out
the one-time pad key that was used in the

creation of c from m?

So I hope all of you
realize that in fact, given the message in

the cipher text it's very easy to recover
what the key is. In particular the key is

simply M XOR C. Then we'll see that if
it's not immediately obvious to you we'll

see why that's, the case, a little later
in the talk, in the lecture. Okay alright

so the 1-time pad is a really cool from a
performance point of view all you're doing

is you exo-ring the key in the message so
it's a super, super fast. Cypher for

encrypting and decrypting very long
messages. Unfortunately it's very

difficult to use in practice. The reason
it's difficult to use is the keys are

essentially as long as the message. So if
Alice and Bob want to communicate

securely, so you know Alice wants to send
a message end to Bob, before she begins

even sending the first bit of the message,
she has to transmit a key to Bob that's as

long as that message. Well, if she has a
way to transmit a secure key to Bob that's

as long as the message, she might as well
use that same mechanism to also transmit

the message itself. So the fact that the
key is as long as the message is quite

problematic and makes the one-time pad
very difficult to use in practice.

Although we'll see that the idea behind
the one-time pad is actually quite useful

and we'll see that a little bit later. But
for now I want to focus a little bit on

security. So the obvious questions are,
you know, why is the one-time pad secure?

Why is it a good cypher? Then to answer
that question, the first thing we have to

answer is, what is a secure cipher to
begin with? What is a, what makes cipher

secure? Okay, so the study, security of
ciphers, we have to talk a little bit

about information theory. And in fact the
first person, to study security of ciphers

rigorously. Is very famous, you know, the
father of information theory, Claude

Shannon, and he published a famous paper
back in 1949 where he analyzes the

security of the one-time pad. So the idea
behind Shannon's definition of security is

the following. Basically, if all you get
to see is the cypher text, then you should

learn absolutely nothing about the plain
text. In other words, the cypher text

should reveal no information about the
plain text. And you see why it took

someone who invented information theory to
come up with this notion because you have

to formulize, formally explain what does
information about the plain text actually

mean. Okay so that's what Shannon did and
so lemme show you Shannon's definition,

I'll, I'll write it out slowly first. So
what Shannon said is you know suppose we

have a cypher E D that's defined over
triple K M and C just as before. So KM and

C define the key space, the message space
and the cypher text space. And when we say

that the cypher text sorry we say that the
cypher has perfect secrecy if the

following condition holds. It so happens
for every two messages M zero and M1 in

the message space. For every two messages
the only requirement I'm gonna put on

these messages is they have the same
length. Yeah so we're only, we'll see why

this requirement is necessary in just a
minute. And for every cyphertext, in the

cyphertext space. Okay? So for every pair
of method messages and for every cipher

text, it had better be the case that, if I
ask, what is the probability that,

encrypting N zero with K, woops.
Encrypting N zero with K gives C, okay? So

how likely is it, if we pick a random key?
How likely is it that when we encrypt N

zero, we get C. That probability should be
the same as when we encrypt N1. Okay, so

the probability of encrypting n one and
getting c is exactly the same as the

probability of encrypting n zero and
getting c. And just as I said where the

key, the distribution, is over the
distribution on the key. So, the key is

uniform in the key space. So k is uniform
in k. And I'm often going to write k arrow

with a little r above it to denote the
fact that k is a random variable that's

uniformly sampled in the key space k.
Okay, this is the main part of Shannon's

definition. And let's think a little bit
about what this definition actually says.

So what does it mean that these two
probabilities are the same? Well, what it

says is that if I'm an attacker and I
intercept a particular cypher text c, then

in reality, the probability that the
cypher text is the encryption of n zero is

exactly the same as the probability that
it's the incryption of n one. Because

those probabilities are equal. So if I
have, all I have the cypher text C that's

all I have intercepted I have no idea
whether the cypher text came from M zero

or the cypher text came from M one because
again the probability of getting C is

equally likely whether M zero is being
encrypted or M one is being encrypted. So

here, we have the definition stated again.
And I just wanna write these properties

again more precisely. So let's write this
again. So what [inaudible] definition

means is that if I am given a particular
cipher text, I can't tell where it came

from. I can't tell if it's, if the message
that was encrypted. Is either N zero or N

one and in fact, this property is true for
all messages. For all these N zero, for

all N zero and N ones. So not only can I
not tell if'c' came from N zero or N one,

I can't tell if it came from N two or N
three or N four or N five because all of

them are equally likely to produce the
cypher text'c'. So what this means really

is that if you're encrypting messages with
a one time pad then in fact the most

powerful adversary, I don't really care
how smart you are, the most powerful

adversary. Can learn nothing about the
plain text, learns nothing about the plain

text. From the cypher text. So to say it
in one more way, basically what this

proves is that there's no, there's no
cypher text-only attack on a cypher that

has perfect secrecy. Now, cypher attacks
actually aren't the only attacks possible.

And in fact, other attacks may be
possible, other attacks may be possible.

Okay. Now that we understand what perfect
secrecy, means, the question is, can we

build ciphers that actually have perfect
secrecy? And it turns out that we don't

have to look very far, the one time
pattern fact has perfect secrecy. So I

want to prove to you this is Shannon's first
results and I wanna prove this fact to

you, it's very simple proof so let's go
ahead and look at it and just do it. So we

need to kind of interpret what does that
mean, what is this probability that E K M

Z is equal to C. So it's actually not that
hard to see that for every message and

every cyphertext the probability that the
encryption of N under a key K the

probability that, that's equal to C, the
probability that our random choice of key

by definition. All that is, is basically
the number of keys. Kay, instruct Kay.

Such that, well. If I encrypt. And with k
I get c. So I literally count the number

of keys and I divide by the total number
of keys. Right? That's what it means, that

if I choose a random key, that key maps m
to c. Right. So it's basically the number

of key that map n to c divided by the
total number of keys. This is its

probability. So now suppose that we had a
cypher such that for all messages and all

cypher texts, it so happens that if I look
at this number, the number of k, k, and k,

such that e, k, m is equal to c. In other
words, I'm looking at the number of keys

that map m to c. Suppose this number
happens to be a constant. So say it

happens to be two, three, or ten or
fifteen. It just hap, happens to be an

absolute constance. If that's the case,
then by definition, for all n0 and n1 and

for all c, this probability has to be the
same because the denominator is the same,

the numerator is the same, it's just as
constant, and therefore the probability is

always the same for all n and c. And so if
this property is true, then the cypher has

to have, the cypher has perfect secrecy.
Okay, so lets see what can we say about

this quantity for the one time pad. So the
sec-, so, the question to you is, if I

have a message in a cipher-text, how many
one time pad keys are there [inaudible]

map, this message ends, so the [inaudible]
C? So, in other words, how many keys are

there, such that M XOR K is equal to C?
So I hope you've all answered one. And

let's see why that's the case. For the one
time pad, if we have that, the encryption

of K of M under K is equal to C. But
basically, well, by definition, that

implies that K XOR M is equal to C. But
that also simply says that K has to equal

to M XOR C. Yes, I just X over both
sides by M and I get that K must equal the

M XOR C. Okay? So what that says is
that, for the one time pad, in fact, the

number of keys, in K, shows the EKM, is
equal to C. That simply is one, and this

holds for all messages in cipher text. And
so, again, by what we said before, it just

says that the one time pad has, perfect
secrecy. Perfect secrecy and that

completes the proof of this [inaudible]
very, very simple. Very, very simple

lemma. Now the funny thing is that
even though this lemma is so simple to

prove in fact it proves a pretty powerful
statement again. This basically says for

the one time [inaudible] there is no
cypher text only attack. So, unlike the

substitution cipher, or the vigenere
cipher, or the roller machines, all those

could be broken by ciphertext-only attack.
We've just proved that for the one-time

pad, that's simply impossible. Given the
cyphertext, you simply learn nothing about

the plaintext. However, as we can see,
this is simply not the end of the story. I

mean, are we done? I mean, basically,
we're done with the course now, cuz we

have a way. To encrypt, so that an
attacker can't recover anything about our

method. So maybe we're done with the
course. But in fact, as we'll see, there

are other attacks. And, in fact, the one
time pad is actually not such a

secure cipher. And in fact, there are
other attacks that are possible, and we'll

see that shortly. Okay? I emphasize again
the fact that it has perfect secrecy does

not mean that the one time pad is the
secure cypher to use. Okay. But as we said

the problem with the one time pad is that
the secret key is really long. If you had

a way of. Communicating the secret key
over to the other side. You might as well

use that exact same method to also
communicate the message to the other side,

in which case you wouldn't need a cypher
to begin with. Okay? So the problem again

is the one time pad had really long keys
and so the obvious question is are there

other cyphers that has perfect secrecy and
possibly have much, much shorter keys?

Well, so the bad news is the Shannon,
after proving that the one-time pad has

perfect secrecy, proved another theorem
that says that in fact if a cypher has

perfect secrecy, the number of keys in the
cypher must be at least the number of

messages that the cypher can handle. Okay,
so in particular, what this means is if I

have perfect secrecy. Then necessarily the
number of keys, or rather the length of my

key, must be greater than the length of
the message. So, in fact, since the one

time pad satisfies us with equality, the
one time pad is an optimal, cipher that

has perfect secrecy, okay? So basically,
what this shows is that this is an

interesting notion. The one time pad is an
interesting cipher. But, in fact, in

reality, it's actually quite hard to use.
It's hard to use in practice, again,

because of these long keys. And so this
notion of perfect secrecy, even though

it's quite interesting, basically says
that it doesn't really tell us the

practical cyphers are going to be secure.
And we're gonna see, but, as we said, the

idea behind the one time pad is quite good.
And we're gonna see, in the next lecture,

how to make that into a practical
system.