Bitcoin Forum

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.

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.


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.

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?

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:


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.

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.

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.

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

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 :)

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!

I really like this:

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

(gave them some merit for all the work).

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

---

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

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

Underlined part I found; It's actually initializing the tames to 0 and the wilds to startingKey (https://github.com/JeanLucPons/Kangaroo/blob/master/Kangaroo.cpp#L715-L721) 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  :)

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.

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

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

puzzle #120

in.txt

where in c++ code read and use value 800000000000000000000000000000 and FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF to use as range search

I would like to compare c++ work
and use modify old python code to use range like c++

now I use JeanLucPons Kangaroo by split keyspace to small part and search
when use full rank, my CPU very high and use Full memory, I think 16GB laptop not enough for 120bit search may be need 64Gb to 128GB high end memory board

This is just not true. The RAM consumed/used is not dependent on the bits being search...it comes down to your DP setting and how often you save the work file.  I don't see your settings/flags when starting the program but you are using a very low -d setting or that plus using a long save to file time.

Sorry I forget tell use with old python version test on 256bit with set max 256bit that eat a lot of memory, that mean

For JeanLucPons Kangaroo it use low memory it work better other Kangaroo

recommend to use with GPU is better (CPU will full 100% resource )

if can have option for Kangaroo version OpenCL will be great

I can see now that searching a 256-bit interval will become feasible if we use 128+ bits of DP mask  :)

How feasible are you talking? So you are working on searching 256-bit interval using 128 + bits of DP mask too?

I forgot about this thread - sorry about that.

Yeah I am, so far I have the actual program running on GPU, it's running at ~260MKeys/s with the expanded dpmask on my T4 though but it's making quite a large number of same herd collisions and dead kangaroos. I had actually expected the speed to be much faster, like around ~1500MKeys/s given that I saw someone's V100 do ~1100MKeys/s.

I doubt checking three more uint64's for equality within the main loop is what's causing this speed drop but it's a good opportunity to peek into the CUDA accelerated Int class and see what else can be sped up.

What are your program flags; your -d setting and range? Too low and you will get many collisions/dead kangas and your speed will also be much lower.

I am using the default settings, and a 40-bit range from the bundled sample in.txt file.

Yeah, that is the problem, GPUs are not made for the 40 bit range, a CPU can get through that in about 1 second...You need to bump up your range to like an 80 bit range and let the GPU open up. Change your input text to this:


and rerun your program

What recommend size for kangaroo if need to split range?
What best size for keyspace?
What best size for DP with keyspace?

example
puzzle #120 = 664613997892457936451903530140172288  keys
split slot size   2**64
split to 2**64 size = 664613997892457936451903530140172288/2**64 = 36028797018963968 slot

DP size = 10
good or not for size 2**64

What keyspace size should be?
and What dp size good for that?

reference on image
for keyspace target should be
frame
edge
https://i.ibb.co/85swrwT/paths.jpg (https://imgbb.com/)


Kangaroo solve puzzle #110 #115 right
What long time to use solve each puzzle #110 #115 ?

puzzle #110 = scan 649037107316853453566312041152512 keys
puzzle #115 = scan 20769187434139310514121985316880384 keys



puzzle #120
Expected time: ~2 months (Tesla V100)
(info on github JeanLucPons/Kangaroo)

that mean  keyspace each days
calculate
2**120-2**119= 664613997892457936451903530140172288  key scan
2 month = 60 Days = 1440 hours

664613997892457936451903530140172288/60 Days = 11076899964874298787142191554756608 scan per days
664613997892457936451903530140172288/1440 hours = 461537498536429140150122660757504 scan per hour

(Tesla V100) nearly scan puzzle #110 on 1.30 hour


size 2**119  use time 1440 hours (Expected time)
split to 1440 slot may be possible lucky use 3 days (96 hour) if jackpot to right slot of peyspace

please advice

from image explain how to kangaroo works
if draw frame edge to on frame and inside frame
do target need to be only on inside frame only kangaroo will be found or not
or don't care kangaroo can found if target is closeup to on frame (near outside)
it require some space for 2 leg of kangaroo have some space to work or not

because I would like to split keyspace from large to small may be possible position of target move from center of keyspace to on edge of frame (close up to near outside)

