CS254 – Network Security

Crypto intro
Jan 27, 2025

1
 Logistics
2

 This Wed: proposal presentation

 Attack & tool presentation next two Weds (Feb 7

and Feb 14)

 In-class quiz about crypto (next Thursday or

afterwards)
 Today’s Class
3

Essential Cryptography
 Symmetric Key Encryption
 Stream and Block Ciphers
 Message-Authentication Codes
 Hash Functions
 Key Establishment
 Asymmetric (Public Key) Encryption
 One-slide takeaway
4

 Extremely tricky to get right

 Basic Cryptography Problems
5
Defends against off-path attacker automatically

Message

Eve
Alice Passive Eavesdropper Bob

Mallory

Man-in-the-Middle
 Ingredients for a Secure Channel
6

Confidentiality Eve
Attacker can’t see the message
Symmetric Ciphers

Integrity
Mallor
Attacker can’t modify the message y
Message Authentication Codes (MACs)
 Confidentiality - Symmetric Key Encryption
7

Encryption Decryption

plaintext ciphertext
plaintext

K encrypt(.) K decrypt(.)

ciphertext ciphertext
plaintext
 Substitution cipher
8

 K = A -> T
B -> X
C -> S
…
Z -> D

E (K, “ABCZ”) = “TXSD”

D (K, “TXSD”) = “ABCZ”
 How to break substitution cypher?
9

 Stats: The most common letter in English

 “E” ~ 12.7%
 “T” ~ 9.1%

…

 Stats: The most common pairs of letters in English

 “HE”

 “AN”

…

 Given ciphertext → plaintext

 Vigener cipher (16th century, Rome)
10

BEAUT I FULN I GHT

+ (mod 26) H E L L O H E L L O H E L L

J J MG U Q K G X C Q L T F

Weakness:
Assume “I” is the most common letter → “Q” is the most common in encrypted letters
→ The first letter of key is “Q” – “I” = “H”
 One-Time Pads
11

First example of a

Provably secure encryption…

Yet may not be practical

 One-Time Pads: 1882
12

P1 P2 P3 P4

 K1 K2 K3 K4

P1  K1 P2  K2 P3  K3 P4  K4

Pi  K i Pi Ki
0 0 0
0 1 1
1 0 1
1 1 0
 Problems with One-Time Pads
13

 Long keys (as long as plaintext)

 Used in special cases in history
 Not practical
◼ Assumes the key safely exchanged
◼ Might as well exchange the plaintext itself

 Improvement
 Stream cipher
 Stream cipher: making OTP practical
14

 Idea: replace “random” key with “pseudorandom” key

 Exchange once, useful for many messages!

 Pseudo Random Generator (PRG):

Key  Message

N bits
(seed)
N << M
M bits
 PRG must be unpredictable
15

 Suppose it is, given earlier bits 1 to i, we can

predict bit i+1 to n

 Plaintext attack can reverse the partial key and

infer the entire key
 An example of HTTP GET request
(known plaintext attack)
16

GET
 Weak PRG
17

 X(n) = a*X(n-1) + b mod c

 Linear-Congruential Generators
 Nice properties of statistical randomness, but
predictable
 Fixed total number of states, will repeat at some point

 Glibc random() is also predictable

 r[i]
= (r[i-3] + r[i-31]) % 2^32
 Output r[i] >> 1
 Two-time pad vulnerability
18

 C1 = M1  PRG(K)
 C2 = M2  PRG(K)
 C1  C2 = ?
 Two-time pad vulnerability
19

 C1 = M1  PRG(K)
 C2 = M2  PRG(K)
 C1  C2 = M1  M2
 Two-time pad vulnerability
20

 C1 = M1  PRG(K)
 C2 = M2  PRG(K)
 C1  C2 = M1  M2

 English encoded in ASCII allows

M1  M2 → M1, M2 (recovery fairly easy)
“”= 0100000
“A” – “Z” = 10XXXXX
“A”  “B” = 00000011
“A”  “C” = 00000010
 Two-time pad vulnerability
21

 Never re-use stream cipher key more than once!

 Example failure: MS-PPTP using the same key bytes
twice (in two directions)
 Another example: 802.11b WEP (PRG seed recycles
every 16M frames)

 Session key (e.g., SSL and TLS)

 Negotiate new key every time, one for client->server,
one for server->client.
 Never reuse the key
22

 If you truly want to reuse the same seed (but

different keys) to generate multiple messages
 One way: use PRG(i || K) for ith message
 A better way

K K1 K2 K3 K4 …

M1 M2 M3 M4
 Block ciphers
25

n bits n bits

PT Block E, D CT Block

Key k bits

Canonical examples:
1. 3DES: n= 64 bits, k = 168 bits
2. AES: n=128 bits, k = 128, 192, 256 bits
 ECB – Electronic Codebook Mode
26

Ci := E(K, Pi) for i = 1, …, n

P1 P2 P3 P4 …

EK EK EK EK

C1 C2 C3 C4 …
 ECB – Electronic Codebook Mode
27

Ci := E(K, Pi) for i = 1, …, n

P1 P2 P3 P4 …

EK EK EK EK

C1 C2 C3 C4 …
 Why not ECB?
28

 The cipher text of an identical block is always

identical… consider a bitmap image…

(plaintext) (ECB mode) (CBC mode)

 CBC: Cipher-Block Chaining Mode
29

Ci := E(K, Pi  Ci-1) for i = 1, …, n

P1 P2 P3 …

?   

EK EK EK

C1 C2 C3 …
 CBC: Cipher-Block Chaining Mode
30

Ci := E(K, Pi  Ci-1) for i = 1, …, n

P1 P2 P3 …

  

Random
“Initialization EK EK EK
Vector”

IV C1 C2 C3 …
 CBC: Cipher-Block Chaining Mode
31

Ci := E(K, Pi  Ci-1) for i = 1, …, n

P1 P2 P3 …

  

Random
“Initialization EK EK EK
Vector”

IV C1 C2 C3 …

DO NOT REUSE INITIALIZATION VECTORS!!

 Block Ciphers Built by Iteration
32

key k

key expansion

k1 k2 k3 kn

R(kn,.)
R(k1,.)

R(k2,.)

R(k3,.)

m c
 AES: state-of-the-art (2000)
33
One block
 AES: state-of-the-art (2000)
34
One block
 How Safe is AES?
35

 Known attacks against 128-bit AES if reduced to 7

rounds (instead of 10)
 128-bit AES very widely used,
though NSA requires 192- or 256-bit keys for
SECRET and TOP SECRET data
 CPU cache timing side channel attacks
 Lookup table access?

 What should you use?

 Conservative answer: Use 256-bit AES
 So far, confidentiality only, but no integrity
36

 c=mk
 Attacker can change the ciphertext by
cp
 When decrypted,
(c  p)  k = ?
(c  p)  k = ((m  k)  p)  k = m  p
 Assuming m has a single bit.
1 indicates attack
 0 indicates retreat
 Can always force the wrong decision (not knowing what m is)
 Integrity
37

 Goal: Integrity, independent of confidentiality

 Example:
 Protecting public binaries on disk
 Protecting ads on web pages
 Attack against integrity
38

 OTP is vulnerable (malleable)

 m -> E (  k) -> m  k
p 

m p <- D (  k) <- (m  k)  p

Modifications are undetectable

And have predictable impact
 Attack against integrity (known
plaintext)
39

 “From Bob…” -> E=“From Bob…”  k

???


“From Eve”

Bob  Eve = 0x07 0x19 0x07

 Integrity:
40
Message Authentication Code (MAC)

k k
message m tag
Alice Bob

Generate tag: Verify tag:

tag  S(k, m) V(k, m, tag) =? ‘yes’

Typical solution is to compute a hash function

as the tag = H(m, k)
 Integrity requires a secret key
41

message m tag
Alice Bob

Generate tag: Verify tag:

?
tag  CRC(m) V(m, tag) = `yes’
Is it safe to use a checksum function?

 Attacker can easily modify message m and re-

compute CRC.

 CRC designed to detect random, not malicious

errors.
 Hash Functions
42

 Ideal: Random
mapping from
any arbitrary-size input
to a fixed size output
 Hash Function Requirements
43

 First pre-image
 Given h(x), find x

 Second pre-image
 Given m1, find m2 s.t. h(m1) = h(m2)

 Collision
 Given nothing, find any m1 != m2 s.t. h(m1) = h(m2)
 Birthday Attack: 70% for 30 students
 MD5 Hash Function
44

 Designed in 1992 by
Ron Rivest
 128-bit output
 128-bit internal state

 512-bit block size

 Like most hash functions,

uses block-chaining
construction
 MD5 is Unsafe – Never use it!
45

 First flaws in 1996;

by 2007, researchers
demonstrated a
collision
 Dec. 2008:
others used this to fake
SSL certificates (cluster
of 200 PS3s)
 MD5 Collision
46

d131dd02c5e6eec4693d9a0698aff95c 2fcab58712467eab4004583eb8fb7f89
55ad340609f4b30283e488832571415a 085125e8f7cdc99fd91dbdf280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e2b487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080a80d1e c69821bcb6a8839396f9652b6ff72a70

d131dd02c5e6eec4693d9a0698aff95c 2fcab50712467eab4004583eb8fb7f89
55ad340609f4b30283e4888325f1415a 085125e8f7cdc99fd91dbd7280373c5b
d8823e3156348f5bae6dacd436c919c6 dd53e23487da03fd02396306d248cda0
e99f33420f577ee8ce54b67080280d1e c69821bcb6a8839396f965ab6ff72a70

Both of these blocks hash to 79054025255fb1a26e4bc422aef54eb4

 SHA Hash Functions
47

 SHA-1 – standardized by NIST in 1995

 160-bit output and internal state
 512-bit block size

 SHA-2 – extension published in 2001

 256 (or 512)-bit output and internal state
 512 (or 1024)-bit block size

 SHA-3 – chosen by NIST in 2012

 256 (512)-bit output
 Different “sponge” construction
 Construction of MAC
51

Assuming we have a good hash function H:

Basic idea: Key is hashed together with the message
MAC1(K,m) = H (K || m)?
MAC2(K,m) = H (H (m) || K)?
 Vulnerable MAC construction?
52

 H (K||m) = H (K||m1,m2, …,mn) = MAC

 Length extension attack
 Length Extension Attack
54

 Block-Chaining Construction
 Also known as Merkle-Damgaard hash

 Vulnerable to length extension attack

 MAC = H (K||m1||..mn)

 Modified m and MAC

 MACA = H (MAC || mn+1)
 mA = m1||..mn|| mn+1
 HMAC is not vulnerable
55

 HMAC(K,m) = H( (K  opad) || H(K  ipad || m))

HMAC provides nice provable security properties

 Symmetric Key Encryption
56

Encryption Decryption

plaintext ciphertext
plaintext

K encrypt(.) K decrypt(.)

ciphertext ciphertext
plaintext
 Key establishment:
Chicken-and-egg problem
57

 How do we share our symmetric key in front of an

eavesdropping adversary?
 Can this be done with an exponential gap?

Eavesdropper??
 Public Key Cryptography
58

 Symmetric key cryptographic is great… but has the

fundamental problem that every send-receiver
pair must establish a secret out of nothing …
 Hard to bootstrap!
 Can we rely on some public info that everyone agrees
on?

 Also known as “Asymmetric Encryption”

 Diffie-Hellman Key Exchange
59

 “Key Exchange” developed by Whitfield Diffie and

Martin Hellman in 1976

 Based on Discrete Log Problem which we believe is

difficult (“the assumption”)
 “One-way” functions
 bk = a → finding the integer k is difficult
◼k = logb a
 Diffie-Hellman Key Exchange
60

1. Alice generates and shares g with Bob

2. Alice and Bob each generate a secret number, which
we denote x and y (“private key”)
3. Alice generates gx and sends it to Bob (“public key”)
4. Bob generates gy and sends it to Alice (“public key”)
5. Alice calculates (gy)x and Bob calculates (gx)y
6. Alice and Bob have (gy)x = gxy = gyx = (gx)y
 Attacking Diffie-Hellman (MITM)
61

Mallory

Chooses
random x gx
Chooses
random v gv
Chooses
random y
gy
Chooses
gw random w

k := (gw)x k := (gw)x k’ := (gv)y

k’ := (gv)y
 Summary of Goals
62

Confidentiality

Integrity

Authentication
 Public Key Cryptography
63

• Two keys
– Private key (sk) known only to individual
– Public key (pk) available to anyone
Alice Bob

c = E(m, pkbob) m = D(c, skbob)

m E c D

pkbob Key pair skbob

 Public Key Encryption

Def: a public-key encryption system is a triple of algs.

(G, E, D)
 G(): randomized alg. outputs a key pair (pk, sk)
 E(m, pk): alg. that takes m∈M and outputs c∈C
 To talk to a person, we use their public key to encrypt

 D(c, sk): alg. that takes c∈C and outputs m∈M or

error
 Only that person can decrypt
Public-Key Encryption Applications

 Non-interactive:
 Secure Email (PGP): Bob has Alice’s pub-key and sends
her an email
 Encrypted File Systems
skA
write read
Alice

E(pkA, data)
Bob File
E(pkB, data)
 Establishing a Shared Secret –
eavesdropping attacker only
Key exchange (e.g., in HTTPS)

Alice Bob

(pk, sk) ⟵ G()

“Alice”, pk
choose random
x ∈ {0,1}128
 Insecure Against Man-in-The-Middle
As described, the protocol is insecure against active attacks

Alice MiTM Bob

(pk, sk) ⟵ G() (pk’, sk’) ⟵ G()

“Alice”, pk
choose random
x ∈ {0,1}128

“Bob”, E(pk, x) “Bob”, E(pk’, x)

 Public Key Encryption –
Integrity/Authenticity
Alice Bob

(pk, sk) ⟵ G()

Still a chicken-and-egg problem?

How can Bob obtain Alice’s pk?

 Establishing Trust
69

 How can Bob know what Alice’s public key is?

 Web of Trust (e.g. PGP)

 Decentralized – everybody can publish their own
public key

 Trust on First Use (TOFU) (e.g. SSH)

 Public Key Infrastructure (PKI) (e.g. SSL)

 Centralized
 What is PKI?
70

 Organizations we trust (often known as

“Certificate Authorities”) generate certificates to
tie a public key to an organization

 We trust that we’re talking to the correct

organization if we can verify their public key with a
trusted authority
 In the Hands of Few
71

 Symantec (which bought VeriSign's SSL interests)

with 35.7% market share
 Comodo SSL with 26.9%
 GlobalSign with 14.9%
 Go Daddy with 13.0%
 DigiCert with 3.4%

 Alternative: DANE (DNSSEC-based)

 SSL/TLS Certificates
72

Subject: C=US/O=Google Inc/CN=www.google.com

Issuer: C=US/O=Google Inc/CN=Google Internet Authority
Serial Number: 01:b1:04:17:be:22:48:b4:8e:1e:8b:a0:73:c9:ac:83
Expiration Period: Jul 12 2010 - Jul 19 2012
Public Key Algorithm: rsaEncryption
Public Key:
43:1d:53:2e:09:ef:dc:50:54:0a:fb:9a:f0:fa:14:58:ad:a0:81:b0:3d
7c:be:b1:82:19:b9:7c3:8:04:e9:1e5d:b5:80:af:d4:a0:81:b0:b0:68:5b:a4:a4
:ff:b5:8a:3a:a2:29:e2:6c:7c3:8:04:e9:1e5d:b5:7c3:8:04:e9:39:23:46

Signature Algorithm: sha1WithRSAEncryption

Signature: 39:10:83:2e:09:ef:ac:50:04:0a:fb:9a:f0:fa:14:58:ad:a0:81:b0:3d
7c:be:b1:82:19:b9:7c3:8:04:e9:1e5d:b5:80:af:d4:a0:81:b0:b0:68:5b:a4:a4
:ff:b5:8a:3a:a2:29:e2:6c:7c3:8:04:e9:1e5d:b5:7c3:8:04:e9:1e:5d:b5
 Signatures on Certificates
73

 c = E(m, sk) // only owner can encrypt

 m = D(c, pk) // anyone can decrypt
 Mathematical properties (e.g., RSA)

 signature = E(sk, certificate)

 <signature, certificate> can be validated by anyone (but too long)

 Oftentimes see a signature algorithm such as sha1WithRSAEncryption

 Sigature = EncryptSK(SHA-1(certificate))

 SHA-1(certificate) = DecryptPK(signature)
 Certificate Chains
74

Firefox / Chrome / Edge

Trust everything
signed by this
“root” certificate Subject: C=US/…/OU=Equifax Secure Certificate Authority
Issuer: C=US/…/OU=Equifax Secure Certificate Authority
Public Key:
Signature: 39:10:83:2e:09:ef:ac:50:04:0a:fb:9a:38:c9:d1
I authorize and
trust this certificate;
here is my Subject: C=US/…/CN=Google Internet Authority
signature Issuer: C=US/…/OU=Equifax Secure Certificate Authority
Public Key:
I authorize and Signature: be:b1:82:19:b9:7c:5d:28:04:e9:1e:5d:39:cd
trust this certificate;
here is my Subject: C=US/…/O=Google Inc/CN=*.google.com
signature Issuer: C=US/…/CN=Google Internet Authority
Public Key:
Signature: bf:dd:e8:46:b5:a8:5d:28:04:38:4f:ea:5d:49:ca
 Certificate Authority Clusterfuck
75
 Public Key Cryptography -- putting
everything together – SSL/TLS
Client Server
(pk, sk) ⟵ G()

cert (pk, signature)

validate signature: it is google.com, and signed by trusted CAs

choose random
session key k c = E(k, pk)

k = D(c, sk)

What if MiTM attacker replay or tamper with the message ?

 Public Key Cryptography -- putting
everything together – SSL/TLS
Client Server
(pk, sk) ⟵ G()
client hello: client_random

server hello: server_random

cert (pk, signature)

validate signature
choose random
pre-master key k c = E(k, pk)

k = D(c, sk)
real key = PRF(k, "master secret", ClientHello.random + ServerHello.random)

Finished: summary = E(hash(all_previous_msgs), sk)

 Relationship between HTTPS and
78
SSL/TLS
 SSL/TLS is a generic cryptographic protocol. SSL
initially, later TLS (successor).

 HTTPS uses SSL/TLS

 SSH uses SSL/TLS as well
 Some Practical Advice
79

 HMAC: HMAC-SHA256

 Block Cipher: AES-256

 Randomness: OS Cryptographic Pseudo Random

Number Generator (CPRNG)

 Public Key Encryption: RSA or ECDSA

 Implementation: OpenSSL
 Don’t Roll Your Own!!
80