Can it be proven that attacker can obtain the full message if he knows some plain-ciphertext pairs?


Assuming you don't use counter-measures against this kind of an attack, a chosen-ciphertext attack works as follows:

Variables: $p$ is field prime, $\alpha$ is the chosen generator, $a$ is the private key, $\alpha^a=\beta$ is the public key. $k'$ and $m'$ are chosen at random.

Note: all the following equations are $(mod$ $p)$.

  1. Suppose you want to decrypt the ciphertext $C=(\gamma,\delta)=(\alpha^k,m*\beta^k)$
  2. Now calculate $C'=(\gamma*\alpha^{k'},\delta*\beta^{k'}*(m'))$
  3. Now give $C'$ to the decryption oracle, you'll get $m''$ in return.
  4. Finally calculate $m=m''*(m')^{-1}$

Why does this work?

Observe that $\gamma'=\gamma*\alpha^{k'}=\alpha^k*\alpha^{k'}=\alpha^{k+k'}=\alpha^{k''}$.
Further observe that $\delta'=\delta*\beta^{k'}*(m')=m*\beta^k*\beta^{k'}*(m')=(m*m')*\beta^{k+k'}=(m'')*\beta^{k''}$

If you let this pair get decrypted, you'll get $m''=m' * m$ in return an hence $m=m''*(m')^{-1}$ holds.

  • $\begingroup$ What is the intuition behind getting m'' instead of getting m directly? $\endgroup$ – MysticForce Nov 23 '16 at 19:34
  • $\begingroup$ @MysticForce you can't ask the oracle to just return you $m$, you have to trick it into giving you $m$ indirectly which is being done here by construction of $m''$. $\endgroup$ – SEJPM Nov 23 '16 at 19:37
  • $\begingroup$ What would be some counter measures to thwart this attack off ? It is possible while keeping these homomorphic properties ? I think I've seen somewhere that no, those are by definitions against but I can't find why. $\endgroup$ – Nikkolasg Oct 20 '17 at 12:23
  • $\begingroup$ Also, this attacks suppose the decryption oracle accepts to decrypt (by definition). But is it realisable in practice ? One obvious countermeasure is to require to pass a NIZK (a schnorr signature for example) that the person requesting the decryption holds the private key the message is encrypted to. Otherwise, this attack only lets the attacker find out about his own message (m is encrypted to Y, m' too). $\endgroup$ – Nikkolasg Oct 20 '17 at 12:38
  • 1
    $\begingroup$ @Nikkolasg You can always win the IND-CCA2 game as an adversary if the cipher has a homomorphic property. Also see "Is ElGamal IND-CCA1 secure". The counter-measure to this attack would be "don't use a cipher with a homomorphic property", e.g. use DHIES / ECIES instead. As for two different $\beta$s I'm confused, I'd need a proper description of the scheme to analyze it. $\endgroup$ – SEJPM Oct 20 '17 at 16:45

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.