Pollards kangaroo method to reverse engineer private keys

[fxsniper]

puzzle #120

in.txt

Code:

800000000000000000000000000000
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
02CEB6CBBCDBDF5EF7150682150F4CE2C6F4807B349827DCDBDD1F2EFA885A2630

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

[WanderingPhilospher]

puzzle #120

in.txt

Code:

800000000000000000000000000000
FFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
02CEB6CBBCDBDF5EF7150682150F4CE2C6F4807B349827DCDBDD1F2EFA885A2630

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.

[fxsniper]

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

[NotATether]

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.

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

[bigvito19]

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.

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?

[NotATether]

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.

[WanderingPhilospher]

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.

[NotATether]

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.

[WanderingPhilospher]

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:

Code:

800000000000000000000
FFFFFFFFFFFFFFFFFFFFFFF
037e1238f7b1ce757df94faa9a2eb261bf0aeb9f84dbf81212104e78931c2a19dc

and rerun your program

[fxsniper]

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



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

[fxsniper]

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

[WanderingPhilospher]

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

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.

[fxsniper]

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

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

[fxsniper]

sorry wrong post I move post to kangaroo thread

[NotATether]

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.

[WanderingPhilospher]

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?

[WanderingPhilospher]

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

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

[fxsniper]

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

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?

[WanderingPhilospher]

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

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. 

[nullius]

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.

Bitcoin’s public-key crypto uses 256-bit keys but is deemed to have a 128-bit security level.

[...]

Bitcoin’s public-key security is humanly impossible to break now and for the foreseeable future.

[...]

Bitcoin’s public keys are plenty strong enough to protect the monetary value equivalent of hundreds of billions of dollars.  Or trillions.  Or all the money on Earth.

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.

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.

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

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.

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

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.

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

This is not the reason to avoid address reuse.

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?

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

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

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.

Cheers.

Thanks for asking your questions courteously and intelligently.