CEG5105

Cybersecurity for Computer

Systems
Encryption

1
Outline

• History of ciphers
• Perfectly secret encryption
• Vernam’s cipher
• Symmetric key encryption: Block ciphers, AES
• Secret sharing
• Asymmetric encryption

2
 Setting of Symmetric / Private-
key Encryption
k k

plaintext encryption ciphertext decryption

message, m algorithm Enc (m) algorithm m = Dec (Enc (m))
k k k

• Alice and bob share the same (symmetric) key: k

• How do they agree on a key value?

3
Syntax of Encryption

• Key generation algorithm: Gen is a probabilistic

algorithm that outputs a key k chosen according to
some distribution
• The encryption algorithm: Enc takes as input a key k
and a plaintext m and outputs a ciphertext c. We
denote the encryption of the plaintext by Enck(m)
• The decryption algorithm Dec takes as input a key k
and a ciphertext c and outputs a plaintext m. We
denote the decryption of the ciphertext by Deck(c)

4
Syntax of Encryption

• The correctness requirement of any encryption

scheme is that for every key k output by Gen and
every plaintext message m∈M, it holds that
Deck(Enck(m)) = m

• Alice and Bob must share k secretly. How about Enc

and Dec algorithms?

5
Attack Scenarios
• Ciphertext only attack:
• adversary can only observe the cyphertext
• Known-plaintext attack:
• adversary learns one or more pairs of plaintexts/ciphertexts
encrypted under the same key
• Chosen-plaintext attack:
• adversary has the ability to obtain the encryption of any plaintext(s)
of its choice
• Chosen-ciphertext attack:
• adversary has the ability to obtain the decryption of any ciphertext(s)
of its choice

6
Historical Ciphers: Caesar’s Cipher
Caesar cipher: shift cypher

e.g.: plaintext:begin the attack now

ciphertext:EHJLQWKHDWWDFNQRZ

Encryption key: shift amount (e.g., k=-3)

7
Historical Ciphers: Caesar’s Cipher

• What is the problem Caesar’s Cipher?

• Can you decrypt the following cipher without
knowing the key?

OVDTHUFWVZZPISLRLFZHYLAOLYL

Any secure encryption scheme must have a key

space that is not vulnerable to exhaustive search.

8
 Historical Ciphers: Substitution Cipher
• Monoalphabetic substitution cipher: substitute one letter
for another
plaintext:
ciphertext:

e.g.: plaintext: tellhimaboutme

ciphertext: GDOOKVCXEFLGC

Encryption key: mapping from set of 26 letters

to set of 26 letters

What is the size of keyspace?

9
Historical Ciphers: Substitution Cipher

• Although the mono-alphabetic substitution cipher has a

very large key space, it is still completely insecure.

A large key space is necessary but not sufficient for a

secure cipher!
10
A more sophisticated cipher
 n substitution ciphers, M1,M2,…,Mn
 cycling pattern:
• e.g., n=4: M1,M3,M4,M3,M2; M1,M3,M4,M3,M2; ..
 for each new plaintext symbol, use subsequent substitution
pattern in cyclic pattern
• dog: d from M1, o from M3, g from M4

Encryption key: n substitution ciphers, and cyclic pattern

• key need not be just n-bit pattern

11
Enigma

Encryption key:
• Plugboard setting: similar to substitution cypher
• Rotor arrangement: E.g., 2 – 3 – 1
• Rotor orientation: C – K – F
12
Defining Security for Encryption
• How to formalize the desired notion of security for
symmetric key encryption?
• An encryption scheme is secure if no adversary can…

• Answer 1: find the secret key when given a ciphertext.

• Answer 2: find the plaintext that corresponds to the

ciphertext.

• Answer 3: determine any character of the plaintext that

corresponds to the ciphertext.
13
Defining Security for Encryption
• How to formalize the desired notion of security for
symmetric key encryption?
• An encryption scheme is secure if no adversary can…

• Answer 4: derive any meaningful information about the

plaintext from the ciphertext.

