Pollard's kangaroo ECDLP solver

[CY4NiDE]

So I'm messing with Puzzle #130 and JLP's Pollard Kangaroo ECDLP Solver using a RTX 2070. When I first launch it, this is the speed I get:
[1553.87 MK/s][GPU 1459.12 MK/s]

After a few seconds running at that speed it will slowly decrease until it reaches this speed, where it stays for the rest of the operation:
[1209.19 MK/s][GPU 1134.42 MK/s]

Does anyone know why this is happening?

Thanks in advance!  

Because statistics are wrong until all threads loads kangaroos. Wait about 10-15 seconds to get right numbers.

Oh, this makes total sense. Thank you for your quick and concise answer! 

[EternityMessage]

Code question!

Why the jump table is not saved with work save file?

That way, jump table will be different every time we continue work and loading file, and the potential cycles will be different!

[_Counselor]

Code question!

Why the jump table is not saved with work save file?

That way, jump table will be different every time we continue work and loading file, and the potential cycles will be different!

Jump table generator uses hard-coded fixed seed each time to keep jump sizes equal for all workers.

[shelby0930]

Hey Guys!

I was wondering if a feedback system be established to determine the relative positions of two secp256k1 public keys? For instance, if one wishes to ascertain the distance between the public key associated with private key 100 and the public key of 1, and observes that it takes an average of 5 minutes to transition from key 100 to key 1, could one infer that the distance is halved when moving from key 50 to key 1, resulting in an average time of 2.5 minutes? Is it feasible to obtain such feedback?

[digaran]

Hey Guys!

I was wondering if a feedback system be established to determine the relative positions of two secp256k1 public keys? For instance, if one wishes to ascertain the distance between the public key associated with private key 100 and the public key of 1, and observes that it takes an average of 5 minutes to transition from key 100 to key 1, could one infer that the distance is halved when moving from key 50 to key 1, resulting in an average time of 2.5 minutes? Is it feasible to obtain such feedback?

Well, at first I thought you just cracked elliptic curve cryptography, but again when I think about your idea, of course you can have that, but it won't be accurate and precise, though you are talking about 1 and 100, while in the case of puzzle keys, we are now looking at 2^129 to be the distance between 2 keys. However if you are seeing your speed, you can guess the time yourself, just set the counter on your pc and check how long it takes.

Wait let me tell you, it takes the same as your speed rate, if 10 key per second is your speed, it should take around 10 seconds to go from 1 to 100.

Now I have an idea, what if we divide our key by 2 and start adding 100 trillion G at each step, we should see our original target +100 T at some point in time, right?

For example, target 1000, divide by 2 = 500, if we keep adding 10 to 500 we would reach 1000 after 50 steps and in 51st step we would see 1010, that way we can find our target very fast, right?

Let me go try a few things.😉

[garlonicon]

that way we can find our target very fast, right?

No. Because finite fields are, well, finite. If your key is 1234, then if you use 50 as your step, you will reach 1200, and then 1250, so you will jump over that, without noticing, that you missed it. And then, you will go up from 1250 to that huge n-value, and pass it a few times, to finally land on 1184, and then on 1234.

If you want to better understand that, maybe start with some smaller numbers first? This is a good starting point: "p=79, n=67, base=(1,18)". And when those numbers will be too easy for you, then you can go into higher, and higher values, climbing into bigger curves, by walking one step higher at a time.

For example, target 1000, divide by 2 = 500, if we keep adding 10 to 500 we would reach 1000 after 50 steps and in 51st step we would see 1010,

This is still small enough to make an image out of that. For example, vjudeu made a repository, where you can find all curves from 1 to 1000: https://github.com/vjudeu/curves1000/tree/master/png

Which means, if you have for example p-value around 1000, then you can just draw some 1000x1000 image, and put a white dot on (x,y) coordinates. In this way, you can see all points on some small curve, and explore exactly, how coordinates change, when you change your private keys.

Also, in this way, you can easily see, why prime numbers are used. If you have "p=967, n=907, base=(1,88)", then this is acceptable, and if you look at this image, there is no obvious weakness: https://raw.githubusercontent.com/vjudeu/curves1000/master/png/967.png

However, if you pick some complex numbers, then you can notice, how weak some of those curves are. For example, if you take 999: https://raw.githubusercontent.com/vjudeu/curves1000/master/png/999.png

[shelby0930]

Hey Guys!

I was wondering if a feedback system be established to determine the relative positions of two secp256k1 public keys? For instance, if one wishes to ascertain the distance between the public key associated with private key 100 and the public key of 1, and observes that it takes an average of 5 minutes to transition from key 100 to key 1, could one infer that the distance is halved when moving from key 50 to key 1, resulting in an average time of 2.5 minutes? Is it feasible to obtain such feedback?

