CS 4803 Computer and Network SecurityAlexandra (Sasha) BoldyrevaPublic-key encryption1Recall: symmetric settingS RAK K2Public-key (asymmetric) settingS RAskRpkR3Asymmetric encryption schemesA scheme AE is specified a key generation algorithm K, an encryption algorithm E, and a decryption algorithm D.Sender S(pk,sk)KEpkCMDskC MAE=(K,E,D) It is required that for every (pk,sk) that can be output by K and every M󲰉MsgSp(pk), if C=E(pk,M) then D(sk,C)=MMsgSp(pk)-message spaceReceiver Ror 󲰥or 󲰥4•A sender must know the receiver’s public key, and must be assured that this public key is authentic (really belongs to the receiver). This is ensured be the PKI processes, which are not part of encryption.•Unlike in a symmetric encryption, the asymmetric encryption algorithm is never stateful. •Messages will often be numbers or group elements, encoded as bitstrings whenever necessary. 5Epk(LR(!,!,b))Indistinguishability under chosen-plaintext attacksAdFix an encryption scheme AE=(K,E,D)Pick keys (pk,sk) by running KM0,M1MbLR(!,!,!)bFor an adversary A and a bit b consider two experiments Exp-ind-cpa-b (AE,A), for b=0 or b=1 The difference between probabilities of outputting 0 in two experiments is called ind-cpa-advantage of A in attacking AE. An asymmetric encryption scheme AE is indistinguishable under chosen-plaintext attacks (IND-CPA secure) if ind-cca-advantage of any adversary with “reasonable” resources is “close” to 0.Epk(•)C=Epk(Mb)pk6IND-CPA is not always enoughBleichenbacher’s attack on a previous version of SSL:C'“invalid ciphertext!”C''“invalid ciphertext!”C=Epk(Alice's session key) OKC''' OKC''''''''' “invalid ciphertext!”pkAlice's session key7Epk(LR(!,!,b))Indistinguishability under chosen-ciphertext attacksAdM0,M1MbLR(!,!,!)bThe difference between probabilities of outputting 0 in two experiments is called ind-cca-advantage of A in attacking SE. A symmetric encryption scheme SE is indistinguishable under chosen-ciphertext attacks (IND-CCA secure) if ind-cca-advantage of any adversary with “reasonable” resources is “close” to 0.Epk(•)C=Epk(Mb)Dsk(•)C’M’A is not allowed to query its decryption oracle on ciphertexts returned by its LR encryption oracleFix an encryption scheme AE=(K,E,D)Pick keys (pk,sk) by running KFor an adversary A and a bit b consider two experiments Exp-ind-cca-b (AE,A), for b=0 or b=1 pk8IND-CCA󲰛IND-CPA•IND-CCA secure schemes guarantee security against more powerful adversaries•Any IND-CCA scheme is also IND-CPA•But an IND-CPA scheme is not necessarily IND-CCA9The ElGamal scheme•Let G be a cyclic group of order n and let g be a generator of G. The ElGamal encryption scheme EG=(K, E, D) associated to G,g is as follows:•••Security depends on the choice of G.26 ASYMMETRIC ENCRYPTIONAlgorithm Kx$← ZnX ← gxReturn (X, x)Algorithm EX(M)If M "∈ G then return ⊥y$← Zn; Y ← gyK ← Xy; W ← KMReturn (Y, W )Algorithm Dx((Y, W ))K ← YxM ← W K−1Return MThe plaintext-space associated to a public key X ∈ G is G itself, and if M is not inthis set then the encryption algorithm returns ⊥.The quantities G, g are assumed to be chosen a priori and known to all parties. Atypical example is G = Z∗pwhere p ≥ 3 is a prime. We have discussed in Section ??how to find primes and generators and thus set up G, g in this case.The first thing that should be verified about the El Gamal scheme is that decryp-tion works correctly, meaning Dx(EX(M)) = M for all M ∈ G. This is true becauseof Equation (8.22), which says that the value K in both algorithms is indeed thesame.In common with several other algebraic schemes, in the natural formulation ofthe El Gamal scheme given above, the message is a group element. In practice wemight prefer to think of our starting message as a string. In that case, we wouldencode the string as a group element before using the El Gamal scheme. For exampleif G = Z∗pwhere p is a prime of length k (i.e. 2k−1≤ p < 2k), the scheme could beviewed as enabling us to encrypt any binary string message m of length k −1. To dothis, compute the integer whose binary representation is m and then adding one toit to get an integer M in the range 1, . . . , 2k−1. This M beign in Z∗pcan be thoughtof as the message for the El Gamal scheme. From the group element returned bythe decryption algorithm one can recover the corresponding string message in theobvious way. More generally, the message space can be viewed as any set of stringsof size at most |G|, mapping these to group elements via some injective enco dingfunction for the sake of encryption.Now, we turn to security, concentrating first on security against chosen-plaintextattack. The first thing to consider is whether the adversary could recover the secretkey x from the public key X. This however requires solving the discrete logarithmproblem, which we are assuming is computationally intractable. Next we couldconsider the possibility of recovery of the plaintext M from a ciphertext (Y, W ). Themost obvious attack is for the adversary (given the public key X and a ciphertext(Y, W )) to try to compute the key K from X, Y , and then recover M via M =[[W K−1mod p]]−1. But trying to find K amounts to solving the CDH problem,which as we discussed is believed to be hard.However, by now we know that it is naive to restrict security concerns to keyrecovery or even to recovery of plaintext from ciphertext. We must also address thepossibility of loss of partial information about the plaintext. In other words, weshould be asking whether the scheme meets the notion of IND-CPA we discussedabove. Whether it does or not turns out to depend on the choice of group.Before assessing IND-CPA, we need to clarify something. Recall that encryptionis not, by our definition, required to hide the length of a message, captured by the10The ElGamal scheme in Zp for a prime p•In this group the ElGamal is IND-CPA insecure, namely there exists an adversary A with ind-cpa advantage 1.•The idea: given a ciphertext A can compute Jp(M).•••••Note that M0 is a square and M1 is not. Why?If b=0 then Jp(M0)=1, Jp(W)=s , if b=1 then Jp(M1)=-1, Jp(W)!sHence and"Bellare and Rogaway 27fact that the left-or-right encryption oracle simply returns ⊥ if fed a pair of messagesof equal length. This leads us to ask what is the length of a message when the latteris a group element. As we said