*Bounty: 50*

*Bounty: 50*

I’m following these three articles:

- Kleptography: Using Cryptography Against Cryptography,
- Kleptographic Attack on Elliptic Curve Based

Cryptographic Protocols and - Elliptic Curve Kleptography .

In the first article, a kleptogrpahic attack based on DLP cryptosystem is described. In particular, we can read (pg 67) that $$ z equiv g^{c_1-Wt}Y^{-ac_1-b} bmod p$$

where $c_1$ is the private key of Alice (the sender); $Y equiv g^X bmod p$ is the public key of Eve (eavesdropper); $g$ is a generator of $mathbb{Z}_p$ and $a,b,W$ are three integers used for precaution. Indeed, even if a user is able to invert the hash function $H$, then it is still impossible to detect if the device has been contaminated with a SETUP mechanism (pg 68-69).

In the second article, an analogous of this attack is presented in the context of elliptic curves. Here (pg 139907, algorithm 5)

$$z = (c_1-Wt)P+(-ac_1-b)Y $$

where $P$ is the base point of a strong elliptic curve $E$ over $mathbb{F}_q$. Here, there is not a well know theory such as quadratic-residues and their distributions $mathbb{Z}_p$. Indeed, in 3 we can read: "This kind of

probabilistic detection by the user is very difficult in

elliptic curve cryptosystems compared to discrete log

systems where quadratic residuosity can be used to test a

possible relation between the attacker’s public key and $z$".

Then, my first question is: could the SETUP attack applied to EC be simplified? For example, deleting some extra number $a$ or $b$?

However, in the third article, $z$ is a little more complicated than what we saw in the first two papers.

begin{equation}

z = (ac_1 + h cdot j)P + (bc_1+e cdot u)Y

end{equation}

where $a,h,e,b$ are fixed integers, and $j,u in {0,1 }$ are uniformly and independently chosen at random.

Therefore, my second question rises. What is the best implementation of SETUP attack in ECDH? The second article or the third one?

Here, the "best implementation" means that comparing the algorithms in 2 and 3, we want to find the faster and easier algorithm which leads to the same result and which is the safest. Indeed, the security is based on the randomness of $z$, and in 1 is explained why. Following this first direction, one can think that the algorithm in 2 is secured as the first one 1. However, on elliptic curves, strange things may happen, and in order to obtain the randomness of $z$, we should use the third algorithm 3. I don’t think this is the case, i.e. I think 2 it’s enough to reach the wanted level of security, without using extra integers $a,u$ as in 3.