8

I don't know the exact name of this obfuscation, so I call it variable entanglement for now.

I already saw this principle in a few binaries but I never found a complete description of what was possible and what was not.

The idea is to confuse the reverser by mixing two values together and performing the operations on the mixed values. Once all operations have been performed, one can recompose the results by some simple operations. For example, a naive example could be:

int foo (int a, int b) {
  long long x = 0;
  // Initial entanglement
  x = (a << 32) | b;

  // Performing operations on both variables
  x += (12 << 32) & 72;
  ...

  // Final desentanglement
  a = (int) (x >> 32);
  b = (int) (((int) -1) & x);
} 

Of course, here, we mix everything in one variable (and I did not take care of details such as the overflows). But, you can imagine way more complex initial entanglement where you re-split everything in two variables (or more), e.g. by xoring them together.

Operations such as addition, multiplication, ... have to be redefined for this new format, so it can mislead the reverser.

My question now, does anyone know about different such schema of variable entanglement (the one I gave is really basic) ? And, maybe, can give pointers or publication about it ?

5
  • Is this actual source or is this something a decompiler spat out (or you created based on disassembly)?
    – 0xC0000022L
    Jul 16 '13 at 14:45
  • X is uninitialized. Shouldn't it be | b instead of & b? Also, long is not necessarily double the size of int. Why not post a working example? That might make it easier to give a meaningful answer to your question.
    – newgre
    Jul 16 '13 at 14:55
  • In fact, this is pure junk. It is just here to illustrate the idea. It won't even compile. I have some examples in assembly (x86+SSE), but they are not really explicit and easy to understand.
    – perror
    Jul 16 '13 at 15:14
  • @newgre: Thanks noticing all these errors (sorry to not have fixed this at first, I was busy doing something else...).
    – perror
    Jul 16 '13 at 17:12
  • I don't know about publications that explore this technique specifically, but JBCO does a weak form of this (sable.mcgill.ca/publications/papers/2007-1/…).
    – Antimony
    Jul 17 '13 at 4:13
8

I'm not sure whether this is along the lines you're looking for (and quite possibly you've already figured out all of this and more), but here's a crude formalization and then some implementation thoughts. Conceptually, this tries to separate what it means to entangle several values from how entangled values are represented.

Formalization

Conceptually, entangled values can be thought of as aggregates where the different components retain their values, don't interfere with each other, and can be independently extracted. A convenient way to think of such aggregates is as n-tuples of values; for simplicity I assume n = 2 here. Also, I assume that we have operations to construct tuples from a collection of values, and to extract the component values from a tuple.

We now need to be able to carry out operations on tuples. For this, for each operation op in the original program we now have 2 versions: op1, which operates on the first component of a 2-tuple, and op2, which operates on the second component:

<a1,b1> op1 <a2,b2> = if (b1 == b2) then <(a1 op a2), b1> else undefined
<a1,b1> op2 <a2,b2> = if (a1 == a2) then <a1, (b1 op b2)> else undefined

Finally (and this is where the obfuscation comes in), we need a way to encode tuples as values and decode values into tuples. If the set of values is S, then we need two functions enc and dec that must be inverses of each other:

enc: S x S --> S (encode pairs of values as a single entangled value)
dec: S --> S x S (decode an entangled value into its components)

enc(dec(x)) = x for all x
dec(enc(x)) = x for all x

Examples:

  • enc takes a pair of 16-bit values and embeds them into a 32-bit value w such that x occupies the low 16 bits of w and y occupies the high 16 bits of w; dec takes a 32-bit value and decodes them into a pair where x is the low 16 bits and y is the high 16 bits.

  • enc takes a pair <x,y> of 16 bit values and embeds them into a 32-bit word w such that x occupies the even-numbered bit positions of w and y occupies the odd-numbered bit positions of w (i.e., their bits are interlaced); dec takes a 32-bit value w and decodes them into a pair <x,y> such that x consists of the even-numbered bits of w and y consists of the odd-numbered bits of w.

Implementation considerations

From an implementation perspective, we'd like to be able to perform operations directly on encoded representations of values. For this, corresponding to each of the operations op1 and op2 above, we need to define "encoded" versions op1* and op2* that must satisfy the following soundness criterion:

for all x1, x2, and y: x1 op1* x2 = y IFF enc( dec(x1) op1 dec(x2) ) = y

and similarly for op2*.

A lot of details are omitted (mostly easy enough to work out), and this basic approach could be prettified in various ways, but I don't know whether this is along the lines you were asking for and also whether maybe this is pretty straightforward and you've already worked it all out for yourself. Anyway, I hope this is useful.


From @perror's comment (below) it seems clear that the formalization above is not powerful enough to capture the obfuscation he has in mind (though it might be possible to get a little mileage from generalizing the encoding/decoding functions enc and dec).

I had forgotten about this paper, which discusses a transformation that seems relevant (see Sec. 6.1, "Split variables"):

Christian Collberg, Clark Thomborson, and Douglas Low. Breaking Abstractions and Unstructuring Data Structures. IEEE International Conference on Computer Languages (ICCL'98), May 1998. (link)

4
  • I think you perfectly defined the basic operators and formalized the context of it. But, the example I gave was probably too naive and, thus, a bit misleading. To give maybe a better example, what if you have x=a^b and y=a^(~b) and try to apply some operations on a and b through operations on x and y. In this schema, the word entanglement is a bit more obvious I guess. I will try to dig a bit this schema and propose a full example. Finally, it is totally unrelated but are you Saumya Debray ? (I read several of his papers and I am a big fan! :))
    – perror
    Jul 17 '13 at 15:54
  • I think I understand the subtleties of the obfuscation a little better now -- thanks! I'll need to go think about that some more. (On an unrelated note, my first name is indeed Saumya. :-)
    – debray
    Jul 18 '13 at 2:55
  • @perror : the formalization I gave doesn't seem powerful enough to capture what you have in mind. But meanwhile I remembered a paper by Collberg et al. that describes a transformation that may be relevant: please see the edited response above.
    – debray
    Jul 18 '13 at 13:43
  • Yes, this is exactly what I was looking for ! Thanks ! So, it is called "split variables".
    – perror
    Jul 18 '13 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.