Pollard's kangaroo ECDLP solver - page 82.

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: Wouimbly on July 26, 2020, 10:46:05 AM

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.

iamfreshfish

newbie

Activity: 8

Merit: 0

Quote from: WanderingPhilospher on July 26, 2020, 12:10:59 AM

Quote from: iamfreshfish on July 26, 2020, 12:02:51 AM

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.

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

Wouimbly

newbie

Activity: 8

Merit: 0

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 ?

Marynarz

jr. member

Activity: 40

Merit: 2

Hi all

Quote from: Jean_Luc on May 01, 2020, 10:45:30 AM

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

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)

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 !

Jean_Luc, would you please explain to me why Kangaroo v2.1 has a problem finding this key?

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: iamfreshfish on July 26, 2020, 12:02:51 AM

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.

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

iamfreshfish

newbie

Activity: 8

Merit: 0

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?

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

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

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: iamfreshfish on July 24, 2020, 03:18:24 PM

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.

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]

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.

iamfreshfish

newbie

Activity: 8

Merit: 0

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.

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]

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

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: iamfreshfish on July 23, 2020, 03:54:19 PM

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.

iamfreshfish

newbie

Activity: 8

Merit: 0

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

WanderingPhilospher

full member

Activity: 1162

Merit: 237

Shooters Shoot...

Quote from: iamfreshfish on July 23, 2020, 07:11:40 AM

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

newbie

Activity: 8

Merit: 0

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

Jean_Luc

sr. member

Activity: 462

Merit: 701

Quote from: gmaxwell on July 21, 2020, 05:10:39 AM

Jean_Luc,

Could be of interest to you:

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

Thanks for the reading Wink

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

gmaxwell

staff

Activity: 4284

Merit: 8808

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.

COBRAS

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

Quote from: gmaxwell on July 21, 2020, 05:10:39 AM

Jean_Luc,

Could be of interest to you:

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

Quote from: COBRAS on July 20, 2020, 08:49:37 PM

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 Huh

gmaxwell

staff

Activity: 4284

Merit: 8808

Jean_Luc,

Could be of interest to you:

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

Quote from: COBRAS on July 20, 2020, 08:49:37 PM

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

member

Activity: 873

Merit: 22

$$P2P BTC BRUTE.JOIN NOW ! https://uclck.me/SQPJk

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:

math09183

member

Activity: 170

Merit: 58

Quote from: paniker on July 20, 2020, 04:06:44 AM

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

no pub key - no kangaroo

paniker

newbie

Activity: 49

Merit: 0

Quote from: j2002ba2 on July 20, 2020, 03:44:01 AM

Quote from: paniker on July 20, 2020, 01:55:14 AM

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?

Topic: Pollard's kangaroo ECDLP solver - page 82. (Read 59490 times)