CS408

Cryptography & Internet Security

Lecture 5:
One-time pad

Reza Curtmola
Department of Computer Science
NJIT

The One-Time Pad (OTP)

l Basic Idea:
§ Use a key as long as the plaintext
§ The key is a random string
l Encryption: perform XOR between
plaintext and key
l Decryption: perform XOR between
ciphertext and key

CS 408 Lecture 5 / Spring 2015 2

1
 The One-Time Pad (OTP)
l Use the binary representation (plaintext, key, ciphertext are
sequences of 0s and 1s)
§ Plaintext is x = (x1, x2, …, xn)
§ Key is k = (k1, k2, …, kn)
§ Ciphertext is y = (y1, y2, …, yn)
l Encryption: y = Ek(x) = (x1⊕k1, x2 ⊕k2,…, xn ⊕kn)
l Decryption: x = Dk(y) = (y1⊕k1, y2 ⊕k2,…, yn ⊕kn)

l ⊕ means exclusive OR (XOR), it is a binary bitwise operator

§ 0 ⊕ 0 = 0; 0 ⊕ 1 = 1; 1 ⊕ 0 = 1; 1 ⊕ 1 = 0
§ a ⊕ b is equivalent with (a+b) mod 2

l For example:
§ Plaintext is 11011011
§ Key is 01101001
§ Then ciphertext is 10110010 (note, there is no carriage!)
CS 408 Lecture 5 / Spring 2015 3

Bit Operators
l Bitwise AND
0∧0=0 0∧1=0 1∧0=0 1∧1=1

l Bitwise OR
0∨0=0 0∨1=1 1∨0=1 1∨1=1

l Addition mod 2 (also known as Bitwise XOR)

0 ⊕0=0 0⊕1=1 1⊕0=1 1⊕1=0

CS 408 Lecture 5 / Spring 2015 4

2
 How Secure is the One-Time Pad?
l Intuitively, it is secure …
l The key is random, so the ciphertext is
completely random

CS 408 Lecture 5 / Spring 2015 5

Is one-time pad practical?

l Remember:
§ The key must be chosen at random
§ The key must be at least as long as the plaintext
§ The key must never be reused
l One-time pad is not practical because:
§ Keys can be very long: expensive to produce and
expensive to transmit
§ A key cannot be reused (every encryption must use a
different key, which should be established through a
secure channel before the actual communication)

CS 408 Lecture 5 / Spring 2015 6

3
 Is one-time pad practical?
l Distributing one-time pad keys is inconvenient
and poses significant security risk
§ Large storage media can be used to carry a large one-
time pad key (e.g., thumb drives, DVDs, etc.)
§ The large one-time pad key can then be used to
encrypt many shorter messages
§ Still, it may be a challenge:
• to securely transport the media device
• to securely destroy the device
A 4.7 GB DVD-R full of one-time-pad data, if shredded into
particles 1 mm² in size, leaves over 100 kibibits of (admittedly
hard to recover, but not impossibly so) data on each particle.
(from Wikipedia)

CS 408 Lecture 5 / Spring 2015 7

Names connected with OTP"

l Co-inventors of One-time-pad"
§ Joseph Mauborgne (1881-1971) became a
Major General in the United States Army"
§ Gilbert Vernam (1890 - 1960), was AT&T Bell
Labs engineer"
l Security of OTP"
§ Claude Shannon (1916 - 2001), American
electronics engineer and mathematician, was
“the father” of information theory. "

CS 408 Lecture 5 / Spring 2015 8

4
 Some historical facts
l VENONA project:
§ during WWII, the US and the UK intercepted
encrypted messages sent by the intelligence agencies
of the Soviet Union
§ The Soviets made the mistake of reusing one-time
pads for encrypting messages
§ The encrypted messages were decrypted gradually
between 1946 - 1980

CS 408 Lecture 5 / Spring 2015 9

Shannon (Information-Theoretic) Security

l Basic Idea: Ciphertext should provide no information

about Plaintext
l We also say such a scheme has perfect secrecy.
§ No matter how powerful an adversary is, the scheme cannot be
broken if it has perfect secrecy
l One-time pad has perfect secrecy
§ E.g., suppose that the ciphertext is “wpslq”, can we say any
plaintext is more likely than another plaintext?

l Result due to Shannon, 1949.

C. E. Shannon, Communication Theory of Secrecy Systems , Bell
System Technical Journal, vol.28-4, pp 656--715, 1949.

CS 408 Lecture 5 / Spring 2015 10

5
 Unconditional Security

l The adversary has unlimited

computational resources.
l Analysis is made by using probability
theory.
l Perfect secrecy: observation of the
ciphertext provides no information to
an adversary.
l Result due to Shannon, 1949.
C. E. Shannon, Communication
Theory of Secrecy Systems , Bell
System Technical Journal, vol.28-4,
pp 656--715, 1949.

CS 408 Lecture 5 / Spring 2015 11

Security of one-time pad

