Topic: Pollard's kangaroo ECDLP solver - page 4. (Read 60037 times)

Look, I'm old enough to remember when floppy disks were cutting-edge technology. Back in my day, we didn't have these fancy-schmancy high-resolution screens, and I didn't always need glasses to tell the difference between people. So, forgive me if I mix up faces or names now retired and then. At this rate, I'll be mistaking my cat for the vacuum cleaner 

This coming from a guy who confuses me with some digaran dude. I came across this puzzle in January this year while searching for some tools to help me recover a wallet.dat password from 2016.

It's not about "believing", and I truly don't care on making an impression. I already indicated multiple times what the bottlenecks are:

- use of GPU global memory due to use of local stacks, due to use of GPU group size and multiple places where you don't even need a stack at all. This is the #1 slowdown.
- parts of the algorithm can be merged together, some other parts are really just handbook methods, unoptimized to CUDA hardware and the parallel paradigm

Using registers only, smaller group size, actually using the fast shared memory on-chip for inter-thread calculations, thinking better what the algorithm implies when run on massively number of threads, do make an implementation run 6x faster. This is not simply some optimizations in  JLP's Kangaroo, I am talking about a completely from scratch well-thought system here. It's very nice that this software was used to break 115 bit puzzle, but I will again have my suspicions that this was used for 120 or 125. It is just not up to that level of competence, from a design perspective.


Since no one answered, I will assume it's taken for granted that the multiplication used by JLP is correct (2-folding reduction steps). However, according to page 15 of this research paper:

https://eprint.iacr.org/2021/1151.pdf

under the analysis of "Sloppy reduction" it is proven that unless a correctness check is performed, then you need a 3rd reduction step.

Otherwise, the modular multiplication reduction has a chance (around one in 2**193) to be incorrect, because:


There is a missing potential carry that is assumed it can never happen, after the 2nd reduction. And no one can explain it.

It's impressive that you believe you've developed a version of the Kangaroo that outperforms both the original and all the clones by such a significant margin. Achieving 900 million jumps per second on an underclocked RTX 3050 laptop GPU is indeed a remarkable accomplishment!

Achieving a 6x speed improvement is no small feat, especially considering the limitations you’ve highlighted in the original program. If you truly have a solution that performs this well, sharing it on GitHub isn't just about proving anything to anyone. It's about fostering innovation, collaboration, and growth within the community. By making your work public, you can inspire others, drive progress, and leave a lasting impact on the field. Plus, being part of a collaborative effort can lead to new insights and improvements that benefit everyone.

So, why not contribute to the community and share your impressive work? 

You would have to run on 500 different machines if you wanted to execute the search in parallel depending on the bit range, with the same amount of power. Think of it like this lets say you wanted to search 500 pubkeys in 125 bit range all at the same time, the computing power would be spread too thin it would be more efficient to just run a single pubkey search on 500 different machines concurrently, even though it sounds crazy. I think this is where FUTURE quantum computers would come in. now if you wanted to search for 500 pubkeys in say the 50 bit range, with modern a gpu you could do it relatively quick on 1 computer .

It is like getting a taxi and asking to drive to multiple directions at the same time.

I have a question
It is for people who know the Kangaroo program well.

Kangaroo program has a multiple pubkey search feature, but it searches sequentially. that is, key1 key2 key3. It does not search for key2 before key1 is found. Likewise, it does not search for key3 unless key2 is found. I AM GIVING AN EXAMPLE. We have created 500 pubkeys. Is it possible to search all of them at the same time? Is there anyone working on this? can you share?

Can anyone explain why a sloppy modular multiplication is used? The 3rd step is missing, otherwise there exist probability of an incorrect result. Or is it proven that only 2 steps were sufficient (I doubt it)?

you can subtract from  to 2^20 and divide 2^20 times to 2^20 and get 2^20 pubkeys one of them will be 2^100 if you talk about 2^120 pubkey.

Are there any places where save files are shared for puzzle #130 either using JeanLuc kangaroo or Etars kangaroo

Im having a hard time understanding how distinguished points (DP) work. From what i know you only save the start point, trail length, and DP per a trail and start a new trail when a DP is found. You repeat this until you find a collision DP and some how find the "actual" collision of the pubkey.

I don't understand how finding and only storing DP would lead to finding the pubkey collision. I fully understand how the kangaroo method works by creating 2 maps to find a collision using the birthday paradox. but I'm not sure how you can do this without storing the whole set a points.

Anyone knows if pubKeys of range 2^120 -2^121 have been saved somewhere? Even for lower ranges like 2^118-2^119 if available. I understand there might be Kangaroo work files already saved in this range? We are trialling something at the college and I remember reading about this but can't find the post anymore. Reward is possible for verified files.

First welcome back master @Jean_Luc .. so happy to see ur post.

You cant compare your deep knowledge to others, as you have developed those tools and have a deep knowledge in the Math used.

I consider my self good in programming (i have many years experience in C++ , but very new to GPU) .. i have a good Math background but that part of "elliptic curve cryptography" is another world.

So its not easy .. yes i have downloaded ur source code but that not easy at all to understand the magic happening inside.

I am learning a lot, and i must say many thanks for @WanderingPhilospher as he is a big help answering my doubts ...


I don't know if you do stuff in youtube, but i can imagine that some simple videos explaining some of those aspects will be gorgeous .. maybe i wish too much ..


Regards

I solved it and it's working now with VS2022 and CUDA 12.1. I made some mistakes in the linking.

My question was a little bit short, sorry

I don't think anybody proficient enough for such a port would encounter your issue because they would take care of differences of Unix/Linux compared to Windows. In Linux OS mostly everything i a file and /dev/urandom is the non-blocking random number generating device (file). Reading from this file gives you not blocking random numbers.

You would have to port everything that's specific to Linux to the way it's done in Windows OS. Are you sure you have the knowledge to do this? Based on your question, I hightly doubt it.

Hi!

I migrated the kangaroo repo to VS2022 (windows), but I got an issue:
"Failed to open /dev/urandom No such file or directory"
Has anyone encountered this problem?

RIP my SSD's on the distributed Kangaroo project xD

This program cannot search for multiple keys simultaneously.

It will go over each key in the input file, one at a time.

If a solution is found then it goes to the next.

Someone correct me if I'm wrong, but otherwise I think you need to use the -m parameter to give up the search and start with the next key

In a scenario where the solution could not be found within the given range.

When we restore searching from a saved work file, it only shows the first key in input file after the end range, so what happens to other keys we input for search?

And if we have a speed of 1000MK/s, it would divide by the number of keys right? meaning half the speed is used to search for the second key if we input 2 keys? If that is the case then the expected time should double if there is more than 1 key.
Thus having 4 keys to search for a 130 bit key could take up to 2**68 operations, correct?

I agree with you. I am currently searching for #130, but how can we improve any of the existing tools? We talking creating mathematical shortcuts such as division/subtraction, or making current programs faster, or both lol?!

I am definitely interested in all possibilities.

Also, I am a fan of your python coding, 10000%; really great job(s) on your github repos!

I think there will be a long line to wait.