An Introduction to Linear Mixed Boolean-Arithmetic Obfuscation

Reverse engineers run into this constantly: a function that should be one instruction sprawls into twenty, every one of them harmless on its own. Nothing about it looks like arithmetic, and that is deliberate. This post takes MBA obfuscation apart down to the single rule it is built on, then puts it back together well enough to break it.

All that wiring, just to add six and three

Open a protected binary in a disassembler and you may find a function that looks like it does something trivial, such as adding two numbers, but spells it out as dozens of lines of ANDs, ORs, XORs, negations, and additions. Feed it 6 and 3 and it returns 9. It computes ordinary addition, but the code does not look like addition.

This is Mixed Boolean-Arithmetic, or MBA. This post covers what it is, how to build it, and how to undo it. The code is shown as readable x86-64 assembly, using real instructions and register names. The instruction sequences were also assembled and tested against a plain reference over every byte-pair input.

You do not need a mathematics background. If you know what AND, OR, and XOR do to bits, and you remember how addition works on paper, that is enough.

How it works

Every value a program uses is stored as a row of bits, the 1s and 0s. The number six is 00000110. The processor can read that same row of bits two different ways, depending on the instruction.

The first way is as a number. When you run add or imul, the processor treats 00000110 as the quantity six and does ordinary arithmetic. Six plus one is seven.

The second way is as a row of independent bits, with no notion of a quantity. This is how the bitwise instructions and, or, xor, and not work. They line two values up bit by bit and handle each position on its own. For example, 6 AND 3 lines up 00000110 and 00000011 and keeps a 1 only where both sides have a 1, giving 00000010, or 2. Nothing was added or carried. The operation only compared positions.

So the same bits are either a number or a set of independent bits, and ordinary code uses one reading or the other. Arithmetic works in the number view, and AND, OR, and XOR work in the bit view. MBA mixes the two on purpose. It takes something like x + y and rewrites it as a mix of ANDs, ORs, XORs, and additions that gives exactly x + y for every input but does not look like addition.

Where it shows up

MBA appears wherever code needs to resist inspection. License checks hide the "is this key valid?" logic under MBA so it cannot be found and patched out. White-box cryptography uses it to spread a key across a mass of arithmetic so the key never sits in memory as a clean value. DRM, anti-cheat systems, and malware use the same techniques, malware to hide its logic and defenders to slow down analysis. On the other side are the reverse engineers and researchers who undo it.

Scope

This post covers standard linear MBA, expressions built by adding bitwise pieces together, each multiplied by a whole number. Shifts, rotations, lookup tables, multiplication, and constants placed inside the bitwise operations (such as x AND 1) are outside this model, and the recovery attack at the end does not apply to them. Linear MBA is cheap to apply and is a common first layer in obfuscators. It was always reducible in principle, but for years the available tools handled it poorly. That changed recently, which makes it a good starting point, complex enough to be worth studying and simple enough to work through completely.

Conventions

The functions use the System V calling convention on Linux. The first argument is in edi (call it x), the second in esi (call it y), and the result returns in eax. They operate on 32-bit registers. The examples use byte-sized inputs to keep the numbers small, but nothing depends on the width. The snippets are written for readability. Labels name standalone functions and comments explain the dataflow, while assembler details such as symbol directives and the syntax-mode declaration are left out, so turning a snippet into a complete source file means adding that boilerplate.

One property of the registers matters throughout. A register holds a fixed number of bits, so its arithmetic wraps around like a clock. On a 12-hour clock, 10 plus 5 reads as 3, not 15. On a byte, values wrap at 256, so 255 + 1 gives 0. In this arithmetic the value with every bit set to 1 behaves like -1, because adding 1 to it wraps to 0. That fact, all-ones equals -1, is why not x equals -x - 1, and it is what lets the two views trade places.

1. The basic rewrite rule

Start with addition, taken apart bit by bit. Adding two single bits has four cases. List them next to what XOR and AND give.

