13 Diffie-Hellman key exchange and RSA -------------------------------------- Diffie Hellman - - - - - - - - As already mentioned, the Diffie-Hellman key exchange system allows two people, say Alice and Bob, who do not share any secret information to obtain a shared secret key (which can then for example be used for subsequent private key cryptography). It thus avoids the need for the sharing of secret keys which is difficult in practice and involves trusted third parties or similar (see KL9.1-3 for a discussion). We now formalize what should be expected from such a key exchange protocol: The key exchange experiment KE^eav_{A,Pi}(n): 1. Two parties both holding n execute the protocol Pi. This results in a transcript trans containing all messages exchanged and a string ("key") k:{0,1}^n that is output by both parties. Thus, both parties must output the same key. 2. b<-{0,1}. if b then k':=k else k'<-{0,1}^n 3. Adversary A is given trans and k' and outputs a bit b'. 4. Output = 1 iff b'=b The protocol Pi is deemed secure if the success probability for any prob.polytime adversary A is bounded by 1/2+negl(n). The Diffie-Hellmann protocol Pi for some cyclic group (generating algorithm) G() now works as follows: 1. Alice runs (G,q,g) := G(n) and sends (G,q,g) to Bob. 2. Alice chooses x<-Z_q and computes h1:=g^x 3. Alice sends (G,q,g,h1) to Bob 4. Bob chooses y<-Z_q and sends h2:=g^y to Alice. Bob then outputs k_B:=h1^x 5. Alice outputs k_A:=h2^x /* Note that k_A=k_B=g^{xy} */ We will now show that the Diffie-Hellman protocol is secure under the assumption that DDH is hard for the group in question and the further assumption that the random key k' chosen in the KE^eav experiment is a random element of G rather than an arbitrary random string. Let us call KE'^eav the thus modified experiment. We note that a random group element can be taken of the form g^z for z<-Z_q. We now have Pr(KE'^eav_{A,Pi}(n)=1) = 1/2*Pr(KE'^eav(n)=1 | b=1) + 1/2*Pr(KE'^eav(n)=1 | b=0) = 1/2*(Pr(A(G,g,q,g^x,g^y,g^{xy})=1)+ Pr(A(G,g,q,g^x,g^y,g^z)=0)) = 1/2+1/2*(Pr(A(G,g,q,g^x,g^y,g^{xy})=1)- Pr(A(G,g,q,g^x,g^y,g^z)=1)) <= 1/2+1/2*|Pr(A(G,g,q,g^x,g^y,g^{xy})=1)- Pr(A(G,g,q,g^x,g^y,g^z)=1)| <= 1/2 + 1/2*negl(n) /* assuming hardness of DDH for G() */ We remark that while (under assumptions) Diffie-Hellman is secure against passive eavesdroppers it is vulnerable against more active adversaries that may also send, modify, and swallow messages during the run of the protocol. Achieving security against those requires some means of authenticating messages sent between the parties; a precise formulation of the additional assumptions needed for this is beyond the scope of this book. Public key cryptosystems - - - - - - - - - - - - - We give a formal definition of a public key cryptosystem and its security. Definition: a public key cryptosystem Pi comprises -) a (probabilistic) key generation algorithm Gen() which given security parameter n outputs a pair of keys (pk,sk) /* public, secret */ -) a (probabilistic) encryption algorithm which given plaintext m from some message space and the public key pk produces a ciphertext c: c<-nc_pk(m) -) a deterministic decryption algorithm which given ciphertext c and the secret key sk produces a plaintext m<-Dec_sk(c) in such a way that if c<-Enc_pk(m) then Dec_pk(End_sk(m)) = m. Definition: A public key scheme Pi is semantically secure in the presence of an eavesdropper if the for all (prob. polytime) adversaries A the success probability in the following experiment is bounded by 1/2+negl(n). Experiment PubK^eav_{A,Pi}(n): 1. (pk,sk)<-Gen(n) 2. Adversary A is given pk and outputs messages m0 m1 3. b <- {0,1}; c <- Enc_pk(m_b); c is given to A 4. A outputs a bit b' 5. Outcome is 1 if b=b' and 0 otherwise End of definition We notice that this is just like semantic security in the private key setting except that the adversary has access to the public key which after all is supposed to be public. This means that, since by Kerckhoff's principle, the encryption algorithm is also public, the adversary has access to an encryption oracle and thus---in the public key setting---semantic security in the presence of an eavesdropper (the one above) is as powerful as cpa security. This has the consequence that no public key cryptosystem in which Enc_pk() is deterministic can be semantically secure. Indeed, all the adversary has to do in this case is to precompute the encryptions of its chosen messages m0 and m1. We remark that a semantically secure public key cryptosystem can be combined with any cps-secure private key system by first using the public key to transmit a secret key. This is known as *hybrid encryption*. One can show (Theorem 10.13 of KL) that hybrid encryption yields semantically secure public-key encryption schemes. RSA cryptosystem - - - - - - - - - For this reason, the "textbook RSA" cryptosystem, as indicated in the last chapter, is actually insecure. In order to make it work, it must be enhanced with randomization for example as follows. Fix a length function l(n). Gen(): On input n run GenRSA(n) to obtain (N,e,d). Output pk=(N,e) and sk=(N,d) Enc(): On input m:{0,1}^l(n) and pk=(N,e) choose r<-{0,1}^{||N||-l(n)-1} and output c=(r||m)^e mod N /* the -1 is there to make sure that r||m is in Z_N^* */ Dec(): On input c and sk=(N,d) compute m'=c^d mod N and output the l(n) low-order, i.e. rightmost, bits of m' Now, if the "padding" r is too short, then this does not help because an adversary could try out all possible values for r. It is believed that when r has a length comparable to |m|, then the above scheme is secure (relative to the RSA assumption), but unfortunately, no proof has been found. According to KL (Theorem 10.19) one can show that the scheme is secure when l(n)=O(log(n)), again under the RSA assumption. Note that this means that in order to increase the message size by just one bit one has to double the security parameter and hence the length of the modulus N and the ciphertexts. In practice, one does not want to waste so much bandwidth on the padding and uses heuristic schemes like e.g. RSA-PKCS#1v1.5 which uses a random padding string of length at least 64bit. Another, more modern, method is RSA-OAEP which mixes the padding with the actual plaintext by way of a Feistel network of cryptographic hash functions. Intuitively, this makes the input to the actual RSA encryption look like a random string which then makes the RSA assumption applicable. Viewed more practically, it prevents attacks which only recover parts of the plaintext. In the random oracle model (Lecture 16) RSA-OAEP can be proved semantically secure.