Armadillo ECDSA-113
 

Hi
A month ago I launched my first attack on a armadillo protected target that was using level 10 armadillo license system (ECDSA)

Level10 is ECDSA-113 which of course is using Elliptic Curve.
The curve size is 113 bit and the order of the public point is 112 bit.
Order: "5192296858534827627896703833467507"

The curve is a koblitz curve and the base is usually Optimal Normal Base Type 2 which is very slow when implemented in software. (Well. I was not able to speed it up to much)

To solve the ecdlp on such a curve I first thought that the number of iteration needed would be ~sqrt(2^112) == 2^56 but for the koblitz curve there are speedups.

First speedup would be using the frobenius map and second would be using negation map.
For this one can expect a speedup of ~sqrt(113*2) and this brings us to a total number of iteration ~2^52
For the slow ONB2 curve this woule be too much (I think) but now the fun starts.
There exist a isomorphic base (or there are many of them) but the fastest I could find is the polynomial base with the irreducible polynom x^113 + x^9 +1.
Going from ONB2 to polynomial base was a bit pain at first but when you know what to do it's pretty easy.

Also in 2010 intel introduced the CLMUL instruction that can do carry less multiplication (polynomial multiplication) in ASM and reducing modulo x^113 + x^9 +1 is pretty fast when using xmm registers.

So the speed of the first solver I tested using the ONB2 code was about 20.000 iterations/sec.
The one I ended up running did 46.000.000 iterations/sec running on a Core i7 CPU with 8 threads.
My total combined speed was about 600mill/sec and after 2^50 iterations I solved ECDLP for this curve/target.

I guess armadillo is not to much used any more so I guess all this was a bit to late. Or perhaps others have done this before me? I don't know.

But if anyone know of a good/cool target using this protection it would be fun to try again.

If any questions then just shoot.

So... It effectively took three weeks to solve?

Very interesting! I could integrate this in my Armadillo Key Tool (https://github.com/mrexodia/akt)...

The previous attack (as far as I know) was on a weak implementation by Baboon (http://baboon.rce.free.fr/index.php?post/2010/09/04/Armadillo-mange-des-ours-en-slips) but I don't think a brute force approach was tested in public.

You can get the best target by making your own unpackme, or try Armadillo itself...

The latest public (and custom) v9.60 uses:

Feel free to ping me if you need something...

Lets say four weeks but I think I was lucky this time only needed 2^50 iterations. (or lets say extremely lucky)
ECDLP is based on the birthday paradox so you never know exactly the among of work.
2^52 iterations would required 4 times more work.

I would not find it to interested breaking my own ecc parameters :)

This is the real ecc parameters for armadillo itself?
I thought armadillo was obsolete

Would anyone be interested in running an attack on say armadillo?
This require running the solver on their pc and collect distinguished points.
More CPU's will give faster result.

Also if anyone are familiar with GPU coding them perhaps this could also be implemented and run on gfx cards.

I'd say Armadillo is still secure enough then. Who's paying the electricity bill for your little experiment? ;)

My total speed of 600mill/sec was spred over ~20 different computers including friends and family.
The power consummation on todays cpu is not that bad. My laptop Core i7 has a max TDP of 15w.

Lets play with some numbers.
My fastest PC did 46mill/sec. (a Core i7-6700 @ 3.4GHz)
Say we as a group can collect 90 of them
That should give a speed of ~2^32 / sec
After 12 days we would reach 2^52 iterations.
If we are as lucky as I and solve after 2^50 iterations then this would take only ~3 days :)

Some other attacked this curve before I did and implemented it on FPGS's
https://eprint.iacr.org/2014/368.pdf

If I where to release a product today then I would not rely on a 113 bit's koblitz curve. Using a different 113 bits curve would be a bit better and perhaps out of reach for reversers today but new cpu's are hitting the market as we speak and the new inlet with 18 cores and amd with 16 corse will probably be speed monsters.
Would also be fun to try implementing this on GPU.
I know they did some research on this when attacking ecc2k-131.

Damn your tool roxx. I spend countless of hrs extracting the crypto params that your tool can do with just one click :)
Love it.

(Hope I wont get banned for this reply)

Point taken. I ran the numbers again and the power costs s̶h̶o̶u̶l̶d̶ could be well below the cost of a license for whatever software it is you're attacking.

It's not always about the monetary costs...

I think a true keygen for v9.6 would be a fitting end to the Armadillo saga.

When hashing GPU is 100x over CPU, +/- depending of the kind of hash.
I can test in a 3 GPU computer if someone programs that option.
Good luck with this experiment, it is really interesting :)

I can't find the latest armadillo version so if anyone can share that would be great.

You're talking about 90 CPUs. Keygenning a single software (if you own that amount of hardware) will cost you like 1000+ US-$ for energy alone, if you have to rent cloud computing you will be at 5000+ US-$.

I was thinking more of a joined attack. 90 cpu's is like 90 different people running the solver.

https://transfer.sh/nO14Y/softwarepassport32.exe

I see there are many more of these certs in Armadillo. Did you verify that this is the correct ones to break?

I calculated the base point from basepoint init using the armadillo keygen source "KeyMakerV420j.c".
Don't know if this is the latest code so if you could check and see if they matches yours.

And here they are in polynomial base if anyone wants to play with them

Yeah that cert is the one that matches my key. You can quite easily verify by using the ECDSA_Replace plugin for the inline tab in akt and replace this cert with your own. Keys without any extrainfo should then be accepted.

if someone will code GPU solution I might try it on the most advanced GPU nowadays - Nvidia P100

If you want a target, here is one: VideoReDo (using Armadillo v9.66).

I started solving ecdlp for armadillo. If anyone want to participate then send me a pm and I will give you a download link to the solver with some instructions.
The solver runs on CPU only atm. (No GFX card support yet)

I want to participate. btw, your pm is not allowed to receive.

I posted a link to the solver in the Reversing Software section.
Look for ECC Solver

no linux version?

Some of my friends are running it on linux using wine. This works great.
I don't know to much on how to code on linux so I would need some one to do it for me. I was planing on sharing the core code for the solver so anyone interested in this stuff can play with it.
The core code should be pretty easy converting to linux. It is coded in C using intrinsics for the XMM code.
Rest of the solver using multi threading and windows api for server communication and will probably need more work to convert.

A new version of the solver is posted in the Reversing Software section.
The new version is a bit faster and will also let you get some server statistics on how many points are collected and how many clients are running.
I see more and more clients is joining over time. It was a slow start but speed is picking up.

Is the curve solved? The server is down since more than 12 hours and if my last calculations are correct we would have tested 30-35% of the possible curves until now.

Server is back up again now. Had some problem with my provider.
We have now computed like 2^50 iterations and my last ECDLP solved after this many iterations.
But average iteration needed to solve this curve should be 2^52.
If we are lucky we should find a solution pretty soon :)
I will start checking for a collision daily next week.

any ideas when GPU support will be added up?

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

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

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

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.

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.

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.

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

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

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.