# Pollard's kangaroo attack on Elliptic Curve Groups

Let's say I've intercepted some bits of a Diffie-Hellman private key: $x = n \mod r$. I can get the remaining bits by doing a kangaroo search. This algorithm works over $\mathbb{F}_p$. Can it be adapted to the elliptic curve Diffie-Hellman problem?

In the ECDH problem over $\mathbb{E}(\mathbb{F}_p)$, we're trying to solve $y = x \cdot G$, where $G$ is a base point for the group. With the private key that I have so far, I have the following transformation:

$x = n \mod r \rightarrow x = n + m \cdot r$

$y = (n + m \cdot r) \cdot G = n \cdot G \oplus m \cdot r \cdot G$

So I want to solve $y' = m \cdot G'$ for $m$, where $y' \equiv y \ominus n\cdot G$ and $G' = r\cdot G$, and $\ominus$ is subtraction of points on the curve.

Basically, is the idea to replace exponentiation in the DH kangaroo algorithm with scalar multiplication, and multiplication in the DH kangaroo algorithm with group addition?

$y_{i+1} = y_i G^{f(y_i)}$ in the DH problem, vs.

$y_{i+1} = y_i \oplus (f(y_i) \cdot G)$ in ECDH?

There are faster ways to do scalar multiplication on elliptic curve points, such as the Montgomery ladder, but that only gives you the x-coordinate of the scaled point.

Do I have the right idea about translating this algorithm to the ECDH? Let's assume that I know about Pollard's rho, Shanks' baby-step-giant-step, etc., but that I really want to get this kangaroo working (er, hopping).

• Algorithm applies to EC as well, you're just operating in a different kind of group, the algorithm itself doesn't change. – puzzlepalace May 12 '17 at 3:09
• Cool, thanks. Same algorithm, different group. If you want to leave this as an answer I would accept it. – user47922 May 16 '17 at 5:20

It turns out that, yes, the algorithm applies to ECDH. It can be found in 19.6 of Handbook of Elliptic and Hyperelliptic Curve Cryptography.

More details:

For both the tame and wild kangaroo, the ($i+1$)st hop that the kangaroo takes, $w_{i+1}$, is given by

$$w_{i+1} = w_i \oplus (H(w_{i+1}) \otimes G)$$

Here, $H$ is a hash function, $\otimes$ is scalar multiplication, and $\oplus$ is point addition on an elliptic curve, and $G$ is a base point on the curve.

You can also compute the distance $d_i$ that each kangaroo travels after $i$ steps, with $d_0 = 0$ and $d_{i+1} = d_i + H(w_i)$.

If you want to search for a discrete log in an interval $[a,b]$, let the tame kangaroo lay $N$ "traps", one at each hop. Then set the wild kangaroo loose, starting at $bG$. The hope is that the wild kangaroo will hop into a tame trap. If their paths intersect, we immediately have a solution to the ECDLP.

In the Python code below is a really lame implementation of it the search. I assume there's an available hash function H. p is the prime of the elliptic curve group $\mathbb{E}(\mathbb{F}_p)$, a,b is the search interval $[a,b]$, y and basepoint are parts of the ECDLP to be solved: $y = t\otimes G$. $t$ solves the ECDLP, and the kangaroo search will probabilistically find it. $N$ is the number of iterations.

def kangaroo_search(basepoint, p, y, a, b, N):

# setting the trap
x_tame = 0
y_tame = b * basepoint

while N > 0:

x_tame += H(yT) # scalar addition
y_tame += H(yT) * basepoint # operations are on E(GF_p)
N = N - 1

assert y_tame == (b + x_tame) * basepoint

# wild search
x_wild = 0
y_wild = y

upper_limit = b - a + x_tame
while x_wild < upper_limit:
x_wild += H(y_wild)
y_wild += H(y_wild) * basepoint # operations are on E(GF_p)

if y_wild == y_tame:
print "Victory!"
return b + x_tame - x_wild