Pollard's kangaroo ECDLP solver

[brainless]

You are using a too small DP, too much DPs enter in the HashTable and slow down the search.
The expected RAM to reach 50% probability is 60GB.
And last but not least, you CPU work also and prevent the other threads to work.
Try DP17 or 18 and use -t 0 (no CPU) option.

Kangaroo.exe -d 17 -t 0 -gpu -gpuId 0,1,2,3 -g 136,128,136,128,136,128,136,128 in.txt

if i am not wrong,
you win 115bit puzzle in 13 days, and you count 120 puzzle is more hard as 32 time
its mean 13 x 32 = 416 days you need to win or ?

[j2002ba2]

if i am not wrong,
you win 115bit puzzle in 13 days, and you count 120 puzzle is more hard as 32 time
its mean 13 x 32 = 416 days you need to win or ?

Pollard Kangaroo time grows with square root of the problem.
13 x sqrt(32) = 74 days

The expected time is lower ~45 days.

[WanderingPhilospher]

if i am not wrong,
you win 115bit puzzle in 13 days, and you count 120 puzzle is more hard as 32 time
its mean 13 x 32 = 416 days you need to win or ?

Pollard Kangaroo time grows with square root of the problem.
13 x sqrt(32) = 74 days

The expected time is lower ~45 days.

Close to what JLP has posted on his github page:

Expected time: 2 months on 256 Tesla V100

[WanderingPhilospher]

@Jean Luc

Don't tell me about times or it's not worth it etc. (please):

If I solved a key at the 100 bit range and I want to reuse the dp file generated from that search, how do I reuse it to search for another pubkey in the exact same range and using the exact same dp?

Seems like I'd have to clear out pubkey in header, that all? How to go about it?

[Etar]

@Jean Luc

Don't tell me about times or it's not worth it etc. (please):

If I solved a key at the 100 bit range and I want to reuse the dp file generated from that search, how do I reuse it to search for another pubkey in the exact same range and using the exact same dp?

Seems like I'd have to clear out pubkey in header, that all? How to go about it?

You need tamed wild DPs or cut wild DPs from workfile.

[WanderingPhilospher]

@Jean Luc

Don't tell me about times or it's not worth it etc. (please):

If I solved a key at the 100 bit range and I want to reuse the dp file generated from that search, how do I reuse it to search for another pubkey in the exact same range and using the exact same dp?

Seems like I'd have to clear out pubkey in header, that all? How to go about it?

You need tamed wild DPs or cut wild DPs from workfile.

I don't know so I'm not disagreeing with you but why would you need to cut any tame or wild out?
Same range, only thing changing would be what x coord to look for and compare for solution, right?

[Etar]

-snip-
I don't know so I'm not disagreeing with you but why would you need to cut any tame or wild out?
Same range, only thing changing would be what x coord to look for and compare for solution, right?

here is my reconstructor https://drive.google.com/file/d/1zHwoVjIvYhpgcTy_4sWin_A-3GMiTs5B
when you will first time reconstruct workfile use -checkdp 1 in bat file.
After few persent(or fraction of persent) of job if there will be ok and you don`t get any eror message then close reconstructor> set -checkdp 0> and launch again.
-checkdp 1 need only to see if wild DPs tamed in correct way.
param newpubkey use without prefix 04
If you will see error with -checkdp 1 than previousprivkey set invalid and recocosntructed wild DP has x-coordinate not the same as in source.
Source file not changed during reconstruction.. All DPs going to new work file.
After end of reconstruction you will see somesing like this:

Code:

100.00%
DP count    :240568
HT max      :8[@ 01D30E]
HT min      :0[@ 000001]
Tame count  :120410
Wild count  :120158
NumberOfWalk:0000000000000000
------------------------
TAME  [120410]
TAMED [120158]
SKIPED[0]
TOTAL TAME[240568]

Edit: if you not tamed your wild DPs they are useless to search new pubkeys, just
only memory is used, but there is no sense from them.
It is possible that they will lead to incorrect collisions if not tamed.

[BitCrack]

https://github.com/brichard19/eclambda

Can anyone try my tool on a 2080ti? On a 2080S it gets around 1300MKeys/sec when using 24-bit DP.

I tried your tool (DP18) on a V100.

Code:

[2020-06-22.11:35:35] [Info] DP: 0 TP: 0 853.74 Mpt/s (64 iter/s)
[2020-06-22.11:35:37] [Info] Verifying 40336 results
[2020-06-22.11:35:45] [Info] DP: 0 TP: 0 992.50 Mpt/s (75 iter/s)
[2020-06-22.11:35:48] [Info] Verifying 40362 results
[2020-06-22.11:35:55] [Info] DP: 0 TP: 0 991.18 Mpt/s (75 iter/s)

Kangaroo on a server too, configured in the same way, however, it is not clear how many kangaroo are running in parallel with your program and what grid setting is used.

Code:

GPU: GPU #0 Tesla V100-PCIE-16GB (80x64 cores) Grid(160x128) (207.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^21.32 kangaroos [11.2s]
[2000.07 MK/s][GPU 2000.07 MK/s][Count 2^37.48][01:52][Server     OK]

It says exactly how many kangaroos are running in parallel, 58,395,776 in this example:

Code:

eclambda --name testjob85 --gpu-mem-usage 0.9 --device 2
     ______ ______   __     ___     __  ___ ____   ____   ___
    / ____// ____/  / /    /   |   /  |/  // __ ) / __ \ /   |
   / __/  / /      / /    / /| |  / /|_/ // __  |/ / / // /| |
  / /___ / /___   / /___ / ___ | / /  / // /_/ // /_/ // ___ |
 /_____ / \____/ /_____//_/  |_|/_/  /_//_____//_____//_/  |_|
EC LAMBDA CLIENT
VERSION 1.1.1 ALPHA
[2020-06-22.16:26:33] [Info] Connecting to 127.0.0.1
[2020-06-22.16:26:34] [Info] Target public key:
[2020-06-22.16:26:34] [Info] X:F1367CC260779F7EA6C7E4B7258A4D31A4C41D6282C5200571CE10E748A4AADE
[2020-06-22.16:26:34] [Info] Y:0743F0CA057C7F39A9D9A20D4A93555B19F712920EEEF2F267466A2F3D08662E
[2020-06-22.16:26:34] [Info] Distinguisher: 24 bits
[2020-06-22.16:26:34] [Info] Sending results to server every 10 minutes
[2020-06-22.16:26:34] [Info] Initializing GeForce RTX 2080 SUPER
[2020-06-22.16:26:34] [Info] Compiling OpenCL kernels...
[2020-06-22.16:26:34] [Info] Initializing...
[2020-06-22.16:27:09] [Info] Generating 58,395,776 starting points (7184.1MB)
[2020-06-22.16:27:37] [Info] 10.0%
[2020-06-22.16:27:42] [Info] 20.0%
[2020-06-22.16:27:48] [Info] 30.0%
[2020-06-22.16:27:50] [Info] 40.0%
[2020-06-22.16:27:50] [Info] 50.0%
[2020-06-22.16:27:50] [Info] 60.0%
[2020-06-22.16:27:51] [Info] 70.0%
[2020-06-22.16:27:51] [Info] 80.0%
[2020-06-22.16:27:52] [Info] 90.0%
[2020-06-22.16:27:52] [Info] 100.0%
[2020-06-22.16:27:54] [Info] Refilling GPU cache (319.3MB)
[2020-06-22.16:27:54] [Info] 10.0%
[2020-06-22.16:27:54] [Info] 20.0%
[2020-06-22.16:27:55] [Info] 30.0%
[2020-06-22.16:27:55] [Info] 40.0%
[2020-06-22.16:27:55] [Info] 50.0%
[2020-06-22.16:27:55] [Info] 60.0%
[2020-06-22.16:27:55] [Info] 70.0%
[2020-06-22.16:27:55] [Info] 80.0%
[2020-06-22.16:27:55] [Info] 90.0%
[2020-06-22.16:27:55] [Info] 100.0%
[2020-06-22.16:27:55] [Info] Tuning started
[2020-06-22.16:27:55] [Info] Results collection thread started
[2020-06-22.16:28:05] [Info] DP: 0 TP: 0 587.62 Mpt/s (10 iter/s)
[2020-06-22.16:28:15] [Info] DP: 0 TP: 0 1212.69 Mpt/s (20 iter/s)
[2020-06-22.16:28:25] [Info] DP: 0 TP: 0 1170.13 Mpt/s (20 iter/s)
[2020-06-22.16:28:28] [Info] Tuning complete
[2020-06-22.16:28:35] [Info] DP: 0 TP: 0 1187.71 Mpt/s (20 iter/s)
[2020-06-22.16:28:40] [Info] Verifying 2785 results
[2020-06-22.16:28:45] [Info] DP: 0 TP: 0 1325.58 Mpt/s (22 iter/s)
[2020-06-22.16:28:55] [Info] DP: 0 TP: 0 1322.54 Mpt/s (22 iter/s)
[2020-06-22.16:29:05] [Info] DP: 0 TP: 0 1315.67 Mpt/s (22 iter/s)

It automatically finds the best grid size, so I do not know if it's useful to even display it.

Increasing --gpu-mem-usage increases performance. By default it's low to avoid timing out/crashing for people testing it on display GPUs.

[COBRAS]

https://github.com/brichard19/eclambda

Can anyone try my tool on a 2080ti? On a 2080S it gets around 1300MKeys/sec when using 24-bit DP.

I tried your tool (DP18) on a V100.

Code:

[2020-06-22.11:35:35] [Info] DP: 0 TP: 0 853.74 Mpt/s (64 iter/s)
[2020-06-22.11:35:37] [Info] Verifying 40336 results
[2020-06-22.11:35:45] [Info] DP: 0 TP: 0 992.50 Mpt/s (75 iter/s)
[2020-06-22.11:35:48] [Info] Verifying 40362 results
[2020-06-22.11:35:55] [Info] DP: 0 TP: 0 991.18 Mpt/s (75 iter/s)

Kangaroo on a server too, configured in the same way, however, it is not clear how many kangaroo are running in parallel with your program and what grid setting is used.

Code:

GPU: GPU #0 Tesla V100-PCIE-16GB (80x64 cores) Grid(160x128) (207.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^21.32 kangaroos [11.2s]
[2000.07 MK/s][GPU 2000.07 MK/s][Count 2^37.48][01:52][Server     OK]

It says exactly how many kangaroos are running in parallel, 58,395,776 in this example:

Code:

eclambda --name testjob85 --gpu-mem-usage 0.9 --device 2
     ______ ______   __     ___     __  ___ ____   ____   ___
    / ____// ____/  / /    /   |   /  |/  // __ ) / __ \ /   |
   / __/  / /      / /    / /| |  / /|_/ // __  |/ / / // /| |
  / /___ / /___   / /___ / ___ | / /  / // /_/ // /_/ // ___ |
 /_____ / \____/ /_____//_/  |_|/_/  /_//_____//_____//_/  |_|
EC LAMBDA CLIENT
VERSION 1.1.1 ALPHA
[2020-06-22.16:26:33] [Info] Connecting to 127.0.0.1
[2020-06-22.16:26:34] [Info] Target public key:
[2020-06-22.16:26:34] [Info] X:F1367CC260779F7EA6C7E4B7258A4D31A4C41D6282C5200571CE10E748A4AADE
[2020-06-22.16:26:34] [Info] Y:0743F0CA057C7F39A9D9A20D4A93555B19F712920EEEF2F267466A2F3D08662E
[2020-06-22.16:26:34] [Info] Distinguisher: 24 bits
[2020-06-22.16:26:34] [Info] Sending results to server every 10 minutes
[2020-06-22.16:26:34] [Info] Initializing GeForce RTX 2080 SUPER
[2020-06-22.16:26:34] [Info] Compiling OpenCL kernels...
[2020-06-22.16:26:34] [Info] Initializing...
[2020-06-22.16:27:09] [Info] Generating 58,395,776 starting points (7184.1MB)
[2020-06-22.16:27:37] [Info] 10.0%
[2020-06-22.16:27:42] [Info] 20.0%
[2020-06-22.16:27:48] [Info] 30.0%
[2020-06-22.16:27:50] [Info] 40.0%
[2020-06-22.16:27:50] [Info] 50.0%
[2020-06-22.16:27:50] [Info] 60.0%
[2020-06-22.16:27:51] [Info] 70.0%
[2020-06-22.16:27:51] [Info] 80.0%
[2020-06-22.16:27:52] [Info] 90.0%
[2020-06-22.16:27:52] [Info] 100.0%
[2020-06-22.16:27:54] [Info] Refilling GPU cache (319.3MB)
[2020-06-22.16:27:54] [Info] 10.0%
[2020-06-22.16:27:54] [Info] 20.0%
[2020-06-22.16:27:55] [Info] 30.0%
[2020-06-22.16:27:55] [Info] 40.0%
[2020-06-22.16:27:55] [Info] 50.0%
[2020-06-22.16:27:55] [Info] 60.0%
[2020-06-22.16:27:55] [Info] 70.0%
[2020-06-22.16:27:55] [Info] 80.0%
[2020-06-22.16:27:55] [Info] 90.0%
[2020-06-22.16:27:55] [Info] 100.0%
[2020-06-22.16:27:55] [Info] Tuning started
[2020-06-22.16:27:55] [Info] Results collection thread started
[2020-06-22.16:28:05] [Info] DP: 0 TP: 0 587.62 Mpt/s (10 iter/s)
[2020-06-22.16:28:15] [Info] DP: 0 TP: 0 1212.69 Mpt/s (20 iter/s)
[2020-06-22.16:28:25] [Info] DP: 0 TP: 0 1170.13 Mpt/s (20 iter/s)
[2020-06-22.16:28:28] [Info] Tuning complete
[2020-06-22.16:28:35] [Info] DP: 0 TP: 0 1187.71 Mpt/s (20 iter/s)
[2020-06-22.16:28:40] [Info] Verifying 2785 results
[2020-06-22.16:28:45] [Info] DP: 0 TP: 0 1325.58 Mpt/s (22 iter/s)
[2020-06-22.16:28:55] [Info] DP: 0 TP: 0 1322.54 Mpt/s (22 iter/s)
[2020-06-22.16:29:05] [Info] DP: 0 TP: 0 1315.67 Mpt/s (22 iter/s)

It automatically finds the best grid size, so I do not know if it's useful to even display it.

Increasing --gpu-mem-usage increases performance. By default it's low to avoid timing out/crashing for people testing it on display GPUs.

Your soft support multypubkeys and multyadress in parallel  ? DP calculated automatically ? As for me If DP not automatic soft waste many times, and waste money only, and not give result and not wary about count of used GPU, soft can waste fom 1 to inf GPU times !!!

[WanderingPhilospher]

-snip-
I don't know so I'm not disagreeing with you but why would you need to cut any tame or wild out?
Same range, only thing changing would be what x coord to look for and compare for solution, right?

here is my reconstructor https://drive.google.com/file/d/1zHwoVjIvYhpgcTy_4sWin_A-3GMiTs5B
when you will first time reconstruct workfile use -checkdp 1 in bat file.
After few persent(or fraction of persent) of job if there will be ok and you don`t get any eror message then close reconstructor> set -checkdp 0> and launch again.
-checkdp 1 need only to see if wild DPs tamed in correct way.
param newpubkey use without prefix 04
If you will see error with -checkdp 1 than previousprivkey set invalid and recocosntructed wild DP has x-coordinate not the same as in source.
Source file not changed during reconstruction.. All DPs going to new work file.
After end of reconstruction you will see somesing like this:

Code:

100.00%
DP count    :240568
HT max      :8[@ 01D30E]
HT min      :0[@ 000001]
Tame count  :120410
Wild count  :120158
NumberOfWalk:0000000000000000
------------------------
TAME  [120410]
TAMED [120158]
SKIPED[0]
TOTAL TAME[240568]

Edit: if you not tamed your wild DPs they are useless to search new pubkeys, just
only memory is used, but there is no sense from them.
It is possible that they will lead to incorrect collisions if not tamed.

Thank you! I ran it on a lower bit, just the reconstruct, I haven't tested by running next pubkey.

[WanderingPhilospher]

Ah Ok, the timeout for idle client is 1hour, after the connection is closed. However when the client will send new DP, the connection is restored.

@Jean Luc...so I was running a longer test today. Same thing happened, started with 10 clients and a few hours in I dropped down to 6, and server says "closing connection..." but then it's back up to 10 clients but Kangaroo power does not reflect that of original kangaroo power. Example, if I started out with 10 clients and 2^25 kangaroos, it dropped to 6 clients, back up to 10 but now only 2^18. Why is that? Also, server does not state "client connecting..." the client number just goes back up to 10. Should I just let it be?

edit: I checked client side and it says server ok, but I can see where it stopped with this error: "The operation timed out" 
Thoughts?

[Jean_Luc]

Yes that's normal, the kangaroo counter works fine the first time and when a reconnection happens, the counter is not incremented again but the kangaroo are there. When a reconnection happens, the server does not display new connection.
I will fix this ASAP, it is just a display bug.
10 reflects the number of clients which have send DP in the last hour.
You can work around this by changing in Constant.h the IDLE timeout.

Code:

// Timeout before closing connection idle client in sec
#define CLIENT_TIMEOUT 3600.0

The important thing to check is the production of DP using -winfo on the server workfile(s).

[WanderingPhilospher]

Yes that's normal, the kangaroo counter works fine the first time and when a reconnection happens, the counter is not incremented again but the kangaroo are there. When a reconnection happens, the server does not display new connection.
I will fix this ASAP, it is just a display bug.
10 reflects the number of clients which have send DP in the last hour.
You can work around this by changing in Constant.h the IDLE timeout.

Code:

// Timeout before closing connection idle client in sec
#define CLIENT_TIMEOUT 3600.0

The important thing to check is the production of DP using -winfo on the server workfile(s).

Ok, I will do that. Yes, the DPs were still accumulating but that would happen whether it was 10 clients or 6.
I'm just glad it is still working as designed. I left it alone and letting it ride for now.
Thank you for the quick response!

