Pages:
Author

Topic: Pollard's kangaroo ECDLP solver - page 27. (Read 59389 times)

full member
Activity: 706
Merit: 111
October 09, 2021, 05:23:06 PM

Anyway, this is the script I promised I'd show you guys in my previous post: https://gist.github.com/ZenulAbidin/cbe69f8a2496514773140516e3666519

You give it any public key in the file input.txt, adjust the script values such as the number of trailing bits, number of results etc. and it will print you the list of most likely public keys.

Warning: bit numbers >20 will cause you to run out of memory fast. Also it might take about an hour or so to complete depending on the bit size. I am working on a fix for both of these.


What does Std. Deviation: 1.1902380714238083 mean?
newbie
Activity: 5
Merit: 2
October 09, 2021, 04:30:54 PM
PureBasic executables get false positives by AV heuristic cause some ransomware used PureBasic. You can search it with google.
member
Activity: 170
Merit: 58
October 09, 2021, 03:56:57 PM
Hmm.
One of the anti-viruses found a trojan: TrojanSpy.Carberp.eut
I have no complaints. Just wondering why.
https://www.virustotal.com/gui/file/d92bd6d9ff7f2f6239b731d3529dfd6827e9d6ce853a115a768d0f16fc799126

 Grin

What do you think, why there are no sources attached?  Grin Grin
How do you know what that program does?
sr. member
Activity: 642
Merit: 316
October 09, 2021, 12:48:41 PM
I create new topic for BSGS cuda https://bitcointalk.org/index.php?topic=5364845.new#new
Because i don`t want to make offtop on this thread.
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
October 09, 2021, 08:43:27 AM
Why no linux version ?

I think Etar only does Windows releases.



Anyway, this is the script I promised I'd show you guys in my previous post: https://gist.github.com/ZenulAbidin/cbe69f8a2496514773140516e3666519

You give it any public key in the file input.txt, adjust the script values such as the number of trailing bits, number of results etc. and it will print you the list of most likely public keys.

Warning: bit numbers >20 will cause you to run out of memory fast. Also it might take about an hour or so to complete depending on the bit size. I am working on a fix for both of these.



-snip-
One of the anti-viruses found a trojan: TrojanSpy.Carberp.eut
I have no complaints. Just wondering why.
https://www.virustotal.com/gui/file/d92bd6d9ff7f2f6239b731d3529dfd6827e9d6ce853a115a768d0f16fc799126
Can`t say. I use PBv5.31 to compile app. It is licensed version(not cracked or so.) But I think if the other more well-known antiviruses did not find anything, then this is a false alarm. And so decide for yourself.

I wouldn't worry about it given that only 3 obscure AV vendors flagged it. Perhaps they don't like CPU-intensive loops with multiple threads.  Wink
sr. member
Activity: 642
Merit: 316
October 09, 2021, 07:54:24 AM
I put source files to the github, so anybody can compile by self.
jr. member
Activity: 48
Merit: 11
October 09, 2021, 07:46:51 AM
-snip-
One of the anti-viruses found a trojan: TrojanSpy.Carberp.eut
I have no complaints. Just wondering why.
https://www.virustotal.com/gui/file/d92bd6d9ff7f2f6239b731d3529dfd6827e9d6ce853a115a768d0f16fc799126
Can`t say. I use PBv5.31 to compile app. It is licensed version(not cracked or so.) But I think if the other more well-known antiviruses did not find anything, then this is a false alarm. And so decide for yourself.
I'm sure it's a false positive, too. This is the first time I've seen the name of this antivirus and it doesn't inspire confidence in me.
full member
Activity: 431
Merit: 105
October 09, 2021, 07:33:11 AM
Trojan:Win32/Sabsik.FT.A!ml , this one is found by windows,

etayson love your software man, the previous server software great.
now this one greatest, thanks a lot, hope false positive obviously.
sr. member
Activity: 642
Merit: 316
October 09, 2021, 07:04:56 AM
-snip-
One of the anti-viruses found a trojan: TrojanSpy.Carberp.eut
I have no complaints. Just wondering why.
https://www.virustotal.com/gui/file/d92bd6d9ff7f2f6239b731d3529dfd6827e9d6ce853a115a768d0f16fc799126
Can`t say. I use PBv5.31 to compile app. It is licensed version(not cracked or so.) But I think if the other more well-known antiviruses did not find anything, then this is a false alarm. And so decide for yourself.
jr. member
Activity: 48
Merit: 11
October 09, 2021, 05:30:39 AM
--snip--
If you need help testing I am sure there are 70+ people WANTING to test Smiley

additionally if you do want to test speeds I have an RTX 3070
Ready for testing https://github.com/Etayson/BSGS-cuda/releases
Source code will be available after testing and fix bugs.

Hmm.
One of the anti-viruses found a trojan: TrojanSpy.Carberp.eut
I have no complaints. Just wondering why.
https://www.virustotal.com/gui/file/d92bd6d9ff7f2f6239b731d3529dfd6827e9d6ce853a115a768d0f16fc799126
member
Activity: 873
Merit: 22
$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk
October 08, 2021, 07:37:51 PM
--snip--
If you need help testing I am sure there are 70+ people WANTING to test Smiley

additionally if you do want to test speeds I have an RTX 3070
Ready for testing https://github.com/Etayson/BSGS-cuda/releases
Source code will be available after testing and fix bugs.

Why no linux version ?

Br.
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
October 08, 2021, 06:09:54 PM
~snip
By the position of the publickey in the list, I can determine according to the method of NotATether the privatekey (did not unterstand it actually... lol). Or I just bit shift the input and output 16 times by 2 getting actually generate a "decision tree". Then I only need to follow the decision tree and get the correct private key.

~

Isn't this just a more complicated meet in the middle attack? Another alternative method that also works:

Generate public keys p - 0 .... p - 65535

One of those public keys is guaranteed to have a private key with the lower 16 bits all zeroed out, thus divisible by 65536

Then just calculate private keys with stride 65536: 1 * 65536, 2 * 65536 ..... up until 2^24 * 65536 and match against your generated keys


The issue here is: 1. you need a known public key (not just an address) and 2. as you move up in key size, you need insane storage requirements, like for a 120 bit key the most optimal solution is to generate 2^60 public keys and match those against 2^60 private keys

....which is comparable to what kangaroo already does, but kangaroo doesn't have that large memory requirement.


Except you don't need to calculate all keys with stride 65536 - we know that RNG software will (practically) never generate predictable keys that look like 11111100000 and like that so we measure how "random" a public key looks, by calculating the mean number of sequences (2 1-bits, 3 0-bits, and others) and store them in a vector, then for any PK we want to check we place it as another vector next to that one like this:

[mean   sample]

And compute the avg. std. deviation of that by computing column-wise variance to get 1-column vector [ variance ], then take the mean of all values of that vector, then compute the square root.

The result is a coefficient that tells us how "random-looking" the PK is.

Now if we sort by coefficient, we can eliminate a bunch of stride amounts that give us absurd private keys like the one above. The question is now what is the function that will increment the stride to the next one based on random-looking coefficient?

I have a script for the coefficient calculation and it's working, but I'm on mobile right now so I have to wait to share it later.
sr. member
Activity: 642
Merit: 316
October 08, 2021, 01:48:28 PM
--snip--
If you need help testing I am sure there are 70+ people WANTING to test Smiley

additionally if you do want to test speeds I have an RTX 3070
Ready for testing https://github.com/Etayson/BSGS-cuda/releases
Source code will be available after testing and fix bugs.
jr. member
Activity: 77
Merit: 7
October 08, 2021, 12:11:50 AM
Have a some progress in BSGS for cuda.
Binary search replace with hashtable and after this results is:
With single 2080ti, 570Mgiantstep with 2^26 babysteps HT find key in 338 seconds (start from 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000)
Code:
GPU #0 Cnt:000000000000000000000000000000000000000000000000bac8c00000000001  570MKey/s x67108864 2^29.16 x2^26=2^55.16
***********GPU#0************
Total solutions: 2
KEY!!>49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4
Pub: 59a3bfdad718c9d3fac7c187f1139f0815ac5d923910d516e186afda28b221dc994327554ced887aae5d211a2407cdd025cfc3779ecb9c9d7f2f1a1ddf3e9ff8
****************************
Found in 338 seconds
GPU #0 finished
cuda finished ok

