Understanding the Movfuscator

[Nytro]

Understanding the Movfuscator

14 MAR 2019 • 12 mins read

MoVfuscator is the PoC for the Turing Completeness of Mov instruction.
Yes, you guessed it right. It uses only mov’s, except for a few places.
This makes reversing difficult, because the control flow is obfuscated.

I’ll be analyzing the challenge Mov of UTCTF’19 using IDA Free.

MoV

The Stack

Movfuscator uses its own stack. The stack consists of an array of addresses. The stack looks like this

Each element of the stack is at an offset of 0x200064 from it’s stack address. The stack begins at 0x83f70e8 and it grows from high to low address.

The stack pointer is saved in the variable sesp. The variable NEW_STACK stores the address of guard.

mov esp, NEW_STACK              ; address of guard
mov esp, [esp-0x200068]         ; address of A[n-1]
mov esp, [esp-0x200068]         ; address of A[n-2]
;   ...
;   n times
;   ...
;   use esp

So, mov esp, [esp-0x200068], subtracts 4 from esp.
Now we can understand what start does.

mov dword [esp-4*4], SIGSEGV
mov dword [esp-4*4+4], offset sa_dispatch
mov dword [esp-4*4+8], 0
call sigaction

mov dword [esp-3*4], SIGILL
mov dword [esp-3*4+4], offset sa_loop
mov dword [esp-3*4+8], 0
call sigaction

;
;   ...
;
.plt:08048210                 public dispatch
.plt:08048210 dispatch        proc near               ; DATA XREF: .data:sa_dispatch↓o
.plt:08048210                 mov     esp, NEW_STACK
.plt:08048216                 jmp     function
.plt:08048216 dispatch        endp

Movfuscator uses SIGSEGV to execute a function, and SIGILL to execute a JMP instruction which jumps to master_loop. Because we can’t mov to eip, which is invalid in x86.

Execution is controlled using the on variable. This is a boolean variable that determines whether a statement will be executed or not.

The master_loop sets the value of on and then disables toggle_execution. This is the structure of if statement.

def logic_if(condition, dest, src)
    if (condition)
        dest = src
    else
        discard = src

It then adds sesp with 4 and stores the sum in stack_temp.

Push

The array sel_data contains two members - discard and data_p. This is a MUX which selects data_p if on is set. So, if on is set, eax contains the address of NEW_STACK. And the value of esp-4 is stored in NEW_STACK, which is the stack pointer. And then the value of stack_temp is stored in the current stack pointer.

The above set of instructions are equivalent to

mov eax, [stack_temp]
sub esp, 4
mov [esp], eax

It can also be represented as

push dword [stack_temp]

The sequnce of instructions until 0x0804843C do the following

mov eax, [sesp]
add eax, 4
push eax
push dword [sesp]
push 0x880484fe

It conditionally sets the value of target to branch_temp. The target variable is the destination an unconditional jump. In this code, the target is set to 0x88048744.

Let’s see how jump’s are implemented.

on = 1
...
target = jump_destination
; save registers R, F, D
on = 0
...
if (fetch_addr == target)
{
    ; restore registers R, F, D
    on = 1
}
...

The above code saves the registers.

It now checks if the fetch address equals the address contained in target. The equal-to comparison is computed for each byte and the result is the logical-and of the four comparisons. The result of the comparison is stored in the boolean variable b0.
Now if b0 is set, the registers are restored and the on variable is set.

This is equivalent to the following if the on variable is set.

push 0
call _exit

You must be wondering how I deduced the call instruction. Here is it

Function Call

Function calls are implemented using the SIGSEGV signal. The array fault is defined like this

.data:085F7198 fault           dd offset no_fault      ; DATA XREF: _start+51F↑r
.data:085F719C                 dd 0

.data:085F71A0 no_fault        dd 0

So, fault when indexed with on returns 0 if on is set, otherwise a valid address. This return value is dereferenced which results in a SIGSEGV (Segmentation Fault) if its zero.

But since, the value of target is 0x88048744. The control jumps to main.

In main, the registers are restored and the on flag is set. After that it pushes fp, R1, R2, R3, F1, dword_804e04c, D1 into the stack

The function prologue

It first assigns the frame pointer fp to the current stack pointer and allocates 37 dwords (148 bytes) from the stack. This is equivalent to the following x86

mov ebp, esp    ;   ebp is **fp**
sub esp, 148

Computes fp-19*4 and stores the value of R3 into the address. So, this is basically

mov R3, 0
mov [fp-19*4], R3