[Jean_Luc]

@Jean Luc
If I solved a key at the 100 bit range and I want to reuse the dp file generated from that search, how do I reuse it to search for another pubkey in the exact same range and using the exact same dp?

You just merge the file, but at the moment you will take benefit only from old tames.

[racminer]

hi @BitCrack
Will you consider releasing a server-client version of bitcrack  ?

[BitCrack]

hi @BitCrack
Will you consider releasing a server-client version of bitcrack  ?

Yes, I have been working on it for a little while.

[racminer]

hi @BitCrack
Will you consider releasing a server-client version of bitcrack  ?

Yes, I have been working on it for a little while.

Great news 

don't forget to merge this https://github.com/brichard19/BitCrack/issues/256 if it is not already done.
And thanks a lot.

[RBan]

Hey guys please forgive my ignorance, I’m new to this and I was wondering if someone can clarify something that is related to the security of elliptic curves in general.

When we do an addition the secp256k1 curve’s equation (y² = x³ + 7 mod p) creates a loop that overflow and wraps max+1 to 0

My question is what is the possibility for the following:

1- A script that determines if an addition has reached the end of the curve and looped

2- An extended curve (over a larger field, or a larger mod p?) that would yield the same results for addition as secp256k1 but would loop further down the curve, so that by verifying the result, if the point is not on the secp256k1, we’d know it has looped.

My guess is that both are impossible as it would completely compromise the security of the elliptic curve, I just wanted to hear an educated answer on the matter.

Thank you

[Jean_Luc]

1- A script that determines if an addition has reached the end of the curve and looped

If you add 2 points and you know only one of the priv key of the 2 points, you cannot know if you make a turn or not otherwise ECDLP could be solved easily in polynomial time.

[arulbero]

I will definitely reduce jD to 128 bits in the next release, the less constant mem usage is better, there is 64Kb available but for L1 cache the lowest is the best.

What about removing completely the jD array?