Pollard's kangaroo attack on Elliptic Curve Groups

Question

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).

Answer 1

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                                                                                

  # index not found                                                                                                    
  return None