Quote from: PawGo on February 08, 2021, 02:13:23 PM

Hello

I would like to share with you my modifications of Jean-Luc's famous Kangaroo program. I adapted it to be used as a 'WIF solver'.
In general, there are 2 cases - where stride is large enough not to collide with WIF checksum or when it is more complicated and stride collides.
I described it and showed test examples on github:
https://github.com/PawelGorny/Kangaroo
but I will also rewrite it here.

Let's take WIF: 5HrdZxkxnVst8Q3qCLJkeiLe1k4AmSDaAhqQVUYVxVSBkf5VfUu which encodes the private key 0552e025571c01bcda0297c22731d74becbd30d07e4ec355c741825fffc0a672.
Decoded WIF shows checksum 524412ca
The corresponding public key is 04777c026b8085951da7117395bf269c055f36bf2ddf623281962855edee36d4e73bec2fa87b122 a0f1b2841ef4f7afdec2443f89c151ee2597feac18ae0d62bdf

Search without checksum (large stride)

Let's take WIF 5HrdZxkxnVst8Q_____keiLe1k4AmSDaAhqQVUYVxVSBkf5VfUu
Now, we may find the first WIF to be tested, it will be 5HrdZxkxnVst8Q11111keiLe1k4AmSDaAhqQVUYVxVSBkf5VfUu. When we decode it, we find the private key which is the beginning of our range: 0552e025571c01bcd9eda59365a2fb3ae0bd7547dfeeeb13d971d848bcbf0467
Now, we must calculate the number of WIFs in our range. Beause we have 5 missing characters, it will be 58^5 = 656356768 (271f35a0 hex)
To have the end of range for Kangaroo, we must calculate fake end which is start + range

Code:

new BigInteger("0552e025571c01bcd9eda59365a2fb3ae0bd7547dfeeeb13d971d848bcbf0467",16).add(new BigInteger("656356768",10)).toString(16) =
552e025571c01bcd9eda59365a2fb3ae0bd7547dfeeeb13d971d848e3de3a07

We check where is the most right unknown character - it's position will tell us what is the stride. In our case it is 58^32 = af820335d9b3d9cf58b911d87035677fb7f528100000000
Because WIFs encodes checksum, we must observe if stride collides with checksum. Fortunately - not, because the last 8 characters (length of checksum) are 0s. We may remove these zeros and get shorter stride.
The final configuration file is:

Code:

552e025571c01bcd9eda59365a2fb3ae0bd7547dfeeeb13d971d848bcbf0467
552e025571c01bcd9eda59365a2fb3ae0bd7547dfeeeb13d971d848e3de3a07
04777c026b8085951da7117395bf269c055f36bf2ddf623281962855edee36d4e73bec2fa87b122a0f1b2841ef4f7afdec2443f89c151ee2597feac18ae0d62bdf

and test:

Code:

$ ./kangaroo -stride af820335d9b3d9cf58b911d87035677fb7f5281 test_af820335d9b3d9cf58b911d87035677fb7f5281.txt
Kangaroo v2.2
Start:552E025571C01BCD9EDA59365A2FB3AE0BD7547DFEEEB13D971D848BCBF0467
Stop :552E025571C01BCD9EDA59365A2FB3AE0BD7547DFEEEB13D971D848E3DE3A07
Keys :1
Stride:
MaxRange: 271F35A0
Jump: AF820335D9B3D9CF58B911D87035677FB7F5281
Number of CPU thread: 2
Range width: 2^30
Jump Avg distance: 2^15.04
Number of kangaroos: 2^11.00
Suggested DP: 1
Expected operations: 2^16.11
Expected RAM: 13.3MB
DP size: 1 [0x8000000000000000]
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 0: 1024 kangaroos

verify PK 552E025571C01BCD9EDA59365A2FB3AE0BD7547DFEEEB13D971D848BEA7DAF2
Key# 0 [2N]Pub: 0x03777C026B8085951DA7117395BF269C055F36BF2DDF623281962855EDEE36D4E7
Priv: 0x552E025571C01BCD9EDA59365A2FB3AE0BD7547DFEEEB13D971D848BEA7DAF2
RealPriv: 0x552E025571C01BCDA0297C22731D74BECBD30D07E4EC355C741825FFFC0A672