In every row, a + b equals (a XOR b) + 2·(a AND b). XOR gives the answer when it fits in one bit. In the one case where the answer is 2, XOR reads 0 and AND reads 1, and twice that 1 supplies the missing 2. Full numbers work the same way, one column at a time, because binary addition is column addition. XOR is the digit you write down, and AND is the carry into the next column, which counts double.

x + y = (x XOR y) + 2·(x AND y)

In x86-64, compute x ^ y, compute x & y, double the second, and add.

; x + y  =  (x ^ y) + 2*(x & y)
add_xor_carry:
    mov  r8d, edi          ; r8 = x
    xor  r8d, esi          ; r8 = x ^ y
    mov  eax, edi
    and  eax, esi          ; eax = x & y
    add  eax, eax          ; eax = 2*(x & y)
    add  eax, r8d          ; eax = (x ^ y) + 2*(x & y)
    ret

2. A family of rewrites

There is a second way to split addition, from the same table. In every row, a + b also equals (a OR b) + (a AND b), since OR catches "at least one bit set" and AND adds back the extra 1 where both are set. This gives:

x + y = (x OR y) + (x AND y)

; x + y  =  (x | y) + (x & y)
add_or_and:
    mov  r8d, edi
    or   r8d, esi          ; r8 = x | y
    mov  eax, edi
    and  eax, esi          ; eax = x & y
    add  eax, r8d
    ret

Now there are two ways to write x + y. Since both equal x + y, they equal each other, and rearranging that gives more rules. Each line below is the previous equation with terms moved across the equals sign.

x XOR y = (x OR y) - (x AND y)
x OR  y = x + y - (x AND y)
x AND y = x + y - (x OR y)

; x ^ y  =  (x | y) - (x & y)
xor_via:
    mov  eax, edi
    or   eax, esi          ; x | y
    mov  r8d, edi
    and  r8d, esi          ; x & y
    sub  eax, r8d
    ret

; x | y  =  x + y - (x & y)
or_via:
    lea  eax, [rdi+rsi]    ; x + y
    mov  r8d, edi
    and  r8d, esi          ; x & y
    sub  eax, r8d
    ret

; x & y  =  x + y - (x | y)
and_via:
    lea  eax, [rdi+rsi]    ; x + y
    mov  r8d, edi
    or   r8d, esi          ; x | y
    sub  eax, r8d
    ret

So XOR, OR, and AND have each become an arithmetic expression, and addition has become a bitwise one. Any operation can be written in terms of the other view, and that is what obfuscation uses.

3. An expression equal to zero

If two expressions always give the same value, then subtracting one from the other always gives zero. Take the XOR rule from Section 2 and move everything to one side.

Z(x, y) = (x AND y) - (x OR y) + (x XOR y)      always 0, for every x and y

; Z = (x & y) - (x | y) + (x ^ y)   ==   0
zero_Z:
    mov  eax, edi
    and  eax, esi          ; x & y
    mov  r8d, edi
    or   r8d, esi          ; x | y
    sub  eax, r8d          ; (x&y) - (x|y)
    mov  r8d, edi
    xor  r8d, esi          ; x ^ y
    add  eax, r8d
    ret

Z is zero for every input, so you can multiply it by any number and add it into a calculation without changing the result, while adding bit operations that do nothing. The method is to rewrite the operations using Section 2, then add zero-valued terms like Z as padding.

4. Generating rewrites automatically

Deriving rules by hand is fine for learning but not for use. A fixed list means every obfuscated x + y looks the same, and anything that repeats can be matched and reversed with a lookup table. Obfuscators generate new zero-valued expressions on demand so the same code never looks the same twice.

The method is small. A bitwise expression reads two input bits and produces one output bit, and there are only four input pairs (0,0, 0,1, 1,0, 1,1). So a bitwise expression is described by four numbers, one output per case. Call it the expression's fingerprint. x AND y is 0,0,0,1, x OR y is 0,1,1,1, x XOR y is 0,1,1,0. An expression is zero for all inputs exactly when its fingerprint is 0,0,0,0, because the full result is built one bit-column at a time and each column sees one of those four cases. So finding new width-independent zero identities means finding whole-number multipliers for a set of bitwise pieces whose fingerprints add up to 0,0,0,0, which is a small system of equations a computer solves at once. Adding more pieces gives more identities, which is how an obfuscator varies the same x + y.

5. Building the obfuscation

To disguise x + y, take three steps. First, split it with the rule from Section 1, x + y = (x XOR y) + 2·(x AND y). Second, rewrite the x XOR y piece as (x OR y) - (x AND y), which turns the expression into (x OR y) + (x AND y). Third, add 7·Z as padding. Collecting like terms leaves a linear MBA with no x + y visible in it.

obf(x, y) = 7·(x XOR y) + 8·(x AND y) - 6·(x OR y)

This does not look like x + y, but it equals it. In x86-64, using lea to fold the small multiplications into address arithmetic:

; obf = 7*(x^y) + 8*(x&y) - 6*(x|y)    (equals x + y)
obf:
    mov  r8d, edi
    xor  r8d, esi          ; r8  = x ^ y
    mov  r9d, edi
    and  r9d, esi          ; r9  = x & y
    mov  r10d, edi
    or   r10d, esi         ; r10 = x | y
    lea  eax, [r8+r8*2]    ; 3*(x^y)
    add  eax, eax          ; 6*(x^y)
    add  eax, r8d          ; 7*(x^y)
    lea  ecx, [r9*8]       ; 8*(x&y)
    add  eax, ecx          ; + 8*(x&y)
    lea  ecx, [r10+r10*2]  ; 3*(x|y)
    add  ecx, ecx          ; 6*(x|y)
    sub  eax, ecx          ; - 6*(x|y)
    ret

It also holds when the sum overflows a 32-bit register, so it reproduces addition including wraparound, not only for small inputs. Repeat the three steps on the result, nesting them, and you get the kind of output seen in protected software.

6. Why standard tools often don't undo it

Three kinds of analysis can struggle with an expression like this, each for a different reason.

Compilers only go partway. A compiler's cleanup passes work in one view at a time, so they reduce x XOR x to 0 or x + 0 to x. Recovering x + y from a deep mix means crossing between the bit view and the number view, which they do not do reliably. You can see this directly. Compile the obfuscated expression as unsigned C at -O2 and disassemble it. Unsigned matters here, because signed overflow in C is undefined, and unsigned keeps the C semantics matched to the 32-bit wraparound the assembly uses.

; gcc -O2 output for  return 7*(x^y) + 8*(x&y) - 6*(x|y);  with x, y unsigned
obf_c:
    mov    edx, edi
    xor    edx, esi
    lea    eax, [rdx*8+0x0]
    sub    eax, edx
    mov    edx, edi
    or     edi, esi
    and    edx, esi
    lea    eax, [rax+rdx*8]
    lea    edx, [rdi+rdi*2]
    add    edx, edx
    sub    eax, edx
    ret

That is eleven instructions that still compute the obfuscation. The compiler did not reduce it to addition. For comparison, return x + y; compiles to lea eax, [rdi+rsi] and ret. Studies of GCC, Clang, and MSVC show optimizers often shrink MBA expressions and sometimes collapse simple ones, so obfuscated code is often reduced in size without being fully undone by optimization alone.

Solvers may not scale. An SMT solver can prove two expressions equal by expanding every operation down to individual bits. This is fast for one small expression but grows quickly on 64-bit values wrapped in many nested layers, to the point where the proof becomes too slow.

Pattern matching has nothing to match. Since Section 4 lets an obfuscator use different padding each time, two functions that compute the same thing can share no common shape, so there is no fixed signature to scan for.

7. The next tier: reversible encodings

Linear MBA is pieces added together, each times a whole number. The next tier adds multiplication to build reversible encodings, so values never appear in the open.

Choose an encoding you can reverse. The simplest multiplies by a number and adds another, E(v) = 181·v + 97. The multiplier must be odd, because in wraparound arithmetic multiplying by an odd number never maps two inputs to the same output, so the original can be recovered. An even multiplier loses information. To reverse the multiply, use its inverse, the number that cancels it the way division cancels multiplication. For 181 in byte arithmetic that number is 157, since 181 × 157 comes to 1 after wraparound.

; E(v) = (181*v + 97) mod 256
encode:
    imul  eax, edi, 181
    add   eax, 97
    movzx eax, al          ; keep one byte (mod 256)
    ret

; D(e) = (157*(e - 97)) mod 256      (157 is the inverse of 181 mod 256)
decode:
    sub   edi, 97
    imul  eax, edi, 157
    movzx eax, al
    ret

You can work on encoded values without decoding them. Adding two encoded numbers gives 181·(a + b) + 194, which is E(a + b) plus an extra 97, so addition in the encoded domain is "add the two encodings and subtract 97".

For example, encoding 200 and 111 gives 201 and 220, the encoded sum is 68, and only decoding turns it back into 55, which is 200 + 111 with byte wraparound (311 − 256). The unencoded sum 55 does not appear until the final decode. Chain several encodings, use more elaborate reversible formulas, and add linear MBA on top, and recovering one operation means undoing several layers.

8. Breaking linear MBA

Linear MBA has one weakness. Because it is only pieces added together, it is cheap to undo.

However large a two-variable linear MBA expression looks, it reduces to four values, a constant plus an amount of x, an amount of y, and an amount of x AND y.

f(x, y) = c0 + c1·x + c2·y + c3·(x AND y)

The reason is the one from Section 4. A linear MBA expression treats every bit column by the same rule, and a column has four possible input cases. Four cases means four numbers fix the whole behavior, and those are the four above. It does not matter how large the expression is.

To recover the four values, call the function on four inputs, where each variable is all-zeros (0) or all-ones (-1 from the intro). Writing the four outputs as f00, f0A, fA0, and fAA, the constant is c0 = f00, then c1 = c0 - fA0, c2 = c0 - f0A, and c3 = c0 - c1 - c2 - fAA.

Running this against the assembled obf from Section 5, calling it four times without reading its code, gives c0=0, c1=1, c2=1, c3=0. That is 0 + 1*x + 1*y + 0, or x + y. Four calls undo the obfuscation. The same method works for any two-variable linear MBA, with more variables needing more calls. Modern linear-MBA simplifiers such as MBA-Blast and SiMBA are built on this, using the fact that a linear MBA is only a few values in disguise. It does not handle nonlinear or polynomial MBA, constants inside bitwise terms, shifts, rotations, or control-flow mixing, which need heavier tools.

• Rule-based and algebraic simplifiers. SSPAM applies known rewrite rules by pattern matching, while Arybo expands an expression down to its individual output bits and canonicalizes it there.
• Black-box learning. Syntia and QSynth ignore the code's structure. They feed the function many inputs, watch the outputs, and search for the simplest formula that matches, which gets past any syntactic disguise.
• Layer-by-layer attacks undo a reversible encoding by recovering the outer multiply-and-add first, then handling what is underneath.

Linear MBA used to slow analysts down but is now largely solved. Stronger protection comes from breaking the linearity, from combining MBA with control-flow changes so no single clean formula remains, and from making the black-box approach too slow to use.

9. Where to go next

That is the full loop. Take addition apart into a rewrite rule, generate zero-valued padding, use it to disguise a calculation, and recover the original with four calls. Good next steps are to build an obfuscator that repeats the three construction steps with random padding each round, and to extend the recovery to three variables, where eight input cases mean eight values instead of four. For background, read Zhou, Main, Gu, and Johnson's 2007 paper for the original transforms, then the MBA-Blast and SiMBA papers for why linear MBA no longer holds up.