CS306: Introduction to IT Security Fall 2020
Lecture 3: Perfect Secrecy
Instructor: Nikos Triandopoulos September 15, 2020
2
3.0 Announcements
CS306: Lab sections schedule
u labs
u CS306-Lx Thursdays
ZOOM ID: LAB SPECIFIC!
x
B
C
D
E
F
time
9:30 – 10:20
11:00 – 11:50
12:30 – 13:20
14:00 – 14:50
15:30 – 16:20
Zoom ID
91573945614
93061161569
94976630644
92834271191
94520991826
TAs
Dean, Joseph, Joshua, Uday
Dean, Devharsh, Joseph, Joshua
Dean/Devharsh, Joshua, Mohammad, Uday
Devharsh, Joseph, Mohammad, Uday
Dean, Joseph, Mohammad, Uday
3
CS306: Other announcements
u Lab #2 this Thursday
u Homework #1 this Friday
4
CS306: Tentative Syllabus
Week
Date
Topics
Reading
Assignment
1
Sep 1
Introduction
Lecture 1
–
2
Sep 8
Symmetric-key encryption
Lecture 2
Lab 1
3
Sep 15
Symmetric-key crypto II
4
Sep 22
Public-key crypto I
5
Sep 29
Public-key crypto II
6
Oct 6
Access control & authentication
–
Oct 13
No class (Monday schedule)
7
Oct 20
Midterm
All materials covered
5
CS306: Tentative Syllabus
(continued)
Week
Date
Topics
Reading
Assignment
8
Oct 27
Software & Web security
9
Nov 3
Network security
10
Nov 10
Database security
11
Nov 17
Cloud security
12
Nov 24
Privacy
13
Dec 1
Economics
14
Dec 8
Legal & ethical issues
15
Dec 10 (or later)
Final
(closed “books”)
All materials covered*
6
* w/ focus on what covered after midterm
Last week
u Introduction to the field of IT security u Basic concepts and terms
u Symmetric encryption
7
Today
u Symmetric-key Cryptography u Perfect secrecy
u The One-Time Pad cipher
u Demo
u Why encryption matters?
u Using the Wireshark packet analyzer
8
9
3.1 Perfect secrecy
Security tool: Symmetric-key encryption scheme
Abstract cryptographic primitive, a.k.a. cipher, defined by u a message space M; and
u a triplet of algorithms (Gen, Enc, Dec)
u Gen, Enc are probabilistic algorithms, whereas Dec is deterministic u Gen outputs a uniformly random key k (from some key space K)
M: set of possible messages
Gen
kEve k
Alice m Enc c
c’ m’Bob
Dec
10
Perfect correctness
For any k ∈ K , m ∈ M and any ciphertext c output of Enck(m), it holds that
Pr[Deck (c)=m]=1
11
Towards defining perfect security
u defining security for an encryption scheme is not trivial u e.g., what we mean by << Eve “cannot learn” m (from c) >> ?
u our setting so far is a random experiment u amessagemischosenaccordingtoDM
u akeykischosenaccordingtoDK
u Enck(m)→cisgiventotheadversary
how to define security?
12
Attempt 1: Protect the key k!
u Security means that
the adversary should not be able to compute the key k
u Intuition
u it’d better be the case that the key is protected!…
u Problem
u this definition fails to exclude clearly insecure schemes u e.g., the key is never used, such as when Enck(m) := m
necessary condition
but not
sufficient condition!
13
Attempt 2: Don’t learn m!
u Security means that
the adversary should not be able to compute the message m u Intuition
u it’d better be the case that the message m is not learned… u Problem
u this definition fails to exclude clearly undesirable schemes
u e.g., those that protect m partially, i.e., they reveal the least significant bit of m
14
Attempt 3: Learn nothing!
u Security means that
the adversary should not be able to learn any information about m u Intuition
u it seems close to what we should aim for perfect secrecy… u Problem
u this definition ignores the adversary’s prior knowledge on M u e.g., distribution DM may be known or estimated
u m is a valid text message, or one of “attack”, “no attack” is to be sent 15
Attempt 4: Learn nothing more!
u Security means that
the adversary should not be able to learn any additional information on m
u How can we formalize this? Eve
Eve’s view remains
the same! Eve c
Alice m Enck(m) → c
w/ prob. 0.8
w/ prob. 0.8
m =
attack
no attack w/ prob. 0.2
m =
attack
no attack w/ prob. 0.2
16
Two equivalent views of perfect secrecy
a posteriori = a priori
For every DM, m ∈ M and c ∈ C, for which Pr [C = c ] > 0, it holds that
Pr[ M = m | C = c ] = Pr[ M = m ]
~ C is independent of M For every m, m’ ∈ M and c ∈ C,
it holds that
Pr[ EncK(m) = c ] = Pr[ EncK(m’) = c ]
Eve’s view remains Eve
random experiment DM → m = M
DK → k = K Enck(m) → c = C
Eve
attack
no attack w/ prob. 0.2
the same!
c
attack
no attack w/ prob. 0.2
m =
w/ prob. 0.8
m =
w/ prob. 0.8
17
Perfect secrecy (or information-theoretic security)
Definition 1
A symmetric-key encryption scheme (Gen, Enc, Dec) with message space M,
is perfectly secret if for every DM, every message m ∈ M and every ciphertext c ∈ C for which Pr [C = c ] > 0, it holds that
Pr[ M = m | C = c ] = Pr [ M = m ]
u theaposterioriprobabilitythatanygivenmessagemwasactuallysent
u intuitively
is the same as the a priori probability that m would have been sent
u observingtheciphertextrevealsnothing(new)abouttheunderlyingplaintext 18
Alternative view of perfect secrecy
Definition 2
A symmetric-key encryption scheme (Gen, Enc, Dec) with message space M, is perfectly secret if for every messages m, m’ ∈ M and every c ∈ C, it holds that
Pr[ EncK(m) = c ] = Pr [ EncK(m’) = c ]
u intuitively
u theprobabilitydistributionDCdoesnotdependontheplaintext
u i.e.,MandCareindependentrandomvariables
u theciphertextcontains“noinformation”abouttheplaintext
u “impossibletodistinguish”anencryptionofmfromanencryptionofm’
19
20
3.2 The one-time pad
The one-time pad: A perfect cipher
A type of “substitution” cipher that is “absolutely unbreakable” u invented in 1917 Gilbert Vernam and Joseph Mauborgne
u “substitution” cipher
u individually replace plaintext characters with shifted ciphertext characters u independently shift each message character in a random manner
u to encrypt a plaintext of length n, use n uniformly random keys k1, . . . , kn u “absolutely unbreakable”
u perfectly secure (when used correctly)
u based on message-symbol specific independently random shifts
21
The one-time pad (OTP) cipher
Fix n to be any positive integer; set M = C = K = {0,1}n
u Gen: choose n bits uniformly at random (each bit independently w/ prob. .5)
u Gen → {0,1}n
u Enc: given a key and a message of equal lengths, compute the bit-wise XOR
u Enc(k, m) = Enck(m) → k ⊕ m (i.e., mask the message with the key) u Dec: compute the bit-wise XOR of the key and the ciphertext
u Dec(k,c)=Deck(c):=k⊕c u Correctness
u trivially,k⊕c=k⊕k⊕m=0⊕m=m 22
OTP is perfectly secure (using Definition 2)
For all n-bit long messages m1 and m2 and ciphertexts c, it holds that Pr[EK(m1)=c] = Pr[EK(m2)=c],
where probabilities are measured over the possible keys chosen by Gen.
Proof
u events “EncK(m1) = c”, “m1 ⊕ K = c” and “K = m1 ⊕ c” are equal-probable u K is chosen at random, irrespectively of m1 and m2, with probability 2-n
u thus, the ciphertext does not reveal anything about the plaintext
23
OTP characteristics
A “substitution” cipher
u encrypt an n-symbol m using n uniformly random “shift keys” k1, k2, . . . , kn 2 equivalent views
uK=M=C or
u “shift” method
Perfect secrecy
u since each shift is random, every ciphertext is equally likely for any plaintext Limitations (on efficiency)
u “shift keys” (1) are as long as messages & (2) can be used only once
view 1
{0,1}n
bit-wise XOR (m ⊕ k)
view2 G,(G,+)isagroup addition/subtraction (m +/- k)
24
Perfect, but impractical
In spite of its perfect security, OTP has two notable weaknesses u the key has to be as long as the plaintext
u limited applicability
u key-management problem
u the key cannot be reused (thus, the “one-time” pad)
u if reused, perfect security is not satisfied
u e.g., reusing a key once, leaks the XOR of two plaintext messages u this type of leakage can be devastating against secrecy
These weakness are detrimental to secure communication
u securely distributing fresh long keys is as hard as securely exchanging messages…
25
Importance of OTP weaknesses
Inherent trade-off between efficiency / practicality Vs. perfect secrecy u historically, OTP has been used efficiently & insecurely
u repeated use of one-time pads compromised communications during the cold war
u NSA decrypted Soviet messages that were transmitted in the 1940s
u that was possible because the Soviets reused the keys in the one-time pad scheme
u modern approaches resemble OTP encryption
u efficiency via use of pseudorandom OTP keys u “almost perfect” secrecy
26