Armadillo ECDSA-113

[jump]

Hello,

I have added my computer (speed ~36.000.000) and one of my server(~45.000.000) to help you with recovering Arma ecc. I see there is not so much contributors now so each machine is counted .
May I know if I can use your solver to solve ecc for other Armadillo protected sw? "Video-Re-Do" is the sw for what I want to make working key without patching.

Currently I can only solve Short V3 Level1 and use generated key as trial key after patch the application to accept REGISTER. To be able generate valid key I need to solve Short V3 Level10.

--
Jump

[cachito]

@contextrax
If your share source code maybe someone can add GPU support.
If someone do it then it is a matter of hours instead of days...

[azsd]

sounds interesting.
I have bruteforced an Short V3 Level 3 in less than one day using akt.
but failed to generate new key because akt have some bug which oth2 input box which only accept 4 digital input

[contextrax]

Originally Posted by jump

Hello,

I have added my computer (speed ~36.000.000) and one of my server(~45.000.000) to help you with recovering Arma ecc. I see there is not so much contributors now so each machine is counted .
May I know if I can use your solver to solve ecc for other Armadillo protected sw? "Video-Re-Do" is the sw for what I want to make working key without patching.

Currently I can only solve Short V3 Level1 and use generated key as trial key after patch the application to accept REGISTER. To be able generate valid key I need to solve Short V3 Level10.

--
Jump

The solver is hard coded to use the armadillo crypto params so I need to make a new version with the crypto params for the new target.
But it would take you like 1.7 years to solve with your two computers.

To calculate running time you can take 2^52 / (speed*3600*24) = ~number of days.

The algorithm used is Pollards Rho and it's based on the birthday paradox (luck)
you might solve faster or slower depends on how lucky you are.

(oh and it's 2^52 coz the frobenius and negation map is used. Without this it would be ~2^56)

As far as I can remember it's only the ECC keys that will need this much computer power to solve.
All other keys are based on DLP over a prime field (using ElGamal if I remember) and can be solved using sub exponential algo like Index Calculus.

[contextrax]

Originally Posted by cachito

@contextrax
If your share source code maybe someone can add GPU support.
If someone do it then it is a matter of hours instead of days...

I don't think it is that much faster on GPU but it would be fun to see a GPU implementation.
I don't know GPU coding so I would need some one to do it for me.
I can extract the core code for my solver and share it so others can have a look.
Need some time to clean it up and write some comments to it.

[jump]

Originally Posted by contextrax

The solver is hard coded to use the armadillo crypto params so I need to make a new version with the crypto params for the new target.
But it would take you like 1.7 years to solve with your two computers.

To calculate running time you can take 2^52 / (speed*3600*24) = ~number of days.

The algorithm used is Pollards Rho and it's based on the birthday paradox (luck)
you might solve faster or slower depends on how lucky you are.

(oh and it's 2^52 coz the frobenius and negation map is used. Without this it would be ~2^56)

As far as I can remember it's only the ECC keys that will need this much computer power to solve.
All other keys are based on DLP over a prime field (using ElGamal if I remember) and can be solved using sub exponential algo like Index Calculus.

It is ok, I have available more servers. I just participate on your project with two machines. Also I can get other friend machines so I will get nearly your computing power without problem. But you will have to make public also the server part of your solver to be able collect data centrally.

[contextrax]

Originally Posted by jump

It is ok, I have available more servers. I just participate on your project with two machines. Also I can get other friend machines so I will get nearly your computing power without problem. But you will have to make public also the server part of your solver to be able collect data centrally.

I can provide you with what you need to set it all up but I don't want to share my source code for the solver for various reasons.
Is there a way we can get in contact outside this forum?

Also if you could extract the correct crypto params from the target that will give you registration so I can make a solver for you.

[jump]

I respect that you dont want to share the source. If you want contact me here: privateemail and we can discuss it more. Of course, I can send you crypto params.

Thanks

--
Jump

[Abaddon]

Sorry to bump. Any progress with the project? A pure keygen would be a nice epitaph for this once popular protector.

[Kerlingen]

We should have something around 65-70% of the possible keys. If more people join it will go faster, else it might take 4-6 additional weeks.

[contextrax]

Originally Posted by Abaddon

Sorry to bump. Any progress with the project? A pure keygen would be a nice epitaph for this once popular protector.

We have now collected 4.6 million ecc points (expected 6.5 million) which give above 2^51 number of iterations.
I was expecting 2^52 number of iteration to solve but this is based on luck.
The exact number of iterations today is: 0xAD87E`3B2BA1AE

The order of the fixed point on this curve is 2^112 bit and usually to solve we need above sqrt(2^112) number of iterations. That is 2^56.
Because of the frobenius and the negation map we get a speedup of sqrt(113*2) which gives around 2^52.

If anyone wonder why we need ~6.5 million points to solve then that is something i chose when I selected the properties on the distinguished point.
The properties is actually the hamming weight of the ecc points x coordinate in normal base.
If the number of bits is 25 we have a distinguished point. If I have selected a lower bit count we would have needed less points but also needed more iterations to find one. If I have selected a higher bit count we would have needed more points but less iterations to find one.
To many of them would flood my server and increased the offline work load. To few and we might need to search more and the chances of solving drops.
If my calculations are correct then with 25 bit prop I will need about 25gig of RAM on my offline server to solve. On this server I have 32 gig RAM.
If this blow then I need to find a server with more RAM of recode my offline solver to solve on disk and not load everything to memory.


The birthday paradox is explained on this page: https://en.wikipedia.org/wiki/Birthday_problem

And we can see here that the group is 365 and that sqrt(365) is ~19.
To have a 50% chance of solving (find a collision) we need 23 people which is above 19. With 19 we have like a 40% changes of collision.

So since we are a bit below sqrt(2^52) I would guess we are in the area of
25% chance of solving.
That table also shows that that chances of solving increases rapidly the more points we get.

But also you can see that to be 100% sure of solving we need like 365 people which gives us 2^112 iterations. Of course that is the worst worst case scenario and will probably never happen.

These algorithms based on luck is a bitch

Oh and my last attack on this curve (different target) I solved with only 1.5 million points. I guess I was extremely lucky.

Sorry for explaining the obvious but there might be some that is not to familiar with solving DLP / ECDLP.

[contextrax]

Since I use the negation map then one might end up in fruitless cycles.
My solver will try to detect them if they are small (max 256 points) and restart the current worm. But if they are more that 256 points the solver wont detect them.
These fruitless cycles will not give us anything and will only use cpu and reduce speed.
On my solver I print out some info in the status bar. You will see something like this:
LowDCnt: 146 (1/2048) W:123 T:5000

The LowDCnt is the lowest distinguished point count from any worm.
The (1/2048) is how many worms that have this count and the W:123 is which worm that have this count. T:5000 is the time used on the worm with the lowest count but will be restarted if the solver is stoped etc.

Now say that W:123 will go into a fruitless cycle then the LowDCnt will stay at 146 for all time and this is bad.
What I do from time to time is take a screen shot of the solver and after some days I compare the screen shot with the solver. If W:123 is the same and LowDCnt is unchanged I restart the worm. I have not encounter this yet but perhaps all of you running can do the same check.
Now if you see this then I would really like to get a copy of your save state file and you should also now stop the solver and delete the savestate and restart. That is the easy way to get out of a fruitless cycle.

If you wonder what a worm is then because of the cost of a field inversion I used the Montgomery trick to reduce them. To do so I have to split the work so that I can update many points at the same time. This is where name name worm comes from.
On a dual core HT cpu you will see 1024 worms and on a quad core HT you will see 2048 and so on. So on a quad core 2048 points (worms) are updated simultaneously to get the max speed. When a point is updated (a new point is found) then you can look at it as if it's crawling around if the group and when two of these worms collide we have a solution. Of course they need to crawl to the nearest distinguished point but they will both follow the same path when they collide coz of the random walk function f().

[SKiLLa]

Joined the club; the solver seems pretty effective with my 8 logical cores @ ~99% (~45M iterations/s) utilization and it's not even frying my machine

One quick question/suggestion: I'm using v1.42, which seems to be the latest/current one; but is there (or shouldn't there be) an update-notification within the solver itself, to ensure we're all on the same page ?

[contextrax]

Originally Posted by SKiLLa

Joined the club; the solver seems pretty effective with my 8 logical cores @ ~99% (~45M iterations/s) utilization and it's not even frying my machine

One quick question/suggestion: I'm using v1.42, which seems to be the latest/current one; but is there (or shouldn't there be) an update-notification within the solver itself, to ensure we're all on the same page ?

What do you mean by an update notification?
If or when we solve I will inform everyone using this thread that we are done and can stop the solver.
I will also inform this in the server msg you see when you get the server statistics.

Or did you think of something else?

-

All of the solver ecc threads is started with IDLE priority only. This is done so you should be able to use your pc while it's running.

[SKiLLa]

No I simply meant an update to the solver .exe it self
I get that the status and data itself will be updated through the Server-stats.

For example if you would encounter a bug (i.e. want to push a fix) or have some improved attack algorithm.

Ofcourse for this specific EC-113 Arma curve it's not very likely (since most crunching already has been done); but perhaps for a future version attacking a different curve or using different (non Arma) Crypto-constraints. ECC is everywhere nowadays, so I can imagine another iteration some day ...