l What happens if key is reused in one-
time pad?
§ y1 = Ek(x1) = x1 ⊕ k
y2 = Ek(x2) = x2 ⊕ k
§ Then, adversary can compute
y1 ⊕ y2 = x1 ⊕ k ⊕ x2 ⊕ k = x1 ⊕ x2
If adversary knows x1, it can find out x2!

CS 408 Lecture 5 / Spring 2015 12

6
 Begin Math

CS 408 Lecture 5 / Spring 2015 13

Random Variable
Definitions
l A random variable is a variable whose value is not known,
and which can take different values
§ A probability distribution describes the probabilities of different
values occurring
l A discrete random variable, X, consists of:
§ a countable set X of values it may take (e.g., a set of integers)
§ a probability distribution defined over X

The probability that the random variable X takes on the

value x is denoted Pr[X =x]; sometimes, we will abbreviate
this to Pr[x] if the random variable X is fixed.
It must be that:

0 " Pr[x] " 1 for all x # X

$ Pr[x] = 1
x #X

CS 408 Lecture 5 / Spring 2015 14

7
 Relationships between Two Random Variables
Definitions
Assume X and Y are two random variables, we define:
l conditional probability: Pr[x|y] is the probability that X
takes on the value x given that Y takes value y
l

l joint probability: Pr[x, y] = Pr[x|y] Pr[y] = Pr[y|x] Pr[x] is

the probability that X takes value x and Y takes value y

l independent random variables: X and Y are said to be

independent if Pr[x,y]=Pr[x] Pr[y], for all x ∈ X and all
y∈Y

CS 408 Lecture 5 / Spring 2015 15

Elements of Probability Theory

Find the conditional probability of event X given the conditional
probability of event Y and the unconditional probabilities of events
X and Y.

Bayes’ Theorem
If Pr[y] > 0 then:

Pr[x]Pr[y | x]
Pr[x | y] =
Pr[y]

Corollary
X and Y are independent random variables if and only if
! Pr[x|y] = Pr[x], for all x ∈ X and all y ∈ Y.

CS 408 Lecture 5 / Spring 2015 16

8
 End Math

CS 408 Lecture 5 / Spring 2015 17

Ciphers Modeled by Random Variables

Consider a cipher (P, C, K, E, D). We assume that:
1. there is a probability distribution on the plaintext
(message) space
2. the key space also has a probability distribution. We
assume:
• the key is chosen before the message and
• the key and the plaintext are independent random variables
3. the ciphertext is also a random variable

CS 408 Lecture 5 / Spring 2015 18

9
 Perfect Secrecy

Definition
Informally, perfect secrecy means that an
attacker can not obtain any information about
the plaintext by observing the ciphertext.

What type of attack is this?

Definition
A cryptosystem has perfect secrecy if
Pr[x|y] = Pr[x], for all x ∈ P and y ∈ C,
where P is the set of plaintexts and C is the set
of ciphertexts.

CS 408 Lecture 5 / Spring 2015 19

What can I say about Pr[x|y] and Pr[x], for all x ∈ P and y ∈ C,
Don t know it, but can
given be computed
Bayes: Pr[x]Pr[y | x]
Pr[x | y] =
Pr[y]
KNOWN: Pr[x], Pr[k] Don t know it, but can
be computed
C(k): the set of all possible ciphertexts if key is k.

!
Pr[y] = # Pr[k]Pr[x] Pr[y | x] = " Pr[k]
k:y "C (k ) k:x= Dk (y )

Pr[x]
!
" Pr[k]
! Pr[x | y] = k:x= D k (y )

" Pr[k] Pr[x]

k:y #C ( k )

CS 408 Lecture 5 / Spring 2015 20

10
 One-time Pad has Perfect Secrecy
l P, C, K = {0,1}n , key k is chosen at random and is
used once per message
l We need to show that ∀x ∀y, Pr[x | y] = Pr[x]
(for all plaintexts and ciphertexts, the prob. of finding
information about the plaintext x given a ciphertext y is
the same as the prob. of finding information about the
plaintext given just x)

Pr[x|y] = Pr[x] Pr[y|x] / Pr[y] (cf. Bayes theorem)

= Pr[x] Pr[k] / ∑x∈X (Pr[x] Pr[k])
= Pr[x] 1/2n / ∑x∈X (Pr[x] 1/2n)
= Pr[x] / ∑x∈X (Pr[x])
= Pr[x]

CS 408 Lecture 5 / Spring 2015 21

Modern Cryptography

l One-time pad requires the length of

the key to be the length of the
plaintext and the key to be used only
once. Difficult to manage.
l Alternative: design cryptosystems,
where a key is used more than once.
l What about the attacker? Resource
constrained, make it infeasible for
adversary to break the cipher.

CS 408 Lecture 5 / Spring 2015 22

11
 Theoretically-motivated Principles
l Change frequently all cryptographic keys

l Make plaintext as random as possible

(e.g., via compression)

l Use probabilistic encryption

CS 408 Lecture 5 / Spring 2015 23

Recommended Reading

l Chapter 2.9
l Chapter 15.4
(for Perfect Secrecy of OTP)

CS 408 Lecture 5 / Spring 2015 24

12