Introduction to Modern Cryptography
Michele Ciampi
(Slides courtesy of Prof. Jonathan Katz)
Lecture 4, part 1
1 / 24
One-time Pad
2 / 24
One-time Pad (OTP)
▶ Patented in 1917 by Vernam
▶ Invented (at least) 35 years earlier
▶ Proven perfectly secret by Shannon (1949)
3 / 24
One-time Pad
▶ Let M = {0, 1}n
▶ Gen: choose a uniform key k ∈ {0, 1}n
▶ Enck (m) = k ⊕ m
▶ Deck (c) = k ⊕ c
▶ Deck (Enck (m)) = k ⊕ (k ⊕ m) = (k ⊕ k) ⊕ m = m
4 / 24
One-time Pad
5 / 24
Perfect Secrecy of One-time Pad
Theorem
The One-time Pad satisfies perfect secrecy.
Intuition
▶ Any observed ciphertext can correspond to any message
▶ (This is necessary, but not sufficient, for perfect secrecy)
▶ Having observed a ciphertext, the attacker cannot conclude
for certain which message was sent
6 / 24
Perfect Secrecy of One-time Pad
Proof.
▶ Fix arbitrary distribution over M = {0, 1}n , and choose
arbitrary m, c ∈ {0, 1}n
▶ Check if
Pr[M = m|C = c] = Pr[M = m]
7 / 24
Perfect Secrecy of One-time Pad
Proof.
▶ Recall (Bayes’ theorem)
Pr[C = c|M = m] Pr[M = m]
Pr[M = m|C = c] =
Pr[C = c]
▶ We can see that ∀c, m
Pr[C = c|M = m] = Pr[M ⊕ K = c|M = m] =
= Pr[m ⊕ K = c] = Pr[K = c ⊕ m] = 2−n
8 / 24
Perfect Secrecy of One-time Pad
Proof.
By law of total probability:
Pr[C = c] =
X
= Pr[C = c|M = m′ ] Pr[M = m′ ]
m′
X
= Pr[K = m′ ⊕ c|M = m′ ] Pr[M = m′ ]
m′
X
= 2−n Pr[M = m′ ]
m′
X
= 2−n Pr[M = m′ ] = 2−n
m′
9 / 24
Perfect Secrecy of One-time Pad
Proof.
Pr[M = m|C = c] =
Pr[C = c|M = m] Pr[M = m]
=
Pr[C = c]
2 −n Pr[M = m]
=
2−n
= Pr[M = m]
10 / 24
One-time Pad and Brute-force Attacks
▶ OTP resists even a brute-force attack
▶ Decrypt a ciphertext with every key returns every possible
plaintext (incl. every ASCII/English string)
▶ No way of telling the correct plaintext
Image credit: https://nakedsecurity.sophos.com
11 / 24
One-time Pad
▶ The One-time Pad achieves perfect secrecy!
▶ Resists even a brute-force attack
▶ One-time Pad has historically been used in the real world
▶ e.g. red phone between Washington and Moscow
▶ Not currently used! Why?
12 / 24
One-time Pad
Limitations of OTP
1. The key is as long as the message
2. A key must be used only once
▶ Only secure if each key is used to encrypt a single message
▶ (Trivially broken by a known-plaintext attack)
=⇒ Parties must share keys of (total) length equal to the
(total) length of all the messages they might ever send
13 / 24
Using the Same Key Twice?
▶ Say
c1 = k ⊕ m1
c2 = k ⊕ m2
▶ Attacker can compute
c1 ⊕ c2 = (k ⊕ m1 ) ⊕ (k ⊕ m2 ) = m1 ⊕ m2
▶ This leaks information about m1 , m2
14 / 24
Using the Same Key Twice?
m1 ⊕ m2 leaks information about m1 , m2
Is this significant?
▶ m1 ⊕ m2 reveals where m1 , m2 differ
▶ No longer perfectly secret!
▶ Exploiting characteristics of ASCII...
15 / 24
ASCII table (recall)
https://hubpages.com/technology/What-Are-ASCII-Codes
16 / 24
Using the Same Key Twice: recall ASCII
Observatoins
▶ Letters begin with 0x4, 0x5, 0x6 or 0x7
▶ =⇒ letters all begin with 01...
▶ ASCII code for the space character 0x20 = 00100000
▶ =⇒ the space character begins with 00...
▶ XOR of two letters gives 00...
▶ XOR of letter and space gives 01...
▶ Easy to identify XOR of letter and space!
17 / 24
Using the Same Key Twice
▶ The last byte of c1 ⊕ c2 starts with 01
▶ Therefore
c1 ⊕ c2 = m1 ⊕ m2 = x ⊕ 00100000
x = c1 ⊕ c2 ⊕ 00100000
▶ e.g. let c1 ⊕ c2 = 01010000
x = 01010000 ⊕ 00100000
x = 01110000 = 0x70 = ”p”
▶ Attacker learns one plaintext character: m1 = p or
m2 = p
18 / 24
One-time Pad
Drawbacks
▶ Key as long the message
▶ Only secure if each key is used to encrypt once
▶ Trivially broken by a known-plaintext attack
Note
These limitations are inherent for schemes achieving perfect
secrecy
19 / 24
Optimality of the One-time Pad
Theorem
If (Gen, Enc, Dec) with message space M is perfectly secret,
then |K| ≥ |M|.
Intuition
▶ Given any ciphertext, try decrypting under every possible
key in K
▶ This gives a list of up to |K| possible messages
▶ If |K| < |M| =⇒ some message is not on the list
20 / 24
Optimality of the One-time Pad
Proof.
▶ Assume |K| < |M|
▶ Need to show that there is a distribution on M, a message
m, and a ciphertext c such that
Pr[M = m|C = c] ̸= Pr[M = m]
21 / 24
Optimality of the One-time Pad
Proof.
▶ Take the uniform distribution on M
▶ Take any ciphertext c
▶ Consider the set M (c) = {Deck (c)}k∈K
▶ the set of messages that could yield the ciphertext c
▶ |M (c)| ≤ |K| < |M | =⇒ ∃m s.t. m ∈
/ M (c):
Pr[M = m|C = c] = 0 ̸= Pr[M = m]
22 / 24
Summary
▶ We defined the notion of perfect secrecy (PS)
▶ We proved that the One-time Pad achieves PS
▶ We proved that the One-time Pad is optimal (in the key
length)
▶ i.e. we cannot improve the key length
▶ Are we done? What about the limitations of OTP?
▶ Address OTP’s limitations by relaxing the definition
▶ But in a meaningful way...
▶ (next slides)
23 / 24
End
References: From Section 2.2 until the end of Chapter 2.
24 / 24