Search with checksum (small stride)

Let's take WIF 5HrdZxkxnVst8Q3qCLJkeiLe1k4Am____hqQVUYVxVSBkf5VfUu
Now, we may find the first WIF to be tested, it will be 5HrdZxkxnVst8Q3qCLJkeiLe1k4Am1111hqQVUYVxVSBkf5VfUu. When we decode it, we find the private key which is the beginning of our range: 0552e025571c01bcda0297c22731d74becbd30cfb218f04dc91299473f61ffde
Now, we must calculate the number of WIFs in our range. Beause we have 4 missing characters, it will be 58^4 = 11316496
To have the end of range for Kangaroo, we must calculate fake end which is start + range

Code:

new BigInteger("0552e025571c01bcda0297c22731d74becbd30cfb218f04dc91299473f61ffde",16).add(new BigInteger("11316496",10)).toString(16) =
552e025571c01bcda0297c22731d74becbd30cfb218f04dc9129947400eacee

We check where is the most right unknown character - it's position will tell us what is the stride. In our case it is 58^18 = 2b85840fc1d6a480ae7fa240000
Unfortunately the stride collides with checksum (last 8 characters are not 0s). It means that for our calculations we must take into account the proper checksum And this is difficult part, because the real checksum is unknown. In our test it is known, but in real-life it could be needed to see how many possibilities there are. For example, in this case, playing with missing characters of WIF we may observe that last 4 characters of checksum are fixed. The first 4 could be changed, BUT the 4th character gets only 4 values. It means that if we want to use this method for real-life problem, we may need to do calculations for 16*16*16*4 checksums (in fact will less operations needed, because many checksums will generate the same private key in addition to the stride).
Because stride collides with checksum, we will have to use the full (long) value and pass checksum as a parameter.
The final configuration file is:

Code:

552e025571c01bcda0297c22731d74becbd30cfb218f04dc91299473f61ffde
552e025571c01bcda0297c22731d74becbd30cfb218f04dc9129947400eacee
04777c026b8085951da7117395bf269c055f36bf2ddf623281962855edee36d4e73bec2fa87b122a0f1b2841ef4f7afdec2443f89c151ee2597feac18ae0d62bdf

and test:

Code:

$ ./kangaroo -stride 2b85840fc1d6a480ae7fa240000 -checksum 524412ca test_2b85840fc1d6a480ae7fa240000_524412ca.txt
Kangaroo v2.2
Start:552E025571C01BCDA0297C22731D74BECBD30CFB218F04DC91299473F61FFDE
Stop :552E025571C01BCDA0297C22731D74BECBD30CFB218F04DC9129947400EACEE
Keys :1
Stride:
MaxRange: ACAD10
Jump: 2B85840FC1D6A480AE7FA240000
checksum:
Number of CPU thread: 2
Range width: 2^24
Jump Avg distance: 2^11.97
Number of kangaroos: 2^11.00
Suggested DP: 0
Expected operations: 2^13.25
Expected RAM: 12.4MB
DP size: 0 [0x0]
SolveKeyCPU Thread 1: 1024 kangaroos
SolveKeyCPU Thread 0: 1024 kangaroos

verify PK 552E025571C01BCDA0297C22731D74BECBD30CFB218F04DC91299473FAD12F9
Key# 0 [2N]Pub: 0x03777C026B8085951DA7117395BF269C055F36BF2DDF623281962855EDEE36D4E7
Priv: 0x552E025571C01BCDA0297C22731D74BECBD30CFB218F04DC91299473FAD12F9
RealPriv: 0x552E025571C01BCDA0297C22731D74BECBD30D07E4EC355C741825FFFC0A672

It has no mean to solve 2**11, or even 2**40 puzzles so what?

BTC is 2*256, and you need to do 2**128 to crack real world btc

if you can do 2**40, and have a means to do 2**40 on the ball park then that puts you in the game of find a hit that year

The problem with the kangaroo BULLSHIT is that real world there are no problem in the 2*20 domain

There are two ways to crack BTC

1.) use large bloom filter and find key/address pairs with value, and have search space that is doing 2**40 compares per second

2.) use advanced crypto methods to crack ecdlp256 using known back doors ( this is huge problem in prime number theory, but there tools out there )