Software Reverse Engineering: Diffusing Phase 6

Baby, I hate little secrets you keep from me x_x

The article continues the previous one where we diffused phase 5 of bomb binary. Let’s get started with diffusing the last one, phase 6 on Linux platform using GNU Gdb.

This writeup is a part of the article series —

• Software Reverse Engineering: Ripping Apart Bomb Binary (Windbg: Windows)
• Software Reverse Engineering: Diffusing Phase 1(GNU GDB: Linux)
• Software Reverse Engineering: Diffusing Phase 2 (Windbg: Windows)
• Software Reverse Engineering: Diffusing Phase 3 (Windbg: Windows)
• Software Reverse Engineering: Diffusing Phase 4 (Windbg: Windows)
• Software Reverse Engineering: Diffusing Phase 5 (Windbg: Windows)
• Software Reverse Engineering: Diffusing Phase 6 (GNU GDB: Linux)

Rescue Mission: Phase_6

The disassembly for phase_6() is unsurprisingly long enough to be explained in a single shot. Let’s look disassembly for phase_6() (diass phase_6) to gain a broader coverage and subsequently digging into smaller fragments to gain clarity.

0x000055555555585b <+0>: endbr64             ; CET instruction
; callee saved regs
0x000055555555585f <+4>: push   %r14         
0x0000555555555861 <+6>: push   %r13
0x0000555555555863 <+8>: push   %r12
0x0000555555555865 <+10>: push   %rbp
0x0000555555555866 <+11>: push   %rbx
; stack cookie trying to cover from stack corruption just in case
0x000055555555586b <+16>: mov    %fs:0x28,%rax   
0x0000555555555874 <+25>: mov    %rax,0x58(%rsp)  
0x0000555555555879 <+30>: xor    %eax,%eax
; read_six_numbers() taking input on top of stack
0x000055555555587b <+32>: mov    %rsp,%r13        
0x000055555555587e <+35>: mov    %r13,%rsi       
0x0000555555555881 <+38>:  call  0x555555555c11 <read_six_numbers>
...
0x0000555555555891 <+54>:  call  0x555555555be5 <explode_bomb>
...
0x00005555555558aa <+79>:  call  0x555555555be5 <explode_bomb>
...
0x00005555555558e0 <+133>: lea  0x3919(%rip),%rdx  # <node1>
0x00005555555558e7 <+140>: cmp   $0x1,%ecx
...
0x000055555555595a <+255>: call  0x555555555be5 <explode_bomb>
...
(more disassembly here)

Function prologue shows compiler saving registers (callee-saved registers RBP, RBX, r12-r15 pushed onto the stack) for their use in this function, stack canary being placed, calling read_six_numbers(const char *ips, int *nums); which expects 6 integers as input placing them on top of stack and a few calls to explode_bomb() which we need to avoid. read_six_numbers() is the same routine that we reversed while diffusing phase 2. Apart from that there is a symbol node1 which indicates that the program probably uses some sort of aggregate data type (like linked list, hash table, tree, graph etc.). Let’s analyze this function in smaller fragments. Below is the pseudocode for this prologue.

void phase_6 (const char *ips) {
    int nums[6];
    read_six_numbers (ips, nums);
...
}

First fragment of phase_6

First approach to this output was to deduce which of the callee saved registers was used for what purposes. I guess stepping through the below disassembly is the quickest way to infer this.

Iterative comparison among integer input

After stepping through the code and tracing some values, I could infer the following —

• registers RSP, RSI, R13, R12 and RBP point to the top of the stack.
• RBX and R14d are used as counters.

Below is the pseudocode I crafted for this fragment —

// Variable i   is r14d
// Variable ptr is r13
// Variable j   is ebx
int *ptr = &nums[0], i = 1;
while ((unsigned int )(*ptr - 1) <= 5) {    // phase_6+94
    if (i > 5) {     // termination condition for this loop: r14d
         // phase_6+120
         ....
    }
    // duplicate integer check
    for (int j = i /* ebx = r14d */; j <= 5; ++j) {            '
        if (*ptr == nums[j]) {
             explode_bomb ();
        }        
    }                
    ++i;        // ++r14d
    ++ptr;      // (r13 += 4) modification expression for loop
    explode_bomb();
}

Yeah, we now encountered nested loops !

The outer while loop iterates over the user supplied integers ensuring that the each of the input integer is in range [0–6] while the inner for loop ensures that there is no duplicate number supplied by user. Value of i is incremented to till 5 until which it checks for duplicate integers, but what’s after that ?

Cheers to more !

Using same approach, we deduce the purpose of some registers by tracing them while stepping through each instruction.

reversing data structure in phase_6

This snippet of code seems to be working on a liked list where —

• RSI is index into nodes[]
• EAX is count.
• ECX is current number from input integers.
• RDX points to the current node.

for (int rsi = 0 ; rsi != 6; ++rsi) {
    ecx = nums[rsi];    // user-supplied integer
    eax = 1;            // count
    rdx = head_node;    // initially points to the head node element
    if (ecx > 1) {
        do {                // phase_6+145
            rdx = rdx->next;
            ++eax;
        } while (ecx != eax);
    }
// store it into nodes[] array (on stack)
nodes[rsi] = rdx;
++rsi;
}
// link all nodes on stack (create a linked list)
nodes[0]->next = nodes[1];
nodes[1]->next = nodes[2]
nodes[2]->next = nodes[3];
nodes[3]->next = nodes[4];
nodes[4]->next = nodes[5];
nodes[5]->next = 0;

Logically, the initial loop creates list nodes by iterating over the user supplied integers (nums[]) and subsequently putting it onto the allocated memory in stack segment (i.e. at nodes[] array). It then links all nodes together to form a linked list of user supplied integers (see phase_6+171).

A node structure is —

struct node {    
    int data;           // ???? this is getting compared for checks
    int num;
    struct node *next;
}

So far, so good !

Let’s look at the remaining disassembly

After linking all nodes, let’s examine our how our nodes look like.

(gdb) until *phase_6+171
(gdb) x/10xg $rsp
0x7fffffffdf90: 0x0000000200000001 0x0000000400000003
0x7fffffffdfa0: 0x0000000600000005 0x0000000000000000
0x7fffffffdfb0: 0x0000555555559200 0x0000555555559210
0x7fffffffdfc0: 0x0000555555559220 0x0000555555559230
0x7fffffffdfd0: 0x0000555555559240 0x0000555555559110

As we change the order of our input, we see the change in arrangement of these nodes which would are linked accordingly.

(gdb) until *phase_6+171
(gdb) x/10xg $rsp
0x7fffffffdf90: 0x0000000400000005 0x0000000100000003
0x7fffffffdfa0: 0x0000000600000002 0x0000000000000000
0x7fffffffdfb0: 0x0000555555559240 0x0000555555559230
0x7fffffffdfc0: 0x0000555555559220 0x0000555555559200
0x7fffffffdfd0: 0x0000555555559210 0x0000555555559110

data values in each node

It seems that every number we enter from 1–6 is having predefined value for ‘data’ member. The data member of struct node is a value which we do NOT control but the order of arrangement of nodes is what we can control here, nodes should be created in descending order of their values stored in data member.

The instruction at phase_6+251 compares the value of in current node to that in the next node pointed to by the current node. It expects a descending order of their data value. If not given, the bomb explodes !

0x0000555555555950 <+245>: mov    0x8(%rbx),%rax
0x0000555555555954 <+249>: mov    (%rax),%eax
0x0000555555555956 <+251>: cmp    %eax,(%rbx)

Here are the values associated with each user input number:

1: 0x212
2: 0x1c2
3: 0x215
4: 0x393
5: 0x3a7
6: 0x200

Ordering them in from largest to smallest we get — 5 4 3 1 6 2 . Let’s try this sequence of input.

phase_6 diffused x_x

Pseudocode for phase_6()

Pseudocode for phase_6()

Epilogue

This challenge involved reverse engineering linked list (as well as its operations including creating, linking and comparing nodes) , nested loops and if-else code constructs. We also had to deal with understanding mathematical expressions, pointer arithemetic and deducing the usage of callee saved registers by tracing code flow. This is it for the night gentlemen, I guess we just saved the world !

Cheers,
Abhinav Thakur
(a.k.a compilepeace)

Connect on Linkedin