Pollards kangaroo method to reverse engineer private keys

[Phillwilk]

Sorry if this should be elsewhere but the level of technical detail in the main pollard kangaroo method thread is far beyond my level of technical understanding.

I just want to check my understanding and see where I might not have a good grap of the basics before proceeding. My assumptions are below;

* The pollard kangaroo method can drastically reduce the amount of work required to obtain the private key from the public key but requires the public key as an input to do this.

* Once an address has spent some of it's funds that address public key is revealed in the spend transaction.

* The funds which are not spent are returned to a change address leaving a balance of 0.

* The address should not be reused as a malicious actor can start generating the private keys from the moment the spend transaction is confirmed.

Feel free to correct any of the above points but if the above is correct; can anyone answer the following;

* Address reuse was extremely common in the early days and there are several addresses with 1000+ BTC balances with outgoing transactions revealing the public key.

Why has this not been used to steal the funds?

I'm sure there is a limiting factor to this method but I could do with it being spelled out in layman's terms.

Cheers.

[1713571231]

1713571231

[1713571231]

1713571231

[1713571231]

1713571231

[1713571231]

1713571231

[NotATether]

* The pollard kangaroo method can drastically reduce the amount of work required to obtain the private key from the public key but requires the public key as an input to do this.

That's actually not how it works. We take a range with a minimum and maximum number [a, b] that's in 256-bit space, and we "search" for the private key in (and only in) that interval by taking a starting term somewhere in that range, and then keep adding a smaller variable-sized increment. Each one of these increments is called a hop or jump.

EDIT: yes we also take the public key as input just to clarify.

We actually take two starting numbers as part of the Kangaroo algorithm, one of these is called a "wild" kangaroo which uses a starting term that is an estimate of G (the generator point) * the private key, and then computes more terms trying to "jump" to the private key.

The other kangaroo is a "tame" one because it's starting point is the public key itself, which is already known. In this way we can have many wild kangaroos with different estimates of what G*the private key is, and one tame kangaroo, and compute them all in parallel.

When a term of a wild kangaroo matches a term of the tame kangaroo we call that a "collision" and that number can be used to derive the private key easily.

Now as you might have guessed the range to search has to be very small, otherwise if the range to search in is too large the algorithm will take too long to find a collision on modern hardware. Combined with the fact that Kangaroo can't search outside the range, that's why this is impractical to brute force random people's private keys and their money hasn't been stolen en masse.

* The funds which are not spent are returned to a change address leaving a balance of 0.

This actually only happens to the outputs that has been spent. If an address has many outputs and only one is spent then the others remain in the address leaving some BTC leftover in there.

[Phillwilk]

Thanks for the reply, knew my understanding must have a big hole in it.

So the additional information an attacker would need is to know a range that the private key is within [a, b]. Now I understand why a flaw in generating the private key (not truly random) can result in encryption failure on an other wise cryptographically secure system.

Thanks for the info on UTXO, always thought it was weird to leave funds on an exposed address but the above explains it.

One other question, how small does the range [a, b] have to be to consider it an immenent security threat with current hardware?

[BurtW]

Here is an experiment to determine the answer to your question

https://bitcointalk.org/index.php?topic=1306983.msg51460251#msg51460251

Here my comment from that thread:

Well, what is the sacramental meaning of the step through 5? And he just brute force? because, it seems, it is necessary that the address be translated to its public key lit up. Arulbero could not until there is no output, find the number or could?)).

The author of the puzzle did that transaction to spend from every fifth address.  

My guess is that it is an experiment to see how far people can get when there is an available spend transaction versus addresses with no available spend transaction.

He has been known to visit this thread.  Perhaps he will explain it.

Obviously it is much easier to get the private key when there is a spend transaction on the address. #1 through #61 took a long time whereas #65, #70, #75 and #80 were snatched up pretty soon after the author added the spend transaction to those addresses.  I expect #85 will also be snatched up in due time.

As discussed #85, #90, #95, #100, #105, #110 are all within the realm of possibility given enough time and resources.  It looks as if #115 would be a new world record so someone with enough equipment and motivation can probably get that one.  Beyond that it is very iffy.

Note that since there is a spend transaction on these addresses we will probably see more of them before we ever see the next address without a spend transaction, #62.  This is a HUGE difference in effort.

I think one of the take home messages here might be that due to this difference in effort and other factors having to do with privacy and the fungibility of Bitcoin in general:  do not reuse Bitcoin addresses.  Bitcoin addresses should be used exactly twice:  once to fund them and once to spend them - then never used again.

As I predicted:

https://blockchair.com/bitcoin/outputs?q=transaction_id(56857085)&s=index(asc)#

Brute force has claimed the BTC up to 63 bits and the next brute force target address has 64 bits.

Kangaroos have claimed up to 115 bits the and next target for the kangaroos is 120 bits.

[WanderingPhilospher]

Here is an experiment to determine the answer to your question

https://bitcointalk.org/index.php?topic=1306983.msg51460251#msg51460251

Brute force has claimed up to 61 bits.

Kangaroos have claimed up to 80 bits.

kangaroos have claimed up to 115 bits.

[BurtW]

kangaroos have claimed up to 115 bits.

I think that is a new world record but would have to research it to make sure.  If so, the person who claimed the 0.115 BTC should get some fame for that - if they want the fame...

[WanderingPhilospher]

kangaroos have claimed up to 115 bits.

I think that is a new world record but would have to research it to make sure.  If so, the person who claimed the 0.115 BTC should get some fame for that - if they want the fame...

I think Zielar and/or Jean Luc (the finders) said it tied the record at 114 bits.

[Phillwilk]

Thanks for the info, is there a consolidated list of the puzzles that have been solved and the likely method used to solve them?

[BurtW]

Thanks for the info, is there a consolidated list of the puzzles that have been solved and the likely method used to solve them?

This is the only transaction I know of that is specifically designed to experimentally determine the security strength of Bitcoin.

[NotATether]

kangaroos have claimed up to 115 bits.

I think that is a new world record but would have to research it to make sure.  If so, the person who claimed the 0.115 BTC should get some fame for that - if they want the fame...

Since the jump size is limited to 64 bits it quickly becomes impractical to search ranges that are say 128 bits long without extending the code.

I estimate it would take at least 2^64 jumps for the program to get from one end of that particular range to another, and who knows how much that translates to in terms of running time.

EDIT this may not be correct see my below reply

[WanderingPhilospher]

kangaroos have claimed up to 115 bits.

I think that is a new world record but would have to research it to make sure.  If so, the person who claimed the 0.115 BTC should get some fame for that - if they want the fame...

Since the jump size is limited to 64 bits it quickly becomes impractical to search ranges that are say 128 bits long without extending the code.

I estimate it would take at least 2^64 jumps for the program to get from one end of that particular range to another, and who knows how much that translates to in terms of running time.

Code:

F737013293C98AC672D66B872468B8C0EF395CF200FE98D3E2F4915D39000000 FFB147D2479E70AE8656DD645BD0E1458D98543C555FF33CCC87B4592C966CB6
8A90D1581D2E2DF040F87DDF49A52B3691AA54F7BE8C0647FAB5F3EEDB000000 0002E3B2800D79DAD9CBFEE901E1E1F0A8991BB922941DD1D9C4E94369C2C31C
FE648F53DF416B87C9EA9E2DC8E456AEED7836A5FC9A40F085D1ECD995000000 FFF9ECC78E1E3477E5EF2FA877761578FF7A8E73CE6F3CD47A6DD2682A9D3D09
DACEE00338E64CED5641E8C2C7679ECC1B72729CCFB5BBC40CED057F5C000000 001EB2689F2D30D9FAAF28A9E16E998702FA4F597D4EC573A7857261D5758245

All depends on the program you use.
What do you mean the jump size is limited? I do believe the max is set at 128, and one could change that, however, for JLP's program, it just can't write to file with the current 126 bit restriction.
I have hopped around the elliptic wheel and picked up many 24 to 32 DP points. I believe I probably hold the useless record of most 32 bit DPs

