Armadillo ECDSA113
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 ECDSA113 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.