• Answer 5: compute any function of the plaintext from the

ciphertext.

14
Perfectly Secret Encryption

Definition: An encryption scheme (Gen, Enc, Dec) over

a message space M is perfectly secret if for every
probability distribution over M, every message m ∈ M,
and every ciphertext c ∈ C for which Pr[C = c] > 0:

Pr[M = m | C = c] = Pr[M = m]

• Show that this is equivalent to:

Pr[C = c | M = m] = Pr[C = c]

15
Perfectly Secret Encryption:
An example
• Message (M) is either:
• m0 = don’t attack tomorrow
• m1 = attack tomorrow
• Choose key (K) based on a coin flip
• Ciphertext (C) is
• original message if heads
• flipped message if tails

• Observing ciphertext has no effect on the knowledge of the

adversary!
• Pr[M = m | C = c] = Pr[M = m]
16
Perfectly Secret Encryption:
One-Time Pad (Vernam 1917)
• Key Generation: 𝑘𝑘 is chosen uniformly from K = {0,1}l

• Encryption: Given a message 𝑚𝑚 ∈ {0,1}𝑙𝑙 and a key 𝑘𝑘 ∈ {0,1}l the

output is
𝑐𝑐 ≔ 𝑘𝑘 ⊕ 𝑚𝑚

• Decryption: Given the key 𝑘𝑘 ∈ {0,1}𝑙𝑙 and cyphertext 𝑐𝑐 ∈ {0,1}𝑙𝑙 ,

the output is
𝑚𝑚 ≔ 𝑘𝑘 ⊕ 𝑐𝑐

17
Perfectly Secret Encryption at a
lower price?
Theorem: Let (Gen, Enc, Dec) be a perfectly-secret encryption scheme
over a message space M, and let K be the key space as determined by
Gen.
Then |K| ≥ |M|.
A cipher must be practically, if not mathematically, indecipherable.
- Kerckhoffs

• Can we use a short key (e.g., hundreds of bits) to securely

encrypt many long messages?
Modern cryptography,
• Limits the computational power of adversary
• Allows a negligible probability of success for adversary
• Computational security rather than information theoretically
(perfectly) secure
18
Computational Security

• Concrete approach:
• With key length n, an adversary running in time t
succeeds in breaking the scheme with probability t/2n.
• Asymptotic approach: Probabilistic Polynomial
Time (PPT) adversary
• Efficient algorithms: for constants 𝑎𝑎, 𝑐𝑐 the algorithms run
in 𝑎𝑎 × 𝑛𝑛𝑐𝑐 time on security parameter 𝑛𝑛.
• Small probability of success: adversary wins with
probability less than any inverse polynomial in n. E.g.,
𝑛𝑛−𝑐𝑐 .

19
PPT adversary: Examples

• Secure scheme 1: an adversary running for n3

minutes can succeed in breaking the scheme with
probability 240 · 2−n
• Secure scheme 2:
• Honest parties run 106 · n2 cycles
• Adversary runs 108 · n4 cycles
• Adversary wins with probability 220 · 2-n

Asymptotic security does not depend on any

specific assumptions regarding, e.g., the type of
computer an adversary will use.

20
Definitions of Computationally-
Secure Symmetric-key Encryption
Algorithms:
• Gen: takes as input the security parameter 1n and
outputs a key k:
k  Gen(1n)
• Enc: takes as input a key k and a plaintext message
m ∈ {0, 1}∗, and outputs a ciphertext c:
c  Enck(m)
• Dec: takes as input a key k and a ciphertext c, and
outputs a message m.
m := Deck(c)

21
Definitions of Computationally-
Secure Symmetric-key Encryption
Adversary (Eve):
• Eavesdrops (cipher-text only)
• but can be more powerful! (later)
• Runs in polynomial time
Security objective:
• Eve should not learn any partial information about
the plaintext from ciphertext
• Equivalent to indistinguishability:
• Eve cannot tell apart Enck(m1) and Enck(m2) even if she
chooses m1 and m2 of the same length.

