Topic: Pollards kangaroo method to reverse engineer private keys (Read 1830 times)

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.

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

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

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

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.

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

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.

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.

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

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

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.

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

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

---

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.

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. 

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

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

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?

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.

sorry wrong post I move post to kangaroo thread

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