Pollard's kangaroo ECDLP solver

[RBan]

when you say

#addition factor, in this case its G or +1 decimal
K ='0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c 4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8'

you mean add +1 decimal to previous pubkey? The "G" is throwing me off

Yes I mean G as in the generator point which is equal to 1 in decimal but the code should allow for any address to be added I just used 1 for simplicity

[/quote]
Sorry, I had more questions but posted too soon.

Kangaroos...sounds like what you want they aren't necessarily kangaroos, just a 'brute force" type of jump. Start at pubk a, add increment to pubka to create pubk b, rinse and repeat. Each time a new pubk is created and 'visited' you want to convert that pubk to a BTC address and write both to a file. rinse and repeat all until a predesignated address is reached (end of range) or end after so many jumps. Anything I missed?


[/quote]

Thats exactly correct yes, consistently adding a specific key, converting output to address, then writing it to a CSV file. How would that look like in a Python code?

[paniker]

How we can recieve a pub key?  try to do all without mistakes

i make a from address 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN a pub 3EE4133D991F52FDF6A25C9834E0745AC74248A4 in hash 160, is it right or or everyone use some online stuff for it?

Can someone wrote how to start kangaroo in range? i try to make it via doc, but not understand... and not understand how it looking for address, where i must to write it?

For Windows:

Example of input text document that contains ranges and public key you are searching for, let's call it/save it as input.txt:

Code:

1000000
1FFFFFF
03057fbea3a2623382628dde556b2a0698e32428d3cd225f3bd034dca82dd7455a 

1000000 = start of range
1FFFFFF  = end of range
03057... = public key you are searching for

Save the input text document in same folder as Kangaroo.exe

Kangaroo doesn't search for an address but a public key.

[TheArchaeologist]

How we can recieve a pub key?  try to do all without mistakes

i make a from address 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN a pub 3EE4133D991F52FDF6A25C9834E0745AC74248A4 in hash 160, is it right or or everyone use some online stuff for it?

In case of your example you can't find the pubkey of the address 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN. That's because it is a Pay 2 Public Key Hash address. What you tried to do I guess is a base58 decode of the address. The tool at http://gobittest.appspot.com/Address might be of help to you fur understanding purposes. Just fill in the address in the last field and you will get the values all the way to the RIPEMD-160 of the hash of the private key. But since RIPEMD and SHA are hashing algorithms that will only work in one direction there is no way you can calculate the public key.

In case of a P2PKH address the public key becomes known when the address is used for an outgoing transaction. In that case for the unlocking script the public key has to be supplied and it will be checked if it hashes to the correct value. But in your case the address doesn't have any outgoing transactions so the public key is not known to anyone but the person who also has the private key.

[paniker]

So...how do use a kangaroo without pub key?  What all of you looking for without it?

How we can recieve a pub key?  try to do all without mistakes

i make a from address 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN a pub 3EE4133D991F52FDF6A25C9834E0745AC74248A4 in hash 160, is it right or or everyone use some online stuff for it?

In case of your example you can't find the pubkey of the address 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN. That's because it is a Pay 2 Public Key Hash address. What you tried to do I guess is a base58 decode of the address. The tool at http://gobittest.appspot.com/Address might be of help to you fur understanding purposes. Just fill in the address in the last field and you will get the values all the way to the RIPEMD-160 of the hash of the private key. But since RIPEMD and SHA are hashing algorithms that will only work in one way there is no way you can calculate the public key.

In case of a P2PKH address the public key becomes known when the address is used for an outgoing transaction. In that case for the unlocking script the public key has to be supplied and it will be checked if it hashes to the correct value. But in your case the address doesn't have any outgoing transactions so the public key is not known to anyone but the person who also has the private key.

[paniker]

How we can recieve a pub key?  try to do all without mistakes

i make a from address 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN a pub 3EE4133D991F52FDF6A25C9834E0745AC74248A4 in hash 160, is it right or or everyone use some online stuff for it?

In case of your example you can't find the pubkey of the address 16jY7qLJnxb7CHZyqBP8qca9d51gAjyXQN. That's because it is a Pay 2 Public Key Hash address. What you tried to do I guess is a base58 decode of the address. The tool at http://gobittest.appspot.com/Address might be of help to you fur understanding purposes. Just fill in the address in the last field and you will get the values all the way to the RIPEMD-160 of the hash of the private key. But since RIPEMD and SHA are hashing algorithms that will only work in one way there is no way you can calculate the public key.

In case of a P2PKH address the public key becomes known when the address is used for an outgoing transaction. In that case for the unlocking script the public key has to be supplied and it will be checked if it hashes to the correct value. But in your case the address doesn't have any outgoing transactions so the public key is not known to anyone but the person who also has the private key.

Another one question:
I open dos in JeanLuc github at kangaroo, and see a data about 64bit, as he wrote there:
"""
Exemple with a 64bit key:

Kangaroo.exe -d 10 -s -w save.work -wsplit -wi 10 ..\VC_CUDA8\in64.txt
"""

I look at info:

Kangaroo v1.6
Start:5B3F38AF935A3640D158E871CE6E9666DB862636383386EE0000000000000000
Stop :5B3F38AF935A3640D158E871CE6E9666DB862636383386EEFFFFFFFFFFFFFFFF

what??)) is it real range or another decoding i need to do or what is it?

[iamfreshfish]

Hello,
I was hoping someone would be kind enough to simplify what the program is doing. What I gathered was that it using the Kangaroo algo which essentially picking 2 random points at set intervals and checking for a collision. I think I started trying to read the start of this thread but was totally lost. I have 1 1080ti that I like to tinker with...have made vanity addresses, messed with Bitcrack for the 32btc puzzle but those were easy to understand. I dont like running things unless I learn something

Also I tried running it but the gpu never really started processing anything and couldnt make heads or tails of the output on the CMD

Any simplified explanation would be greatly appreciated so I can use that to then start learning more and tweaking , etc.

Thanks

[j2002ba2]

So...how do use a kangaroo without pub key?  What all of you looking for without it?

Pollard Kangaroo algorithm needs as input a public key and an interval for private key.

So... you don't use kangaroo without pub key.

One can get a public key from spent transaction, or early P2PK transaction.

[paniker]

So...how do use a kangaroo without pub key?  What all of you looking for without it?

Pollard Kangaroo algorithm needs as input a public key and an interval for private key.

So... you don't use kangaroo without pub key.

One can get a public key from spent transaction, or early P2PK transaction.

ok, how everyone here use kangaroo for 64? just interest, or for 74,77 and etc?

[math09183]

ok, how everyone here use kangaroo for 64? just interest, or for 74,77 and etc?

no pub key - no kangaroo

[COBRAS]

Update.


I was find a interesting site http://safecurves.cr.yp.to/ with interesting info.

Degenerate Fault Attacks on Elliptic Curve
Parameters in OpenSSL

https://eprint.iacr.org/2019/400.pdf

Interesting picture form this PDF:

[gmaxwell]

Jean_Luc,

Could be of interest to you:

https://github.com/bitcoin-core/secp256k1/pull/767

Degenerate Fault Attacks on Elliptic Curve
Parameters in OpenSSL
https://eprint.iacr.org/2019/400.pdf

Not applicable to this thread. It's about fault attacks, where you cause a glitch in a cpu while signing to make it miscompute and leak a key. They demonstrate a particular form of this against several curves.

I don't think their countermeasure advice is all that great.  Sure, storing G as x/y is cheap and stops this particular approach (except in ecdh) so everyone should do that and effectively everything does, but if an attacker can cause skipped instructions there probably are a bunch of other ways to attack.  Better to verify after signing, like bitcoin core does.

[COBRAS]

Jean_Luc,

Could be of interest to you:

https://github.com/bitcoin-core/secp256k1/pull/767

Degenerate Fault Attacks on Elliptic Curve
Parameters in OpenSSL
https://eprint.iacr.org/2019/400.pdf

Not applicable to this thread. It's about fault attacks, where you cause a glitch in a cpu while signing to make it miscompute and leak a key. They demonstrate a particular form of this against several curves.

I don't think their countermeasure advice is all that great.  Sure, storing G as x/y is cheap and stops this particular approach (except in ecdh) so everyone should do that and effectively everything does, but if an attacker can cause skipped instructions there probably are a bunch of other ways to attack.  Better to verify after signing, like bitcoin core does.

operation at line 5 typically fails in that case (either because
the  square  root  algorithm  fails  on  nonquadratic  residues,  or
because the resulting point fails point validation). This implies
that, for example, secp192k1 and secp256k1 are susceptible to
the SCPD attack, but secp224k1 is not.

EDIT wtere are many different attack for ex chnge curve, change random euation of ecps256k1 to linear form, use more faster then ecps256k1.lib math operation realisation etc.

Q. Did someone know how to modify public key(for ex "split publick key") for get smaler byte range of privkey

[gmaxwell]

Yes, I read the entire paper.


For  simplicity,  we  focus  on  the  attack against curves with j-invariant equal to 0 (i.e.,A= 0), but the attack also generalizes to the curves with non zero j-invariant. Indeed,  in  that  case,  the  faulty  curve  becomes  supersingular  according  to  Proposition  1,  and  hence  the  MOV  attack of  Proposition  2  applies


And they give attack costs about other curves. If an attacker can fault your computation, you're pretty screwed regardless of what curve you use unless countermeasures are implemented. I bet in a lot of implementations a well timed fault can cause them to just print the secret key.

Fault attacks remain completely irrelevant to this thread.

[Jean_Luc]

Jean_Luc,

Could be of interest to you:

https://github.com/bitcoin-core/secp256k1/pull/767

Thanks for the reading
It seems they have built a very similar algorithm than my DRS62 modular inversion.
It is clearly faster than the Fermat/Euler method for secp256k1 prime.
Depending on platform, the DRS62 cost is around 150 ModSquare (with ModSquare optimized for secp256k1 prime).

[iamfreshfish]

Sorry I cant add to the discourse but would really appreciate if you guys could help me out
1) Is the kangaroo algo essentially looking for the x,y coordinates on the curve that make up BTC key? All I could gather was that essentially 2 random points are selected and plotted and if an eventual collision occurs you have the key?

2) I tried to run the program with my 1080ti but couldnt make heads or tails of the settings (hence my previous question to try and understand what it all pertains to)...could you help me out with a config that would be adequate for that gpu?

Thanks

[WanderingPhilospher]

Sorry I cant add to the discourse but would really appreciate if you guys could help me out
1) Is the kangaroo algo essentially looking for the x,y coordinates on the curve that make up BTC key? All I could gather was that essentially 2 random points are selected and plotted and if an eventual collision occurs you have the key?

2) I tried to run the program with my 1080ti but couldnt make heads or tails of the settings (hence my previous question to try and understand what it all pertains to)...could you help me out with a config that would be adequate for that gpu?

Thanks

Windows or Linux?

[iamfreshfish]

Running windows, but have a pc I can install Ubuntu on (have the USB ready

[WanderingPhilospher]

Running windows, but have a pc I can install Ubuntu on (have the USB ready

no, I run on Windows as well. Just run the default settings. The program will auto detect your GPUs grid size and will multiply it by 2. So if your grid size is 20x100 the program will auto set it at 40x200.

As far as what's happening

The program uses 2 herds of kangaroos, a tame herd and a wild herd. When 2 kangaroos (a wild one and a tame one) collide, the key can be solved.

Using the distinguished point method...if a wild kangaroo lands on a dp that a tame has already landed on, from that point, the wild will follow same path as tame and yes, the private key will be solved.

All of the setting options are described here:

https://github.com/JeanLucPons/Kangaroo (there are many) but the basic settings could/would be something like:

Kangaroo.exe -t 0 -gpu -gpuId 0 -i inputfile.txt -o outputfile.txt

that's basically saying -t 0 = no cpu threads, -gpu = use gpu, -gpuId 0 = use GPU as 0 index (if you have more you can use -gpuId 0,1,2,3,etc), -i = input file that contains the range you want to search and the pubkey you are searching for, -o = output file that pubkey and private key will be written to.

[iamfreshfish]

 

The program uses 2 herds of kangaroos, a tame herd and a wild herd. When 2 kangaroos (a wild one and a tame one) collide, the key can be solved....

Using the distinguished point method...if a wild kangaroo lands on a dp that a tame has already landed on, from that point, the wild will follow same path as tame and yes, the private key will be solved.

Thanks. So the idea is that the tame herd is a series of numbers that are  increasing in a constant way and the wild herd is variables that are "randomly" moving forward...when a collision occurs, how does that determine the public key?

Also, I did get the prog to run but this is what I get:

Start:7FFFFFF76B48C000
Stop :FFFFFFFFFFFFFFFF
Keys :1
Range width: 2^64
Expected operations: 2^33.05
Expected RAM: 12.3MB
DP size: 20 [0xFFFFF00000000000]
Waring: Server does not support -ws, ignoring
Kangaroo server is ready and listening to TCP port 17403 ...
[Client 0][Kang 2^-inf][DP Count 2^-inf/2^13.05][Dead 0][05:00][2.0/4.0MB]
SaveWork: safe.work1done [2.0 MB] [00s] Sat Jul 25 00:15:34 2020
[Client 0][Kang 2^-inf][DP Count 2^-inf/2^13.05][Dead 0][05:56][2.0/4.0MB]

This output makes no sense to me as its unclear as to how well my GPU is performing. What is "dead" and why am I only using 12MB of expected RAM when I have 11GB?

[WanderingPhilospher]

The program uses 2 herds of kangaroos, a tame herd and a wild herd. When 2 kangaroos (a wild one and a tame one) collide, the key can be solved....

Using the distinguished point method...if a wild kangaroo lands on a dp that a tame has already landed on, from that point, the wild will follow same path as tame and yes, the private key will be solved.

Thanks. So the idea is that the tame herd is a series of numbers that are  increasing in a constant way and the wild herd is variables that are "randomly" moving forward...when a collision occurs, how does that determine the public key?

Also, I did get the prog to run but this is what I get:

Start:7FFFFFF76B48C000
Stop :FFFFFFFFFFFFFFFF
Keys :1
Range width: 2^64
Expected operations: 2^33.05
Expected RAM: 12.3MB
DP size: 20 [0xFFFFF00000000000]
Waring: Server does not support -ws, ignoring
Kangaroo server is ready and listening to TCP port 17403 ...
[Client 0][Kang 2^-inf][DP Count 2^-inf/2^13.05][Dead 0][05:00][2.0/4.0MB]
SaveWork: safe.work1done [2.0 MB] [00s] Sat Jul 25 00:15:34 2020
[Client 0][Kang 2^-inf][DP Count 2^-inf/2^13.05][Dead 0][05:56][2.0/4.0MB]

This output makes no sense to me as its unclear as to how well my GPU is performing. What is "dead" and why am I only using 12MB of expected RAM when I have 11GB?

Looks like you are only running a server mode.  Show me your current config/batch file. Run the example I showed you and don't run as a server. Basically, when you are running server mode, it's just that, a server. It is waiting for a client to connect to it. With one gpu, you do not need to run as server.