Hello,
Regarding https://bitcointalksearch.org/topic/solving-wif-in-a-hybrid-mode-5265788, would it be possible to modify kangaroos to work on sparse range?
I would like to launch search on range [a0, ..., ai, ..., aN], where ai = a0+(i*s), with stride 's'.
As I understand now program 'scales down' range to 0->aN', with a corresponding changes on pubkey, right?
Regards,
Topic: Pollard's kangaroo ECDLP solver - page 81. (Read 58567 times)
Hi! Just wonder what is the impact of searching multiple pubkey at once ?
Does the key are search one by one or all at once ?
If you have more than one pubkey in your input file, the program searches one by one. If you don't use the -m option, the program could search for the first pubkey forever. Does the key are search one by one or all at once ?
Ok, still trying to wrap my head around the concept 
But getting there. Hats to those of you here who understand all this
So I got it to run.
1080ti on Windows
Bat file >> Kangaroo.exe -t 0 -gpu -gpuId 0 -ws -w save.work -wi 30 input.txt
Starts off at 200Mkeys/s and then continuously drops
Also why does this algo seem to only work for bit ranges that are multiples of 5?
Glad you finally got it to work. But getting there. Hats to those of you here who understand all thisSo I got it to run.
1080ti on Windows
Bat file >> Kangaroo.exe -t 0 -gpu -gpuId 0 -ws -w save.work -wi 30 input.txt
Starts off at 200Mkeys/s and then continuously drops
Also why does this algo seem to only work for bit ranges that are multiples of 5?
Now that you finally got rid of the server command, you can play around with the grid size numbers for your gpu, up to you.
The MKey/s drop but shouldn't be that much. I have had 1070s that maintain above 200 MKey/s.
I do not know what you mean by multiples of 5...if you are referring to the puzzle, that's because every 5th address in the puzzle has the pubkeys exposed. This program works by only knowing the pubkey. But the program will work for any range, any "multiple".
Yeah it was weird but I was running out of space...was gobbling up RAM and I'm assuming pagefile as well but when I moved the app to a separate drive it is now running at 500Mkeys/s
As for the "every 5th" I now understand that this algo requires the public key and the other BTC puzzle programs just brute force all the private key options in a range
Hi! Just wonder what is the impact of searching multiple pubkey at once ?
Does the key are search one by one or all at once ?
Does the key are search one by one or all at once ?
Hi all
Jean_Luc, would you please explain to me why Kangaroo v2.1 has a problem finding this key?
Yes From time to time it fails and go out the range. The number of dead kangaroo (collision in same herd) increase.
The idea of replaying walk is good, I do like this in my BTCCollider.
Here is an output on 30 trials.
The final private key is not reconstructed here, you need to add (mod n) start range + N/2
The idea of replaying walk is good, I do like this in my BTCCollider.
Here is an output on 30 trials.
The final private key is not reconstructed here, you need to add (mod n) start range + N/2
Code:
Kangaroo v1.3
Start:62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004A0000000000
Stop :62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004AFFFFFFFFFF
Keys :1000
Number of CPU thread: 2
Range width: 2^40
Jump Avg distance: 2^20.00
Number of kangaroos: 2^11.00
Suggested DP: 8
Expected operations: 2^21.15
Expected RAM: 6.5MB
DP size: 5 [0xF800000000000000]
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos
Key# 0 S3Pub: 0x03C88A1817454E1B49AEEF4D22DB60CD1FFF0513DECC2AFC52219C28C99CFE36A1
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E3E9F06D632
[ 0] 2^21.709 Dead:4 Avg:2^21.709 (2^21.148)
Start:62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004A0000000000
Stop :62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004AFFFFFFFFFF
Keys :1000
Number of CPU thread: 2
Range width: 2^40
Jump Avg distance: 2^20.00
Number of kangaroos: 2^11.00
Suggested DP: 8
Expected operations: 2^21.15
Expected RAM: 6.5MB
DP size: 5 [0xF800000000000000]
SolveKeyCPU Thread 0: 1024 kangaroos
SolveKeyCPU Thread 1: 1024 kangaroos
Key# 0 S3Pub: 0x03C88A1817454E1B49AEEF4D22DB60CD1FFF0513DECC2AFC52219C28C99CFE36A1
Priv: 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E3E9F06D632
[ 0] 2^21.709 Dead:4 Avg:2^21.709 (2^21.148)
Code:
Kangaroo.exe -t 0 -d 11 -m 3.0 -gpu -g 80,256,80,256 -gpuId 0,1 -o found.txt in.txt
Kangaroo v2.1
Start:62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004A0000000000
Stop :62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004AFFFFFFFFFF
Keys :293566
Number of CPU thread: 0
Range width: 2^40
Jump Avg distance: 2^19.97
Number of kangaroos: 2^22.32
Suggested DP: 0
Expected operations: 2^25.49
Expected RAM: 12.9MB
DP size: 11 [0xFFE0000000000000]
GPU: GPU #0 GeForce GTX 1060 6GB (10x128 cores) Grid(80x256) (207.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
GPU: GPU #1 GeForce GTX 1060 6GB (10x128 cores) Grid(80x256) (207.0 MB used)
SolveKeyGPU Thread GPU#1: creating kangaroos...
SolveKeyGPU Thread GPU#1: 2^21.32 kangaroos [12.9s]
SolveKeyGPU Thread GPU#0: 2^21.32 kangaroos [12.9s]
[185.39 MK/s][GPU 185.39 MK/s][Count 2^28.49][Dead 204][02s (Avg 00s)][6.4/21.9M
B]
Key# 0 [XX]Pub: 0x03C88A1817454E1B49AEEF4D22DB60CD1FFF0513DECC2AFC52219C28C99CF
E36A1
Aborted !
Kangaroo v2.1
Start:62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004A0000000000
Stop :62CE27C8FED90758A834C2CB6E3F19BC8A0B5E7D92C0FC0F57004AFFFFFFFFFF
Keys :293566
Number of CPU thread: 0
Range width: 2^40
Jump Avg distance: 2^19.97
Number of kangaroos: 2^22.32
Suggested DP: 0
Expected operations: 2^25.49
Expected RAM: 12.9MB
DP size: 11 [0xFFE0000000000000]
GPU: GPU #0 GeForce GTX 1060 6GB (10x128 cores) Grid(80x256) (207.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
GPU: GPU #1 GeForce GTX 1060 6GB (10x128 cores) Grid(80x256) (207.0 MB used)
SolveKeyGPU Thread GPU#1: creating kangaroos...
SolveKeyGPU Thread GPU#1: 2^21.32 kangaroos [12.9s]
SolveKeyGPU Thread GPU#0: 2^21.32 kangaroos [12.9s]
[185.39 MK/s][GPU 185.39 MK/s][Count 2^28.49][Dead 204][02s (Avg 00s)][6.4/21.9M
B]
Key# 0 [XX]Pub: 0x03C88A1817454E1B49AEEF4D22DB60CD1FFF0513DECC2AFC52219C28C99CF
E36A1
Aborted !
Jean_Luc, would you please explain to me why Kangaroo v2.1 has a problem finding this key?
Ok, still trying to wrap my head around the concept But getting there. Hats to those of you here who understand all this
So I got it to run.
1080ti on Windows
Bat file >> Kangaroo.exe -t 0 -gpu -gpuId 0 -ws -w save.work -wi 30 input.txt
Starts off at 200Mkeys/s and then continuously drops
Also why does this algo seem to only work for bit ranges that are multiples of 5?
Glad you finally got it to work. But getting there. Hats to those of you here who understand all thisSo I got it to run.
1080ti on Windows
Bat file >> Kangaroo.exe -t 0 -gpu -gpuId 0 -ws -w save.work -wi 30 input.txt
Starts off at 200Mkeys/s and then continuously drops
Also why does this algo seem to only work for bit ranges that are multiples of 5?
Now that you finally got rid of the server command, you can play around with the grid size numbers for your gpu, up to you.
The MKey/s drop but shouldn't be that much. I have had 1070s that maintain above 200 MKey/s.
I do not know what you mean by multiples of 5...if you are referring to the puzzle, that's because every 5th address in the puzzle has the pubkeys exposed. This program works by only knowing the pubkey. But the program will work for any range, any "multiple".
Ok, still trying to wrap my head around the concept But getting there. Hats to those of you here who understand all this
So I got it to run.
1080ti on Windows
Bat file >> Kangaroo.exe -t 0 -gpu -gpuId 0 -ws -w save.work -wi 30 input.txt
Starts off at 200Mkeys/s and then continuously drops
Also why does this algo seem to only work for bit ranges that are multiples of 5?
But getting there. Hats to those of you here who understand all thisSo I got it to run.
1080ti on Windows
Bat file >> Kangaroo.exe -t 0 -gpu -gpuId 0 -ws -w save.work -wi 30 input.txt
Starts off at 200Mkeys/s and then continuously drops
Also why does this algo seem to only work for bit ranges that are multiples of 5?
Quote
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?
This is not exact, but will give you an example. The tame herd starts at random points, let's say at the middle of the range, then they make jumps. When they land on a dp, it's recorded. The wild herd starts at random points and they make jumps, but they normally start in a range behind the tame herd. If they land on a dp, it's recorded. Quote
We have to solve P = k.G, P is the public key, we know that k lies in the range [k1,k2], G is the SecpK1 generator point.
(Tame,Wild) = Collision
k = k1 + Tame.dist - Wild.dist
(Tame,Wild) = Collision
k = k1 + Tame.dist - Wild.dist
Quote
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.
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:
Quote
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]
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?
Quote
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.
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:
Quote
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]
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?
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
Quote
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.
Running windows, but have a pc I can install Ubuntu on (have the USB ready
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? 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
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
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
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).
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.
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,
Could be of interest to you:
https://github.com/bitcoin-core/secp256k1/pull/767
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.
Could be of interest to you:
https://github.com/bitcoin-core/secp256k1/pull/767
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
Jean_Luc,
Could be of interest to you:
https://github.com/bitcoin-core/secp256k1/pull/767
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.
Could be of interest to you:
https://github.com/bitcoin-core/secp256k1/pull/767
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.
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:
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:
ok, how everyone here use kangaroo for 64? just interest, or for 74,77 and etc?
no pub key - no kangaroo
Jump to: