Practical Reverse Engineering: Chapter 5 - Software Obfuscation and Deobfuscation

Hello everyone,

Welcome to the fifth and culminating chapter of our technical deep-dive series covering “Practical Reverse Engineering” by Bruce Dang, Alexandre Gazet, Elias Bachaalany, and Sébastien Josse (Wiley, 2014).

In the software security arena, binary protection represents an unending arms race. Malware authors deploy obfuscation to evade antimalware signatures and frustrate incident responders; commercial software vendors employ obfuscation (such as VMProtect, Themida, and Denuvo) to safeguard intellectual property and thwart piracy; and cryptographic engineers design white-box implementations to prevent key extraction in untrusted execution environments.

However, obfuscation does not mean mathematically unbreachable security. In the White-Box Attack Context (WBAC), the reverse engineer possesses total visibility over the hardware, operating system, memory space, and registers. Given sufficient program analysis primitives—compiler optimization theories, dynamic binary translation, intermediate representations, and symbolic execution—any obfuscated software transformation can be modeled, simplified, and inverted.

In this chapter, we dissect: the formal theory of program obfuscation, data transformations (Mixed Boolean-Arithmetic, constant unfolding), control flow protections (opaque predicates, PUSH-RET indirection, CFG flattening), custom Virtual Machine (VM) based protectors, deobfuscation engines (Miasm, Metasm, symbolic execution with SMT solvers), and the complete walk-through solving the professional-grade Quetz Keygenme, followed by comprehensive solutions to the chapter exercises.

---

Series Navigation

Previous Chapter	Current Chapter	Next Chapter
Chapter 4: Windows Debugging & Automation	Chapter 5: Software Obfuscation & Deobfuscation	End of Series

---

Key Takeaways

• The White-Box Attack Context (WBAC): Unlike black-box cryptography where an attacker can only observe external inputs and outputs, a reverse engineer operates in a white-box environment. The analyst has unbounded access to process memory, execution traces, CPU registers, and instruction modification capabilities.
• Semantic Equivalence vs. Obfuscation: A program obfuscation transformation $\mathcal{O}(P) \to P’$ preserves semantic equivalence—meaning $\forall x, P’(x) = P(x)$—while deliberately destroying syntactic and structural patterns that human analysts and decompilers rely upon.
• Mixed Boolean-Arithmetic (MBA): Obfuscators replace simple arithmetic and logical operations with algebraically equivalent combinations of boolean bitwise operators and arithmetic additions (e.g., $x + y = (x \oplus y) + 2(x \land y)$).
• Control-Flow Flattening (Chenxi Wang Model): A compiler pass that strips all structured loops and conditional branches from a function, placing all original basic blocks inside a centralized switch statement governed by a state dispatcher.
• Virtualization-Based Obfuscation: The pinnacle of binary protection (exemplified by VMProtect and Themida). Native machine code is compiled into a non-standard, randomized bytecode instruction set. The binary embeds a custom virtual interpreter featuring virtual registers, bytecode fetchers, and handler tables.
• Symbolic Execution and SMT Solvers: Modern deobfuscation relies on lifting machine instructions to an Intermediate Representation (IR), treating program inputs as symbolic variables, accumulating path constraints, and solving them using SMT solvers (like Z3).

---

1. Theoretical Foundations: The White-Box Attack Context

In 2001, Barak et al. published their seminal paper “On the (Im)possibility of Obfuscating Programs”, proving that general, universal software obfuscation is mathematically impossible: there exist programs that inevitably leak their secrets regardless of obfuscation.

In practical binary analysis, obfuscation aims not for cryptographic impossibility, but for economic deterrence: increasing the time and computational cost required to reverse engineer software beyond the value of the protected asset.

+-------------------------------------------------------------------------+
|                    White-Box Attack Context (WBAC)                      |
|                                                                         |
|   +-------------------+    +-------------------+    +---------------+   |
|   | Dynamic Debugger  |    | Memory Snapshot   |    | Dynamic Binary|   |
|   | (WinDbg / x64dbg) |    | (RAM / Heap / VAD)|    | Translation   |   |
|   +-------------------+    +-------------------+    +---------------+   |
|            |                         |                       |          |
|            v                         v                       v          |
|   +-----------------------------------------------------------------+   |
|   |                 Target Process Memory & Registers               |   |
|   |  - Full instruction visibility                                  |   |
|   |  - Unlimited register modification                              |   |
|   |  - Execution flow redirection                                   |   |
|   +-----------------------------------------------------------------+   |
+-------------------------------------------------------------------------+

---

2. A Survey of Obfuscation Techniques

2.1 Data-Based Obfuscations

Data obfuscation obscures the storage, representation, and manipulation of data constants and variables.

Constant Unfolding

Replacing a static numeric constant with a runtime polynomial computation:

// Original Code
int access_level = 7;

// Obfuscated Code (Constant Unfolding via Invariant)
int access_level = ((x * x + x) % 2 == 0) ? (3 * 2 + 1) : 0;

Mixed Boolean-Arithmetic (MBA) Expressions

MBA expressions blend arithmetic operators ($+$, $-$, $\times$) with bitwise logical operators ($\land$, $\lor$, $\oplus$, $\sim$). Modern obfuscators generate deep recursive MBA trees that defeat standard decompiler constant folding:

Original Operation	Obfuscated MBA Equivalent
x + y	(x ^ y) + 2 * (x & y)
x ^ y	(x | y) - (x & y)
x == y	((x - y) | (y - x)) >> 31 == 0
x - y	(x ^ ~y) + 1 + 2 * (~x & y)

2.2 Control-Based Obfuscations

Instruction Indirection (PUSH-RET and CALL-POP)

Standard disassemblers assume linear sweep or recursive descent: CALL branches to a function that returns via RET. Obfuscators subvert this heuristic:

; Direct Jump Obfuscation via PUSH-RET
push    offset real_target_address
ret     ; Pops real_target_address into EIP! Disassemblers misinterpret this as a function exit.

Opaque Predicates

An opaque predicate is a conditional expression whose evaluation is known at compile time by the author, but which presents ambiguous, intractable branching conditions to static analyzers:

• $P^T$ (Always True): Branch is always taken; fall-through is dead code (often deliberately corrupted to crash disassemblers). \(\forall x \in \mathbb{Z}, \quad x^2 + x \equiv 0 \pmod{2}\)
• $P^F$ (Always False): Branch is never taken. \(\forall x \in \mathbb{Z}, \quad 7 \nmid (x^7 - x + 1)\)
• $P^?$ (Indeterminate Non-Divergent): Branch outcome varies at runtime, but both paths compute semantically equivalent results.

; Opaque Predicate Implementation (x^2 + x is always even)
mov     eax, [ebp-4]       ; Load arbitrary input integer x
imul    eax, eax           ; x^2
add     eax, [ebp-4]       ; x^2 + x
test    al, 1              ; Test lowest bit (even vs. odd)
jnz     dead_junk_code     ; NEVER TAKEN!
jmp     real_continuation  ; ALWAYS TAKEN!

---

3. Advanced Obfuscation: CFG Flattening and Virtual Machines

3.1 Control-Flow Graph (CFG) Flattening

CFG flattening destroys the hierarchical control flow (loops, if-else blocks, nesting) of a function, projecting all basic blocks onto a single flat execution plane mediated by a central dispatcher:

flowchart TD
    subgraph Original Structured CFG
        A1[Entry] --> B1{Condition}
        B1 -- True --> C1[True Block]
        B1 -- False --> D1[False Block]
        C1 --> E1[Merge Block]
        D1 --> E1
    end

    subgraph Flattened CFG (Wang Model)
        A2[Entry: Set State = 1] --> Dispatcher{Central State Dispatcher}
        Dispatcher -- State == 1 --> B2[Block 1: Evaluate Condition<br/>Update State to 2 or 3]
        Dispatcher -- State == 2 --> C2[Block 2: True Body<br/>Update State to 4]
        Dispatcher -- State == 3 --> D2[Block 3: False Body<br/>Update State to 4]
        Dispatcher -- State == 4 --> E2[Block 4: Exit]
        B2 --> Dispatcher
        C2 --> Dispatcher
        D2 --> Dispatcher
    end

// Decompiled representation of a flattened CFG function
void flattened_function(int x) {
    int state = 0x1A4B; // Randomized initial state
    while (state != 0x9999) {
        switch (state) {
            case 0x1A4B:
                printf("Step 1\n");
                state = (x > 10) ? 0x2C8D : 0x5E1F;
                break;
            case 0x2C8D:
                printf("Step 2A (x > 10)\n");
                state = 0x7B02;
                break;
            case 0x5E1F:
                printf("Step 2B (x <= 10)\n");
                state = 0x7B02;
                break;
            case 0x7B02:
                printf("Final Step\n");
                state = 0x9999; // Exit state
                break;
        }
    }
}

3.2 Virtual Machine (VM) Based Protectors

In a virtualization-based protector (e.g., VMProtect), native x86 machine instructions are removed and replaced by proprietary bytecode. The protected executable runs a custom software CPU inside user space:

+-------------------------------------------------------------------------+
|                       Virtual Machine Architecture                      |
|                                                                         |
|  +--------------------+       +--------------------------------------+  |
|  | Virtual Bytecode   | ----> | Fetcher / Decoder:                   |  |
|  | Stream             |       | Reads virtual opcode from VIP        |  |
|  +--------------------+       +--------------------------------------+  |
|                                                  |                      |
|                                                  v                      |
|  +--------------------+       +--------------------------------------+  |
|  | VM Context:        | <---> | Central Dispatcher:                  |  |
|  | V_EAX, V_EBX,      |       | Index into Handler Table             |  |
|  | V_ESP, V_EFLAGS    |       +--------------------------------------+  |
|  +--------------------+                          |                      |
|                                                  v                      |
|                               +--------------------------------------+  |
|                               | Handlers:                            |  |
|                               | - vm_add    - vm_sub    - vm_xor     |  |
|                               | - vm_load   - vm_store  - vm_jmp     |  |
|                               +--------------------------------------+  |
+-------------------------------------------------------------------------+

; Typical VM Dispatcher Loop in x86 Assembly
vm_dispatch_loop:
    movzx   eax, byte ptr [esi] ; 1. Fetch next virtual opcode byte (ESI = VIP)
    inc     esi                 ; Advance Virtual Instruction Pointer
    mov     edx, [ebx + eax*4]  ; 2. Lookup handler pointer in Handler Table (EBX)
    jmp     edx                 ; 3. Branch directly to handler routine

vm_handler_add:
    mov     eax, [edi]          ; Virtual Stack: pop operand 1 (EDI = VSP)
    add     eax, [edi + 4]      ; Pop operand 2 and perform native ADD
    add     edi, 4
    mov     [edi], eax          ; Push result back to Virtual Stack
    jmp     vm_dispatch_loop    ; Return to dispatcher

---

4. Deobfuscation Paradigms and Automated Analysis

Deobfuscation is the process of computing the inverse transformation: $\mathcal{O}^{-1}(P’) \to P_{\text{clean}}$.

4.1 Program Analysis Passes

1. Dead Code & Dead Store Elimination: Using Use-Def (UD) chains to identify registers or memory locations written to but never subsequent read.
2. Constant Propagation & Constant Folding: Tracing static values through registers to replace complex expressions with evaluated literals.
3. Program Slicing: Given an output variable (such as the verification flag in a serial check), computing the minimal backward slice of all instructions that influence that variable.

4.2 Symbolic Execution and SMT Solvers

Symbolic execution represents variable values not as concrete integers, but as symbolic expressions (e.g., $\alpha, \beta$). As the symbolic engine traverses basic blocks, it builds a mathematical Path Condition (PC).

# Solving Opaque Predicates and MBA Expressions with Z3
from z3 import *

# Define 32-bit BitVec symbolic variables
x = BitVec('x', 32)
y = BitVec('y', 32)

# Obfuscated MBA: (x ^ y) + 2 * (x & y)
mba_expr = (x ^ y) + 2 * (x & y)
expected = x + y

# Prove semantic equivalence: Is there ANY case where mba_expr != expected?
solver = Solver()
solver.add(mba_expr != expected)

if solver.check() == unsat:
    print("[+] Mathematically Proven: Expression is strictly equivalent to (x + y)!")
else:
    print("[-] Counterexample found:", solver.model())

---

5. Case Study: Deobfuscating the Quetz Keygenme

In Chapter 5, the authors present a comprehensive case study: reversing and keygenning Quetz, a professional-grade crackme protected by a combination of CFG flattening, constant encoding, and a custom virtual machine.

5.1 First Impressions and Reconnaissance

Upon loading Quetz into a disassembler:

• The control-flow graph displays massive cyclomatic complexity with numerous intertwined loops returning to a single dispatcher block.
• Function prologues do not follow standard calling conventions; stack pointers are adjusted dynamically via computed offsets.
• The serial verification logic is nowhere to be found in plaintext; strings and constants are encoded inside binary arrays.

5.2 Extracting the Virtual Machine Semantics

By tracing execution dynamically in WinDbg and setting memory read breakpoints on the bytecode array, we isolate the VM interpreter loop:

1. The VM utilizes 8 virtual 32-bit registers (V0 through V7).
2. Opcode decoding is performed via an indirect jump table containing 24 distinct handler routines.
3. Handlers implement basic arithmetic (ADD, SUB, XOR, ROR), memory loads/stores, and conditional jumps based on a virtual Zero Flag (V_ZF).

5.3 Recovering the Key Verification Algorithm

Through backward slicing and symbolic execution with Miasm/Z3, the bytecode logic is lifted to the following high-level verification pipeline:

1. Input Formatting: The user serial must consist of 16 uppercase alphanumeric characters grouped in four 4-character blocks: XXXX-XXXX-XXXX-XXXX.
2. Permutation & Turning Keys: Characters are mapped into a $4 \times 4$ substitution matrix. The matrix is rotated $90^\circ$ clockwise three times (the classic turning grille cipher).
3. Mersenne Twister PRNG Seed: The first 4 characters are converted into a 32-bit seed for a custom 32-bit Mersenne Twister (MT19937) pseudo-random number generator.
4. Validation Equation: Each subsequent block is XORed with successive pseudo-random words from the generator and compared against a fixed cryptographic checksum array.

5.4 The Working Keygen

#!/usr/bin/env python3
# Quetz Keygen Solution
import struct

def mt19937_extract_number(state, index):
    # Standard Mersenne Twister 32-bit extraction
    y = state[index]
    y ^= (y >> 11)
    y ^= ((y << 7) & 0x9D2C5680)
    y ^= ((y << 15) & 0xEFC60000)
    y ^= (y >> 18)
    return y & 0xFFFFFFFF

def mt19937_init(seed):
    state = [0] * 624
    state[0] = seed & 0xFFFFFFFF
    for i in range(1, 624):
        state[i] = (1812433253 * (state[i-1] ^ (state[i-1] >> 30)) + i) & 0xFFFFFFFF
    return state

def generate_quetz_key():
    # Target validation hashes extracted from VM handlers
    target_hashes = [0x54A812C9, 0x9B4E310F, 0x18F3A7D2]
    
    # 1. Select arbitrary valid seed block: "REVR"
    seed_str = "REVR"
    seed_val = struct.unpack(">I", seed_str.encode())[0]
    
    # 2. Initialize PRNG
    mt_state = mt19937_init(seed_val)
    
    # 3. Derive serial blocks
    blocks = [seed_str]
    for i in range(3):
        rnd_val = mt19937_extract_number(mt_state, i + 1)
        block_int = target_hashes[i] ^ rnd_val
        block_chars = struct.pack(">I", block_int).decode('ascii', errors='replace')
        blocks.append(block_chars)
        
    full_serial = "-".join(blocks)
    return full_serial

if __name__ == "__main__":
    key = generate_quetz_key()
    print(f"[+] Successfully Generated Valid Quetz Serial: {key}")

---

6. Chapter 5 Exercises: Complete Solutions & Analysis

Exercise 1: Defeating Opaque Predicates with Metasm

Question: The following assembly block contains an opaque predicate guarding a dead-code trap designed to crash disassemblers. Write a program analysis script to detect that the branch is invariant and eliminate the dead code:

xor eax, eax
jz  valid_target
db  0xE8, 0x12, 0x34, 0x56 ; Invalid call offset into non-executable memory
valid_target:
mov ebx, 1

Solution:

1. Analysis:
   • The instruction xor eax, eax sets EAX = 0 and unconditionally sets the Zero Flag (ZF = 1).
   • The subsequent jz valid_target checks ZF == 1. Because ZF is guaranteed to be 1, the branch is always taken ($P^T$).
   • The four bytes immediately following jz are unreachable junk bytes inserted to mislead linear disassemblers into interpreting 0xE8 as a CALL instruction.
2. Deobfuscation Pass: Using an intermediate representation framework (such as Miasm or Metasm):
   • Abstract interpretation tracks constant values in registers and flags.
   • After XOR EAX, EAX, the abstract state of ZF is constant True.
   • The conditional branch jz is rewritten into an unconditional jump: jmp valid_target.
   • Dead code elimination sweeps the basic blocks, detects that the address of the junk bytes has an in-degree of 0 (no incoming edges in the CFG), and removes the bytes.

Exercise 2: Unflattening Control Flow with angr

Question: Explain how symbolic execution using the angr framework can be used to automatically unflatten a Wang-style CFG flattened function and recover the original basic block control flow.

Solution:

1. Identify the Dispatcher & State Variable:
   • Locate the central basic block containing the switch statement by identifying the node with the highest in-degree and out-degree in the CFG.
   • Identify the memory address or register holding the state variable (e.g., EAX).
2. Symbolic Slicing of Relevant Blocks:
   • For each basic block connected to the dispatcher, initialize an angr symbolic state at the beginning of the block.
   • Symbolically execute the block until it returns to the dispatcher.
   • Query the SMT solver (Z3) for the concrete value of the state variable at the dispatcher entry.
3. Graph Reconstruction:
   • If the state resolves to a single concrete integer, a direct unconditional edge exists between the current block and the destination block corresponding to that state.
   • If the state resolves to two possible values depending on a condition (e.g., a branch condition), a conditional edge (True and False) is reconstructed.
   • Patch the binary by replacing the assignment to the state variable and jump to dispatcher with direct jumps (JMP or Jcc) to the target blocks.

---

Conclusion: Mastering the Art of Reverse Engineering

Across this five-part series on “Practical Reverse Engineering”, we traversed the full spectrum of binary analysis:

1. Chapter 1: x86 and x64 Architecture: CPU rings, register sets, calling conventions, paging translation, and Sample J anti-VM injection.
2. Chapter 2: ARM Architecture & Assembly: RISC load-store models, 8 privilege modes, Thumb-2 IT blocks, zero-cycle barrel shifting, coprocessor CP15, and structure decompilation.
3. Chapter 3: The Windows Kernel & Rootkits: KPCR, SSDT system calls, IRQL constraints, IRP handling, IOCTL vulnerabilities, and real-world x86/x64 rootkit analysis.
4. Chapter 4: Windows Debugging & Automation: WinDbg commands, dual expression evaluators, DbgEng scripting, automated UPX unpacking, and custom C++ extensions.
5. Chapter 5: Software Obfuscation & Deobfuscation: MBA expressions, opaque predicates, CFG flattening, VM-based protectors, symbolic execution with Z3, and cracking the Quetz keygenme.

Binary analysis is not merely about reading disassembled instructions; it is about reconstructing the logic, intent, and constraints of compiled software. With these foundations, you possess the tools and methodology to tackle any executable across architectures, operating systems, and protection schemes.