22
How to Generate
Randomness
• We need random values for Key Generation
algorithm. E.g., generating a random pad.
• Different kinds of random events:
• Coin flip, dice roll
• CPU temperature
• Camera, microphone signals
• Hard disk speed variations
• Atmospheric noise measurements: www.random.org
• Radioactive decay
• Quantum measurements

23
Pseudorandomness
• A pseudorandom string looks like a uniformly distributed string, as long as
the entity that is “looking” runs in polynomial time.
• Refers to a distribution on strings not a fixed string.
• Completely deterministic, but looks like random.
• Long pseudorandom string can be generated from a relatively short random
seed (or key)

Information Theoretical Computational

perfect secrecy indistinguishability

true randomness pseudorandomness

24
Stream Ciphers – A Secure Fixed
Length Encryption Scheme
• Uses pseudo-random generator (PRG) to generate
pseudorandom stream
• Key Generation: k  {0,1}𝑛𝑛 chosen uniformly at
random
• Encryption: c ≔ m ⊕ PRG(k)
• Decryption: m ≔ c ⊕ PRG(k)

Similar to OTP. What is gained here?

25
Stream Ciphers – Secure
Multiple Encryptions
• Uses pseudo-random generator (PRG) to generate
pseudorandom stream from key and initialization
vector (IV)
• Key Generation: k  {0,1}𝑛𝑛 chosen uniformly at
random
• Encryption: c ≔ m ⊕ PRG(k, 𝐼𝐼𝐼𝐼)
Send IV, c
• Decryption: m ≔ c ⊕ PRG(k, 𝐼𝐼𝐼𝐼)

26
Security under Chosen-
Plaintext Attacks (CPA)
• Adversary is allowed to ask for encryptions of multiple
messages that it chooses
plaintext
Encryption
oracle
ciphertext

• Recall indistinguishability:
• Eve must not be able to tell apart Enck(m1) and Enck(m2)
• But Eve can request oracle encrypt the messages m1 and m2
and thus obtain Enck(m1) and Enck(m2)!
No deterministic encryption scheme can be secure
against chosen-plaintext attacks
27
CPA in Practice
• An example from WW2:
• In May 1942, US Navy cryptanalysts discovered that
Japan was planning an attack on Midway island
• They learned this by intercepting a communication
message containing the ciphertext fragment “AF”
believed to be “Midway island”
• They instructed the US forces at Midway to send a
plaintext message that their freshwater supplies were
low
• The Japanese intercepted this message and
immediately reported that “AF” was low on water.
• Evidence that “AF” was indeed Midway

28
Pseudorandom Functions
• Pseudorandomness is instrumental constructing CPA-secure
encryption. Consider keyed function F:

F ∶ {0, 1}∗ × {0, 1}∗ → {0, 1}∗

key (k) input

• Key is chosen uniformly at random and fixed:

Fk: {0, 1}∗ → {0, 1}∗
input

• Fk is pseudorandom function if it is indistinguishable

from a function chosen at random from the set of
functions having same domain and range
29
Stream Ciphers – CPA Secure
Encryption Scheme
• Uses pseudo-random function (PRF) to generate
stream from random value ‘𝑟𝑟’ and key

• Key Generation: k  {0,1}n chosen uniformly at

random
• Encryption: c ≔ m ⊕ PRFk(𝑟𝑟) with 𝑟𝑟  {0,1}n
chosen uniformly at random
Send 𝑟𝑟,c
• Decryption: m ≔ c ⊕ PRFk(𝑟𝑟)

30
Block Ciphers and
Pseudorandom Permutations
• Pseudo-random permutation (PRP) is a one-to-
one keyed PRF
• All PRPs are also PRFs, therefore we can replace
PRPs PRFs in any construction
• Block cipher is in fact a pseudorandom
permutation
• Encrypt each block separately. Padding is done to
align data size to the block size