Well, at first I thought you just cracked elliptic curve cryptography, but again when I think about your idea, of course you can have that, but it won't be accurate and precise, though you are talking about 1 and 100, while in the case of puzzle keys, we are now looking at 2^129 to be the distance between 2 keys. However if you are seeing your speed, you can guess the time yourself, just set the counter on your pc and check how long it takes.

Wait let me tell you, it takes the same as your speed rate, if 10 key per second is your speed, it should take around 10 seconds to go from 1 to 100.

Now I have an idea, what if we divide our key by 2 and start adding 100 trillion G at each step, we should see our original target +100 T at some point in time, right?

For example, target 1000, divide by 2 = 500, if we keep adding 10 to 500 we would reach 1000 after 50 steps and in 51st step we would see 1010, that way we can find our target very fast, right?

Let me go try a few things.😉

Hey Have you tried something? lemme know and btw.. do you think there exists a way to get feedback on the position of the secp256k1 public key?

[garlonicon]

Hi, is there a way to find private key range from the public key, (Start and Stop range) ?

No, because then ECDSA would be instantly broken. Also, that range is always relative to the base point. Which means:

Code:

range getRangeFromPubkey(Pubkey point);             //this will not work
range getRangeFromPubkey(Pubkey point,Pubkey base); //this could work, but would require breaking ECDSA

In general, if you give someone a public key alone, then asking for a private key is not the right question. The right question is: I have these two points, and I want to know the distance between them.

do you think there exists a way to get feedback on the position of the secp256k1 public key?

What do you mean by "position"? Because each point has just a pair of (x,y) coordinates, and for small enough curves, you can directly see that, for example if you have 1000x1000 image, you can directly see the position for each and every public key.

[EternityMessage]

Why code uses self made hash table?

Isn't it much faster to use C++ std::map ?

[bjpark]

"I'm testing Kangaroo 2.2, and I'm encountering an error with the public key value. It contains 66 characters, including 02 03, yet I'm unsure why I'm getting an error. I've conducted numerous tests thus far, but this is the first time encountering such an issue."

kangaroo.exe -gpu test.txt

test.txt ===>

11111
1111111111
038aa5e9f35d54df0ce7ea2131cd54c54c3100e89eb41c905a40c66c1d03648e5e
02402e14312240377f607dd6700fba6245bf26a866cc4e608441dcc938b4992e3c
0242ac97574153a0aed0b8115c0b1a430f8ff1040e5cc377d76d3886e2696edf06

error

Kangaroo v2.2
ParsePublicKeyHex: Error invalid public key specified (Not lie on elliptic curve)
C:\Users\admin\Desktop\result.txt, error line 4: 0242ac97574153a0aed0b8115c0b1a430f8ff1040e5cc377d76d3886e2696edf06

[digaran]

How did you obtain it exactly? In fact all 3 are invalid.

[bjpark]

How did you obtain it exactly? In fact all 3 are invalid.

It's right that all 3 are wrong
I got it from the public key by subtracting the public key value, but I'll get it from the actual key again.



[new]
Thank you.
We found the cause.
An error occurred because the y value of the public key main key was entered incorrectly
main = 0x0c8a2c9469582f356343842ad36a9272e434eb5259807923f0046840e77b28b6 , 0x2fed4282430443b400cbefe2f1d7c8fbc6452bf68623c8993a3efb7b767fcd7b
I should've put it in and calculated it
main = 0x0c8a2c9469582f356343842ad36a9272e434eb5259807923f0046840e77b28b6 , 0x2fed4282430443b400cbefe2f1d7c8fbc6452bf68623c8993a3efb7b767fc

An error occurred because the y-value was missing a few characters in the back
Thank you.

[3dmlib]

Hello. What parameters or something to change in the code to speed-up this program on 4090 card? It only 1.2 times faster than on 3090 card, but it should be about 1.9 times faster. Thanks.

[ABCbits]

Hello. What parameters or something to change in the code to speed-up this program on 4090 card? It only 1.2 times faster than on 3090 card, but it should be about 1.9 times faster. Thanks.

After searching for all post in this thread[1] and github repository[2], it looks like you're first person who mention "4090" or any RTX 4000 series. And while it's obvious, have you tried all guidance on github repository. For example,

-g g1x,g1y,g2x,g2y,...: Specify GPU(s) kernel gridsize, default is 2*(MP),2*(Core/MP)

Powerfull GPUs with large number of cores won't be very efficient on small range, you can try to decrease the grid size in order to have less kangaroos but the GPU performance may not be optimal

[1] https://ninjastic.space/search?content=4090&topic_id=5244940
[2] https://github.com/search?q=repo%3AJeanLucPons%2FKangaroo%204090&type=issues

[r1ckpwn]

Hi, i'm studying Kangaroo Software made by JeanLucPons and I'm trying to know if there is a possibility to compute more pubkeys during an attack.

Searching in the official git I've found that Jean said:

Yes,
I will add some note about this on the readme. It is a bit tricky.
Multi key support is not yet supported, for this you will need first to create a large tame array for a given range and then attack keys with it.

What does it mean? large tame array? Means maybe doing an one pubkey attack in a specific range complete that range using save.work and use it for other keys to attack? If I wanna do multi pubkey attack?

Thank you guys for replies.

[3dmlib]

Hello. What parameters or something to change in the code to speed-up this program on 4090 card? It only 1.2 times faster than on 3090 card, but it should be about 1.9 times faster. Thanks.

After searching for all post in this thread[1] and github repository[2], it looks like you're first person who mention "4090" or any RTX 4000 series. And while it's obvious, have you tried all guidance on github repository. For example,

-g g1x,g1y,g2x,g2y,...: Specify GPU(s) kernel gridsize, default is 2*(MP),2*(Core/MP)

Powerfull GPUs with large number of cores won't be very efficient on small range, you can try to decrease the grid size in order to have less kangaroos but the GPU performance may not be optimal

[1] https://ninjastic.space/search?content=4090&topic_id=5244940
[2] https://github.com/search?q=repo%3AJeanLucPons%2FKangaroo%204090&type=issues

Yes. I tried all possible grid size combinations. Also, I tried to compile on latest cuda version using more recent compute_89 shader model. Same result. The maximum I have on 4090 is about 2500 MK/s. On 3090 is 2200 MK/s. 4090 should be faster. Looks like Kangaroo need some optimization for large number of cores 4090 have. Any ideas where this optimization can be made? Thanks.

[ABCbits]

--snip--

Yes. I tried all possible grid size combinations. Also, I tried to compile on latest cuda version using more recent compute_89 shader model. Same result. The maximum I have on 4090 is about 2500 MK/s. On 3090 is 2200 MK/s. 4090 should be faster. Looks like Kangaroo need some optimization for large number of cores 4090 have. Any ideas where this optimization can be made? Thanks.

I see. While i have no idea which optimization can be done, you might want to try fork of this software or implementation written by different people. Here are few example,
https://github.com/ZenulAbidin/Kangaroo-256
https://github.com/PawelGorny/Kangaroo
https://github.com/secoc/Pollard-Rho-kangaroo

P.S. i haven't tried any of those.

[3dmlib]

--snip--

Yes. I tried all possible grid size combinations. Also, I tried to compile on latest cuda version using more recent compute_89 shader model. Same result. The maximum I have on 4090 is about 2500 MK/s. On 3090 is 2200 MK/s. 4090 should be faster. Looks like Kangaroo need some optimization for large number of cores 4090 have. Any ideas where this optimization can be made? Thanks.

I see. While i have no idea which optimization can be done, you might want to try fork of this software or implementation written by different people. Here are few example,
https://github.com/ZenulAbidin/Kangaroo-256
https://github.com/PawelGorny/Kangaroo
https://github.com/secoc/Pollard-Rho-kangaroo

P.S. i haven't tried any of those.

After some tests I found that memory speed is an issue. It GPU memory bound, not GPU chip. This is why it can't scale well for more GPU cores.

[3dmlib]

Hello.

Point Secp256K1::NextKey(Point &key) {
  // Input key must be reduced and different from G
  // in order to use AddDirect
  return AddDirect(key,G);
}

Is anybody can explain me why this function in secp256k1.cpp file not work correctly?
As I understand it should return next public key like as increment private key by 1 and compute public key from it.
What is reduced public key?

Thanks.

[arulbero]

What is reduced public key?

A public key is a point of the elliptic curve. A point can be represented by 3 coordinates (X,Y,Z) (projective coordinates) or by 2 coordinates (x,y) (affine coordinates).

The passage from projective to affine coordinates is the "reduction"

x = X/Z
y = Y/Z

https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/Point.cpp#L64

Point Secp256K1::NextKey(Point &key) {
  // Input key must be reduced and different from G
  // in order to use AddDirect
  return AddDirect(key,G);
}

Is anybody can explain me why this function in secp256k1.cpp file not work correctly?
As I understand it should return next public key like as increment private key by 1 and compute public key from it.

The addition between 2 points in projective coordinates is performed by the function Add:

https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/SECP256K1.cpp#L369

and it is faster, because it avoids the inverse of x;


the addition between the same 2 points in affine coordinates is performed instead by the function AddDirect:

https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/SECP256K1.cpp#L238.

To compute NextKey function (that calls the AddDirect function), you have:

a) to use a point in affine coordinates (because the AddDirect function needs affine coordinates)
b) to avoid the case P = G, because to perform G+G (in the general P + P ) the AddDirect function doesn't work

you need instead the DoubleDirect function:
https://github.com/JeanLucPons/Kangaroo/blob/354bb80491752262eaca3613557e1bd306b5414d/SECPK1/SECP256K1.cpp#L438