refer from image explain again
do kangaroo work only leg two side meet on center only  or can be any angle like flip/rotate work like two point from left and right to meet on top center or can be top and bottom meer to center or form high left right meet to center on bottom  or left high low meet to meddle

https://i.ibb.co/85swrwT/paths.jpg (https://imgbb.com/)

If you are using 1 gpu, it really doesn't matter, just go for luck as you state. I have already spoke to this, used in conjunction with BSGS, but hey man, keep asking hoping you get a different answer...You either break it up in a size you are willing to wait until it completes. a 64 bit subrange, a 68 bit subrange, however long you can go without using your PC and gpu.  Let the program dictate your subrange dp. Set a -m 2 setting to make sure the pubkey is not in the subrange. Keep track of your ranges as has been shown how to do. Let it run. One gpu, let it run, let it eat.

Also, I couldn't figure out all your math but I think you are looking at Kangaroo program the wrong way. It doesn't matter about total keys; it doesn't scan every key. It scans one point, is it a dp yes=send to hashtable, no=jump again...the jumps are close to half range size. so if searching 2^120 range, then jumps are close to 2^60. When a tame and wild have the same position coords/points, then the puzzle is solved.

For your math; each V100 was averaging 1500-1600MKey/s, or jumps per second. so on a 4x V100 GPU rig, the rig was averaging 6000 to 6400 jumps/MKey/s; it took a little over 2 days for 110 and a little over 11 (or 13) days for 115.

Thank you
puzzle #110  = solve in 2 days
puzzle #115  = solve in 11 days
puzzle #120  = (2 month or may be 3 month not yet solve)
4x Tesla V100

yes, I understand kangaroo it not scan all key like bitcrack, I testing it and know from python version, kangaroo random a lot until meet condition get value, wonder method random difference tame and wild each time but found kay answer same whatever  tame and wild  difference but it meet same you tell

sorry wrong post I move post to kangaroo thread

This explains a lot about what could be wrong with my program.

To my understanding, we have a bunch of tame kangaroos that curve towards the "left", and wild kangaroos that curve towards the "right". A dead kangaroo happens when you draw a curve too far past some maximum length and if you get unexpected collisions in the same herd then your DP checks have gone bonkers.

Negative. A dead kangaroo means either 2 tames or 2 wilds landed on the same point; meaning they would hop along the same path therefore one of them is useless. The program detects dead kangaroos and resets them.

The drawing was just to show how they intersect, the wilds or tames could have approached from other side or reversed, left, right, etc. just showing paths "crossing", landing on same point, following same path until next dp and key solved.

I told you what your issue was with dead kangaroos; too small of a range for a GPU and a very low -d setting (you said you let program decide so I know it was very low for a GPU.)  did you find the key in that small 40 bit range?

that was actually using 256 V100s; I was telling you the jump rate of a rig that had 4 V100s running.

Ok, 256 GPU x Tesla V100
use 256 GPU on cloud right
how mush cost for 256 unit Tesla V100?

The person who used them/found the keys has access to them. I'm not sure if he had costs or not. But if you or I were to rent 256 of them, not sure we would make a profit.  ;D

Everyone got sidetracked with the fun game of cracking keys that were purposely created to be insecure.  Nobody answered the essential substance of OP’s questions.

From an inexpert position, Phillwilk politely and intelligently some important questions about Bitcoin’s security.  He is completely incorrect in some of his basic assumptions; his questions should be answered!

The summary version:

• Securely generated public keys that are exposed on the blockchain are not vulnerable to being broken.  Not even by Pollard’s kangaroos.
• The exposed public keys being broken in the challenge thread (https://bitcointalk.org/index.php?topic=1306983.0) are from a restricted keyspace.  They were purposely generated to be insecure.  That is why they can be broken.
• The reason to avoid address reuse is not security, but privacy.  Exposing your public keys does not make them vulnerable to cracking.  Whereas reusing addresses is sort of like publishing your bank statements to the whole world.  It reveals information about how much money you have, and where that money is.  That can make you vulnerable to attacks by hackers or armed robbers (https://github.com/jlopp/physical-bitcoin-attacks).  But it does not make your keys vulnerable to cracking, whether by Pollard’s kangaroos or otherwise.

The whole purpose of a “public key” is that it is safe to make public.  If a public key that gets revealed is vulnerable to cracking, then the cryptographic algorithm is totally insecure!  Whereas Bitcoin uses the secp256k1 algorithm, which is quite secure (https://bitcointalk.org/index.php?topic=2859033.0).

---

Define “drastically”.

In nontechnical terms, think of it as if Bitcoin’s public-key security were a mountain.  Pollard’s kangaroos hop in with some dump trucks, and they remove some dump-truck loads of rocks from the top of the mountain.  The mountain is still huge!  Taking a bunch of rocks off the top does not make a meaningful difference.

The challenge keys that are being cracked are purposely created not to be a mountain, but rather, to be a pile of rocks the size of a house.  Pollard’s kangaroos hop in with their dump trucks...  It doesn’t take them very long to haul away all of the rocks.

The problem with this metaphor is that Bitcoin’s security is not the size of a mountain; it is more like the size of a planet.


Yes.  However, this causes no meaningful loss of security.

The notion of some security benefit to hiding keys behind hashes is a pernicious myth in Bitcoin.  It is based on ignorance about cryptography.  People who make such claims do not know what they are talking about.

The purpose of a public-key cryptosystem is that the public key can be made public.  If a public-key algorithm loses security upon publication of the public key, then the algorithm is broken, and it should never be used for any purpose whatsoever.

Ethereum reuses known public keys.  PGP uses known public keys.  The TLS certificates that authenticate HTTPS in your web browser use known public keys.  It is secure to do this.


In proper usage, yes.  But this is for reasons of privacy, not security.  Re-using addresses makes blockchain analysis so easy that it’s like publishing your bank statements on the Internet, where they can be read anonymously by hackers, scammers, stalkers, robbers, etc.


This is not the reason to avoid address reuse.


Smart question.  The answer:  Revealing the public key causes no meaningful loss of security.


The limiting factor is Pollard’s kangaroos will need to jump around for trillions of years to crack a securely generated key.  Pollard’s kangaroos are “fast” insofar as they are faster than other methods, which would take even longer.

Last year, on this forum, Pollard’s kangaroos cracked a key restricted to a 115-bit keyspace.  Securely generated public keys are generated uniformly at random within a 256-bit keyspace.  And the difference is not linear:  A secure Bitcoin key is not 2.2x (256/115) harder to break than a 115-bit key, but rather, about ten thousand million trillion (10²¹) times harder to break.

My maths here are back-of-the-envelope, but should be approximately correct within a few orders of magnitude; and the numbers here are so astronomically huge that any error makes no practical difference.  If someone wants to quantify this more precisely, that would be interesting.


Thanks for asking your questions courteously and intelligently.

Can possible to create Pollards kangaroo have multi kangaroo ?

1. multi multi set of kangaroo
multiple kangaroo  (may be like opem kagaroo.ext multi set in same  time

2. multi wild and tame
may be like  wild-A  wild-B wild-C wild-D and tame-A tame-B tameC tameD

make it multiple may be powerful

haha, I am pretty sure this already exists.  If you look when you start the program, it tells you how many Kangaroos are running. 2^xx Kangaroos.

Half are wild and half are tame. There are millions of kangaroos running at the same time.

If we talking about JeanLucPons implementation, there are 1024 kangaroos for each CPU core and 128 for each GPU grid point by default.

Thank you

I see only 2 Tame +Wild, it calculate only 1 set

That mean JeanLucPons Kangaroo have multiple Kangaroo already.
I think it is have 1 Kangaroo because I read a python code version, when scripts calculate is work only 1 process
so I think is have only 1 process that mean have 1 kangaroo works

if you mean multiple jump on program is count multiple kangaroo, that difference with about What  meaning

reference from image JeanLucPons Kangaroo explain
I count 1 leg and pair of 2 leg Tame and Wild total is 1 kangaroo set

imagine my idea is  from image have left leg many leg and right leg many leg and calculate al same time not only

so if have multiple leg same time and they all can meet any time to solve problem

multiple set of kangaroo
this may be like open kangaroo multiple program to do same job with think may be it random jump to difference and some program open will be found from difference random

multi tame and wild this may be mutant
this is like star or multiple spot meet one point

please help to confirm I thinking is already happen on Kangaroo

if they all already have in side present Kangaroo present edition may be need to think more idea to make it can handle with high bits puzzle
for now Kangaroo  stuck with high bits may be area of jumping is too many wide make kangaroo tired until power less

if not yet have kangaroo version multi legs
Can possible some one try develop new strategy copy cat from kangaroo mutant
create thousand of legs ang make it jump like kangaroo and calculate each other all leg to meet match point  
and run all on GPU

https://i.ibb.co/85swrwT/paths.jpg (https://imgbb.com/)


https://i.ibb.co/Cn1C8N5/2021-03-27-14-58-38-What-is-Intersecting-Lines-Definition-Facts-Example-and-25-more-pages-Pr.png (https://imgbb.com/)


https://i.ibb.co/VgYg5KR/GfG-exx2.png (https://ibb.co/X7x7Mw1)

You have to stop taking that illustration so literally.  That "leg" is just one tame and one wild. Now imagine millions of those spread out over the illustration, that is what it would really look like.

correct so for a gpu with a grid size of (which you can adjust grid size via the program flags) 128,256 then you have 128x256x128 (default) which equals 4,194,304 kangaroos (half tame and half wild) for that one gpu. If you have multi gpu, times that by that number.

Ok, Thank you I got it.

I just come later, and don't know a lot about it in detail

How long time use develop kangaroo on puzzle thread?
kangaroo develop after brute force by bitcrack first right after that struck with long time scan all address and try use algorithm help to scan address

I would do the reverse actually, attempt kangaroo first, and only then when that times out resort to a linear brute-force such as BitCrack, because if Kangaroo doesn't get early luck at the key, say at least 50% of the expected range to search in, then you'll probably have to run through the entire range to get the key you're looking for.

With a linear cracker you can choose whichever points you want to search in thanks to the birthday paradox problem. And you have a better chance of getting "lucky", that is, finding the key early on in the range.

How can use birthday paradox to find key I not yet get this method how it work

with topic  reverse engineer private keys

may be method reverse engineer private keys  need to create some new algorithm

like example public point attack
generate private key with pubkey and convert to public point  now we have 3 number for use calculate reverse engineer

private key = 1329227995784915872903807060280344576
X = 73729489189146206306669255701359614973467519172738994441001234600131693731952
Y = 52215583774525796109567946288556659634043653399932078971590626905269875474081

private key = 664613997892457936451903530140172288
X = 63066765102144977597923579437181551876011710207298597143023780209765509321725
Y = 106007349317296939888635500379499007381281650903559653902304432927687101375981

may be need to do massive calculate (with random)

example prank algorithm
private key = X+X-Y*random/Y+Y-X

create not exit algorithm to attack and hit private key
or other way may be got zone of private key location and using kangaroo or bit crack scan

generate ton of private key from 2**120  may be million or 10 million (or 1 billion) for create algorithm
however may be can use only for this puzzle range only and then for other puzzle number need to rebuild for that range again.

just thin brain storm idea how to solve puzzle by other method

It's not an algorithm per se but a theory. A theory that if you have a group of people and you keep adding more people to the group you will eventually find two people with the same birthday.

The 50% chance barrier is broken around n=23 (23 people, ie 23x(22/2) out of 365 different possible pairs to choose from).

Of course we break 100% as soon as there are 367 people but you see that's a long way up.

Now in relation to private keys, we have some keyspace range, say 2^100. Except instead of trying to find TWO keys with the same property we are trying to find exactly ONE private key in the set.

So we exhaust 50% here at 2^99. BUT there are many, many private keys that form the same base58 hash so the problem can be reduced from 1/2^256 to 1/2^160 chance of finding a collision. So, it has been scaled down by about 62.5% and we can estimate that the size of equivalent public keys in here is 2^100 * 62.5% = 2^62.5.

The network does not care which public keys were actually used as long as they hash to the same RIPEMD160 hash (and you used a P2[W]PKH address).

The reason people say the birthday paradox does apply to the kangaroo method is because we are trying to find two same points.  More precise we are trying to find two matching points, "x coords". One by a tame, and one by a wild.  Once that is achieved, you subtract the distances traveled (depending on what program you are using) to uncover the private key of the public key you were searching for.

But it does not apply to brute force methods.