Cryptography Review Day: Ensuring Privacy, Integrity, and Authenticity

Cryptography: Review Day David Brumley dbrumley@cmu.edu Carnegie Mellon University

m or error m Public Channel c c D Bob Alice E ke ke Eve read/write access Cryptonium Pipe Goals: Privacy, Integrity, and Authenticity 2

3

Privacy and Encryption 4

Perfect Secrecy [Shannon1945] (Information Theoretic Secrecy) Defn Perfect Secrecy (informal): We re no better off determining the plaintext when given the ciphertext. Alice Bob 1. Eve observes everything but the c. Guesses m1 2. Eve observes c. Guesses m2 Goal: Eve 5

The One Time Pad Miller, 1882 and Vernam, 1917 M = C = K = {0,1}n m: k: 0 1 1 1 1 0 0 1 1 0 1 0 0 0 c: 1 0 1 1 1 1 0 k: m: 1 0 1 1 0 1 1 0 0 1 0 1 0 0 6

PRNGs, Stream Cipher PRNG(k): Amplify a small amount of randomness k. Stream Cipher: PRNG(k) xor M 7

Block Ciphers Modes of operations CBC, CTR, etc. What modes do for security, e.g., why ECB is bad, why randomize an IV for CBC, etc. Definitions Is a block cipher a PRP or PRF Attacks 8

Exhaustive Search for block cipher key Goal: given a few input output pairs (mi, ci = E(k, mi)) i=1,..,n find key k. Attack: Brute force to find the key k. Homework: What is the probability that the key k found with one <m,c> pair is correct? For two pairs? 9

Meet in the middle attack Define 2E( (k1,k2), m) = E(k1 , E(k2 , m) ) key-len = 112 bits for 2DES E(k2, ) E(k1, ) c m m c' c c Idea: key found when c = c : E(ki, m) = D(kj, c) 10

Semantic security under CPA Modes that return the same ciphertext (e.g., ECB, CTR) for the same plaintext are not semantically secure under a chosen plaintext attack (CPA) (many-time-key) m0, m0 M C0 E(k,m) m0, m1 M Cb E(k,mb) Challenger Adversary A k K if cb = c0 output 0 else output 1 11

Semantic security under CPA Modes that return the same ciphertext (e.g., ECB, CTR) for the same plaintext are not semantically secure under a chosen plaintext attack (CPA) (many-time-key) m0, m0 M C0 E(k,m) m0, m1 M Cb E(k,mb) Challenger Adversary A k K if cb = c0 output 0 else output 1 Encryption modes must be randomized or use a nonce (or are vulnerable to CPA) 12

Hashes and MACS 13

Message Integrity Goal: integrity (not secrecy) Examples: Protecting binaries on disk. Protecting banner ads on web pages Security Principles: Integrity means no one can forge a signature 14

Secure PRF: An Alternate Interpretation For b = 0,1 define experiment EXP(b) as: Challenger F b Adversary b Def: PRF is a secure PRF if for all efficient A, A does no better than guessing for b . 15

Secure MAC Game Challenger Adversary A 1. k = KeyGen(l) m1,...,mq 2. Picks m1, ..., mq 3. Compute i in 0...q: ti = S(mi, k) t1,...,tq m,t 4. picks m not in m1,...,mq Generates t 5. b = V(m,t,k) existential forgery if b= yes b = {yes,no} Security goal: A cannot produce a valid tag on a message Even if the message is gibberish 16

Birthday Paradox Rule of Thumb Given N possibilities, and random samples x1, ..., xj, PR[xi = xj] 50% when j = N1/2 17

One-way and Collision Resistance f is one-way if there is no computationally efficient Adversary given f(x) =y that can find a x such that f(x ) = y f is collision resistant if it is difficult to find two inputs x and x such that f(x) = f(x ) These are different concepts! (Think of a collision resistant function that is not one way) 18

Generic attack on hash functions Let H: M {0,1}n be a hash function ( |M| >> 2n ) Generic alg. to find a collision in time O(2n/2) hashes Algorithm: 1. Choose 2n/2random messages in M: m1, , m2n/2 (distinct w.h.p ) 2. For i = 1, , 2n/2 compute ti = H(mi) {0,1}n 3. Look for a collision (ti = tj). If not found, got back to step 1. How well will this work? 19

Brute Force Online Brute Force Attack: input: hp = hash(password) to crack for each i in dictionary file if(h(i) == hp) output success; Time Space Tradeoff Attack: precompute: h(i) for each i in dict file in hash tbl input: hp = hash(password) check if hp is in hash tbl rainbow tables 20

Salts Enrollment: 1. 2. compute hp=h(password + salt) store salt || hp Verification: 1. 2. Look up salt in password file Check h(input||salt) == hp What is this good for security, given that the salt is public? Salt doesn t increase security against online attack, but does make tables much bigger. 21

Authenticated Encryption 22

Motivating Question: Which is Best? Encryption Key = KE; MAC key = kI Option 1: SSL (MAC-then-encrypt) E(kE , m||tag) m S(kI, m) tag m m tag Option 2: IPsec (Encrypt-then-MAC) E(kE, m) m S(kI , c) tag m m Option 3: SSH (Encrypt-and-MAC) E(kE, m) m S(kI , m) tag m m 23

An authenticated encryptionsystem (E,D) is a cipher where As usual: E: K M N C but D: K C N M { } reject ciphertext as invalid Security: the system must provide Semantic security under CPA attack, and ciphertext integrity. The attacker cannot create a new ciphertext that decrypts properly. 24

CCA Game Definition Let ENC = (E,D) over (K,M,C). For b = {0,1} randomly chosen for i=1, ,q: (1) CPA query: Chal. k K Adv. b mi,0 , mi,1 M : |mi,0| = |mi,1| Ex: could query a changed ci ci E(k, mi,b) (2) CCA query: ci C : ci {c1, , ci-1} b {0,1} mi D(k, ci) 25

Public Key Cryptography 26

1. Pick a from [0,p-1) 2. Pick b from [0,p-1) 3. ga mod p Bob Alice 4. gb mod p 5. Compute (ga)b mod p as secret key 6. Compute (gb)a mod p as secret key Eve Eve observes: g, ga, gb Goal: compute a (or b) (i.e., calculate the discrete log) or compute gab 27

MITM Adversary As described, Diffie-Hellman is insecure against active Man In The Middle (MITM) attacks Alice MITM Bob ga mod p gm mod p gm mod p gb mod p gmb mod p gma mod p 28

Easy and Hard Problems Factoring Discrete Log Exponentiation 29

Questions? 30

Questions? 31

END

Thought 33

Public Key Encryption Def: a public-key encryption system is a triple of algorithms (G, E, D) G(): randomized alg. outputs a key pair (pk, sk) E(pk, m): randomized alg. that takes m M and outputs c C D(sk,c): determisitic alg. that takes c C and outputs m M or Consistency: (pk, sk) output by G : m M: D(sk, E(pk, m) ) = m Note: Without randomization, an attacker can determine E(pk,m1) = E(pk,m2) when m1=m2 34

Semantic Security For b=0,1 define experiments EXP(b) (i.e., EXP(0) and EXP(1)): pk Chal. Adv. A b m0 , m1 M : |m0| = |m1| (pk,sk) G() c E(pk, mb) b {0,1} EXP(b) No query encryptions of messages. Why? Def: Enc =(G,E,D) is sem. secure (a.k.a IND-CPA) if for all efficient A: AdvSS [A,Enc] = |Pr[EXP(0)=1] Pr[EXP(1)=1] | < negligible 35