31
Block Ciphers
• Message to be encrypted P C P C
processed in blocks of n 00 10 00 11
bits
01 11 01 00
• Cipher uses a one-to-one
mapping to map n bits of 10 01 10 01
plaintext to n bit 11 00 11 10
cyphertext …
• Set of all one-to-one P C P C
functions = Number of 00 11 00 01
possible mappings: 2n!
01 10 01 00
• Each mapping stores 2n
entries 10 01 10 11
11 00 11 10
32
Block Ciphers

• Block ciphers should be viewed as pseudorandom

permutations and not as encryption schemes.
• DES and AES are standardized block ciphers. They
are efficient and have been intensively scrutinized.
• We do not aim to construct a new block cipher,
rather provide an intuition as to how modern block
ciphers are constructed and why.

33
Block Ciphers – Confusion
Diffusion Paradigm
Shannon introduced a basic paradigm for
constructing concise random-looking functions.
• Confusion: Each bit of the ciphertext should depend on
several parts of the key, obscuring how key affects
ciphertext
• Diffusion: if we change a single bit of the plaintext, then
about half of the bits in the ciphertext should change
• The repeated use of confusion and diffusion ensures that
any small changes in the input propagate quickly to very
large changes  avalanche effect

34
Block Ciphers – Substitution-
permutation Networks
• Layers of substitution
and permutation
• Substitution: apply small
random functions
• Permutation: mix the
outputs of the random
functions
• Repeat many times
• S-box must be invertible
(1-to-1) and onto.

35
Advanced Encryption
Standard (AES)
• Substitution- permutation network.
• Block sizes of 128, 192, or 256 bits.
• 4 Stages in every round of AES (10-14 rounds):
• AddRoundKey: a 16 byte round key is derived from the
master key, and is interpreted as a 4 by 4 array of bytes
• SubBytes: Substitution based on a single fixed lookup
table
• ShiftRows: cyclically shift bytes to the left
• MixColumns: invertible linear transformation

36
Advanced Encryption
Standard (AES)

Substitution

Permutation

37
Limitations of Private-Key
Encryption
• Requires sender, receiver know
shared secret key
• Options:
• Physically meet somewhere
• Use trusted messenger service
• In a company with E employees,
what is the storage complexity for
each pair of employee to share a
secret key?
• Q: how to agree on key in first
place (particularly if never “met”)?

38
Secret Sharing:
Key Distribution Centers
Key Distribution Center

‘Alice wishes to
communicate with Bob’

Use K_AB as a shared secret

• What are the benefits and disadvantages?

• How many keys are stored by each employee?
• What happens when a new employee joins?
• What if KDC crashes, or is compromised?
• E.g., Needham-Schroeder protocol
39
Diffie-Helman Key Exchange
(1976)
• Can we use encryption without
first sharing a secret?
• Asymmetry: easy to multiply
two large primes but difficult to
recover these primes from their
product
• Interactive key-exchange
protocol where parties without
any secret information generate
a secret key by communicating
over an open network

40
Diffie-Helman Key Exchange
(1976)
1. Alice and Bob agree on two large prime numbers, p and 𝑔𝑔, and a
public key exchange algorithm.
2. Alice chooses a secret integer 𝑎𝑎, and computes 𝐴𝐴 = 𝑔𝑔𝑎𝑎 mod p.
She sends A to Bob.
3. Bob chooses a secret integer 𝑏𝑏, and computes 𝐵𝐵 = 𝑔𝑔𝑏𝑏 mod p.
He sends B to Alice.
4. Alice computes 𝑘𝑘 = 𝐵𝐵𝑎𝑎 mod p. Bob computes 𝑘𝑘 = 𝐴𝐴𝑏𝑏 mod p.
5. Alice and Bob now both have shared secret key 𝑘𝑘, which they can
use to encrypt communications

41
 Asymmetric/Public-key
Encryption

pk sk

plaintext encryption ciphertext decryption

message, m algorithm Enc (m) algorithm m = Decsk(Encpk(m))
pk

• A receiver generates public key (pk) and private key

(sk)
• Solves the key distribution problem
• Many senders, one receiver need only a pair of keys.
• Much more expensive. 100-1000 times more!

42