EXETOOLS FORUM  

Go Back   EXETOOLS FORUM > General > General Discussion

Notices

Reply
 
Thread Tools Display Modes
  #1  
Old 08-17-2017, 23:15
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 66 Times in 18 Posts
contextrax Reputation: 17
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.
Reply With Quote
The Following 3 Users Gave Reputation+1 to contextrax For This Useful Post:
deepzero (08-18-2017), nulli (08-22-2017), tonyweb (08-26-2017)
The Following 11 Users Say Thank You to contextrax For This Useful Post:
alekine322 (08-18-2017), cachito (09-25-2017), deepzero (08-18-2017), elephant (08-22-2017), jump (08-22-2017), niculaita (08-17-2017), nulli (08-22-2017), sendersu (08-18-2017), tonyweb (08-26-2017), WaSt3d_ByTes (08-18-2017), WRP (08-18-2017)
  #2  
Old 08-18-2017, 02:42
tofu-sensei tofu-sensei is offline
Friend
 
Join Date: Jul 2004
Posts: 108
Rept. Given: 1
Rept. Rcvd 14 Times in 8 Posts
Thanks Given: 1
Thanks Rcvd at 7 Times in 3 Posts
tofu-sensei Reputation: 14
So... It effectively took three weeks to solve?
Reply With Quote
  #3  
Old 08-18-2017, 03:30
UniSoft's Avatar
UniSoft UniSoft is offline
Family
 
Join Date: May 2010
Location: Shenzhen, China
Posts: 80
Rept. Given: 21
Rept. Rcvd 245 Times in 34 Posts
Thanks Given: 14
Thanks Rcvd at 159 Times in 33 Posts
UniSoft Reputation: 200-299 UniSoft Reputation: 200-299 UniSoft Reputation: 200-299
Quote:
Originally Posted by contextrax View Post
But if anyone know of a good/cool target using this protection
Visual Assist X 10.9.2231.0
Reply With Quote
  #4  
Old 08-18-2017, 05:09
mr.exodia's Avatar
mr.exodia mr.exodia is offline
Super Moderator
 
Join Date: Nov 2011
Posts: 845
Rept. Given: 496
Rept. Rcvd 1,154 Times in 308 Posts
Thanks Given: 91
Thanks Rcvd at 526 Times in 201 Posts
mr.exodia Reputation: 1100-1299 mr.exodia Reputation: 1100-1299 mr.exodia Reputation: 1100-1299 mr.exodia Reputation: 1100-1299 mr.exodia Reputation: 1100-1299 mr.exodia Reputation: 1100-1299 mr.exodia Reputation: 1100-1299 mr.exodia Reputation: 1100-1299 mr.exodia Reputation: 1100-1299
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:

Code:
  Short V3 Level 10:
    Chk : B5EC5364
    Sym: BDA4FA1C
  BaseP : 1570789295 (Size=50, Diff=112C, MD5=0F656698)
  Pub.X : 2127081270816270912006137526418476
  Pub.Y : 7206819234412870204027887633390168
Feel free to ping me if you need something...
__________________
x64dbg: http://x64dbg.com
My Blog: http://mrexodia.cf
Reply With Quote
The Following 2 Users Say Thank You to mr.exodia For This Useful Post:
contextrax (08-18-2017)
  #5  
Old 08-18-2017, 06:20
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 66 Times in 18 Posts
contextrax Reputation: 17
Quote:
Originally Posted by tofu-sensei View Post
So... It effectively took three weeks to solve?
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.
Reply With Quote
  #6  
Old 08-18-2017, 06:30
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 66 Times in 18 Posts
contextrax Reputation: 17
Quote:
Originally Posted by mr.exodia View Post
You can get the best target by making your own unpackme, or try Armadillo itself...
I would not find it to interested breaking my own ecc parameters

Quote:
Originally Posted by mr.exodia View Post
The latest public (and custom) v9.60 uses:

Code:
  Short V3 Level 10:
    Chk : B5EC5364
    Sym: BDA4FA1C
  BaseP : 1570789295 (Size=50, Diff=112C, MD5=0F656698)
  Pub.X : 2127081270816270912006137526418476
  Pub.Y : 7206819234412870204027887633390168
Feel free to ping me if you need something...
This is the real ecc parameters for armadillo itself?
I thought armadillo was obsolete
Reply With Quote
  #7  
Old 08-18-2017, 06:54
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 66 Times in 18 Posts
contextrax Reputation: 17
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.
Reply With Quote
  #8  
Old 08-18-2017, 16:47
tofu-sensei tofu-sensei is offline
Friend
 
Join Date: Jul 2004
Posts: 108
Rept. Given: 1
Rept. Rcvd 14 Times in 8 Posts
Thanks Given: 1
Thanks Rcvd at 7 Times in 3 Posts
tofu-sensei Reputation: 14
Quote:
Originally Posted by contextrax View Post
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'd say Armadillo is still secure enough then. Who's paying the electricity bill for your little experiment?
Reply With Quote
  #9  
Old 08-18-2017, 17:57
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 66 Times in 18 Posts
contextrax Reputation: 17
Quote:
Originally Posted by tofu-sensei View Post
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.
Reply With Quote
  #10  
Old 08-18-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 66 Times in 18 Posts
contextrax Reputation: 17
Quote:
Originally Posted by mr.exodia View Post
Very interesting! I could integrate this in my Armadillo Key Tool (https://github.com/mrexodia/akt)...
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)
Reply With Quote
The Following User Says Thank You to contextrax For This Useful Post:
mr.exodia (08-18-2017)
  #11  
Old 08-18-2017, 18:52
tofu-sensei tofu-sensei is offline
Friend
 
Join Date: Jul 2004
Posts: 108
Rept. Given: 1
Rept. Rcvd 14 Times in 8 Posts
Thanks Given: 1
Thanks Rcvd at 7 Times in 3 Posts
tofu-sensei Reputation: 14
Quote:
Originally Posted by contextrax View Post
If we are as lucky as I and solve after 2^50 iterations then this would take only ~3 days
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.

Last edited by tofu-sensei; 08-19-2017 at 01:54.
Reply With Quote
  #12  
Old 08-18-2017, 22:23
deepzero's Avatar
deepzero deepzero is online now
VIP
 
Join Date: Mar 2010
Location: Europe
Posts: 188
Rept. Given: 96
Rept. Rcvd 60 Times in 38 Posts
Thanks Given: 60
Thanks Rcvd at 31 Times in 19 Posts
deepzero Reputation: 60
Quote:
Point taken. I ran the numbers again and the power costs should 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.
Reply With Quote
The Following User Gave Reputation+1 to deepzero For This Useful Post:
mr.exodia (08-18-2017)
The Following 3 Users Say Thank You to deepzero For This Useful Post:
Hookahice (02-28-2018), SKiLLa (09-26-2017), tonyweb (08-26-2017)
  #13  
Old 08-18-2017, 22:38
cachito cachito is offline
Friend
 
Join Date: Aug 2015
Location: argentina
Posts: 53
Rept. Given: 0
Rept. Rcvd 12 Times in 8 Posts
Thanks Given: 132
Thanks Rcvd at 51 Times in 30 Posts
cachito Reputation: 13
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
Reply With Quote
  #14  
Old 08-19-2017, 00: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 66 Times in 18 Posts
contextrax Reputation: 17
I can't find the latest armadillo version so if anyone can share that would be great.
Reply With Quote
  #15  
Old 08-19-2017, 00:27
Kerlingen Kerlingen is offline
VIP
 
Join Date: Feb 2011
Posts: 294
Rept. Given: 0
Rept. Rcvd 271 Times in 96 Posts
Thanks Given: 0
Thanks Rcvd at 198 Times in 54 Posts
Kerlingen Reputation: 200-299 Kerlingen Reputation: 200-299 Kerlingen Reputation: 200-299
Quote:
Originally Posted by contextrax View Post
The power consummation on todays cpu is not that bad.
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-$.
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



All times are GMT +8. The time now is 08:30.


ICP05004977
Always Your Best Friend: Aaron, JMI, ahmadmansoor, ZeNiX