Exetools  

Go Back   Exetools > General > General Discussion

Notices

Reply
 
Thread Tools Display Modes
  #31  
Old 09-25-2017, 22:17
jump jump is offline
VIP
 
Join Date: Jan 2009
Posts: 305
Rept. Given: 84
Rept. Rcvd 51 Times in 26 Posts
Thanks Given: 22
Thanks Rcvd at 41 Times in 27 Posts
jump Reputation: 51
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
Reply With Quote
  #32  
Old 09-25-2017, 23:28
cachito cachito is offline
Friend
 
Join Date: Aug 2015
Location: argentina
Posts: 58
Rept. Given: 0
Rept. Rcvd 12 Times in 8 Posts
Thanks Given: 162
Thanks Rcvd at 81 Times in 44 Posts
cachito Reputation: 13
@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...
Reply With Quote
  #33  
Old 09-27-2017, 10:50
azsd azsd is offline
Friend
 
Join Date: Aug 2003
Location: xinyang
Posts: 26
Rept. Given: 2
Rept. Rcvd 0 Times in 0 Posts
Thanks Given: 0
Thanks Rcvd at 0 Times in 0 Posts
azsd Reputation: 0
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
Reply With Quote
  #34  
Old 09-27-2017, 18:10
contextrax contextrax is offline
Friend
 
Join Date: Aug 2017
Posts: 43
Rept. Given: 0
Rept. Rcvd 17 Times in 7 Posts
Thanks Given: 4
Thanks Rcvd at 72 Times in 19 Posts
contextrax Reputation: 17
Quote:
Originally Posted by jump View Post
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.

Last edited by contextrax; 09-27-2017 at 18:20.
Reply With Quote
  #35  
Old 09-27-2017, 18:26
contextrax contextrax is offline
Friend
 
Join Date: Aug 2017
Posts: 43
Rept. Given: 0
Rept. Rcvd 17 Times in 7 Posts
Thanks Given: 4
Thanks Rcvd at 72 Times in 19 Posts
contextrax Reputation: 17
Quote:
Originally Posted by cachito View Post
@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.
Reply With Quote
  #36  
Old 10-02-2017, 18:55
jump jump is offline
VIP
 
Join Date: Jan 2009
Posts: 305
Rept. Given: 84
Rept. Rcvd 51 Times in 26 Posts
Thanks Given: 22
Thanks Rcvd at 41 Times in 27 Posts
jump Reputation: 51
Quote:
Originally Posted by contextrax View Post
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.
Reply With Quote
  #37  
Old 10-03-2017, 16:26
contextrax contextrax is offline
Friend
 
Join Date: Aug 2017
Posts: 43
Rept. Given: 0
Rept. Rcvd 17 Times in 7 Posts
Thanks Given: 4
Thanks Rcvd at 72 Times in 19 Posts
contextrax Reputation: 17
Quote:
Originally Posted by jump View Post
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.
Reply With Quote
  #38  
Old 10-03-2017, 17:34
jump jump is offline
VIP
 
Join Date: Jan 2009
Posts: 305
Rept. Given: 84
Rept. Rcvd 51 Times in 26 Posts
Thanks Given: 22
Thanks Rcvd at 41 Times in 27 Posts
jump Reputation: 51
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

Last edited by jump; 10-05-2017 at 18:31. Reason: delete email
Reply With Quote
  #39  
Old 10-29-2017, 17:16
Abaddon Abaddon is offline
Friend
 
Join Date: May 2016
Posts: 43
Rept. Given: 0
Rept. Rcvd 3 Times in 3 Posts
Thanks Given: 181
Thanks Rcvd at 45 Times in 25 Posts
Abaddon Reputation: 3
Sorry to bump. Any progress with the project? A pure keygen would be a nice epitaph for this once popular protector.
Reply With Quote
  #40  
Old 10-30-2017, 17:19
Kerlingen Kerlingen is offline
VIP
 
Join Date: Feb 2011
Posts: 324
Rept. Given: 0
Rept. Rcvd 276 Times in 98 Posts
Thanks Given: 0
Thanks Rcvd at 308 Times in 95 Posts
Kerlingen Reputation: 200-299 Kerlingen Reputation: 200-299 Kerlingen Reputation: 200-299
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.
Reply With Quote
The Following 2 Users Say Thank You to Kerlingen For This Useful Post:
Abaddon (10-31-2017), TechLord (10-30-2017)
  #41  
Old 10-30-2017, 17:33
contextrax contextrax is offline
Friend
 
Join Date: Aug 2017
Posts: 43
Rept. Given: 0
Rept. Rcvd 17 Times in 7 Posts
Thanks Given: 4
Thanks Rcvd at 72 Times in 19 Posts
contextrax Reputation: 17
Quote:
Originally Posted by Abaddon View Post
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.
Reply With Quote
The Following User Gave Reputation+1 to contextrax For This Useful Post:
mr.exodia (10-31-2017)
The Following 3 Users Say Thank You to contextrax For This Useful Post:
Abaddon (10-31-2017), Apuromafo (03-04-2019), TechLord (10-30-2017)
  #42  
Old 10-30-2017, 18:16
contextrax contextrax is offline
Friend
 
Join Date: Aug 2017
Posts: 43
Rept. Given: 0
Rept. Rcvd 17 Times in 7 Posts
Thanks Given: 4
Thanks Rcvd at 72 Times in 19 Posts
contextrax Reputation: 17
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().
Reply With Quote
The Following 2 Users Say Thank You to contextrax For This Useful Post:
Abaddon (10-31-2017), TechLord (10-30-2017)
  #43  
Old 10-30-2017, 19:54
SKiLLa SKiLLa is offline
Friend
 
Join Date: Jul 2016
Location: Europe
Posts: 27
Rept. Given: 0
Rept. Rcvd 0 Times in 0 Posts
Thanks Given: 17
Thanks Rcvd at 16 Times in 15 Posts
SKiLLa Reputation: 0
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 ?
Reply With Quote
  #44  
Old 10-30-2017, 21:36
contextrax contextrax is offline
Friend
 
Join Date: Aug 2017
Posts: 43
Rept. Given: 0
Rept. Rcvd 17 Times in 7 Posts
Thanks Given: 4
Thanks Rcvd at 72 Times in 19 Posts
contextrax Reputation: 17
Quote:
Originally Posted by SKiLLa View Post
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.
Reply With Quote
  #45  
Old 10-30-2017, 23:33
SKiLLa SKiLLa is offline
Friend
 
Join Date: Jul 2016
Location: Europe
Posts: 27
Rept. Given: 0
Rept. Rcvd 0 Times in 0 Posts
Thanks Given: 17
Thanks Rcvd at 16 Times in 15 Posts
SKiLLa Reputation: 0
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 ...
Reply With Quote
Reply

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Replacing ECDSA in Target (arma) Mynotos General Discussion 3 11-22-2019 00:49


All times are GMT +8. The time now is 16:09.


Always Your Best Friend: Aaron, JMI, ahmadmansoor, ZeNiX, chessgod101
( 1998 - 2024 )