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

COBRAS

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: Jean_Luc on April 24, 2020, 07:39:09 AM

Thanks for the reading and the tests

The dead kangaroos are well handled, they are detected, deleted and recreated.
Was quite a nightmare with the GPU and coalesced memory access Cheesy

The only things that might happen is that a kangaroo enter in a cycle without having a distinguished point in the cycle but it is rather unlikely.
Handling this in the GPU (with a Floyd cycle detection) will just kill GPU performance.

Jean_Luc, can you edit code for geting good resualt ? Please.... I very hope Kangaroo will can brute bitcoin...

??

Jean_Luc

sr. member

Activity: 462

Merit: 701

Thanks for the reading and the tests

The dead kangaroos are well handled, they are detected, deleted and recreated.
Was quite a nightmare with the GPU and coalesced memory access Cheesy

The only things that might happen is that a kangaroo enter in a cycle without having a distinguished point in the cycle but it is rather unlikely.
Handling this in the GPU (with a Floyd cycle detection) will just kill GPU performance.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: Jean_Luc on April 24, 2020, 03:07:43 AM

I solved 20 times the following key (64bit range) and there was a strange 24 dead kangaroos event !? It seems that from times to times the algorithm has hard time to solve the key... Just a matter of probability ? My Mersenne twister fails ? I will make further tests...

Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4
-snip-

I tried to do the same (solved 20 times the same key as you). The total result was the same as test with 64bit before: average 1minute per 64bit range key (total 20:52 min for 20 keys).
It seems that my GPU card is more friendly - maximum kangaroo kills was 8 times for the first time.

[300.90 MKey/s][GPU 300.90 MKey/s][Count 2^34.32][Dead 8][01:06][3192.1MB]
[347.36 MKey/s][GPU 347.36 MKey/s][Count 2^33.94][Dead 7][52s][2462.2MB]
[456.28 MKey/s][GPU 456.28 MKey/s][Count 2^32.93][Dead 1][26s][1223.2MB]
[415.46 MKey/s][GPU 415.46 MKey/s][Count 2^33.44][Dead 4][36s][1742.3MB]
[350.83 MKey/s][GPU 350.83 MKey/s][Count 2^32.23][Dead 0][18s][754.4MB]
[403.60 MKey/s][GPU 403.60 MKey/s][Count 2^33.52][Dead 2][38s][1837.3MB]
[299.12 MKey/s][GPU 299.12 MKey/s][Count 2^31.98][Dead 0][16s][635.9MB]
[458.32 MKey/s][GPU 458.32 MKey/s][Count 2^32.80][Dead 0][26s][1120.4MB]
[280.27 MKey/s][GPU 280.27 MKey/s][Count 2^34.59][Dead 6][01:28][3846.3MB]
[203.74 MKey/s][GPU 203.74 MKey/s][Count 2^30.73][Dead 0][10s][270.9MB]
[296.67 MKey/s][GPU 296.67 MKey/s][Count 2^34.36][Dead 6][01:14][3301.0MB]
[279.64 MKey/s][GPU 279.64 MKey/s][Count 2^31.67][Dead 0][14s][514.0MB]
[324.70 MKey/s][GPU 324.70 MKey/s][Count 2^34.13][Dead 4][01:02][2811.4MB]
[297.73 MKey/s][GPU 297.73 MKey/s][Count 2^34.38][Dead 7][01:14][3339.0MB]
[426.65 MKey/s][GPU 426.65 MKey/s][Count 2^33.35][Dead 2][34s][1635.3MB]
[408.92 MKey/s][GPU 408.92 MKey/s][Count 2^32.45][Dead 2][20s][875.8MB]
[321.43 MKey/s][GPU 321.43 MKey/s][Count 2^34.17][Dead 4][01:02][2876.2MB]
[250.27 MKey/s][GPU 250.27 MKey/s][Count 2^34.98][Dead 7][02:04][5059.6MB]
[321.52 MKey/s][GPU 321.52 MKey/s][Count 2^34.16][Dead 2][01:02][2868.8MB]
[353.13 MKey/s][GPU 353.13 MKey/s][Count 2^33.89][Dead 3][50s][2379.2MB]

Done: Total time 20:52