[albert0bsd]

Thanks for the info, is there a consolidated list of the puzzles that have been solved and the likely method used to solve them?

This is one of the list:

https://bitcointalk.org/index.php?topic=5166284.0

But is not update. let me search the updated one.

Edit: this is the last update topic:

https://bitcointalk.org/index.php?topic=5218972

Best Regards!

[BurtW]

I really like this:

https://bitcointalk.org/index.php?topic=5218972.msg53649852#msg53649852

(gave them some merit for all the work).

[NotATether]

What do you mean the jump size is limited?

https://github.com/JeanLucPons/Kangaroo/blob/master/Kangaroo.cpp#L381-L420

jump size is a uint64_t and it's straight added to the distance.

I had a mind blackout for a moment and thought this was actually adding 64-bit numbers to the kangaroo X,Y; It's actually taking part of the distance and using that as input to a jump table full of G,2G,3G... points.

If I undersrand this snippet correctly then for the kangaroo itself, we subtract p1y (Y from the corresponding jump distance in the table) from p2y (the old y) to get another kangaroo Y, then we multiply this with p2x-p1x (same logic as p1y and p2y) which is old kangaroo old X - X point in jump table, then these are multiplied together to get a 128-bit value which is then squared (so I was wrong about jump search being limited to 64 bits)

Then it looks like it subtracts the kangaroo and the jump distance from this squared value to get new X (also 128 bits), then for Y it subtracts that from the jump distance and multiplied that result by the aforementioned 128-bit value which potentially gives a 256-bit value which is then subtracted from old kangaroo Y to get new Y.

And each operation is taken to the modulus of secp256k1 group order.

Hard to remember our starting points and terms are (X,Y) pairs and not single numbers since we are solving elliptic curves and not descrete logs.  

I wonder what happens if more points are generated in the jump table...

A lot of moving parts in JLPs kangaroo but it is the best on the free market...his program also subtracts the starting range so the actual starting range is always 0; so when a key is solved, it subtracts T-W then adds back original start range. So for 120 bit, it subtracts 800000....effectively reducing search range a full bit to 0 thru 7FFFFF....versus 800000...FFFFFF

Eureka, so that's why he said it's limited to 125 bits and not 126 

[WanderingPhilospher]

What do you mean the jump size is limited?

https://github.com/JeanLucPons/Kangaroo/blob/master/Kangaroo.cpp#L381-L420

Then it looks like it subtracts the kangaroo and the jump distance from this squared value to get new X (also 128 bits), then for Y it subtracts that from the jump distance and multiplied that result by the aforementioned 128-bit value which potentially gives a 256-bit value which is then subtracted from old kangaroo Y to get new Y.

And each operation is taken to the modulus of secp256k1 group order.

A lot of moving parts in JLPs kangaroo but it is the best on the free market...his program also subtracts the starting range so the actual starting range is always 0; so when a key is solved, it subtracts T-W then adds back original start range. So for 120 bit, it subtracts 800000....effectively reducing search range a full bit to 0 thru 7FFFFF....versus 800000...FFFFFF

[NotATether]

his program also subtracts the starting range so the actual starting range is always 0; so when a key is solved, it subtracts T-W then adds back original start range. So for 120 bit, it subtracts 800000....effectively reducing search range a full bit to 0 thru 7FFFFF....versus 800000...FFFFFF

Underlined part I found; It's actually initializing the tames to 0 and the wilds to startingKey and then adds some random number to all of them. The rest of the operations are a mystery I can't find. In particular I can't find the range subtracted/added to a kangaroo, or T-W.

Since there is no subtraction of the range present in the first place I think that's why there's no addition of the range back when a key is found. So the chance there's no "highest-bit killing" operation that decreases intervals by 1 bit is still on the table.

Something else I discovered about this is that his Int class has 5 uint64_t elements, and the 5th one is only used if you overflow 256 bits by eg. adding two very large numbers, not that it'll ever be larger than 2^256 anyway because all of Jean_Luc's integer function calls are modulused by the secp256k1 group order. It basically means I don't have to worry about arithmetic on 256-bit (or 125/6 bit!) ranges that overflows  

