fxsniper
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 406
Merit: 47
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 02, 2022, 01:03:06 PM |
|
https://github.com/JeanLucPons/Kangarookangaroo calculate random both tame and wild right? tame is multiplied with a random number with G wild is multiplied by ADD PUBKEY(target) with a random number if both results is the same X that is collision right? How can control range random of tame? How can control range random of the wild? control on Kangaroo 2.2 (use GPU) (in python kangaroo script I can modify it) distinguished point (DP) -d: Specify the number of leading zeros for the DP method (default is auto) -d dpBit What mean if use -d ? -d 32 = distinguished point 32 bit -d 64 = distinguished point 64 bit -d 128 = distinguished point 128 bit (I did not yet understand it)
|
|
|
|
WanderingPhilospher
Full Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 1120
Merit: 235
Shooters Shoot...
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 02, 2022, 03:01:30 PM |
|
https://github.com/JeanLucPons/Kangarookangaroo calculate random both tame and wild right? tame is multiplied with a random number with G wild is multiplied by ADD PUBKEY(target) with a random number if both results is the same X that is collision right? How can control range random of tame? How can control range random of the wild? control on Kangaroo 2.2 (use GPU) (in python kangaroo script I can modify it) distinguished point (DP) -d: Specify the number of leading zeros for the DP method (default is auto) -d dpBit What mean if use -d ? -d 32 = distinguished point 32 bit -d 64 = distinguished point 64 bit -d 128 = distinguished point 128 bit (I did not yet understand it) kangaroo calculate random both tame and wild right? It assigns a random starting point (basically a private key value) within the user defined start and end range; after that, the kangaroos jump forward/positive based on average jump size; usually range width / 2 + 1. tame is multiplied with a random number with G tame is calculating the point/key it landed on and generating the corresponding pubkey wild is multiplied by ADD PUBKEY(target) with a random number wild is calculating the point/key it landed on and generating the corresponding pubkey AND now adds the target pubkey if both results is the same X that is collision right? yes What mean if use -d ? -d 32 = distinguished point 32 bit to keep it easy to understand, each character in the pubkey is equal to 4 bits. Each pubkey has 64 characters times 4 bits = 256 bits so for a dp of 32, the pubkey has to start with 8 zeros (leading zeros); 8 x 4 = 32. for dp 28, 7 leading zeros, for dp 64, 16 leading zeros, etc.
|
|
|
|
fxsniper
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 406
Merit: 47
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 03, 2022, 01:50:20 AM |
|
if both results is the same X that is collision right? yes Thank you WanderingPhilospher Who can find out they have a collision? How did they find from some testing? I had not been here when started the puzzle
|
|
|
|
BorisTheHorist
Newbie
Offline
Activity: 22
Merit: 3
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 03, 2022, 05:26:00 AM |
|
if both results is the same X that is collision right? yes Thank you WanderingPhilospher Who can find out they have a collision? How did they find from some testing? I had not been here when started the puzzle Well, Collisions work from DPs and as on wikipedia "the similarity between a visualisation of the algorithm and the Greek letter lambda ( λ ). The shorter stroke of the letter lambda corresponds to the sequence { x i }, since it starts from the position b to the right of x. Accordingly, the longer stroke corresponds to the sequence { y i }, which "collides with" the first sequence (just like the strokes of a lambda intersect) and then follows it subsequently. " You know you have a collision if two different kangaroos start to output the same value. Say K1 output 1,3,5,8,9 and K2 output 2,4,5,8,9 we know that between K1 and K2 after 3 or 2 they collide. We then can then refer to the tame kangaroo and correlate the input value of the wild one or as JeanLucPons put it himself "The program uses 2 herds of kangaroos, a tame herd and a wild herd. When 2 kangoroos (a wild one and a tame one) collide, the key can be solved". the actual outputs are valid public keys and the inputs are valid private keys.
|
|
|
|
WanderingPhilospher
Full Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 1120
Merit: 235
Shooters Shoot...
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 03, 2022, 02:49:37 PM |
|
if both results is the same X that is collision right? yes Thank you WanderingPhilospher Who can find out they have a collision? How did they find from some testing? I had not been here when started the puzzle I'm not sure what you mean by who can find out they have a collision...the program lets you know when a collision has occurred and the key has been solved.
|
|
|
|
fxsniper
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 406
Merit: 47
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 03, 2022, 02:57:15 PM |
|
I'm not sure what you mean by who can find out they have a collision...the program lets you know when a collision has occurred and the key has been solved.
I mean, How to know ECDSA has collisions like that? know from any report/research? or who find out just would like to know step by step develop on this forum before Pollard's kangaroo ECDLP release the first version is that python script right and then develop c++ for use GPU with high speed calculate
|
|
|
|
WanderingPhilospher
Full Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 1120
Merit: 235
Shooters Shoot...
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 03, 2022, 10:25:07 PM |
|
I'm not sure what you mean by who can find out they have a collision...the program lets you know when a collision has occurred and the key has been solved.
I mean, How to know ECDSA has collisions like that? know from any report/research? or who find out just would like to know step by step develop on this forum before Pollard's kangaroo ECDLP release the first version is that python script right and then develop c++ for use GPU with high speed calculate Ummmm the theory has been around since the 1970s; some smart people were just able to program it into a modern day programming language to speed it up/incorporate the use of GPUs. More info: https://en.wikipedia.org/wiki/Pollard%27s_kangaroo_algorithm
|
|
|
|
NotATether
Legendary
Offline
Activity: 1694
Merit: 7171
In memory of o_e_l_e_o
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 04, 2022, 04:27:31 AM |
|
I mean, How to know ECDSA has collisions like that?
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.
|
|
|
|
pikanakapika
Newbie
Offline
Activity: 7
Merit: 1
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 04, 2022, 11:29:13 AM Last edit: June 04, 2022, 02:36:49 PM by pikanakapika Merited by NotATether (1) |
|
I mean, How to know ECDSA has collisions like that?
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. 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 ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) .
|
|
|
|
NotATether
Legendary
Offline
Activity: 1694
Merit: 7171
In memory of o_e_l_e_o
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
June 06, 2022, 07:28:46 AM |
|
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.
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]. 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 ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) . 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 ;-)
|
|
|
|
Evillo
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 185
Merit: 15
Two things you should never abandon: Family & BTC
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 01, 2022, 06:17:06 PM |
|
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
|
Cool Story Bro. BTC: 1EviLLo1Y5VeNn2Lajv9tdZTkUuVgePVYN
|
|
|
NotATether
Legendary
Offline
Activity: 1694
Merit: 7171
In memory of o_e_l_e_o
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 02, 2022, 10:17:58 AM |
|
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
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).
|
|
|
|
iceland2k14
Jr. Member
Offline
Activity: 33
Merit: 67
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 03, 2022, 09:26:25 AM |
|
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
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.
|
|
|
|
Evillo
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 185
Merit: 15
Two things you should never abandon: Family & BTC
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 03, 2022, 10:55:40 PM |
|
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
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. 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
|
Cool Story Bro. BTC: 1EviLLo1Y5VeNn2Lajv9tdZTkUuVgePVYN
|
|
|
Evillo
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 185
Merit: 15
Two things you should never abandon: Family & BTC
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 03, 2022, 11:02:08 PM |
|
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
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). 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
|
Cool Story Bro. BTC: 1EviLLo1Y5VeNn2Lajv9tdZTkUuVgePVYN
|
|
|
NotATether
Legendary
Offline
Activity: 1694
Merit: 7171
In memory of o_e_l_e_o
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 05, 2022, 04:09:45 AM |
|
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
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 ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif)
|
|
|
|
WanderingPhilospher
Full Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 1120
Merit: 235
Shooters Shoot...
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 06, 2022, 06:47:49 PM |
|
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
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). 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 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.
|
|
|
|
Evillo
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 185
Merit: 15
Two things you should never abandon: Family & BTC
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 06, 2022, 09:16:41 PM Last edit: July 06, 2022, 09:28:17 PM by Evillo |
|
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
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). 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 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. 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
|
Cool Story Bro. BTC: 1EviLLo1Y5VeNn2Lajv9tdZTkUuVgePVYN
|
|
|
WanderingPhilospher
Full Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif) ![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 1120
Merit: 235
Shooters Shoot...
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 06, 2022, 11:04:26 PM Last edit: July 06, 2022, 11:31:20 PM by WanderingPhilospher |
|
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
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). 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 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. 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 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). now i realize why kangaroo is great only for puzzle range search 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. 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 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.
|
|
|
|
Evillo
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 185
Merit: 15
Two things you should never abandon: Family & BTC
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
July 07, 2022, 07:07:20 AM |
|
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
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). 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 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. 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 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). now i realize why kangaroo is great only for puzzle range search 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. 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 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. 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"
|
Cool Story Bro. BTC: 1EviLLo1Y5VeNn2Lajv9tdZTkUuVgePVYN
|
|
|
|