CS 380S 0x1A Great Papers in Computer Security Vitaly Shmatikov http www cs utexas edu shmat courses cs380s slide 1 W Diffie and M Hellman New Directions in Cryptography ToIT 1976 slide 2 Diffie Hellman Key Establishment Alice and Bob never met and share no secrets Public information p and g where p is a large prime number g is a generator of Z p Z p 1 2 p 1 a Z p i such that a gi mod p Pick secret random X Pick secret random Y gx mod p gy mod p Alice Compute k gy x gxy mod p Bob Compute k gx y gxy mod p slide 3 Why Is Diffie Hellman Secure Discrete Logarithm DL problem given gx mod p it s hard to extract x There is no known efficient algorithm for doing this This is not enough for Diffie Hellman to be secure Computational Diffie Hellman CDH problem given gx and gy it s hard to compute gxy mod p unless you know x or y in which case it s easy Decisional Diffie Hellman DDH problem given gx and gy it s hard to tell the difference between gxy mod p and gr mod p where r is random slide 4 Security of Diffie Hellman Protocol Assuming the DDH problem is hard Diffie Hellman protocol is a secure key establishment protocol against passive attackers Eavesdropper can t tell the difference between the established key and a random value Can use the established key for symmetric cryptography Approx 1000 times faster than modular exponentiation Basic Diffie Hellman protocol is not secure against an active man in the middle attacker slide 5 Public Key Encryption Key generation computationally easy to generate a pair public key PK private key SK Computationally infeasible to determine private key SK given only public key PK Encryption given plaintext M and public key PK easy to compute ciphertext C EPK M Decryption given ciphertext C EPK M and private key SK easy to compute plaintext M Infeasible to compute M from C without SK Trapdoor function Decrypt SK Encrypt PK M M slide 6 ElGamal Encryption Key generation Pick a large prime p generator g of Z p Private key random x such that 1 x p 2 Public key p g y gx mod p Encryption Pick random k 1 k p 2 E m gk mod p m yk mod p Decryption Given ciphertext compute x mod p Recover m x mod p slide 7 When Is Encryption Secure Hard to recover the key What if attacker can learn plaintext without learning the key Hard to recover plaintext from ciphertext What if attacker learns some bits or some property of the plaintext Informal goal ciphertext should hide all useful information about the plaintext except its length slide 8 Attack Models Assume that the attacker knows the encryption algorithm and wants to decrypt some ciphertext Ciphertext only attack Known plaintext attack stronger Knows some plaintext ciphertext pairs Chosen plaintext attack even stronger Can obtain ciphertext for any plaintext of his choice Chosen ciphertext attack very strong Can decrypt any ciphertext except the target slide 9 The Chosen Plaintext CPA Game Idea attacker should not be able to learn any property of the encrypted plaintext Attacker chooses as many plaintexts as he wants and learns the corresponding ciphertexts When ready he picks two plaintexts M0 and M1 He is even allowed to pick plaintexts for which he previously learned ciphertexts He receives either a ciphertext of M0 or a ciphertext of M1 He wins if he guesses correctly which one it is slide 10 CPA Game Formalization Define Enc M0 M1 b to be a function that returns encrypted Mb 0 or 1 Think of Enc as a magic box that computes ciphertexts on attacker s demand he can obtain a ciphertext of any plaintext M by submitting M0 M1 M or he can submit M0 M1 Attacker s goal is to learn just one bit b slide 11 Chosen Plaintext Security Consider two experiments A is the attacker Experiment 0 A interacts with Enc 0 and outputs bit d Experiment 1 A interacts with Enc 1 and outputs bit d Identical except for the value of the secret bit d is attacker s guess of the secret bit Attacker s advantage is defined as If A knows secret bit he should be able to make his output depend on it Prob A outputs 1 in Exp0 Prob A outputs 1 in Exp1 Encryption scheme is chosen plaintext secure if this advantage is negligible for any efficient A slide 12 Simple Example Any deterministic stateless encryption scheme is insecure against chosen plaintext attack Attacker can easily distinguish encryptions of different plaintexts from encryptions of identical plaintexts Attacker A interacts with Enc b Let X Y be any two different plaintexts C1 Enc X Y b C2 Enc Y Y b If C1 C2 then output 1 else output 0 The advantage of this attacker A is 1 Prob A outputs 1 if b 0 0 Prob A outputs 1 if b 1 1 slide 13 Semantic Security Goldwasser and Micali 1982 Ciphertext hides even partial information about the plaintext No matter what prior knowledge attacker has about the plaintext it does not increase after observing ciphertext Equivalent to ciphertext indistinguishability under the chosen plaintext attack It is infeasible to find two messages whose encryptions can be distinguished slide 14 Semantic Security of ElGamal Semantic security of ElGamal encryption is equivalent to DDH Given an oracle for breaking DDH show that we can find two messages whose ElGamal ciphertexts can be distinguished Given an oracle for distinguishing ElGamal ciphertexts show that we can break DDH Break DDH given a triplet ga gb Z we can decide whether Z gab mod p or Z is random slide 15 DDH ElGamal Pick any two messages m0 m1 Receive E m gk m yk y gx is the ElGamal public key To break ElGamal must determine if m m0 or m m1 Run the DDH oracle on this triplet gk y gv m yk gkv m0 gk gx v m g x v k m0 v is random If this is a DH triplet then m m0 else m m1 This breaks semantic security of ElGamal why slide 16 1 ElGamal DDH Suppose some algorithm A breaks ElGamal Given any public key A produces plaintexts m0 and m1 whose encryptions it can distinguish with advantage Adv We will use A to break DDH Decide given ga gb Z whether Z gab mod p or not Give y ga mod p to A as the public key A produces m0 and m1 Toss a coin for bit x and give A the ciphertext gb mx Z mod p This is a valid ElGamal encryption of mx iff Z gab mod p slide 17 2 ElGamal DDH A receives gb mx Z mod p This is a valid ElGamal encryption of mx iff Z gab mod p A outputs his guess of bit x why If A guessed x correctly we say that Z gab mod p otherwise we say that Z is random …