[WanderingPhilospher]

In particular I can't find the range subtracted/added to a kangaroo, or T-W.

Since there is no subtraction of the range present in the first place I think that's why there's no addition of the range back when a key is found.

That's the way his program works...If you read the thread on his program he and others tell you that it's always subtracting the initial start range so instead of range b-a it's always b-1 - 0.

If you run his program and save the kangaroo files and then export, you will see the offset.  Also, you can save the files, export them, and solve for the key and you will always have to add back the initial start range to solve.

all the tames distances are within the range [0...(a-b)] and all the wilds are within the range [0...(a-b)/2] - for wilds also the sign is used

The program shifts the range to 0, and also shifts the Public Key.

Example for puzzle key #110:
We know that public key is (pk110): 0309976ba5570966bf889196b7fdf5a0f9a1e9ab340556ec29f8bb60599616167d
And we also know that it is in the range [2^109 ... 2^110-1]

The GPU Solver shifts the range by 2^109 to the left, and making the search in the range [2^109 - 2^109 ... 2^110-1 - 2^109] which is [0 ... 2^109 - 1]
So, all the tames are generated within this range from 0 to 2^109-1.

As for wilds, they are generated not from the original public key pk110, but from another point: pk110 - 2^109 * G
This shifted point is pk110s: 02e2cec18b0aa6c9fe69f2dfd7b253594957a1840a3506cb17b4d80d1bd8c37d25

All the DPs in hashtable are within the range [0 ... 2^109-1]: for tame with have distance Td in this range and x-coordinate related to it, for wild we have distance Wd which is +/- [0 ... 2^108] and x-coordinate related to pk110s + Wd * G
All the wild points in hash table are also related to the shifted public key.

PS. Actually instead of solving pk110 within the range [2^109 ... 2^110-1] the program solves the key pk110s within the range [0 ... 2^109-1]

Because the Tame Kangaroos are dependent only on the interval size, while the Wild Kangaroos are dependent on the interval size and the public key. We want to keep the algorithm as generic as possible, and also the ability to reuse the Tame Kangaroos for multiple key searches.

As relating to the Wild Kangaroos, [working_public_key] = [(original_public_key) - (beginning_range)*(secp256k1_generator_point)].
[distinguished_point] = [(+-traveled_distance)*(secp256k1_generator_point)] + [working_public key]

You will need to add back the (beginning_range) when there’s a collision to solve for the (original_public_key).

[_Counselor]

his program also subtracts the starting range so the actual starting range is always 0; so when a key is solved, it subtracts T-W then adds back original start range. So for 120 bit, it subtracts 800000....effectively reducing search range a full bit to 0 thru 7FFFFF....versus 800000...FFFFFF

Underlined part I found; It's actually initializing the tames to 0 and the wilds to startingKey and then adds some random number to all of them. The rest of the operations are a mystery I can't find. In particular I can't find the range subtracted/added to a kangaroo, or T-W.

Look at Kangaroo::InitRange() and Kangaroo::InitSearchKey() - range shifting magic is there.

[fxsniper]

Did you guy modify kangaroo to can use high bit or 256bit

I try to modify python version to high bit and 256bits

problem kangaroo need to calculate prepare table and value before start compare a lot make CPU high and RAM Memory high (full memory) when use 256bits

I think may be have problem both with version JeanLucPons Kangaroo or any C++ same problem may be the keyspace are too high more than kangaroo work fast

[WanderingPhilospher]

Did you guy modify kangaroo to can use high bit or 256bit

I try to modify python version to high bit and 256bits

problem kangaroo need to calculate prepare table and value before start compare a lot make CPU high and RAM Memory high (full memory) when use 256bits

I think may be have problem both with version JeanLucPons Kangaroo or any C++ same problem may be the keyspace are too high more than kangaroo work fast

There are other programs out there.

The only thing running a search in a 256 bit range will do is cause your search time to jump by infinity x 3.14