brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning]

[NotATether]

Yes I agree to open an other topic, I'm still fighting to get the average running time in function of dp and nbKangaroo, this is quite complex and I got unexpected results but interesting
I'll open the new thread when I ends my statistics.

It's been very interesting seeing the results from doing kangaroo hops, so I support this decision. And then this thread should be locked since we seem to be getting derailed.

[arulbero]

I did a test, wanting to know the average time of the birthday paradox when searching collision between 2 tables (like the kangaroo problem).

The kangaroo method is announced to be 2.sqrt(n) but this is for a simple 2 stages algorithm where:
 - you first travel a single tame kangaroo sqrt(n) steps to setup a trap
 - then you make steps with the wild until a collision occurs (it falls in the trap), this second stage is expected to end in sqrt(n) steps.
The factor 2 comes from that. There no need of a hashtable there.

Hi,

let's see if I have understood this Kangaroo algorithm:

P=k*G, you know P and you know that a < k < b, for semplicity :  0 < k < a, for example: 0 < k < 2^64 (starting interval)

you generate many sequence of 2 type of points:

1) tame: each sequence starts from a random point T0 that lies in the starting interval, then

T0, T1, T2, ….     the difference between 2 consecutive points is: G, or 2*G, or 4*G, or 8*G, …, or 2^32*G

2) wild: each sequence starts from P + r*G, where r*G is a random point with a random r private key between 0 < k < 2^31), then:

W0, W1, W2, ….. the difference between 2 consecutive points is: G, or 2*G, or 4*G, …, or 2^32*G

each jump towards the next point depends on the x coordinate (mod 33) of the current point; in this way if a tame kangaroo reach a points already reached from a wild kangaroo (or viceversa), you have a collision and then same path from there.  

In that case T = W ->  t*G = w*G ->  t*G = P + w*G  ->  t*G = k*G + w*G -> k = (t-w) mod n

Besides you use distinguished points to detect this collision.


In this example you generate about 2^32 points  (T points) in the interval [1*G, (2^64+(2^32)(2^32))*G]
and about 2^32 points (W points) in the interval [P+r*G, ((k+r)+(2^32*2^32))*G]

let's say that both type of points have for sure their private keys in [1, 2^65] interval

But can you treat these points like if they were random? Can you apply in this case the birthday paradox?

[MrFreeDragon]

-snip-
But can you treat these points like if they were random? Can you apply in this case the birthday paradox?

The DP method (distinguished points) with a hashtable is used. That means that every subsequent jump is dependent from the x-coordinate of the current location. That means that pseudorandom walks are used for the kangaroos. No need to store all the visited points for this case.

From here the definition (page 4, 1st par): https://eprint.iacr.org/2014/565.pdf

a point is a distinguished point - if its representation exhibits a certain bit pattern, e.g., has the top 20 bits equal
to zero. Whenever one of the parallel random walks reaches such a point it is stored on a central processor

[arulbero]

-snip-
But can you treat these points like if they were random? Can you apply in this case the birthday paradox?

The DP method (distinguished points) with a hashtable is used. That means that every subsequent jump is dependent from the x-coordinate of the current location. That means that pseudorandom walks are used for the kangaroos. No need to store all the visited points for this case.

Yes, this is clear, but these points seem to me not to be really (pseudo)random. There is a order. You can move only forward (from private key's point of view). Therefor many collisions are just impossible to get (instead in the birthday paradox, each new distinguished point has the chance to produce a collision with any previous distinguished point, for example that happens in BTCCollider, because in that case you can jump in any position, you go back and forth across the entire space)

Example with only 2 sequences:

If we suppose that W_100 is = (2^37)*G and T_100 is (2^38)*G, than between T_101, T_102, .... , T_2**32 it is no longer possible to find a single distinguished point with the same coordinate of any distinguished point that lies in W_0, W_1, W_2, ....., W_100. For sure.

Then how do you apply in this case birthday paradox?

It is impossible to get a collision in the path of the same tame kangaroo too, because the same kangaroo cannot turn back, then this is a pseudorandom sequence very particular ...

[Tamarindei]

-snip-
But can you treat these points like if they were random? Can you apply in this case the birthday paradox?

The DP method (distinguished points) with a hashtable is used. That means that every subsequent jump is dependent from the x-coordinate of the current location. That means that pseudorandom walks are used for the kangaroos. No need to store all the visited points for this case.

Yes, this is clear, but these points seem to me not to be really (pseudo)random. There is a order. You can move only forward (from private key's point of view). Therefor many collisions are just impossible to get (instead in the birthday paradox, each new distinguished point has the chance to produce a collision with any previous distinguished point, for example that happens in BTCCollider, because in that case you can jump in any position, you go back and forth across the entire space)

Example with only 2 sequences:

If we suppose that W_100 is = (2^37)*G and T_100 is (2^38)*G, than between T_101, T_102, .... , T_2**32 it is no longer possible to find a single distinguished point with the same coordinate of any distinguished point that lies in W_0, W_1, W_2, ....., W_100. For sure.

Then how do you apply in this case birthday paradox?

It is impossible to get a collision in the path of the same tame kangaroo too, because the same kangaroo cannot turn back, then this is a pseudorandom sequence very particular ...

I think that's why the papers you find don't use the birthday paradox to analyze pollard kangaroo. Birthday paradox is used for the very similar gaudry schost algorithm. Gaudry schost algorithm sets the point to a new random location in the interval as soon as a distinguished point is found and saved.

[HardwareCollector]

Yes, this is clear, but these points seem to me not to be really (pseudo)random. There is a order. You can move only forward (from private key's point of view). Therefor many collisions are just impossible to get (instead in the birthday paradox, each new distinguished point has the chance to produce a collision with any previous distinguished point, for example that happens in BTCCollider, because in that case you can jump in any position, you go back and forth across the entire space)

Example with only 2 sequences:

If we suppose that W_100 is = (2^37)*G and T_100 is (2^38)*G, than between T_101, T_102, .... , T_2**32 it is no longer possible to find a single distinguished point with the same coordinate of any distinguished point that lies in W_0, W_1, W_2, ....., W_100. For sure.

Then how do you apply in this case birthday paradox?

It is impossible to get a collision in the path of the same tame kangaroo too, because the same kangaroo cannot turn back, then this is a pseudorandom sequence very particular ...

Maybe the following links will help with understanding the motivations behind the Kangaroo method:

https://web.northeastern.edu/seigen/11Magic/KruskalsCount/Kruskal'sCount.html

https://web.northeastern.edu/seigen/11Magic/KruskalsCount/Pollard.pdf

Pollard’s Rho method is based on the birthday paradox, but the Kangaroo method on the other hand is not.

[MrFreeDragon]

-snip-
If we suppose that W_100 is = (2^37)*G and T_100 is (2^38)*G, than between T_101, T_102, .... , T_2**32 it is no longer possible to find a single distinguished point with the same coordinate of any distinguished point that lies in W_0, W_1, W_2, ....., W_100. For sure.
-snip-

I am not sure if I understand you correct. But T_101, T_102, ... etc are not the distinguished points, these are jump points. At the start only the jump point table is prepared.
It is not possible to know all the distinguished points within the working range. Distinguished point is a property of point. As soon as the point meets this property, it goes to the hash table:

if tamePosi is distinguished
       add (TAME,tamePosi,tamei) to hashTable
if wildPosi is distinguished
       add (WILD,wildPosi,wildi) to hashTable

The kangaroo (as wild so tame) will jump permanently by pseudorandom steps from the jump table while reach the Point with patterned X-coordinate (the distinguished point). As reach the distinguished point, this point just saved in the hashtable (kangaroo type, distance, Point) check for coliddion, and kangaroo continues to jump.

-snip-
It is impossible to get a collision in the path of the same tame kangaroo too, because the same kangaroo cannot turn back, then this is a pseudorandom sequence very particular ...

The same kangaroo can not go back, but due to symmetry point it so not needed.
P=k*G, you know P and you know that a < k < b. Actually Point P'=k'*G is also suitable for us if k' = b - (k-a) = b + a - k, which is also lies in the range a..b

[Jean_Luc]

Yes the random walk with kangaroo is particular as the path cannot be truncated easily modulo n (n=range size). So the kangaroos can go outside of the range. This is not a problem as the 2 herds travel at the same average speed. The jumpDistane table has an average of sqrt(n) so after sqrt(n) jumps the kangaroos reach the end of the range. The points in the hastable 'older' than ~2.sqrt(n) jumps can be cleared (this is not done, but the collision should happen more or less at the same time).

As we don't know where is the private key, there is a worst case when this key is near the begining or the end of the range.

The worst case correspond to 3sqrt(PI)/2.sqrt(n) and the best case to sqrt(pi).sqrt(n), so the average is 5.sqrt(pi)/4 which give an average time complexity of ~2.21.sqrt(n) (green curve) but the difficulty is to find the complexity according to the number of kangaroo and DP. I found an approximation of the asymptote when nbKangaroo goes to infinity which is ~ cubicroot( nbKangaroo.16.n.2^dp ) (blue curves)
Red curve are experimental points each averaged on 1000 40bits searches with key uniformly distributed in the range.




Edit: A zoom near the average:

[COBRAS]

Hello everybodey !!!

Please help me.

I have access to hiend Tesla GPU what I will end in a same day later.

I try to test Kangaroo on real pubkeys but unsoccesfull. Then  I use DP=9 computation speed down from 500MKeys to 11MKeys/second (!!!!) I try use 68 Byte ranges etc. ALL THIS UNSUCCESFULL FOR ME.

Please someone tall me what settings I will nedd for starting Kangarok( -d, greed size, etc) and what renges I need to use ?

I veryh need help ASAP.

Big thanks !!!

[COBRAS]

This is examples from my today tests:

plazmosis.exe - is a renamed kangaroo.exe

The system cannot find the path specified.

C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Keys :13
Number of CPU thread: 0
Range width: 2^160
Number of random walk: 2^20.58 (Max DP=57)
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 10919.1ms
[459.75 MKey/s][GPU 459.75 MKey/s][Count 2^33.49][Dead 0][30s][34.2MB]  ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^160
Number of random walk: 2^20.58 (Max DP=57)
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
^C
C:\Plasmosis>

C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^80
Number of random walk: 2^20.58 (Max DP=17)
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^80
Number of random walk: 2^20.58 (Max DP=17)
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 7390.7ms

Warning, 66588 items lost
Hint: Search with less threads (-g)
[135.88 MKey/s][GPU 135.88 MKey/s][Count 2^32.10][Dead 0][32s][1832.9MB]  ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^52
Number of random walk: 2^20.58 (Max DP=3)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6336.7ms

Warning, 65695 items lost
Hint: Search with less threads (-g)
[135.05 MKey/s][GPU 135.05 MKey/s][Count 2^31.65][Dead 507][25s][1335.4MB]  ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^52
Number of random walk: 2^20.58 (Max DP=3)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6149.4ms

Warning, 65678 items lost
Hint: Search with less threads (-g)
[332.32 MKey/s][GPU 332.32 MKey/s][Count 2^29.98][Dead 27][04s][417.1MB]  ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^52
Number of random walk: 2^20.58 (Max DP=3)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6128.5ms

Warning, 65678 items lost
Hint: Search with less threads (-g)
[251.78 MKey/s][GPU 251.78 MKey/s][Count 2^30.71][Dead 98][10s][704.4MB]  ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^52
Number of random walk: 2^20.58 (Max DP=3)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6148.2ms
[460.02 MKey/s][GPU 460.02 MKey/s][Count 2^33.81][Dead 1050][37s][40.6MB]  ^C
C:\Plasmosis>

C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^60
Number of random walk: 2^20.58 (Max DP=7)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6501.1ms
[459.77 MKey/s][GPU 459.77 MKey/s][Count 2^34.30][Dead 11][52s][53.5MB]  ^C
C:\Plasmosis>

C:\Plasmosis>plazmosisdna.exe -t 0 -d 15 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^68
Number of random walk: 2^20.58 (Max DP=11)
Warning, DP is too large, it may cause significant overload.
Hint: decrease number of threads, gridSize, or decrese dp using -d.
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 7050.7ms
[459.78 MKey/s][GPU 459.78 MKey/s][Count 2^38.50][Dead 81][16:02][907.6MB]  ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^68
Number of random walk: 2^20.58 (Max DP=11)
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6794.7ms

Warning, 65975 items lost
Hint: Search with less threads (-g)
[268.25 MKey/s][GPU 268.25 MKey/s][Count 2^30.81][Dead 0][10s][749.8MB]  ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 9 -gpu -g 96,128 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^68
Number of random walk: 2^20.58 (Max DP=11)
DP size: 9 [0xFF80000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(96x128) (153.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.58 kangaroos in 6872.2ms
[183.93 MKey/s][GPU 183.93 MKey/s][Count 2^35.38][Dead 0][03:25][6682.8MB]  ^C
C:\Plasmosis>plazmosisdna.exe -t 0 -d 7 -gpu -g 128,256 in.txt
Kangaroo v1.3
Start:0
Stop :FFFFFFFFEBAAEDCE6
Keys :13
Number of CPU thread: 0
Range width: 2^68
Number of random walk: 2^22.00 (Max DP=10)
DP size: 7 [0xFE00000000000000]
GPU: GPU #0 Tesla T4 (40x64 cores) Grid(128x256) (393.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^22.00 kangaroos in 17993.3ms

Warning, 393221 items lost
Hint: Search with less threads (-g)
[11.02 MKey/s][GPU 11.02 MKey/s][Count 2^36.33][Dead 0][22:28][12887.4MB]

[Jean_Luc]

I published a pre-release with the new calculation for expected operation.
I also changed the jump Table size to make it multiple of power of 2 in order to avoid the modulo, this should brings little improvement on GPU.
Thanks to test it
https://github.com/JeanLucPons/Kangaroo/releases/tag/1.4beta

@COBRAS: do not use a Tesla on small range and if you don't know where is the private key (in a range) you have to specify the full range:
0
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140
but in that case, your tesla will end its calculation when the earth will collapse on the sun

[COBRAS]

Video with lincks for reading:

"Pollard-Kangaroo GPU CUDA & Quadratic sieve"   


https://youtu.be/kMevZQc7774

[HardwareCollector]

I published a pre-release with the new calculation for expected operation.
I also changed the jump Table size to make it multiple of power of 2 in order to avoid the modulo, this should brings little improvement on GPU.
Thanks to test it
https://github.com/JeanLucPons/Kangaroo/releases/tag/1.4beta

@COBRAS: do not use a Tesla on small range and if you don't know where is the private key (in a range) you have to specify the full range:
0
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364140
but in that case, your tesla will end its calculation when the earth will collapse on the sun

While using your 72-bit test range on an RTX 2070, out of the box, v1.4beta appears to be slightly slower than v1.3 in terms of group operations per second 770M vs 848M for v1.3. But the average time to solve the 20 ECDLPs was about the same, 1h:23m vs 1h:13m for v1.4beta vs v1.3 respectively

Code:

./kangaroo -t 0 -gpu -gpuId 0 in72.txt
Kangaroo v1.4beta
Start:59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1000000000000000000
Stop :59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1FFFFFFFFFFFFFFFFFF
Keys :20
Number of CPU thread: 0
Range width: 2^72
Jump Avg distance: 2^35.99
Number of kangaroos: 2^20.17
Suggested DP: 14
Expected operations: 2^37.15
Expected RAM: 710.0MB
DP size: 14 [0xfffc000000000000]
GPU: GPU #0 GeForce RTX 2070 (36x64 cores) Grid(72x128) (117.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.17 kangaroos in 9830.1ms
[774.39 MK/s][GPU 774.39 MK/s][Count 2^37.74][Dead 4][05:38 (Avg 03:16)][1075.0MB]
Key# 0 Pub:  0x038F63B86D8EE91D4B78FF4680F927DCC7754CF734A386ED5FA45E71DE9328F433
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D102F962838A4EE7364E
[771.71 MK/s][GPU 771.71 MK/s][Count 2^37.96][Dead 6][06:45 (Avg 03:17)][1247.3MB]
Key# 1 Pub:  0x0389044AFFFD381B496D63F8C80CDAAB5E57E40DEE6A56C8AFA5194B1FFD83FEBB
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1F5821BA583622EEE49
[770.30 MK/s][GPU 770.30 MK/s][Count 2^38.38][Dead 6][08:59 (Avg 03:17)][1668.1MB]
Key# 2 Pub:  0x0338E88602F88C3268C68552C4C53987F41BB42335A8E36658A80D2F5BDF63615B
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D110DC466D7E3D293A10
[771.83 MK/s][GPU 771.83 MK/s][Count 2^35.79][Dead 0][01:38 (Avg 03:17)][282.8MB]
Key# 3 Pub:  0x026776529C6C8932ABF9DCFDCB2DB2784DCE82164914D4C3294FECFE1B48F3BF27
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1DE55BDE3E1B2F36A9B
[771.87 MK/s][GPU 771.87 MK/s][Count 2^36.66][Dead 0][02:50 (Avg 03:17)][509.0MB]
Key# 4 Pub:  0x03312940E0EE296C23B1E7888A4D23FED01358C1021FE2091D909B0A8D8AA80DE1
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D11B78CA8A9FBCDBDE3E
[773.06 MK/s][GPU 773.06 MK/s][Count 2^38.09][Dead 5][07:23 (Avg 03:16)][1364.0MB]
Key# 5 Pub:  0x020097A3826A7BC1EC5383AE390EEA8C436B2B6D2E3770493F7E993B164C9F233E
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D152477D7EC473A483D4
[771.82 MK/s][GPU 771.82 MK/s][Count 2^36.64][Dead 0][02:48 (Avg 03:17)][503.6MB]
Key# 6 Pub:  0x03DAE902F3F4E0A62AA7DF422B2BF802CD9ADA747177F853390BEB7F203E4C3F84
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D10D2AB0CDE883E6B3BC
[770.32 MK/s][GPU 770.32 MK/s][Count 2^37.73][Dead 1][05:48 (Avg 03:17)][1068.4MB]
Key# 7 Pub:  0x023C4E51FD6EB029CFD4DDCBD93FAD060C7D026D252EC37923355D1B192C69B9E3
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1B69F2EC54CEEBA50C4
[770.25 MK/s][GPU 770.25 MK/s][Count 2^37.02][Dead 1][03:36 (Avg 03:17)][655.0MB]
Key# 8 Pub:  0x03C3112770BC8455596AF38A2A2E3F556B1F02758945608364C3AFD22FAD806B8D
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D18D06BC6E25E5C7EAEF
[771.48 MK/s][GPU 771.48 MK/s][Count 2^37.83][Dead 3][06:13 (Avg 03:17)][1142.8MB]
Key# 9 Pub:  0x0264AE637A90AA93798E7BA6CCFD57CB077BCCAE49D3AB76F6857CA044A423E3AC
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1C8A4760400224E8C05
[773.00 MK/s][GPU 773.00 MK/s][Count 2^36.19][Dead 0][02:06 (Avg 03:16)][371.4MB]
Key#10 Pub:  0x0359A0CFB0958A2B6FC562B3824D0BE034C7E947780DAF4B8AF403C72D92496BEF
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D197AD08D8E14C058778
[773.00 MK/s][GPU 773.00 MK/s][Count 2^36.56][Dead 0][02:40 (Avg 03:16)][477.0MB]
Key#11 Pub:  0x020B58A06DC49B931A8B9C08E29306B70FBB56F4F3B8BAB7AEBD409B4DC8086C78
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1C831BC0E9C1450CCCE
[770.41 MK/s][GPU 770.41 MK/s][Count 2^37.58][Dead 2][05:14 (Avg 03:17)][959.8MB]
Key#12 Pub:  0x039E8FE48D08C5465128681D49AE9026240BC612C9BC8A3B6E9D2FA00DBC9021AF
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D17941FCB9F89FAA2C79
[772.81 MK/s][GPU 772.81 MK/s][Count 2^35.69][Dead 0][01:32 (Avg 03:17)][264.3MB]
Key#13 Pub:  0x02131119C5618C26AB5C8DE1B16E60120C918AAC717B06A10ADBCC4BCF44106419
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D166208474EA5CD1D0D9
[773.03 MK/s][GPU 773.03 MK/s][Count 2^35.86][Dead 2][01:42 (Avg 03:16)][295.4MB]
Key#14 Pub:  0x02487FE068AFA2AAFC96EC2941EC8CF4E2600692F8D4F6E4A389AFEA44221E045D
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1AD9E1D5075941AB176
[773.02 MK/s][GPU 773.02 MK/s][Count 2^36.52][Dead 0][02:36 (Avg 03:16)][464.7MB]
Key#15 Pub:  0x034B202C91CF7AA1563048AFCED10781666C8344E0A23884977F5F3396E3CDFBFE
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D166550C0FED3225AE1D
[766.48 MK/s][GPU 766.48 MK/s][Count 2^37.31][Dead 1][04:22 (Avg 03:18)][797.9MB]
Key#16 Pub:  0x023510C7370A558126EF057C738A4943021E5FB08B41799AE097190DFC5538DB69
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D16DA62AB9D45017CFF3
[773.05 MK/s][GPU 773.05 MK/s][Count 2^36.15][Dead 0][02:04 (Avg 03:16)][360.8MB]
Key#17 Pub:  0x0336CE6F79E48B6493CF2BC2DE87BFE9504D30CD62B9B5F992E1A5933D69076A76
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1A7F3A8F6001FFF3E8C
[770.36 MK/s][GPU 770.36 MK/s][Count 2^37.85][Dead 1][06:17 (Avg 03:17)][1157.1MB]
Key#18 Pub:  0x03292ACD7402F076829CF4DC40B659D24ACCF67F2884DF4CD111847C651F18512A
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1DF6AE20D48B230C23C
[771.87 MK/s][GPU 771.87 MK/s][Count 2^35.92][Dead 1][01:46 (Avg 03:17)][307.8MB]
Key#19 Pub:  0x036C4AF425D93153FD0593787399A78322699F498C4703E2D1524C15F0137C2D14
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D13B97B84AC3FBEDF0AF

Done: Total time 01:23:26

[arulbero]

Yes the random walk with kangaroo is particular as the path cannot be truncated easily modulo n (n=range size). So the kangaroos can go outside of the range. This is not a problem as the 2 herds travel at the same average speed. The jumpDistane table has an average of sqrt(n) so after sqrt(n) jumps the kangaroos reach the end of the range.

Ok.

I think that it would be faster if you used a hashtable with precomputed distinguished points (the tame points).

The speed should double.

[HardwareCollector]

I think that it would be faster if you used a hashtable with precomputed distinguished points (the tame points).

The speed should double.

Yes, it should be significantly faster when solving for multiple instances, since there’s no need to discard the previous distinguished points.

[Jean_Luc]

While using your 72-bit test range on an RTX 2070, out of the box, v1.4beta appears to be slightly slower than v1.3 in terms of group operations per second 770M vs 848M for v1.3. But the average time to solve the 20 ECDLPs was about the same, 1h:23m vs 1h:13m for v1.4beta vs v1.3 respectively

Manu thanks for the test
Bad news for the lower speed . On my low cost GPU it is 10% faster. Will try to understand why ?

I think that it would be faster if you used a hashtable with precomputed distinguished points (the tame points).

I don't think it will change something (at least on single key search). You can may be win memory.

In the above readings, a guy announced a speed slightly lower than 1.77sqrt(n) [1.73qrt(n)] but I must say that it is hard to believe his method can beat the birthday paradox. I didn't enter in details in its analysis and it is done on DLP not ECDLP.
In any case, to beat the birthday paradox, you have to find a way to maximize the probability of natural random collision.

[Jean_Luc]

While using your 72-bit test range on an RTX 2070, out of the box, v1.4beta appears to be slightly slower than v1.3 in terms of group operations per second 770M vs 848M for v1.3. But the average time to solve the 20 ECDLPs was about the same, 1h:23m vs 1h:13m for v1.4beta vs v1.3 respectively

As you compile by yourself, could you try to change

In GPU/GPUEngine.h:24

#define NB_JUMP 64

to

#define NB_JUMP 32

and tell me what is your key rate, thanks

[HardwareCollector]

While using your 72-bit test range on an RTX 2070, out of the box, v1.4beta appears to be slightly slower than v1.3 in terms of group operations per second 770M vs 848M for v1.3. But the average time to solve the 20 ECDLPs was about the same, 1h:23m vs 1h:13m for v1.4beta vs v1.3 respectively

As you compile by yourself, could you try to change

In GPU/GPUEngine.h:24

#define NB_JUMP 64

to

#define NB_JUMP 32

and tell me what is your key rate, thanks

With the above recommended changes to v1.4beta:

Code:

./kangaroo -t 0 -d 13 -gpu -gpuId 0 in72.txt
Kangaroo v1.4beta
Start:59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1000000000000000000
Stop :59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1FFFFFFFFFFFFFFFFFF
Keys :20
Number of CPU thread: 0
Range width: 2^72
Jump Avg distance: 2^36.03
Number of kangaroos: 2^20.17
Suggested DP: 14
Expected operations: 2^37.15
Expected RAM: 1419.0MB
DP size: 13 [0xfff8000000000000]
GPU: GPU #0 GeForce RTX 2070 (36x64 cores) Grid(72x128) (117.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.17 kangaroos in 9840.1ms
[860.47 MK/s][GPU 860.47 MK/s][Count 2^37.23][Dead 1][03:32 (Avg 02:56)][1501.4MB]
Key# 0 Pub:  0x038F63B86D8EE91D4B78FF4680F927DCC7754CF734A386ED5FA45E71DE9328F433
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D102F962838A4EE7364E

v1.3 stock with 13-bit distinguished point mask:

Code:

./kangaroo -t 0 -d 13 -gpu -gpuId 0 in72.txt
Kangaroo v1.3
Start:59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1000000000000000000
Stop :59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1FFFFFFFFFFFFFFFFFF
Keys :20
Number of CPU thread: 0
Range width: 2^72
Number of kangaroos: 2^20.17
Suggested DP: 14
Expected operations: 2^37.10
Expected RAM: 1371.0MB
DP size: 13 [0xfff8000000000000]
GPU: GPU #0 GeForce RTX 2070 (36x64 cores) Grid(72x128) (117.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.17 kangaroos in 9829.6ms
[841.66 MK/s][GPU 841.66 MK/s][Count 2^36.81][Dead 0][02:42 (Avg 02:54)][1124.8MB]
Key# 0 Pub:  0x038F63B86D8EE91D4B78FF4680F927DCC7754CF734A386ED5FA45E71DE9328F433
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D102F962838A4EE7364E
[847.09 MK/s][GPU 847.09 MK/s][Count 2^34.48][Dead 0][42s (Avg 02:53)][227.8MB]
Key# 1 Pub:  0x0389044AFFFD381B496D63F8C80CDAAB5E57E40DEE6A56C8AFA5194B1FFD83FEBB
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1F5821BA583622EEE49
[845.55 MK/s][GPU 845.55 MK/s][Count 2^37.67][Dead 2][05:06 (Avg 02:53)][2047.7MB]
Key# 2 Pub:  0x0338E88602F88C3268C68552C4C53987F41BB42335A8E36658A80D2F5BDF63615B
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D110DC466D7E3D293A10
[845.64 MK/s][GPU 845.64 MK/s][Count 2^37.75][Dead 2][05:22 (Avg 02:53)][2159.2MB]
Key# 3 Pub:  0x026776529C6C8932ABF9DCFDCB2DB2784DCE82164914D4C3294FECFE1B48F3BF27
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1DE55BDE3E1B2F36A9B
[842.89 MK/s][GPU 842.89 MK/s][Count 2^36.66][Dead 1][02:36 (Avg 02:54)][1015.0MB]
Key# 4 Pub:  0x03312940E0EE296C23B1E7888A4D23FED01358C1021FE2091D909B0A8D8AA80DE1
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D11B78CA8A9FBCDBDE3E
[845.68 MK/s][GPU 845.68 MK/s][Count 2^37.23][Dead 3][03:48 (Avg 02:53)][1511.0MB]
Key# 5 Pub:  0x020097A3826A7BC1EC5383AE390EEA8C436B2B6D2E3770493F7E993B164C9F233E
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D152477D7EC473A483D4
[840.32 MK/s][GPU 840.32 MK/s][Count 2^36.82][Dead 1][02:54 (Avg 02:55)][1136.9MB]
Key# 6 Pub:  0x03DAE902F3F4E0A62AA7DF422B2BF802CD9ADA747177F853390BEB7F203E4C3F84
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D10D2AB0CDE883E6B3BC
[844.38 MK/s][GPU 844.38 MK/s][Count 2^37.31][Dead 2][04:00 (Avg 02:54)][1593.2MB]
Key# 7 Pub:  0x023C4E51FD6EB029CFD4DDCBD93FAD060C7D026D252EC37923355D1B192C69B9E3
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1B69F2EC54CEEBA50C4
[844.25 MK/s][GPU 844.25 MK/s][Count 2^36.53][Dead 0][02:24 (Avg 02:54)][930.5MB]
Key# 8 Pub:  0x03C3112770BC8455596AF38A2A2E3F556B1F02758945608364C3AFD22FAD806B8D
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D18D06BC6E25E5C7EAEF
[842.89 MK/s][GPU 842.89 MK/s][Count 2^37.37][Dead 3][04:10 (Avg 02:54)][1663.0MB]
Key# 9 Pub:  0x0264AE637A90AA93798E7BA6CCFD57CB077BCCAE49D3AB76F6857CA044A423E3AC
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1C8A4760400224E8C05
[845.50 MK/s][GPU 845.50 MK/s][Count 2^36.55][Dead 0][02:26 (Avg 02:53)][945.1MB]
Key#10 Pub:  0x0359A0CFB0958A2B6FC562B3824D0BE034C7E947780DAF4B8AF403C72D92496BEF
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D197AD08D8E14C058778
[844.35 MK/s][GPU 844.35 MK/s][Count 2^37.88][Dead 2][05:53 (Avg 02:54)][2365.1MB]
Key#11 Pub:  0x020B58A06DC49B931A8B9C08E29306B70FBB56F4F3B8BAB7AEBD409B4DC8086C78
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1C831BC0E9C1450CCCE
[840.41 MK/s][GPU 840.41 MK/s][Count 2^36.25][Dead 1][02:00 (Avg 02:55)][765.7MB]
Key#12 Pub:  0x039E8FE48D08C5465128681D49AE9026240BC612C9BC8A3B6E9D2FA00DBC9021AF
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D17941FCB9F89FAA2C79
[844.44 MK/s][GPU 844.44 MK/s][Count 2^36.02][Dead 0][01:44 (Avg 02:54)][655.9MB]
Key#13 Pub:  0x02131119C5618C26AB5C8DE1B16E60120C918AAC717B06A10ADBCC4BCF44106419
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D166208474EA5CD1D0D9
[845.74 MK/s][GPU 845.74 MK/s][Count 2^34.68][Dead 0][48s (Avg 02:53)][261.3MB]
Key#14 Pub:  0x02487FE068AFA2AAFC96EC2941EC8CF4E2600692F8D4F6E4A389AFEA44221E045D
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1AD9E1D5075941AB176
[818.45 MK/s][GPU 818.45 MK/s][Count 2^33.45][Dead 0][26s (Avg 02:59)][114.5MB]
Key#15 Pub:  0x034B202C91CF7AA1563048AFCED10781666C8344E0A23884977F5F3396E3CDFBFE
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D166550C0FED3225AE1D
[841.62 MK/s][GPU 841.62 MK/s][Count 2^36.33][Dead 1][02:06 (Avg 02:54)][807.3MB]
Key#16 Pub:  0x023510C7370A558126EF057C738A4943021E5FB08B41799AE097190DFC5538DB69
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D16DA62AB9D45017CFF3
[841.51 MK/s][GPU 841.51 MK/s][Count 2^36.22][Dead 0][01:58 (Avg 02:54)][752.1MB]
Key#17 Pub:  0x0336CE6F79E48B6493CF2BC2DE87BFE9504D30CD62B9B5F992E1A5933D69076A76
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1A7F3A8F6001FFF3E8C
[848.25 MK/s][GPU 848.25 MK/s][Count 2^35.73][Dead 0][01:28 (Avg 02:53)][536.4MB]
Key#18 Pub:  0x03292ACD7402F076829CF4DC40B659D24ACCF67F2884DF4CD111847C651F18512A
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D1DF6AE20D48B230C23C
[845.62 MK/s][GPU 845.62 MK/s][Count 2^37.06][Dead 0][03:24 (Avg 02:53)][1339.9MB]
Key#19 Pub:  0x036C4AF425D93153FD0593787399A78322699F498C4703E2D1524C15F0137C2D14
       Priv: 0x59C0465E6C5C5502E17E79A74FE1FF5365707890EB68D13B97B84AC3FBEDF0AF

Done: Total time 58:02

[Jean_Luc]

Thanks
So it seems a bit faster with 32 jumps.
I will make tests to see if affects the average number of operation.

[MrFreeDragon]

Thanks
So it seems a bit faster with 32 jumps.
I will make tests to see if affects the average number of operation.

Why it was faster with 32 jumps for him? Do you have the exaplanation?

Also nice things you added:
Expected operations: 2^37.15
Expected RAM: 1419.0MB

What is the current formula you use for Expected operations?