Public Key Cryptography and Key Management Solutions

Public Key Cryptography David Brumley dbrumley@cmu.edu Carnegie Mellon University Credits: Many slides from Dan Boneh s June 2012 Coursera crypto class, which is awesome!

Key management Problem: Communicating among n users. k1,2 U1 U2 k1,4 k3,2 k4,2 k1,3 U4 U3 k4,3 Total: O(n) keys per user 2

One Solution: Trusted Third Party (TTP) Everyone needs only one key U1 U2 k1,TTPk2,TTP TTP k4,TTPk3,TTP U4 U3 Can we remove the TTP as a communication and privacy bottleneck? 3

Session Keys and Mitigating TTP Privacy Concerns Alice (ka) Bob (kb) 1. E(kt, talk to bob ) TTP (kt) 2. Choose random KAB 3. E(ka, A,B || KAB) ticket = E(kb, A,B || Kab) 4. E(Kab, Hi. ) ticket = E(kb, A,B || Kab) 5. D(kb, A,B || Kab) D(Kab, Hi. || Knew) Basis for Kerberos 4

Security Analysis Suppose (E,D) is secure (i.e., semantically secure). Eve sees messages, but learns nothing about kab TTP needed to set up every session TTP can decrypt everything Alice (ka) Bob (kb) TTP (kt) Eve Sees All Traffic 5

Key question Can we generate shared keys without an online trusted 3rd party? Answer: yes! Starting point of public-key cryptography: Merkle (1974), Diffie-Hellman (1976), RSA (1977) More recently: ID-based enc. (BF 2001), Functional enc. (BSW 2011) 6

The Diffie-Hellman Protocol Whitfield Diffie Martin Hellman 7

Bob Alice Eve Goal: establish shared key for security against eavesdroppers without a TTP 8

Discrete Log: A Review Recall: Logarithms are the inverse of exponentiation. by = x is equivalent to logb(x) = y Consider arithmetic mod p, where p is a prime. The discrete log to the base b of x is an integer y such that by mod p = x. Example. Let p = 17. Then: 34 mod 17 = 81 mod 17 = 13. So 34 = 13 (mod p) And the discrete log3(13) = 4 9

Discrete Log Example Fix a prime p>2 and g in (Zp)* of order q. Consider the function: f( x ) = gx in Zp Now, consider the inverse function: Dlogg (gx) = x where x in {0, , q-2} Example: Let g = 2 in Z11. Dlog2(2x)=y s.t. y = 2x mod 11 gx Dlog2(gx) 2x mod 11 1 0 20=1 21=2 28=3 22=4 24=5 29=6 27=7 23=8 26=9 25=10 2 1 3 8 4 2 5 4 6 9 7 7 8 3 9 6 10 5 10

Easy: Given b, y, and p, compute by by mod p See Handbook of Applied Cryptography , available free online Believed Hard: Given b, p, x, compute y such that by mod p = x. The Discrete Log problem A candidate One Way Function 11

Key Exchange with Discrete Log Setup: Fix a public large prime p(~600 digits 2048 bits) and a public number g between 0 and p. 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 k = (ga)b mod p 5. Compute k = (gb)a mod p 6. Use k for symmetric (authenticated) encryption. 12

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 1 (computational DH): compute a (or b) (i.e., calculate the discrete log) or compute gab Goal 2 (strong DDH): Given (g, ga, gb) return whether x = gab or gc where c != ab 13

How hard is the DH function mod p? Suppose prime p is n-bits long. Best known algorithm (GNFS)*: Sym Key 80 bits 128 bits 256 bits (AES) Modulus 1024 bits 3072 bits 15360 bits Elliptic Curve 160 bits 256 bits 512 bits Can we do DH another way that is faster? Slow transition to elliptic curve * O-hat means left lots of lower-order terms off 14

Elliptic curve Diffie-Hellman 15

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 16

Public Key Encryption 17

Public Channel c c D Bob Alice E Eve Last few slides: establish shared key (only) without TTP. What about actual encryption? 18

Public Key Encryption Public KeyBob Private KeyBob Public Channel c c D Bob Alice E Eve 19

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): deterministic 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 20

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 21

Establishing a shared secret Alice Bob (pk, sk) G() Alice , pk choose random x {0,1}128 Bob , C = E(pk,x) D(sk,c) = x x is shared key 22

Security (eavesdropping) Adversary sees pk, E(pk, x)and wants x M Semantic security means the adversary cannot distinguish { pk, E(pk, x), x } from { pk, E(pk, x), rand M } Note: protocol is also vulnerable to MITM attack 23

Public key encryption: constructions Constructions generally rely on hard problems from number theory and algebra 24

Notation Let N denotes a n-bit positive integer. Notation: (In powerpoint, we will sometimes use Zn since it doesn t have fancy latex fonts.) Can do addition and multiplication modulo N 25

Intractable problems with composites Suppose N=pq is a 1024 bit number where |p| = |q|. Let (N) = (p-1)(q-1) Easy Problems: 1. Computing xy mod N 2. Inverting elements. If z = x mod N, finding x-1 Hard Problems: 1. Factor N 2. Given xy mod N, compute the y th root (when gcd(y, (N)) = 1) 26

The factoring problem Gauss (1805): The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic. Current world record: RSA-768 (232 digits) Work: two years on hundreds of machines Factoring a 1024-bit integer: about 1000 times harder likely possible this decade 27

RSA and Trapdoors 28

Trapdoor functions (TDF) Def: a trapdoor func. X Y is a triple of efficient algs. (G, F, F-1) G(): randomized alg. outputs a key pair (pk, sk) F(pk, ): det. alg. that defines a function X Y F-1(sk, ) (the trapdoor): a function Y X that inverts F(pk, ) (pk, sk) output by G x X: F-1(sk, F(pk, x) ) = x 29

Arithmetic Mod Composites Let N = p q where p,q are prime elements in ZN} ZN= {0,1,2, ,N-1} ; (ZN)* = {invertible Facts: x ZN is invertible gcd(x,N) = 1 Number of elements in (ZN)* is (N) = (p-1)(q-1) = N-p-q+1 Euler s thm: x (ZN)* : x (N) = 1 30

The RSA trapdoor permutation First published in Scientific American, Aug. 1977 Very widely used: SSL/TLS: certificates and key-exchange Secure e-mail and file systems many others 31

The RSA trapdoor permutation G(): choose random primes p,q 1024 bits. Set N=pq. choose integers e, d s.t. e d = 1 mod (p-1)(q-1) output pk = (N, e) , sk = (N, d) ; RSA(x) = xe F( pk, x ): (in ZN) F-1( sk, y) = yd ; yd = RSA(x)d = xed = xk (N)+1 = (x (N)) k x = x 32

The RSA assumption RSA is assumed to be a one-way trapdoor permutation For all efficient algs. A: Pr[ A(N,e,y) = y1/e ] < negligible where p,q n-bit primes, N pq, y ZN* 33

Textbook RSA is insecure Textbook RSA encryption: public key: (N,e) secret key: (N,d) Insecure cryptosystem !! Is not semantically secure and many attacks exist me (in ZN) m Encrypt: c Decrypt: cd The RSA trapdoor permutation is not an encryption scheme ! 34

RSA encryption in practice Never use textbook RSA. RSA in practice: ciphertext int. msg Preprocessing RSA msg key Main questions: How should the preprocessing be done? Can we argue about security of resulting system? 35

PKCS1 v2.0: OAEP Preprocessing function: OAEP [BR94] msg 01 00..0 rand. H + check pad on decryption. reject CT if invalid. G + {0,1}n-1 plaintext to encrypt with RSA Thm [FOPS 01] : If RSA is a trap-door permutation, then RSA-OAEP is secure when H,G are perfect hash functions (technically, random oracle)*. *In practice: use SHA-256 for H and G 36

Is RSA a one-way permutation? To invert the RSA one-way func. (without d) attacker must compute: x from c = xe (mod N). How hard is computing e th roots modulo N ?? Best known algorithm: Step 1: factor N (hard) Step 2: compute e th roots modulo p and q (easy) 37

38

Implementation attacks Timing attack: [Kocher et al. 1997], [BB 04] The time it takes to compute cd (mod N) can expose d. Power attack: [Kocher et al. 1999] The power consumption of a smartcard while it is computing cd (mod N) can expose d. Faults attack: [BDL 97] A computer error during cd (mod N) can expose d. (common defense: check output with 10% slowdown) 39

Extra slides if time 40

RSA Key Generation Trouble [Heninger et al./Lenstra et al.] OpenSSL RSA key generation (abstract): prng.seed(seed) p = prng.generate_random_prime() prng.add_randomness(bits) q = prng.generate_random_prime() N = p*q Suppose poor entropy at startup: Same p will be generated by multiple devices, but different q N1 , N2 : RSA keys from different devices gcd(N1,N2) = p 41

RSA Key Generation Trouble [Heninger et al./Lenstra et al.] Experiment: factors0.4% of public HTTPS keys! Lesson: Make sure random number generator is properly seeded when generating keys 42

Questions? 43

END

Number Theory Primer 45

Background We will use a bit of number theory to construct: Key exchange protocols Digital signatures Public-key encryption More info: http://shoup.net/ntb/ntb-v2.pdf http://cseweb.ucsd.edu/~mihir/cse107/ and other places across the web. 46

Modular Arithmetic Defn: a = b mod N iff a-b = kN Addition and multiplication work as expected, e.g., x(y+z) = x*y + x*z Examples: 47

Greatest Common Divisor Def: for integers x,y, gcd(x,y) is the greatest common divisor of x and y. Fact: for all integers x, y there exists integers a,b such that: a*x +b*y = gcd(x,y) and a,b can be found efficiently with the extended Euclidian algorithm Example: gcd(12, 18) = 6 2*12 + (-1)*18 = 6 Def: If gcd(x,y) = 1, then we say x and y are relative primes. 48

Modular Inversion Over the rationals the inverse of 2 is . What about modulo N? Def: The inverse of an integer x is an integer y such that x*y = 1 mod N, and is denoted x-1 Example: Let N be an odd integer. Then the inverse of 2 is (N+1)/2 Proof: 49

Which Elements Have Inverses? Thm: an element x only has an inverse mod N iff gcd(x, N) = 1 Computing: Calculate gcd(x,N) using extended Euclidian to come up with ax + bN = 1. Then a*x =1 mod N, so a is the inverse for x. Example: For N = 12, we have the following invertible elements: gcd(1, 12) = 1 gcd(2, 12) = 2 gcd(3, 12) = 3 gcd(4, 12) = 4 gcd(5, 12) = 1 gcd(0, 12) = 0 gcd(6, 12) = 6 gcd(7, 12) = 1 gcd(8, 12) = 4 gcd(9, 12) = 3 gcd(10, 12) = 2 gcd(11, 12) = 1 50