That "dead" kangaroo case is the cycle running. Kangaroos running in cycles do not find new points, but slow down the algorithm and also might cause it to fail. This was described by Edlyn Teske in Computing discrete logarithms with theparallelized kangaroo method work (see 6.3):

https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.32.8520

EDIT: remove code tag from the 20 results to bold the maximum DEAD

Jean_Luc

sr. member

Activity: 462

Merit: 701

Yes there is a problem with the spreading of wild kangaroo i think.
They should be spread with a -(k2-k1)/2 translation, the keys you solved are close to the upper bound, it explains the factor of 2.
I will try this ASAP.
Many thanks for the tests Wink

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Tried to use Kangaroo v1.2 on Ubuntu and searched for 2^80 range width. The 1st key was solved for the same tim 3h15min, the 2nd for 4h and the 3d for 4h13min. Here are the results:

Code:

input 5 public keys:
046cf3ec949c28918ed0fdc48980b3339343ceb822acd9b7b3a0d16d9606aeb139507c48c74b81fde39c415117f914fd850e8a64bde218e99b6d74b2012977df56
04948282bfa4cc7aaa1722f0f72ce9b3708061960084ba188a2c66713c46070f45c9a997916266123aacbc5fbc76e1a0a133ab92410466f19f92e67ab1716f0db4
0491a7b757335e7026e83c42b868dd6c4a8f379e7ef059de9a1fc1b7e4e770749ae1ed4034f6d24d0da3d7ce10ce3c543dade4b812f118e0d0897ca2d42aa1e3d7
0420c453ffcc3840c90c33f695bb1d573d2860c2203c75808ae45a168aa17995af952bea588e1362d9cefe0977a96ea79f554d5809291c20339b3427b55c48859f
0432b9ca00d710738587a4ac0f7aad49516e0ca04ea1a19e9548ae29f00675df84963ba73af8fa4e3bb969c438150ae9f1fc6f3957b3b8be9aab78f19ff7caf20a

I used the adjusted keys (deducted the start range from every point), but actually such adjustment does not make sense.

Code:

Kangaroo v1.2
Start:0
Stop :FFFFFFFFFFFFFFFFFFFF
Keys :5
Number of CPU thread: 0
Range width: 2^80
Number of random walk: 2^20.81 (Max DP=17)
DP size: 17 [0xffff800000000000]
GPU: GPU #0 GeForce GTX 1080 Ti (28x128 cores) Grid(56x256) (177.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.81 kangaroos in 6624.7ms
[443.06 MKey/s][GPU 443.06 MKey/s][Count 2^42.05][Dead 3][03:15:57][2655.9MB]  
Key# 0 Pub:  0x026CF3EC949C28918ED0FDC48980B3339343CEB822ACD9B7B3A0D16D9606AEB139 
       Priv: 0xCB5EBB3EF3883C1866D4 
[457.08 MKey/s][GPU 457.08 MKey/s][Count 2^42.39][Dead 5][04:00:43][3365.8MB]  
Key# 1 Pub:  0x02948282BFA4CC7AAA1722F0F72CE9B3708061960084BA188A2C66713C46070F45 
       Priv: 0xCB5EB5ABC43BEBAD3207 
[456.63 MKey/s][GPU 456.63 MKey/s][Count 2^42.47][Dead 8][04:13:19][3540.3MB]  
Key# 2 Pub:  0x0391A7B757335E7026E83C42B868DD6C4A8F379E7EF059DE9A1FC1B7E4E770749A 
       Priv: 0xCB5E5698AAAB6CAC52B3

The version 1.2 is faster by 2-3% compared with the version 1.1

I stoped the code and did not wait for the remaining 2 keys. We can see that for 2^80 range it needed 2^42.05, 2^42.39 and 2^42.47 operations, however on average 2^41 was enough. So the total time for every key was 2-3 times longer (!!!) For 2^80 range it makes big difference (1.5 hours vs 3 hours).

But due to the tests made I can confirm that on GTX 1080ti (11Gb) the key in 2^80 range could be found for 3-4 hours, although 1.5 hours on average was expected.

Jean_Luc, are all the wild kangaroos start from the one public key point? I guess that symmetry would halve the total time...

We have to solve P = k.G, we know that k lies in the range [k1,k2];
So, (k2-k) also lies in the range [k1,k2]. How about starting the wild kangaroos not only from k, but from both k and (k2-k)?

Jean_Luc

sr. member

Activity: 462

Merit: 701

Quote from: PietCoin97 on April 24, 2020, 03:01:08 AM

Jean luc does it work also with such an key space ?

Start:8000000000000000000000001
Stop :FFFFFFFFFFFFFFFFFFFFFFFFE

or should i give in all 64 bits ?

and are my setting ok or can i get higher speed ?

Yes it should work. Your setup looks good.

Jean_Luc

sr. member

Activity: 462

Merit: 701

I solved 20 times the following key (64bit range) and there was a strange 24 dead kangaroos event !? It seems that from times to times the algorithm has hard time to solve the key... Just a matter of probability ? My Mersenne twister fails ? I will make further tests...

Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4

[115.22 MKey/s][GPU 115.22 MKey/s][Count 2^33.63][Dead 3][02:12][502.4MB]
[115.22 MKey/s][GPU 115.22 MKey/s][Count 2^34.07][Dead 0][02:59][675.8MB]
[115.22 MKey/s][GPU 115.22 MKey/s][Count 2^31.43][Dead 0][29s][113.4MB]
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^33.70][Dead 1][02:19][525.5MB]
[115.22 MKey/s][GPU 115.22 MKey/s][Count 2^35.20][Dead 24][06:31][1472.8MB]
[115.22 MKey/s][GPU 115.22 MKey/s][Count 2^34.44][Dead 7][03:52][872.4MB]
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^33.51][Dead 1][02:02][459.6MB]
[115.22 MKey/s][GPU 115.22 MKey/s][Count 2^34.27][Dead 7][03:27][779.1MB]
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^33.68][Dead 3][02:17][516.3MB]
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^33.85][Dead 3][02:34][581.7MB]
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^32.33][Dead 1][54s][206.9MB]
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^32.40][Dead 0][57s][216.1MB]
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^33.45][Dead 2][01:57][441.1MB]
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^32.97][Dead 1][01:24][319.5MB]
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^34.66][Dead 6][04:29][1012.6MB]
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^32.12][Dead 0][47s][178.9MB]
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^31.66][Dead 0][34s][131.5MB]
[115.23 MKey/s][GPU 115.23 MKey/s][Count 2^33.32][Dead 3][01:47][403.6MB]
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^34.00][Dead 2][02:52][647.1MB]
[115.22 MKey/s][GPU 115.22 MKey/s][Count 2^33.68][Dead 2][02:17][516.5MB]

PietCoin97

jr. member

Activity: 91

Merit: 3

Code:

Kangaroo.exe -t 0 -gpu -gpuId 0,1,2,3,4,5 in.txt
Kangaroo v1.2
Start:8000000000000000000000001
Stop :FFFFFFFFFFFFFFFFFFFFFFFFE
Keys :2048
Number of CPU thread: 0
Range width: 2^99
Number of random walk: 2^22.49 (Max DP=25)
DP size: 25 [0xFFFFFF8000000000]
GPU: GPU #2 P104-100 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#2: creating kangaroos...
GPU: GPU #1 P104-100 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#1: creating kangaroos...
GPU: GPU #0 P104-100 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
GPU: GPU #5 GeForce GTX 1070 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#5: creating kangaroos...
GPU: GPU #3 GeForce GTX 1070 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#3: creating kangaroos...
GPU: GPU #4 GeForce GTX 1070 (15x128 cores) Grid(30x256) (99.0 MB used)
SolveKeyGPU Thread GPU#4: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^19.91 kangaroos in 9236.5ms
SolveKeyGPU Thread GPU#2: 2^19.91 kangaroos in 9508.7ms
SolveKeyGPU Thread GPU#1: 2^19.91 kangaroos in 9569.1ms
SolveKeyGPU Thread GPU#3: 2^19.91 kangaroos in 8538.5ms
SolveKeyGPU Thread GPU#5: 2^19.91 kangaroos in 8782.5ms
SolveKeyGPU Thread GPU#4: 2^19.91 kangaroos in 8431.8ms
[1323.30 MKey/s][GPU 1323.30 MKey/s][Count 2^45.83][Dead 0][14:44:30][147.1MB]

Jean luc does it work also with such an key space ?

Start:8000000000000000000000001
Stop :FFFFFFFFFFFFFFFFFFFFFFFFE

or should i give in all 64 bits ?

and are my setting ok or can i get higher speed ?

Jean_Luc

sr. member

Activity: 462

Merit: 701

During the night, I solved the key with the same config file as Etar in 2^41.59 iterations (09:06:32) and 1 dead kangaroo.
It seems normal. I will make further tests to see if changing the jumps can improve things a bit...

Code:

C:\C++\Kangaroo\VC_CUDA10\x64\Release>Kangaroo.exe -t 0 -gpu ..\..\in.txt
Kangaroo v1.2
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB4800000000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48FFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^80
Number of random walk: 2^18.58 (Max DP=19)
DP size: 19 [0xFFFFE00000000000]
GPU: GPU #0 GeForce GTX 1050 Ti (6x128 cores) Grid(12x256) (45.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^18.58 kangaroos in 1376.4ms
[115.21 MKey/s][GPU 115.21 MKey/s][Count 2^41.59][Dead 1][09:06:28][485.7MB]
Key# 0 Pub:  0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC
       Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4

Done: Total time 09:06:32

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: Jean_Luc on April 23, 2020, 11:58:50 AM

Yes I remarked that this first key of this set often generate dead kangaroos (even in 64bit range)
The fact that the startrange is not zero should not impact, it is just a translation. It is equivalent to what MrFreeDragon said.
-snip-

Finally I could solve the 80bit key from the 16key example for 3h14min. But I made the adjustment I wrote before.

Changed the range in the following way:

Code:

Real ranges:
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB4800000000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48FFFFFFFFFFFFFFFFFFFF

Changed to (deducted the Start Range value):
Start:0
Stop :FFFFFFFFFFFFFFFFFFFF

And also made the corrsponding changes to the public keys: deducted the Point 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB4800000000000000000000*G from every Public key, so:

Code:

The initial pubic keys:
0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
04A50FBBB20757CC0E9C41C49DD9DF261646EE7936272F3F68C740C9DA50D42BCD3E48440249D6BC78BC928AA52B1921E9690EBA823CBC7F3AF54B3707E6A73F34
0404A49211C0FE07C9F7C94695996F8826E09545375A3CF9677F2D780A3EB70DE3BD05357CAF8340CB041B1D46C5BB6B88CD9859A083B0804EF63D498B29D31DD1
040B39E3F26AF294502A5BE708BB87AEDD9F895868011E60C1D2ABFCA202CD7A4D1D18283AF49556CF33E1EA71A16B2D0E31EE7179D88BE7F6AA0A7C5498E5D97F
04837A31977A73A630C436E680915934A58B8C76EB9B57A42C3C717689BE8C0493E46726DE04352832790FD1C99D9DDC2EE8A96E50CAD4DCC3AF1BFB82D51F2494

were replaced by these ones:
046cf3ec949c28918ed0fdc48980b3339343ceb822acd9b7b3a0d16d9606aeb139507c48c74b81fde39c415117f914fd850e8a64bde218e99b6d74b2012977df56
04948282bfa4cc7aaa1722f0f72ce9b3708061960084ba188a2c66713c46070f45c9a997916266123aacbc5fbc76e1a0a133ab92410466f19f92e67ab1716f0db4
0491a7b757335e7026e83c42b868dd6c4a8f379e7ef059de9a1fc1b7e4e770749ae1ed4034f6d24d0da3d7ce10ce3c543dade4b812f118e0d0897ca2d42aa1e3d7
0420c453ffcc3840c90c33f695bb1d573d2860c2203c75808ae45a168aa17995af952bea588e1362d9cefe0977a96ea79f554d5809291c20339b3427b55c48859f
0432b9ca00d710738587a4ac0f7aad49516e0ca04ea1a19e9548ae29f00675df84963ba73af8fa4e3bb969c438150ae9f1fc6f3957b3b8be9aab78f19ff7caf20a

And the result for the 1st key was found for 3:14 hours:

Code:

Start:0
Stop :FFFFFFFFFFFFFFFFFFFF
Keys :5
Number of CPU thread: 0
Range width: 2^80
Number of random walk: 2^20.81 (Max DP=17)
DP size: 17 [0xffff800000000000]
GPU: GPU #0 GeForce GTX 1080 Ti (28x128 cores) Grid(56x256) (177.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.81 kangaroos
[436.47 MKey/s][GPU 436.47 MKey/s][Count 2^42.02][Dead 8][03:14:17][2606.2MB]  
Key# 0 Pub:  0x026CF3EC949C28918ED0FDC48980B3339343CEB822ACD9B7B3A0D16D9606AEB139 
       Priv: 0xCB5EBB3EF3883C1866D4

Now we can retrieve the target private key:
Final Priv = 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB4800000000000000000000 + 0xCB5EBB3EF3883C1866D4 = 0x49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4

I know that these adsjutments should not affect the time to solve, however in my case without adjustments i could not solve the 1st 80bit from example for 4 hours, with the adjustments the 1st key was solved for 3:14 hours.

If Etar could test that adjusted public keys with the adjusted ranges (with leading zeros) on his 2080ti it would be great. Etar should have the speed 2.5 times faster, so the 1st key should be solved for 1:15-1:30 hours.

COBRAS

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

What if use many publick key from 1 adress ? Maby jrivate key will be 1 and private key search for many public adreses will get more trustwothy result ?

Can someone test this idea ?

Jean_Luc

sr. member

Activity: 462

Merit: 701

Yes I remarked that this first key of this set often generate dead kangaroos (even in 64bit range)
The fact that the startrange is not zero should not impact, it is just a translation. It is equivalent to what MrFreeDragon said.
All kangaroos are uniformly distributed in the range and make random jumps form G up to 2*sqrt(k2-k1).G
Even if kangaroos goes out of the range it is not really a problem.
I will try to change the calculation on random jump to see if it improve something.

[18.00 MKey/s][Count 2^34.40][20:47][Dead 10][20.2MB]
Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4

[115.23 MKey/s][GPU 115.23 MKey/s][Count 2^33.52][Dead 5][02:02][463.9MB]
Key# 0 Pub: 0x0259A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EBB3EF3883C1866D4

Etar

sr. member

Activity: 642

Merit: 316

Quote from: MrFreeDragon on April 23, 2020, 11:44:53 AM

could have Probably the kangaroos are jumping outside the range and make the width much wider.

What if just adjust the range to the one with leading zeros and also adjust the public key to search. I mean "to substract 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb4800000000000000000000 from the range and from the public key as well. So the range will be 0x00000000000000000000 - 0xffffffffffffffffffff and the public key will be Q - kG , where Q is the target public key and k is the start of the range.

Kangaroo cant jump outside because step is modulo n
If i will get all time dead kangaroo due to collision in the same tribe i cant see positive moment in this algorithm.
Any way thanks for reseaching. You a very-very good programmer!

MrFreeDragon

sr. member

Activity: 443

Merit: 350

I have tried the same 80bit range as you:

Code:

49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb4800000000000000000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48ffffffffffffffffffff

Kangaroo v1.1, Range width 2^80, 16 keys from the example.
For 2hours 30 minutes at speed 433Mkey the script performed 2^41.7 operations, killed 7 kangaroos, but did not solve the key.

I have some idea but not sure if it is correct and could have the impact.
For the range with leading zeros everything worked fine (I mena then I tried the 80bit key from the challenge example). But we are all killing kangaroos with the 16 key example.... and not solving them. Probably the kangaroos are jumping outside the range and make the width much wider.

What if just adjust the range to the one with leading zeros and also adjust the public key to search. I mean "to substract 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb4800000000000000000000 from the range and from the public key as well. So the range will be 0x00000000000000000000 - 0xffffffffffffffffffff and the public key will be Q - kG , where Q is the target public key and k is the start of the range.

Jean_Luc

sr. member

Activity: 462

Merit: 701

Quote from: Etar on April 23, 2020, 10:11:03 AM

My gpu have only 11gb of memory
I dont know how hashtable can be 13 gb in this reason.
No, i did not try other keys. Only from example.

The hash table is centralized and managed by the CPU.
You have 7 dead kangaroo, a dead kangaroo is a collision in the same herd, and the kangaroo is re created.
There is the same probability to get a dead kangaroo or to solve the key.
Having 7 dead kangaroo without solving the key is like throwing 7 times a coin and having consecutively nine time "heads", bad luck !

On this key, i got 20 dead kangaroos ! ~2^35 , ~4 times more iterations needed compare to the average 2^33...

[114.85 MKey/s][GPU 114.85 MKey/s][Count 2^34.98][Dead 20][05:41][1269.3MB]
Key#11 Pub: 0x03D4E6FA664BD75A508C0FF0ED6F2C52DA2ADD7C3F954D9C346D24318DBD2ECFC6
Priv: 0x49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48CB5EE3579364DE939B0C

Etar

sr. member

Activity: 642

Merit: 316

Quote from: MrFreeDragon on April 23, 2020, 09:55:31 AM

. Actually at this stage the code sould solve the key within the next every minute.

Your 2080ti actually made 2^41 operations for 40 minutes (1h8min / 2^0.74) or 2^40 operations for 20 minutes. So everything works good. You just was unlucky with the probability to solve...

I think the same but i was wait 2 h Huh

And it is not unlucky there should be other reason. I launch this config few times. And no one times not get result.

I think that bsgs algoritm is more-more predicteble.
You know how many memory you need for calculation. You know speed and you know how many time you need to check range.
Kangaroo algorithm not used less memory as i see due to grow hashtable in time.
Or if hashtable allocate in begining i dont know if i can allocate hashtable for range 2^255.
And if i allways will get dead kangaroo how i will know that i solve range and there no key...
So if range will be 128 bit so you dont know will you found key or you will get out of memory or all times wiil get dead kangaroo.

Etar

sr. member

Activity: 642

Merit: 316

Quote from: Jean_Luc on April 23, 2020, 09:50:00 AM

Quote from: Etar on April 23, 2020, 09:46:51 AM

2h and nothing, speed drop to 267Mkey, GPU usage drop to 25%

That's strange, may be a bug somewhere, the gpu usage drops may be because the HashTable becomes too big.
I'll try
Did you try with others key ?

My gpu have only 11gb of memory
I dont know how hashtable can be 13 gb in this reason.
No, i did not try other keys. Only from example.

MrFreeDragon

sr. member

Activity: 443

Merit: 350

Quote from: Jean_Luc on April 23, 2020, 09:23:58 AM

Quote from: Etar on April 23, 2020, 08:40:14 AM

