Can it be proven that attacker can obtain the full message if he knows some plain-ciphertext pairs?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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)$.
- Suppose you want to decrypt the ciphertext $C=(\gamma,\delta)=(\alpha^k,m*\beta^k)$
- Now calculate $C'=(\gamma*\alpha^{k'},\delta*\beta^{k'}*(m'))$
- Now give $C'$ to the decryption oracle, you'll get $m''$ in return.
- 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$ Commented Nov 23, 2016 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$– SEJPMCommented Nov 23, 2016 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$ Commented Oct 20, 2017 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$ Commented Oct 20, 2017 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$– SEJPMCommented Oct 20, 2017 at 16:45