CS155
Cryptography Overview
Cryptography
Is
A tremendous tool
The basis for many security mechanisms
Is not
The solution to all security problems
Reliable unless implemented properly
Reliable unless used properly
Something you should try to invent
or implement yourself
Kerckhoff’s principle
A cryptosystem should be secure
even if everything about the
system, except the secret key,
is public knowledge.
Goal 1:secure communication
Step 1: Session setup to exchange key
Step 2: encrypt data
Goal 2: Protected files
Disk
Alice File 1 Alice
No eavesdropping
No tampering
File 2
Analogous to secure communication:
Alice today sends a message to Alice tomorrow
Symmetric Cryptography
Assumes parties already
share a secret key
Building block: sym. encryption
nonce
Alice Bob
m, n E(k,m,n)=c c, n D(k,c,n)=m
E D
k k
E, D: cipher k: secret key (e.g. 128 bits)
m, c: plaintext, ciphertext n: nonce (aka IV)
Encryption algorithm is publicly known
• Never use a proprietary cipher
Use Cases
Single use key: (one time key)
• Key is only used to encrypt one message
• encrypted email: new key generated for every email
• No need for nonce (set to 0)
Multi use key: (many time key)
• Key used to encrypt multiple messages
• files: same key used to encrypt many files
First example: One Time Pad
(single use key)
Vernam (1917)
Key: 0 1 0 1 1 1 0 0 1 0
Plaintext:
⊕
1 1 0 0 0 1 1 0 0 0
Ciphertext: 1 0 0 1 1 0 1 0 1 0
Shannon ‘49:
OTP is “secure” against ciphertext-only attacks
Stream ciphers (single use key)
Problem: OTP key is as long the message
Solution: Pseudo random key -- stream ciphers
key
PRG
c⟵ PRG(k) ⊕m
⊕ message
ciphertext
Stream ciphers: ChaCha (643 MB/sec)
Dangers in using stream ciphers
One time key !! “Two time pad” is insecure:
C1 ⟵ m1 ⊕ PRG(k)
C2 ⟵ m2 ⊕ PRG(k)
Eavesdropper does:
C1 ⊕ C2 ⇒ m1 ⊕ m 2
Enough redundant information in English that:
m 1 ⊕ m2 ⇒ m1 , m2
Block ciphers: crypto work horse
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
IV handled as part of PT block
Building a block cipher
Input: (m, k)
Repeat simple “mixing” operation several times
DES: Repeat 16 times:
mL ⟵ mR
mR ⟵ mL⊕ F(k,mR)
• AES-128: Mixing step repeated 10 times
Difficult to design: must resist subtle attacks
• differential attacks, linear attacks, brute-force, …
Block Ciphers Built by Iteration
key k
key expansion
k1 k2 k3 kn
R(kn, )
R(k1, )
R(k2, )
R(k3, )
m c
R(k,m): round function
for DES (n=16), for AES-128 (n=10)
Incorrect use of block ciphers
Electronic Code Book (ECB):
PT: m1 m2
CT: c1 c2
Problem:
if m1=m2 then c1=c2
In pictures
Correct use of block ciphers: CTR mode
E(k,x): maps key k and n-bit block x to a n-bit block y
Counter mode (CTR) with a random IV:
IV m[0] m[1] … m[L]
E(k,IV) E(k,IV+1) … E(k,IV+L)
⊕
IV c[0] c[1] … c[L]
ciphertext
Note: Parallel encryption
Use cases: how to choose an IV
Single use key: no IV needed (IV=0)
Multi use key: (CPA Security)
Best: use a fresh random IV for every message
Can use unique IV (e.g 0, 1, 2, 3, …)
benefit: may save transmitting IV with ciphertext
uniqueIV counter
128 bits
In pictures
encrypt with CTR
Why is CTR secure? not today
Performance: [openssl speed]
Intel Core 2 (on Windows Vista)
Cipher Block/key size Speed (MB/sec)
ChaCha 643
3DES 64/168 30
AES-128/GCM 128/128 163
AES is dramatically faster with AES-NI instructions:
• Intel SkyLake: 4 cycles per round, fully pipelined
AESENC xmm15, xmm1
Data integrity
Message Integrity: MACs
Goal: message integrity. No confidentiality.
ex: Protecting public binaries on disk.
k k
Message m tag
Alice Bob
Generate tag: Verify tag: ?
tag ⟵ S(k, m) V(k, m, tag) = `yes’
note: non-keyed checksum (CRC) is an insecure MAC !!
Secure MACs
Attacker information: chosen message attack
for m1,m2,…,mq attacker is given ti ⟵ S(k,mi)
Attacker’s goal: existential forgery.
produce some new valid message/tag pair (m,t).
(m,t) ∈ { (m1,t1) , … , (mq,tq) }
A secure PRF gives a secure MAC:
S(k,m) = F(k,m)
V(k,m,t): `yes’ if t = F(k,m) and `no’ otherwise.
Construction 1: ECBC
m[0] m[1] m[2] m[3]
⊕ ⊕ ⊕
E(k,⋅) E(k,⋅) E(k,⋅) E(k,⋅)
Raw CBC
key = (k, k1) E(k1,⋅) tag
Construction 2: HMAC (Hash-MAC)
Most widely used MAC on the Internet.
H: hash function.
example: SHA-256 ; output is 256 bits
Building a MAC out of a hash function:
Standardized method: HMAC
S( k, m ) = H( k⊕opad || H( k⊕ipad || m ))
SHA-256: Merkle-Damgard
m[0] m[1] m[2] m[3]
IV H(m)
h h h h
h(t, m[i]): compression function
Thm 1: if h is collision resistant then so is H
“Thm 2”: if h is a PRF then HMAC is a PRF
Why are these MAC constructions secure?
… not today – take CS255
Why the last encryption step in ECBC?
CBC (aka Raw-CBC) is not a secure MAC:
Given tag on a message m, attacker can deduce
tag for some other message m’
How: good crypto exercise …
Authenticated Encryption:
Encryption + MAC
Combining MAC and ENC (CCA)
Encryption key KE MAC key = KI
Option 1: MAC-then-Encrypt (SSL)
MAC(M,KI) Enc KE
Msg M Msg M MAC
Option 2: Encrypt-then-MAC (IPsec)
Enc KE MAC(C, KI)
Secure for
all secure Msg M MAC
primitives
Option 3: Encrypt-and-MAC (SSH)
Enc KE MAC(M, KI)
Msg M MAC
Recommended mode (currently)
AES-GCM:
• encrypt-then-MAC
• Counter mode AES
• Carter-Wagman MAC
Public-key Cryptography
Public key encryption: (Gen, E, D)
Gen
pk sk
m c c m
E D
Applications
Session setup (for now, only eavesdropping security)
Alice Bob
pk
Generate (pk, sk)
choose random x
E(pk, x) (e.g. 48 bytes)
x
Non-interactive applications: (e.g. Email)
Bob sends email to Alice encrypted using pkalice
Note: Bob needs pkalice (public key management)
Applications
Encryption in non-interactive settings:
Encrypted File Systems
skA
write read
Alice
E(pkA, KF)
Bob File
E(kF, File) E(pkB, KF)
Applications
Encryption in non-interactive settings:
Key escrow: data recovery without Bob’s key
Escrow
Service
write
skescrow
E(pkescrow, KF)
Bob
E(kF, File) E(pkB, KF)
Trapdoor functions (TDF)
Def: a trapdoor func. X⟶Y is a triple of efficient
algs. (G, F, F-1)
• G(): randomized alg. outputs key pair (pk, sk)
• F(pk,⋅): det. alg. that defines a func. X⟶Y
• F-1(sk,⋅): func. Y ⟶ X that inverts F(pk,⋅)
Security: F(pk, ⋅) is one-way without sk
Public-key encryption from TDFs
• (G, F, F-1): secure TDF X ⟶ Y
• (Es, Ds) : symm. auth. encryption with keys in K
• H: X ⟶ K a hash function
We construct a pub-key enc. system (G, E, D):
Key generation G: same as G for TDF
Public-key encryption from TDFs
• (G, F, F-1): secure TDF X ⟶ Y
• (Es, Ds) : symm. auth. encryption with keys in K
• H: X ⟶ K a hash function
E( pk, m) : D( sk, (y,c) ) :
x⟵ R
X, y ⟵ F(pk, x) x ⟵ F-1(sk, y),
k ⟵ H(x), c ⟵ Es(k, m) k ⟵ H(x), m ⟵ Ds(k, c)
output (y, c) output m
In pictures:
F(pk, x) Es( H(x), m )
header body
Security Theorem:
If (G, F, F-1) is a secure TDF,
(Es, Ds) provides auth. enc.
and H: X ⟶ K is a “random oracle”
then (G,E,D) is CCAro secure.
Digital Signatures
Public-key encryption
Alice publishes encryption key
Anyone can send encrypted message
Only Alice can decrypt messages with this key
Digital signature scheme
Alice publishes key for verifying signatures
Anyone can check a message signed by Alice
Only Alice can send signed messages
Digital Signatures from TDPs
(G, F, F-1): secure TDP X ⟶ X
H: M ⟶ X a hash function
Sign( sk, m∈X) : Verify( pk, m, sig) :
output output
sig = F-1(sk, H(m) ) 1 if H(m) = F(pk, sig)
0 otherwise
Security: existential unforgeability under a chosen message
attack (in the random oracle model)
Public-Key Infrastructure (PKI)
Anyone can send Bob a secret message
… provided they know Bob’s public key
How do we know a key belongs to Bob?
If imposter substitutes another key, can read Bob’s
messages
One solution: PKI
Trusted root Certificate Authority (CA)
CA certifies that a given public-key belongs to Bob
… more on this next time
Putting it all together: SSL/TLS (simplified)
Client-hello
Server-hello
Key exchange
Server-key-exchange
C S
Client key-exchange
finished
finished
Confirmation
Encrypted session
Limitations of cryptography
Cryptography works when used correctly !!
… but is not the solution to all security problems
XKCD 538