Great ! So, we have a dword at fp-0x4c initialized to 0.
Then we have an array of bytes at fp-0x47 initialized as follows

mov R0, 0x1a
mov byte [fp-18*4], R0
mov R0, 0x19
mov byte [fp-0x47], R0
mov R0, 11
mov byte [fp-0x46], R0
mov R0, 0x31
mov byte [fp-0x45], R0
mov R0, 6
mov byte [fp-17*4], R0
mov R0, 4
mov byte [fp-0x43], R0
mov R0, 0x18
mov byte [fp-0x42], R0
mov R0, 0x10
mov byte [fp-0x41], R0
mov R0, 10
mov byte [fp-16*4], R0
mov R0, 0x33
mov byte [fp-0x3f], R0
mov R0, 0x19
mov byte [fp-0x3e], R0
mov R0, 10
mov byte [fp-0x3d], R0
mov R0, 0x33
mov byte [fp-15*4], R0
mov R0, 0
mov byte [fp-0x3b], R0
mov R0, 10
mov byte [fp-0x3a], R0
mov R0, 0x3c
mov byte [fp-0x39], R0
mov R0, 0x19
mov byte [fp-14*4], R0
mov R0, 13
mov byte [fp-0x37], R0
mov R0, 6
mov byte [fp-0x36], R0
mov R0, 0x19
mov byte [fp-0x35], R0
mov R0, 0x3c
mov byte [fp-13*4], R0
mov R0, 14
mov byte [fp-0x33], R0
mov R0, 0x10
mov byte [fp-0x32], R0
mov R0, 0x3c
mov byte [fp-0x31], R0
mov R0, 0x10
mov byte [fp-12*4], R0
mov R0, 12
mov byte [fp-0x2f], R0
mov R0, 0x32
mov byte [fp-0x2e], R0
mov R0, 10
mov byte [fp-0x2d], R0
mov R0, 0x14
mov byte [fp-11*4], R0
mov R0, 13
mov byte [fp-0x2b], R0
mov R0, 6
mov byte [fp-0x2a], R0
mov R0, 0x19
mov byte [fp-0x29], R0
mov R0, 0x3c
mov byte [fp-10*4], R0
mov R0, 0x19
mov byte [fp-0x27], R0
mov R0, 6
mov byte [fp-0x26], R0
mov R0, 0x33
mov byte [fp-0x25], R0
mov R0, 4
mov byte [fp-9*4], R0
mov R0, 10
mov byte [fp-0x23], R0
mov R0, 0x33
mov byte [fp-0x22], R0
mov R0, 0x19
mov byte [fp-0x21], R0
mov R0, 14
mov byte [fp-8*4], R0
mov R0, 6
mov byte [fp-0x1f], R0
mov R0, 0x31
mov byte [fp-0x1e], R0
mov R0, 0x31
mov byte [fp-0x1d], R0
mov R0, 0x1e
mov byte [fp-7*4], R0
mov R0, 0x3c
mov byte [fp-0x1b], R0
mov R0, 0x17
mov byte [fp-0x1a], R0
mov R0, 10
mov byte [fp-0x19], R0
mov R0, 0x31
mov byte [fp-6*4], R0
mov R0, 6
mov byte [fp-0x17], R0
mov R0, 0x19
mov byte [fp-0x16], R0
mov R0, 10
mov byte [fp-0x15], R0
mov R0, 9
mov byte [fp-5*4], R0
mov R0, 0x3c
mov byte [fp-0x13], R0
mov R0, 0x19
mov byte [fp-0x12], R0
mov R0, 12
mov byte [fp-0x11], R0
mov R0, 0x3c
mov byte [fp-4*4], R0
mov R0, 0x19
mov byte [fp-0xf], R0
mov R0, 13
mov byte [fp-0xe], R0
mov R0, 10
mov byte [fp-0xd], R0
mov R0, 0x3c
mov byte [fp-3*4], R0
mov R0, 0
mov byte [fp-0xb], R0
mov R0, 13
mov byte [fp-0xa], R0
mov R0, 6
mov byte [fp-0x9], R0
mov R0, 0x31
mov byte [fp-2*4], R0
mov R0, 0x31
mov byte [fp-7], R0
mov R0, 10
mov byte [fp-6], R0
mov R0, 0x33
mov byte [fp-5], R0
mov R0, 4
mov byte [fp-4], R0
mov R0, 10
mov byte [fp-3], R0
mov R0, 2
mov byte [fp-2], R0

At 0x804ba9c, the int variable at fp-0x4c is set to 0.

If target is 0x8804bb37, it executes the following

if (target == 0x8804bb37)
{
    ;   restore the registers
    R{0,1,2,3} = jmp_r{0,1,2,3}
    F{0,1} = jmp_f{0,1}
    D{0,1} = jmp_d{0, 1}
    dword_804e044 = dword_85f717c
    dword_804e04c = dword_85f7184

    ; set execution flag
    on = 1
}

mov R3, [fp-19*4]
if (on)
{
    mov R3, [R3]
    mov R2, [fp-37*4]
    add R2, R3
    mov R1, [fp-18*4]
    add R3, R1
    mov R0, byte [R3]
    mov R3, R0
    xor R3, 0x53
    sub R3, 3
    xor R3, 0x33
    mov R0, R3
    mov [R2], R0
}

Since, the target contains 0x88048744 which is not 0x8804bb37, none of the instructions in the if enclosed by on is executed.

At 0x0804C2D4, we have another branch check

if (target == 0x8804C2D4)
{
    RESTORE_REGS()
    on = 1
}

    mov R3, [fp-19*4]

if (on)
{
    add R3, 1
    mov [fp-19*4], R3
    mov R3, [fp-19*4]
    setc
    sbb R3, 0x47
    mov branch_temp, 0x8804bb37
}

alu_false contains 1 at index 0, and 0 at the remaining indices. So, this sets the complement of the Carry flag.
ZeroFlag is evaluated as a NOR logic, i.e., ZF = !(alu_s[0] | alu_s[1] | alu_s[2] | alu_s[3])

alu_b7 is an array of 256 dwords, the first 128 are zero, and the rest are 1. Indexing into this array determines the Sign bit (bit 7) of the index.

Okay, so alu_cmp_of represents a truth table. Of what ? Well, there are only two out of the eight minterms set. So, we get the following SOP

x'ys + xy's'

Where x, y, s are the sign bits of alu_x, alu_y, alu_z.
Cool ! This is the overflow flag

It xor’s SignFlag and OverflowFlag and sets target to branch_temp which is 0x8804bb37. By x0ring the sign and overflow flags we get the LessThan flag.

So, if R3 is less than 0x47, the target is set to 0x8804bb37.
Then we have the following

mov byte [fp-0x4d], 0
if (target == 0x8804CA3B)
{
    on = 1
}
if (on)
{
    mov esp, fp
    mov D1, [esp]
    mov dword_804e04c, [esp+4]
    sub esp, 4*2
    mov eax, [esp]
    sub esp, 4
    mov F1, eax
    mov eax, [esp]
    sub esp, 4
    mov R3, eax
    mov eax, [esp]
    sub esp, 4
    mov R2, eax
    mov eax, [esp]
    sub esp, 4
    mov R1, eax
    mov eax, [esp]
    sub esp, 4
    mov fp, eax
    mov eax, [esp]
    sub esp, 4
    mov branch_temp, eax
    mov target, branch_temp
    on = 0
}

A SIGILL is executed which causes the control to jump to master loop. And the execution of the instructions are skipped until the address the control reaches at 0x804bb37

So, this is basically a while loop.

Wow !!

The control first compares R3 with 0x47 and branches to 0x804bb37 while R3 is less than 0x47. When the condition becomes false, it executes from 0x804ca3b

Algorithm

So, the logic is

int main()
{
    int i = 0;
    char arr[] = { 26, 25, 11, 49, 6, 4, 24, 16, 10, 51, 25, 10, 51, 0, 10, 60, 25, 13, 6, 25, 60, 14, 16, 60, 16, 12, 50, 10, 20, 13, 6, 25, 60, 25, 6, 51, 4, 10, 51, 25, 14, 6, 49, 49, 30, 60, 23, 10, 49, 6, 25, 10, 9, 60, 25, 12, 60, 25, 13, 10, 60, 0, 13, 6, 49, 49, 10, 51, 4, 10, 2 };

    for (i = 0; i < 0x47; ++i)
    {
        arr[i] = (arr[i]^0x53)-3 ^ 0x33;
    }
}

Executing the above code, yields the flag - utflag{sentence_that_is_somewhat_tangentially_related_to_the_challenge}

 

Sursa: https://x0r19x91.github.io/2019/utctf-mov

[u0m3]

La ce nivel au ajuns unii... Sa reproduci instructiuni prin mov...

[Nytro]

Da, mov (dar si alte instructiuni) sunt Turing complete.