6
$\begingroup$

I want to understand the Pollard kangaroo attack on elliptic curves. I found this Pollard's kangaroo attack on Elliptic Curve Groups Q/A pretty helpful, but not complete. The posts provides a pretty good algorithm for the attack:

def pollardKangaroo(P, Q, a, b, N):
    # Tame Kangaroo Iterations:
    xTame, yTame = 0, b * P
    for i in range(0,N):
        xTame += Hash(yTame)
        yTame += Hash(yTame) * P
    # yTame == (b + xTame) * P should be true
    # Wild Kangaroo Iterations:
    xWild, yWild = 0, Q
    wildLimit = b - a + xTame
    while xWild < wildLimit:
        xWild += Hash(yWild)
        yWild += Hash(yWild) * P
        if yWild == yTame: return b + xTame - xWild
    # No result was found:
    return None

I did the algorithm on paper and it worked. $P$ and $Q$ are the points in the ECDLP: $Q = n\cdot P$. $a$ and $b$ give the interval, in which the attack searches for $n$. So the algorithm can only succeed if $n \in [a,b]$. Now I got two problems: The hash-function and the parameter $N$ are not explained/defined.

My questions:

  1. Is the hash-function just a semi-random generator and can be pretty simple (e.g. H(point) = x + y + 1)?
  2. How exactly is $N$ defined? What value should $N$ be? How does the value of $N$ affect the algorithm?
$\endgroup$
  • $\begingroup$ I took a pretty easy curve($y^2 = x^3 + x^2 + x$ over $F_{131}$) and then I computed $Q = n * P$ with a small $n$ and searched with $a = n-2$ $b = n+2$. What do you mean with "patience"? $\endgroup$ – Titanlord Aug 4 at 10:06
  • 1
    $\begingroup$ A BSc Kangaroo Methods for Solving the Interval Discrete Logarithm Problem that might be interesting for you. $\endgroup$ – kelalaka Aug 4 at 10:12
  • $\begingroup$ But then, how does the Problem define N? So far I thought $N = sqrt{b-a}$ but now I think this is wrong. ( I read the basic part of the thesis, not the optimization, but I still got no idea how to choose it ) $\endgroup$ – Titanlord Aug 4 at 10:38
  • 1
    $\begingroup$ The kangaroos are expected to hop around randomly. Therefore any good random number generator is good. It should depend on the current position so that when the tame kangaroo set a trap after some jumps if the wild crosses one of the paths of the tame, it will fall into the trap. Hashing is good for this case since it is deterministic. $\endgroup$ – kelalaka Aug 4 at 12:18
  • 1
    $\begingroup$ I did the calculations and the plots using Python and SageMath. Here is the code: gitlab.cs.fau.de/ky78hupy/pollard-kangaroo/-/blob/master/… $\endgroup$ – Titanlord Aug 6 at 7:47
1
$\begingroup$

My First Attempts:

So I did some testings on the curve $E: y^2 = x^3 + x^2 + x$ with $F_{131}$ and the points $P = (42,69)$ and $Q = 42 \cdot P$. My results for different $N$:

enter image description here

My result for a different Hash function:

enter image description here

So this got me confused, because I did not see any results for different N and I thought only the hash-function is for optimization. But the real answer is much more complex. My sources are wikipedia, handbook of elliptic and hyperelliptic curve cryptography and the original paper.

Answers:

  1. Yes, the hash-function is a semi-random number generator. But it is important for the algorithm! The runtime of the algorithm and the failure rate depends on the hash-function. If the result set is to small, the runtime gets pretty bad. If the result set is to big, the failure rate increases. With the handbook I got the result set $\{ 1,2,..., \sqrt{(b-a)}/2 \}$ and it works pretty good.

  2. I found the answer in the origional paper: $N$ defines the failure rate. If $N$ is low, the failure rate is bigger. So that's the reason I did not see significant changes in the plots. Hint: I still have no idea, if I have to store all intermediate results of the tame kangaroo or not. ( I will edit the post, if I find the answer )

New Code:

The handbook is the main source for the code optimizations. This python code is used with SageMath:

hashValue = 0
def Hash(P): 
    if P == 0: return 1
    return int(P.xy()[0]) % hashValue +int(P.xy()[1]) % hashValue+ 1

def pollardKangaroo(P, Q, a, b):
    global hashValue
    hashValue = math.ceil(sqrt((b-a))/2)
    # Tame Kangaroo Iterations:
    xTame, yTame = 0, b * P
    for i in range(0,math.ceil(0.7*sqrt(b-a))):
        xTame += Hash(yTame)
        yTame += Hash(yTame) * P
    # yTame == (b + xTame) * P should be true
    # Wild Kangaroo Iterations:
    xWild, yWild = 0, Q
    for i in range(0, math.ceil(2.7*sqrt(b-a) ) ):
        xWild += Hash(yWild)
        yWild += Hash(yWild) * P
        if yWild == yTame: return b + xTame - xWild
    # No result was found:
    return 0

This now always generates a pretty reasonable plot for the wild kangaroo (same curve and basepoint):enter image description here

Reminder:

There are a lot of improvments of the algorithm. My algorithm is not perfect! My main goal was to understand how the hash-function and the numbers of iterations affect the algorithm. And! I will edit this post, if I will find some more important informations.

| improve this answer | |
$\endgroup$

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.