Topic: Pollards kangaroo method to reverse engineer private keys - page 2. (Read 1861 times)

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.

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

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

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

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

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

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

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

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

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.

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

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

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

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

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.

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  

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

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 

I really like this:

https://bitcointalksearch.org/topic/m.53649852

(gave them some merit for all the work).