Topic: Pollard's kangaroo ECDLP solver - page 19. (Read 59389 times)

Yes, you can find any smaller bit key in it's range or in a range larger than it's original range.
Quick example, searching for private key 1 (0x1):
you can find it by finding key 2 - key 1 (0x2-0x1), or key 3 - key 2 (0x3-0x2), or move a lot higher up, 0xffffffffff - 0xfffffffffe = 0x1

It is possible to found key on other range?

my testing with puzzle#32 (32bit key)
all wide 31-32 bit can found key on many point collision

and it can found on 40bit range or higher that key
if on low bit key that pubkey*genpoint can collision on many point on 256bit range

but for puzzle #120 may be can found on range 121 bit or 160 bit

The problem is 120bit is too much wide
 

Right, group operations = kangaroo jumps/keys checked/group additions/etc. We are speaking the same language. If you run the program, it will show you the expected operations. That is what I am talking about.

Classified

But there are a few ways you can do this, you just have to tinker and experiment with code.

But again, I am hoping for a combination of things to occur as has occurred at lower bit ranges during tests and trials, but the biggest thing is, more group ops during the tame only run = less group ops needed during wild only run. Factor that with running all pubs concurrently, I am hoping for better than 2^60.5 total group ops.

EDIT: after rereading what you posted and what I responded with, I think I missed the mark.
I am not avoiding any additions or group ops by running all pubkeys at once.
Think of it this way...if you are running the slowest of slow python script (which I have done during test startup) and you create a file with 1,024 pubkeys (or however many you want), and the program reads the file and every pubkey and then starts adding or subtracting to create new points/pubkeys, it is not skipping or avoiding additions or subtractions. Let's say you want the script to offset each pubkey in the file by adding 0x1, sequentially up to 0x1000, it would work like this:
pub1 in file = add 0x1
pub2 in file = add 0x1
...
pub 1024 in file = add 0x1
_____________________
pub1 in file = add 0x2
pub2 in file = add 0x2
...
pub 1024 in file = add 0x2
_____________________
pub1 in file = add 0x1000
pub2 in file = add 0x1000
...
pub 1024 in file = add 0x1000

The program is not avoiding any additions, in this case of using a python script, it is looping; pub1 +, pub2 +....pub1024+, rinse and repeat.
Does that make sense?

Yes but when i speak about ops (operations to do) , i speak about group additions (Kangaroo jumps). Checking for DP in the hashtable is negligible in time compared to the cost of grop operation
I d'ont understand how you avoid the additions when you check the 1024 pubkey at once.

I will need to run/check all of the new 1,024 pub keys through the range.
With JLP's Kangaroo program, I would need to do this one pubkey at a time. However, I modified some code to allow me to run and check all 1,024 pubkeys at once/concurrently.
A few thoughts about this...I am hoping with double the needed tame points, the less wild group ops needed for a collision. I have completed tests at lower bits and this was the case however,
this is a much larger range and untested.

Keeping the math simpler (at least for me):
The original 120 bit range (reduced to 119 bit range): 119/2 + 1 = 2^60.5 expected group ops
In the 110 bit range (reduced to 109 bit range): 109/2 + 1 = 2^55.5 expected group ops
So straight up, 109 bit range = 32 times less but as you stated (and I know) I have to check all 1,024 new pubkeys. I am hoping by having at least double the amount of required tames plus being able to check all pubs concurrently, I can beat the original 2^60.5 expected group ops.
I have beaten the averages in lower bit ranges (up to 84 bit range) but this is new territory. We shall see what happens!

Hi WanderingPhilospher ,

Can u explain a little more your algorithm of dividing the pubkey before doing the Kangaroo search?
Because if i well understand when you reduce the range to 2^110 (division by 1024)

You will have to do an average of (cf Jean luc formula) :

2.08*sqrt(k2-k1) =  2.08*sqrt(2^(120-10)-2^(119-10)) = 5.29*10^16 ops

but as you say only 1 or 2 of the dividing split range will contains a pubkey with (pubkey+n)%1024==0
so you will have to repeat the search 512 times and do an average of

(1024/2)*5.29*10^16=5.42*10^19 ops  before having a collision.

But with the initial config of the kangaroo you will only have:

2.08*sqrt(k2-k1)=1.69*10^18 to do (32 times less)

There is no magic to ensure any address will be in the first 160 bits other than division, but that would take many keys like 2^96 keys to ensure that. 2^256(bit range)/2^96(keys) = 2^160 bit range (the first with many leading zeros).

Kangaroo basically creates many (millions or as many as needed to solve for privkey) of offset pubs/addresses. It stores only the ones you tell it to via a mask/distinguished points...either x amount of leading or trailing 0s. It stores the tame ones (x point and actual privkey) and wild ones (x point and offset of actual privkey); when the x points match with tame and wild, the key is solved. So unlike bruteforce that checks a privkey and then dumps it, kangaroo stores the ones you tell it to via the distinguished point argument.

To solve a key in the giant 2^256 range, kangaroo program needs to check roughly 2^128 points/privkey and applicable pubkey (for leading or trailing 0s) So if you used a DP of 40, then the program would roughly store 2^88 (128-40) points (x points) and applicable privkey (distances).

As a real world example, I am currently searching for the 120 puzzle in the 110 bit range, using a DP of 25. I divided 120's pubkey by 1,024 (2^10) which generates 1,024 new pubkeys related to the original pubkey, but only 1 (at most 2) of the new pubkeys are in the 110 bit range (the remaining pubkeys are spread out over the entire key space). So I will generate enough Tame points first and then run back through the range looking for Wilds. I expect to need to store 2^31 (110/2 + 1 - 25) total points and distances to solve the key, which will take an estimated checking of 2^56(ish) total keys. Now if I tried to bruteforce the same key, it could take me up to 2^110 total keys to check.

But here is a more interesting question, if I have 1 address and 2^96 other privkeys can unlock it, if I take the same address (if I know the pubkey) and create 2^20 more addresses that relate to the address, are there now 2^116 privkeys that will unlock the original address?? Or possibly even more when you factor in uncom and com pubkeys->ripemd160?? Hmmmmm...

Thanks for replying .. i learned a lot from this .. what I'm still confused about, is how to implement this in practical terms, like say if i want to find a key in the first 160 bit .. you know, that silly range with a lot of leading zeros .. i consider it our only safe haven in this gigantic keyspace .. if i want to use kangaroo to find collisions , how could i use addition/substraction of pub key to look there? Isn't this method gonna look for 256 bit keys anyway? I understood from your explanation how easy it is to use one public key to get well ahead of usual brute force prv key tools .. but does generating so many keys on kangaroo lead to a find in the first 160 bits? or the entire keyspace?

Excuse my ignorance im way better in other things but not kangaroo .. i even went all the way to automate all the other brute force tools so I don't have to waste anymore time on something that is highly unlikely to find stuff any time soon .. but your last reply got me thinking we might have a greater advantage this way .. i might even be able to automate search on kangaroo as well if it really could lower search down to 2^128 .. im currently doing some thorough reading hoping to get the hang of this specific point 👉 "finding colliding keys in the first 160 bits"

I understand the whole 2^96 collision theory. That was not the issue. The issue was how you limit the power of Kangaroo versus say keyhunt or bitcrack. Why does Kangaroo have to shoot blindly? Why do you consider it shooting blindly? With your perspective, the same would be for any searching program, even looking for a collision with 2^96 priv keys that would lead to a single funded address.

It all comes down to if you know the public key of a funded address.

I can create 2^96 public keys that if one is found, will lead me back to any public key/private key of an address. You really have to understand how Kangaroo works and the speed up it provides with any given keyspace. You can also create many more addresses for one funded address to increase the chance of a 2^96 collision. If you take one address that is funded, and you know its pub key, from that you can create many more addresses, that if found, would lead you back to the key you want.

For all of the funded addresses where the pub key is known, I can use kangaroo and find 2^31 of those addresses (and I'm certain there aren't that many funded addressed) before bitcrack searches the first 2^160 possibilities (considering GPU speed is the same for both programs).

Perhaps, this is what confused me the most. If you have an address and know its public key, and need to search for it, Kangaroo is trillions x trillions x infinity faster than brute force LOL. That is all. So my rebuttal would be, if you know the public key of ANY key, the most searching you would have to do with Kangaroo is 2^128, whereas with a bruteforce search, it could be anywhere in a 2^160 range. So kangaroo is great, even outside of puzzle ranges.

It's easy to understand. Again, if you know the pub key.
Address a = privkey unknown and pubkey 1
if we add 1 to Address a, we get Address b
So now, if we find Address a then we know its privkey.
But If we find Address b first, then we know Address b privkey - 1 = Address a privkey; thus we have solved and found Address a's privkey.
So if you have a list of 1000 funded addresses, just add or subtract 1 from each and now you have 2000 addresses that will lead to x amount of BTC. Now add or subtract 2 from each, now you have 3000 addresses, etc. etc.

Ok I'll try to explain how i see it

My conclusion depends on 2 factors:

1- number of private keys, public keys and address in the entire bitcoin space
2- the way hash functions distribute outcome along the entire range

so point 1 above is simple. in bitcoin, every single private key corresponds to only one public key .. however, any single address could be opened with 2^96 private keys .. hence 2^96 public keys would correspond to such address as well

Point 2 has all the magic, as it is deemed certain that good hash functions would have a sort of distribution that ends up almost evenly across a huge space, we can easily assume that every 160 bit in the entire range would encompass all possible bitcoin addresses .. so for example if we look for the address of puzzle number 160 in range from 1 to 160 .. we would have been doing the same as someone searching for that exact address in the next 160 bits .. and same for someone searching in the 3rd 160 bit range and so on until the last 160 bits in the keyspace .. all of those searchers would in theory find the private key that opens that address although all of these private keys are different AND produce different public keys as well ..

So in conclusion, many private keys and public keys will correspond to the same address and the keyword here is 160 bits range .. the advantage of looking for the puzzle wallets is that you narrowed down that 160bits .. in this case, any program will perform better but kangaroo would be the best performer

But this becomes the exact opposite if we choose to look for all funded addresses in any 160 bit range (remember that entire ADDRESS space is gonna get repeated in every 160 bit key range) .. so assuming i wanna search for these addresses (23 million addresses) in the first 2^100 unsearched range (ranges where all the rest of puzzles weren't visited and most likely has all funded addresses lying somewhere within) .. if we decide to use kangaroo, we would have to :
1st find public keys for all these addresses which means we will only be looking for addresses that spent some money.. leaving us with way less addresses than we want to search for

2nd for each public key, we would be searching for the EXACT private key that produced that exact public key which means we are not looking for a colliding key here, we are looking for a 256 bit private key, a well randomized one .. we are not only increasing difficulty by many folds, but also searching in the wrong range .. in order for one to search for a well randomized pvt key, one has to search in not any 160 bit range but in almost the whole keyrange space .. that's why i said kangaroo is only great for puzzles .. while programs like keyhunt or bitcrack can be directed to the first 160 bit range and get us a colliding private key, kangaroo has to shoot blindly in the sky of the entire range in the hopes it lands on a funded address

As for the addition and subtraction point you mentioned, i might need to read up on more about it as I don't yet get why it would get a collision

I am sorry, I do not understand what you are saying, exactly.
IMO, Kangaroo is still doing a brute force, of sorts. Instead of checking every private key sequentially, it makes jumps/strides to private keys, calculates the public key, verifies if public key ends with/starts with user inputted distinguish point, if yes, it stores the public key and the applicable private key, if no, discards the priv/pub keys. But the way you can use a Kangaroo program to look for more than one private key that will unlock one wallet, is to to subtract or add from original public key. So if you created 2^10 new public keys from the original public key, if you find any of those public keys, you can now unlock the original public key's private key.

As for what you say you realized, no programs, whether kangaroo or bitcrack or bsgs, etc are "efficient" for searching the entire key range. Meaning they were designed for the puzzle. However, each one will eventually find what you are looking for, even in the entire keyspace, and that all depends on hardware and time resources.

Yeah... it's highly unlikely that you'd find a funded private key within 2^100 keys left & right of the one your program is currently searching

Wow .. how come I didn't realize this from the beginning! So instead of brute forcing using collision, it will actually try to find one or more of the 2^96 addresses that the public key resolves to .. i can easily assume ALL those addresses would be empty except the one that actually has the puzzle funds 🤣 now i realize why kangaroo is great only for puzzle range search

Thank you for clarifying .. this makes sense now.. so it's not looking for private keys that can open that address .. it only looks to solve a "certain public key provided by user" which means only one corresponding private key .. not any of the the rest possible ones .. i got it now thanks

All the 2^96 possible spendable keys which leads to same address will have different pubkeys. The Kangaroo algo collide only with a particular given pubkey (+5 more according to symmetry and endomorphism). Therefore it will not be able to find any of those extra 2^96 possibilities.

Kangaroo does not know anything about addresses, so the private key you get is the one that can sign coins from any of the 2^96 colliding addresses (the addresses are defined to be any that collide with the input public key).

Guys Quick question, since I can't get my head around how Kangaroo works in terms of Maths, i was wondering if Kangaroo would still consider a private key within the range, a valid key even if it turns out to be just another colliding key of the 2^96 possible keys that resolve to an address on average .. actually thinking of this while writing, I don't see a reason why not .. but would like if someone could confirm

Well yeah, but you'd still need to figure out the Y coordinate for the nonce*G point - using only raw tx data on the blockchain - before you can run it through Kangaroo [and something tells me that it's not S or Z].


I was assuming fxsniper was talking specifically about Bitcoin tx signatures (which use ECDSA with sha256 hash) so I made my post around that idea.

Of course, an ECDSA signature based on an MD5 or CRC32 hash wouldn't be too hard to break ;-)

Sure you can: R of the signature is the X coordinate of the curve point nonce*G. So you can use kangaroo to search for (R, y) and (R, -y). Then you would have the nonce k and could solve for privatekey.
And it usually is a sha256 hash for the message but I don't think ECDSA specifies a hashing algorithm so you can use whatever you want for the hash as long as the other side knows what algorithm you have been using if they want to rebuild the hash from the message.
So I think you should refresh your knowledge of ECDSA .

I don't think Pollard's Kangaroo will work against ECDSA sigs because there is a SHA512 hash of the message bytes which forms a second line of defence against brute-force.

So even if you cook up a Kangaroo iteration that takes you from R,S to the origional message, it's still hashed, so you'd have to find a different way around that.