With 6x660super, 270Mgiantstep per card with 2^26 babysteps HT find key in 117 seconds (start from 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000)
Code:
GPU #3 Cnt:000000000000000000000000000000000000000000000000b96a000000000001  272MKey/s x67108864 2^28.09 x2^26=2^54.09
GPU #0 Cnt:000000000000000000000000000000000000000000000000b340000000000001  259MKey/s x67108864 2^28.02 x2^26=2^54.02
GPU #1 Cnt:000000000000000000000000000000000000000000000000ba6e000000000001  274MKey/s x67108864 2^28.10 x2^26=2^54.10
GPU #2 Cnt:000000000000000000000000000000000000000000000000b398000000000001  270MKey/s x67108864 2^28.08 x2^26=2^54.08
***********GPU#3************
Total solutions: 2
GPU #4 Cnt:000000000000000000000000000000000000000000000000bcf0000000000001  269MKey/s x67108864 2^28.08 x2^26=2^54.08
GPU #5 Cnt:000000000000000000000000000000000000000000000000c3fa000000000001  284MKey/s x67108864 2^28.15 x2^26=2^54.15
GPU #0 Cnt:000000000000000000000000000000000000000000000000b658000000000001  261MKey/s x67108864 2^28.03 x2^26=2^54.03
KEY!!>49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4
Pub: 59a3bfdad718c9d3fac7c187f1139f0815ac5d923910d516e186afda28b221dc994327554ced887aae5d211a2407cdd025cfc3779ecb9c9d7f2f1a1ddf3e9ff8
****************************
Found in 117 seconds
Much better than before. Wink

If you need help testing I am sure there are 70+ people WANTING to test Smiley

additionally if you do want to test speeds I have an RTX 3070
full member
Activity: 161
Merit: 230
October 07, 2021, 10:47:56 AM
You could give me your 40 bit public key. But cracking it is kind of waste of time, as I would need to do alot manually, you know...

But how to crack it:
I would bit shift your public key by 65536 ( 2 ^ 16).  I will then have 65536 pubkeys and one of them is in range 2 ^ 24. I will run it on BitCrack and get the key in 2 ^24. By the position of the publickey in the list, I can determine according to the method of NotATether the privatekey (did not unterstand it actually... lol). Or I just bit shift the input and output 16 times by 2 getting actually generate a "decision tree". Then I only need to follow the decision tree and get the correct private key.

So instead of having to crack a 2^40 key (1,099511628×10¹² possibilities), i only need to crack a 2^24 key (16777216 possibilities). So with my Vega 56 and 300 MKey/s I would need for the 2 ^ 40 about an hour and for the 2 ^24 keys only 1 second. So if my programm is doing everything automatically, it would take about 1 second to crack a 2^40 key.

Isn't this just a more complicated meet in the middle attack? Another alternative method that also works:

Generate public keys p - 0 .... p - 65535

One of those public keys is guaranteed to have a private key with the lower 16 bits all zeroed out, thus divisible by 65536

Then just calculate private keys with stride 65536: 1 * 65536, 2 * 65536 ..... up until 2^24 * 65536 and match against your generated keys


The issue here is: 1. you need a known public key (not just an address) and 2. as you move up in key size, you need insane storage requirements, like for a 120 bit key the most optimal solution is to generate 2^60 public keys and match those against 2^60 private keys

....which is comparable to what kangaroo already does, but kangaroo doesn't have that large memory requirement.
sr. member
Activity: 642
Merit: 316
October 07, 2021, 08:25:08 AM
Have a some progress in BSGS for cuda.
Binary search replace with hashtable and after this results is:
With single 2080ti, 570Mgiantstep with 2^26 babysteps HT find key in 338 seconds (start from 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000)
Code:
GPU #0 Cnt:000000000000000000000000000000000000000000000000bac8c00000000001  570MKey/s x67108864 2^29.16 x2^26=2^55.16
***********GPU#0************
Total solutions: 2
KEY!!>49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4
Pub: 59a3bfdad718c9d3fac7c187f1139f0815ac5d923910d516e186afda28b221dc994327554ced887aae5d211a2407cdd025cfc3779ecb9c9d7f2f1a1ddf3e9ff8
****************************
Found in 338 seconds
GPU #0 finished
cuda finished ok

With 6x1660super, 270Mgiantstep per card with 2^26 babysteps HT find key in 117 seconds (start from 49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5e0000000000000000)
Code:
GPU #3 Cnt:000000000000000000000000000000000000000000000000b96a000000000001  272MKey/s x67108864 2^28.09 x2^26=2^54.09
GPU #0 Cnt:000000000000000000000000000000000000000000000000b340000000000001  259MKey/s x67108864 2^28.02 x2^26=2^54.02
GPU #1 Cnt:000000000000000000000000000000000000000000000000ba6e000000000001  274MKey/s x67108864 2^28.10 x2^26=2^54.10
GPU #2 Cnt:000000000000000000000000000000000000000000000000b398000000000001  270MKey/s x67108864 2^28.08 x2^26=2^54.08
***********GPU#3************
Total solutions: 2
GPU #4 Cnt:000000000000000000000000000000000000000000000000bcf0000000000001  269MKey/s x67108864 2^28.08 x2^26=2^54.08
GPU #5 Cnt:000000000000000000000000000000000000000000000000c3fa000000000001  284MKey/s x67108864 2^28.15 x2^26=2^54.15
GPU #0 Cnt:000000000000000000000000000000000000000000000000b658000000000001  261MKey/s x67108864 2^28.03 x2^26=2^54.03
KEY!!>49dccfd96dc5df56487436f5a1b18c4f5d34f65ddb48cb5ebb3ef3883c1866d4
Pub: 59a3bfdad718c9d3fac7c187f1139f0815ac5d923910d516e186afda28b221dc994327554ced887aae5d211a2407cdd025cfc3779ecb9c9d7f2f1a1ddf3e9ff8
****************************
Found in 117 seconds
Much better than before. Wink
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
October 05, 2021, 01:03:47 AM
I previously did tests of the probability of repeating bits 1111x and 0000x on a range of 256 bits. To do this I generated 100 million urandom(32) keys and looked for bits 0 and 1. Below is a table of the probabilities of repeating bits 1 or 0 on a 256-bit key.
For example, the probability of a key having 16 ones or 16 zeros is 0.367964%
I can look up the code if you need to

