Automated x86 instruction obfuscation

What you need is an algebraic descripton of what the opcodes do, and a set of algebraic laws that allow you to determine equivalent operations.

Then for each instruction, you look up its algebraic description (for the sake of an example, an

 XOR  eax,mem[ecx]

whose algebraic equivalent is

 eax exclusive_or mem[ecx]

enumerate algebraic equivalences using those algebra equivalents, such as:

 a exclusive_or b ==> (a and not b) or (b and not a)

to generate equivalent algebraic statement for your XOR instruction

 eax exclusive_or mem[ecx] ==> (eax and not mem[ecx]) or (mem[ecx] and not eax)

You may apply more algebraic laws to this, for instance de morgans' theorem:

 a or b ==> not (not a and not b)

to get

(not (not (eax and not mem[ecx])) and (not (mem[ecx] and not eax)))

At this point you have a specification of an algebraic computation that will do the same thing as the original. There's your brute force.

Now you have to "compile" this to machine instructions by matching what instructions will do with what this says. Like any compiler, you likely want to optimize the generated code (no point in fetching mem[ecx] twice). (All of this hard... its a code generator!) The resulting code sequence would be something like:

mov ebx, mem[ecx]
mov edx, ebx
not edx
and edx, eax
not eax
and eax, ebx
not eax
or eax, edx

This is a lot of machinery to build manually.

Another way to do this is to take advantage of a program transformation system that allows you to apply source-to-source transformations to code. Then you can encode "equivalences" as rewrites directly on the code.

One of these tools is our DMS Software Reengineering Toolkit.

DMS takes a langauge definition (essentially as an EBNF), automatically implements a parser, AST builder, and prettyprinter (anti parser, turning AST back into valid source text). [DMS doesn't presently have an EBNF for ASM86, but dozens of EBNFs for various complex langauges have been build for DMS including several for miscellaneous non-x86 assemblers So you'd have to define the ASM86 EBNF to DMS. This is pretty straightforward; DMS has a really strong parser generator].

Using that, DMS will let you write source transformations directly on the code. You could write the following transformations that implement the XOR equivalant and DeMorgan's law directly:

  domain ASM86;

  rule obfuscate_XOR(r: register, m: memory_access):instruction:instruction
  =  " XOR \r, \m " 
      rewrites to
     " MOV \free_register\(\),\m
       NOT \free_register\(\)
       AND \free_register\(\),\r 
       NOT \r
       AND \r,\m
       OR \r,\free_register\(\)";

 rule obfuscate_OR(r1: register, r2: register):instruction:instruction
 = " OR \r1, \r2"
     rewrites to
    " MOV \free_register\(\),\r1
      NOT \free_register\(\)
      AND \free_register\(\),\r2
      NOT \r2
      AND \r1,\r2
      NOT \r1";

with some additional magic in a meta-procedure called "free_register" that determines what registers are free at that point (of the AST match) in the code. (If you don't want to do that, use the top of the stack as temporary everywhere as you did in your example).

You'd need a bunch of rewrites to cover all the cases that you want to obfuscate, with thier combinatorics with registers and memory operands.

Then the transformation engine can be asked to apply these transformations randomly once or more than once at each point in the code to scramble it.

You can see a fully worked example of some algebraic transforms being applied with DMS.