My Hi-End GPU can`t find any key for 1h))

That should work. For 80bit search, 2^41 is an average time, with a probability of ~50% to find the key.
I will try this night.
Many thanks to MrFreeDragon for testing the software Wink

Agree with this comment. The Pollard Kangaroo solves the problem with the less operations (square root from the total width), but with not 100% probability of course.

Etar, if you had this: [1017.74 MKey/s][GPU 1017.74 MKey/s][Count 2^41.74][Dead 2][01:08:13][8578.7MB]. it means that you just was unlucky. However it does not mean that you should restart the code. Actually at this stage the code sould solve the key within the next every minute.

Your 2080ti actually made 2^41 operations for 40 minutes (1h8min / 2^0.74) or 2^40 operations for 20 minutes. So everything works good. You just was unlucky with the probability to solve...

Jean_Luc

sr. member

Activity: 462

Merit: 701

Quote from: Etar on April 23, 2020, 09:46:51 AM

2h and nothing, speed drop to 267Mkey, GPU usage drop to 25%

That's strange, may be a bug somewhere, the gpu usage drops may be because the HashTable becomes too big.
I'll try
Did you try with others key ?

Etar

sr. member

Activity: 642

Merit: 316

2h and nothing, speed drop to 267Mkey, GPU usage drop to 25%

Code:

Kangaroo v1.2
Start:49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB4800000000000000000000
Stop :49DCCFD96DC5DF56487436F5A1B18C4F5D34F65DDB48FFFFFFFFFFFFFFFFFFFF
Keys :16
Number of CPU thread: 0
Range width: 2^80
Number of random walk: 2^22.09 (Max DP=15)
DP size: 15 [0xFFFE000000000000]
GPU: GPU #0 GeForce RTX 2080 Ti (68x64 cores) Grid(136x256) (417.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^22.09 kangaroos in 16571.8ms
[286.75 MKey/s][GPU 286.75 MKey/s][Count 2^42.41][Dead 7][02:15:53][13583.1MB]

there is txt file (the same like example, only 80bit range set)

Code:

49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb4800000000000000000000
49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48ffffffffffffffffffff
0459A3BFDAD718C9D3FAC7C187F1139F0815AC5D923910D516E186AFDA28B221DC994327554CED887AAE5D211A2407CDD025CFC3779ECB9C9D7F2F1A1DDF3E9FF8
04A50FBBB20757CC0E9C41C49DD9DF261646EE7936272F3F68C740C9DA50D42BCD3E48440249D6BC78BC928AA52B1921E9690EBA823CBC7F3AF54B3707E6A73F34
0404A49211C0FE07C9F7C94695996F8826E09545375A3CF9677F2D780A3EB70DE3BD05357CAF8340CB041B1D46C5BB6B88CD9859A083B0804EF63D498B29D31DD1
040B39E3F26AF294502A5BE708BB87AEDD9F895868011E60C1D2ABFCA202CD7A4D1D18283AF49556CF33E1EA71A16B2D0E31EE7179D88BE7F6AA0A7C5498E5D97F
04837A31977A73A630C436E680915934A58B8C76EB9B57A42C3C717689BE8C0493E46726DE04352832790FD1C99D9DDC2EE8A96E50CAD4DCC3AF1BFB82D51F2494
040ECDB6359D41D2FD37628C718DDA9BE30E65801A88A00C3C5BDF36E7EE6ADBBAD71A2A535FCB54D56913E7F37D8103BA33ED6441D019D0922AC363FCC792C29A
0422DD52FCFA3A4384F0AFF199D019E481D335923D8C00BADAD42FFFC80AF8FCF038F139D652842243FC841E7C5B3E477D901F88C5AB0B88EE13D80080E413F2ED
04DB4F1B249406B8BD662F78CBA46F5E90E20FE27FC69D0FBAA2F06E6E50E536695DF83B68FD0F396BB9BFCF6D4FE312F32A43CF3FA1FE0F81DF70C877593B64E0
043BD0330D7381917F8860F1949ACBCCFDC7863422EEE2B6DB7EDD551850196687528B6D2BC0AA7A5855D168B26C6BAF9DDCD04B585D42C7B9913F60421716D37A
04332A02CA42C481EAADB7ADB97DF89033B23EA291FDA809BEA3CE5C3B73B20C49C410D1AD42A9247EB8FF217935C9E28411A08B325FBF28CC2AF8182CE2B5CE38
04513981849DE1A1327DEF34B51F5011C5070603CA22E6D868263CB7C908525F0C19EBA6BD2A8DCF651E4342512EDEACB6EA22DA323A194E25C6A1614ABD259BC0
04D4E6FA664BD75A508C0FF0ED6F2C52DA2ADD7C3F954D9C346D24318DBD2ECFC6805511F46262E10A25F252FD525AF1CBCC46016B6CD0A7705037364309198DA1
0456B468963752924DBF56112633DC57F07C512E3671A16CD7375C58469164599D1E04011D3E9004466C814B144A9BCB7E47D5BACA1B90DA0C4752603781BF5873
04D5BE7C653773CEE06A238020E953CFCD0F22BE2D045C6E5B4388A3F11B4586CBB4B177DFFD111F6A15A453009B568E95798B0227B60D8BEAC98AF671F31B0E2B
04B1985389D8AB680DEDD67BBA7CA781D1A9E6E5974AAD2E70518125BAD5783EB5355F46E927A030DB14CF8D3940C1BED7FB80624B32B349AB5A05226AF15A2228
0455B95BEF84A6045A505D015EF15E136E0A31CC2AA00FA4BCA62E5DF215EE981B3B4D6BCE33718DC6CF59F28B550648D7E8B2796AC36F25FF0C01F8BC42A16FD9

Topic: brute-forcing public keys at amazing speed 2.2 PH/s on CPU [malware warning] - page 5. (Read 3490 times)