4
$\begingroup$

In Hoffstein, Pipher, and Silverman's book An Introduction to Mathematical Cryptography, the authors make the following remark:

An attack in which Eve has access to an oracle that decrypts arbitrary ciphertexts is known as a chosen ciphertext attack. The preceding proposition shows that the ElGamal system is secure against chosen ciphertext attacks. More precisely, it is secure if one assumes that the Diffie–Hellman problem is hard.

where the "preceding proposition" is a walk-through of a proof that if one can decrypt ElGamal ciphertexts, then one can solve the Diffie-Hellman problem.

However, all the sources that I can find online (including several on this site) seem to make the opposite claim, that ElGamal is not secure against chosen ciphertext attacks. The errata for the book makes no mention of this passage. Is my understanding of the authors' statement flawed?

$\endgroup$
  • $\begingroup$ I certainly don't think so. $\;$ $\endgroup$ – user991 Jul 10 '15 at 4:36
7
$\begingroup$

As already mentioned in a previous answer and the comments, you are right regarding that ElGamal is not secure against chosen-ciphertext attacks. An immediate reason is that the scheme is multiplicatively homomorphic, and that is not compatible with CCA: the attacker could query the decryption oracle with the ciphertext that results of multiplying the challenge ciphertext and the encryption of some random message; the homomorphism ensures that $Enc(pk, m_b) \cdot Enc(pk, m') = Enc(pk, m_b \cdot m')$, and therefore, the decryption oracle cannot refuse to respond to the query since the input is different to the challenge; now the adversary only has to remove $m'$ to recover the challenge message.

Also, something worth mentioning is that the proof given in that book does not follow the traditional conventions for proofs in provable security. First, they are not defining the security goal explicitly (i.e., are they trying to prove one-wayness? indistinguishability? some other notion?). And second, usually proofs are constructed as a reduction to a hard problem; that is, these proofs aim to reach a contradiction by which, if the scheme is insecure, then you could solve the hard problem. These proofs follow this template:

  1. Define a security goal (e.g., Indistinguishability (IND)) and an attack model (in this case, chosen ciphertext attacks). Together they form a security notion (e.g., IND-CCA).
  2. Assume the existence of an adversary $\mathcal A$ that breaks the scheme under the security notion.
  3. Simulate the environment of $\mathcal A$. That is, you explicitly construct the oracles required by the attack model. Usually, you need to somehow embed elements from the hard problem instance you want to solve (e.g., elements from a DH tuple $(g^a, g^b)$).
  4. Prove that using $\mathcal A$ you could solve the hard problem.
  5. Since the hard problem is assumed to be hard, we have reached a contradiction, so the initial assumption (i.e., the statement in step 2) is false, and the scheme is actually secure.

However, the proof given in the book is doing something different. It is first assuming that there exists a decryption oracle, and then proving that you could solve the DH problem using it. Since the DH is hard, then the initial assumption must be false. In this case, the initial assumption is that there exists a decryption oracle, but this does not prove at all that the scheme is secure under chosen-ciphertext attacks.

$\endgroup$
  • $\begingroup$ Great answer. As I'm just beginning to explore this field, it gives me a lot to think about. Just a quick question, what does your notation $p_k$, $m_b$, and $m'$ indicate? I assume $p_k$ is the prime used to construct the key and the $m$'s are the various plaintext messages. So then what I'm taking from your response is that the book has successfully proved there is no decryption oracle for ElGamal, but it has not proved (and is incorrect for it to say) that "the ElGamal system is secure against chosen ciphertext attacks". $\endgroup$ – GrahamGoudeau Jul 10 '15 at 21:49
  • $\begingroup$ $pk$ is the public key and $m_b$ is the challenge plaintext in the indistinguishability game. The proof has several defficiencies, starting from not defining what "secure" means. $\endgroup$ – cygnusv Jul 10 '15 at 23:43
1
$\begingroup$

ElGamal is not secure against chosen-ciphertext attacks, and there is a trivial attack. This is incorrect.

$\endgroup$
  • $\begingroup$ While this may be a valid answer, it looks a bit like a comment. Maybe you could edit your answer and explain why this is incorrect? Or you could link to (or mention the title and authors of) the paper that describes that trivial attack. Just some ideas… which might result in a better answer (and more upvotes). $\endgroup$ – e-sushi Jul 10 '15 at 7:09
  • $\begingroup$ A comment from the writer of one of the most widely used texts in Crypto does qualify to be an answer! $\endgroup$ – Hasan Iqbal Dec 10 '18 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.