~

So this effectively means that bit lengths 15+ are unlikely to occur in a private key because they make up less than 1% of the sample population.
jr. member
Activity: 48
Merit: 11
October 04, 2021, 01:15:49 PM
...
In my testing, sequences of greater than 11 zeros or ones only occurred maximum once in an entire sample of 1000 256-bit random numbers.

I previously did tests of the probability of repeating bits 1111x and 0000x on a range of 256 bits. To do this I generated 100 million urandom(32) keys and looked for bits 0 and 1. Below is a table of the probabilities of repeating bits 1 or 0 on a 256-bit key.
For example, the probability of a key having 16 ones or 16 zeros is 0.367964%
I can look up the code if you need to

Code:
1	100,000000%
2 100,000000%
3 100,000000%
4 100,000000%
5 99,991147%
6 98,673109%
7 87,345356%
8 63,436401%
9 39,012922%
10 21,689362%
11 11,414800%
12 5,843793%
13 2,949750%
14 1,479510%
15 0,737481%
16 0,367964%
17 0,183264%
18 0,091321%
19 0,045563%
20 0,022649%
21 0,011249%
22 0,005631%
23 0,002762%
24 0,001374%
25 0,000654%
26 0,000339%
27 0,000176%
28 0,000086%
29 0,000042%
30 0,000025%
31 0,000016%
32 0,000005%
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
October 04, 2021, 12:31:18 PM
I tested it and tried it, I kinda wish you could do that with the addresses.

You could but it wouldn't really make sense. It only makes sense when you do this with private keys. But if I can find a way to "jump" between private keys that are more "natural looking" (see close to the end of this post for this expiration) e.g. if I could find terms to get from something like 1101001001 to e.g. 1101001100 instead of each time incrementing by 1, I could make a more efficient search algorithm than the one Bitcrack is currently doing (linear search).


It also supports analyzing the probability of a sequence of bits occurring in multiple positions, but be warned that that increasing the number of positions to estimate together, uses a lot of memory (A LOT!).


By the way, maybe that could be interesting for you: https://www.geeksforgeeks.org/longest-common-substring-binary-representation-two-numbers/

In fact, I have already implemented this in another (private) script of mine. The results were that groups of 1, 2 and 3 zero and one bits were the most common, followed by groups of 4-8 zeros and ones, then everything else longer than that.

If you generate a bunch of random PKs and count how many sequences of 1, 2, 3, etc zero & one bits they have, then compute their mean (call this sample_mean), you can actually use the result to calculate the average standard deviation between the mean and any private key you throw at it - could be a puzzle key, could be someone's random address private key, anything. Call the sequence counts of this testing privkey groups_testingPK_count. Then the avg. std. deviation is just sqrt(mean(variance[sample_mean, groups_testingPK_count])).

Lower (closer to zero in absolute value) is better, because it means keys start to look more like this:

10001101110010011100

Instead of this:

10101010101010101010

Or even this:

11111111111111111111

I have a conjecture:
The longest amount of consecutive 1 or 0 is sqrt(bits). So sqrt(120) = 10,95. So probably we can skip all numbes which have more than 11 consecutive 1 and 0.

In my testing, sequences of greater than 11 zeros or ones only occurred maximum once in an entire sample of 1000 256-bit random numbers.
a.a
member
Activity: 126
Merit: 36
October 04, 2021, 10:50:46 AM
I have a conjecture:
The longest amount of consecutive 1 or 0 is sqrt(bits). So sqrt(120) = 10,95. So probably we can skip all numbes which have more than 11 consecutive 1 and 0.
Pages:
Jump to: