Pages:
Author

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

legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
July 02, 2022, 05: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).
member
Activity: 185
Merit: 15
Two things you should never abandon: Family & BTC
July 01, 2022, 01: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
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
June 06, 2022, 02: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].

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

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 ;-)
newbie
Activity: 7
Merit: 1
June 04, 2022, 06:29:13 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.


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.
legendary
Activity: 1568
Merit: 6660
bitcoincleanup.com / bitmixlist.org
June 03, 2022, 11:27:31 PM
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.
full member
Activity: 1232
Merit: 242
Shooters Shoot...
June 03, 2022, 05: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
member
Activity: 406
Merit: 47
June 03, 2022, 09:57:15 AM
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
full member
Activity: 1232
Merit: 242
Shooters Shoot...
June 03, 2022, 09:49:37 AM

Code:
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.
newbie
Activity: 22
Merit: 3
June 03, 2022, 12:26:00 AM

Code:
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.
member
Activity: 406
Merit: 47
June 02, 2022, 08:50:20 PM

Code:
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
full member
Activity: 1232
Merit: 242
Shooters Shoot...
June 02, 2022, 10:01:30 AM
https://github.com/JeanLucPons/Kangaroo
kangaroo 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)

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

Code:
tame is multiplied with a random number with G
tame is calculating the point/key it landed on and generating the corresponding pubkey

Code:
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

Code:
if both results is the same X that is collision right?
yes

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

member
Activity: 406
Merit: 47
June 02, 2022, 08:03:06 AM
https://github.com/JeanLucPons/Kangaroo
kangaroo 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)


newbie
Activity: 1
Merit: 0
May 18, 2022, 08:51:16 AM

Someone try making sach scrypt ? Share code pls ?

Br

What is sach scrypt ?

Did you mean search script or  scrypt hash algorithms ?

They meant "such a script"
member
Activity: 873
Merit: 22
$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk
May 08, 2022, 06:11:52 PM

Someone try making sach scrypt ? Share code pls ?

Br

What is sach scrypt ?

Did you mean search script or  scrypt hash algorithms ?

1048576 and 1073741824 pubkeys with each other addition and mutiplication
member
Activity: 406
Merit: 47
May 08, 2022, 11:11:46 AM

Someone try making sach scrypt ? Share code pls ?

Br

What is sach scrypt ?

Did you mean search script or  scrypt hash algorithms ?
member
Activity: 873
Merit: 22
$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk
April 29, 2022, 04:19:42 PM
" I got it down to 104 bits today, but with 32,000 pubkeys; better than the normal 2^16 normally required, but I can't figure out a way to shrink it down to one key... "

for 10 bit down = 1024 pubkeys
for 20 bit down = 1024*1024 = 1048576 pubkeys
for 30 bit down = 1024*1024*1024 = 1073741824 pubkeys

1048576 and 1073741824 pubkeys with each other addition and mutiplication will return you 260 pubkeys apear where 16 pubkeys sure inside 10 bit down from main pubkey
these 260 pubkeys again played for get 30 bit down for 1/720 pubkeys
now you can start to find with above tip



can you share script to do these calculations or explain a way please


Someone try making sach scrypt ? Share code pls ?

Br
newbie
Activity: 22
Merit: 3
April 19, 2022, 01:36:20 AM

Now kangaroo found problem same BitCrack  both range search is very large
kangaroo method still works but is stuck with a very large range of search

I do simple easy tests on both 120 bit and 160 bit (and 256) with keyspace (under 32 bit wide) nearby it is still found key
but when used with a very large rank and nowhere is key store, so kangaroo is stunned

Kangaroo and BSGS are both O root n complexity
root 120 is 2^60
2^60 is 1,152,921,504,606,846,976.
Can the discrete logarithm be computed in polynomial time on a classical computer? someday, but not tomorrow.
member
Activity: 406
Merit: 47
April 18, 2022, 05:24:37 AM

Now kangaroo found problem same BitCrack  both range search is very large
kangaroo method still works but is stuck with a very large range of search

I do simple easy tests on both 120 bit and 160 bit (and 256) with keyspace (under 32 bit wide) nearby it is still found key
but when used with a very large rank and nowhere is key store, so kangaroo is stunned
newbie
Activity: 22
Merit: 3
April 13, 2022, 11:35:03 PM
Hi, is there a way to find private key range from the public key, (Start and Stop range) ? Can someone point me to the right direction


For any random private key this is not (yet?) possible, in the case of the puzzle the creator initially put an amount of btc correlating to the bit length of the corresponding key.
Like 0.64 btc to puzzle 64 (16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN)
member
Activity: 406
Merit: 47
April 13, 2022, 12:51:45 AM
it can possible to calculate rollback to know the sample tame and wild?
just idea would like to test check how far tame and wild on 120 bit
Pages:
Jump to: