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/Kangaroobut 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

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:

552e025571c01bcd9eda59365a2fb3ae0bd7547dfeeeb13d971d848bcbf0467

552e025571c01bcd9eda59365a2fb3ae0bd7547dfeeeb13d971d848e3de3a07

04777c026b8085951da7117395bf269c055f36bf2ddf623281962855edee36d4e73bec2fa87b122a0f1b2841ef4f7afdec2443f89c151ee2597feac18ae0d62bdf

and test:

$ ./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

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:

552e025571c01bcda0297c22731d74becbd30cfb218f04dc91299473f61ffde

552e025571c01bcda0297c22731d74becbd30cfb218f04dc9129947400eacee

04777c026b8085951da7117395bf269c055f36bf2ddf623281962855edee36d4e73bec2fa87b122a0f1b2841ef4f7afdec2443f89c151ee2597feac18ae0d62bdf

and test:

$ ./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