Throughout my journey in learning malware analysis, I discovered that one essential skill for a Malware Analyst is recognizing C code constructs in assembly. This includes identifying generic data structures, arrays, linked lists, and trees. In this article, I will share my walkthrough of solving the sixth phase of the "The Most Important Assembly Exercise You'll Ever Do: Binary Bomb Lab" advised to be done in OST2 Architecture 1001: x86-64 Assembly.
This challenge involves reverse engineering linked lists and their operations, including creating, linking, and comparing nodes, as well as recognizing if statements and loop constructs.
Linked List
A linked list is a data structure that consists of a sequence of nodes, and each node includes a field that contains a reference to the next node in the sequence. The main advantage of using a linked list over an array is that the order of the linked nodes can differ from the order in which the data items are in memory or disk. Therefore, linked lists allow the insertion and removal of nodes at any point in the list.
Node Assertion
For learning and debugging purposes, the following C code example of a linked list, its assertion and traversal. Our linked list consists of a series of node structures named newnode, and it's manipulated by 2 functions :
insertNode() : is using "if statement", "loop" and "Struct" code constructs.
printNode() : is using only "loop" and "Struct" code constructs.
The insertion function create nodes and fill them with data and the print function iterates over all the nodes and prints their contents.
#include<stdio.h>#include<stdlib.h>typedefstruct Node{int data;struct Node* next;}Node;Node* head =NULL;voidinsertNode(int value){ Node* newnode =NULL; Node* current =NULL; newnode = (Node*)malloc(sizeof(Node));newnode->data = value;if (head ==NULL) { head = newnode;newnode->next =NULL; }else { current = head;while (current->next!=NULL) { current =current->next; }current->next = newnode;newnode->next =NULL; }}voidprintNodeValue(){ Node* temp = head;int i =1;while (temp!=NULL) {printf("Value of Node:%d is:%d\n",i,temp->data); temp =temp->next;++i; }}intmain(){insertNode(1);insertNode(2);insertNode(3);insertNode(4);insertNode(5);insertNode(6);printNodeValue();return0;}
The best way to dissect the related disassembly is to identify the main C code constructs used on this program starting from main function. Recognizing these constructs makes the analysis easier.
Disassembly
I will explain the main parts of the disassembly related to the insertNode() function of the executable.
At points 1 and 2, since the newnode struct is a local variable, its base address will be stack-based. Thus, rax holds the base address of the structure. At point 3, Offset 0x0 stores the integer value within the struct, and ecx corresponds to the value argument. At point 4, the compare statement before a conditional jump indicates an if statement construct. If the zero flag (ZF) is set to 1, it means we are creating the first node; consequently, the head will contain the base address of this first node. As mentioned at point 5 in the disassembly, the next member of the newnode, located at offset 0x8, will point to NULL. Otherwise, if the zero flag (ZF) is set to 0, we will enter a while loop construct, which is similar to a for loop but lacks an increment section. At point 6, a conditional jump occurs followed by an unconditional jump. The only way for this code to stop execution is for the conditional jump to be taken. At point 7, we observe from point 8 that the object var_E8 contains a pointer that references another object of the same type. At point 9, we ensure that the next member of the last node always points to NULL.
The same approach can be adopted to recognized code constructs used in printNode() function:
We should realise that temp is assigned eax, which comes from [rax+8] , which itself came from a previous assignment of temp. This means that whatever struct temp is must contain a pointer 8bytes into it (x64 architecture). This points to another struct that must also contain a pointer 8 bytes into another struct and so on.
Diffusing Phase 6
By relying on the knowledge previously acquired, especially recognizing C code constructs and understanding the code's higher-level operations, we will be able to defuse this phase using Windbg.
The disassembly for phase_6() is long enough to be explained in a single shot. Let’s look disassembly for phase_6() (uf phase_6) then focus on the main parts which will lead us to diffuse the bomb.
Our input string is loaded into the rcx register then there is a strange reference to a bomb!node1 that gets loaded into the stack space mov qword ptr [rbp+8],rax) .That made me very curious to display what stored in bomb!node1 :
The list is terminated with a null next pointer. So far so good, the values of the list are known so it's appropriate to resume walking the body of phase_6().
As far as we're reaching our goal, we're going to generate a pseudocode for each part:
struct Node {int value;int index;struct Node *next;};voidphase_6(constchar* input){struct Node* list = ..... // Generated linked list of 6 nodesstruct Node* head = list;int nums[6];read_six_numbers (input, nums);}
Verify the input values
After some debugging I came up with this code where I tried to make it more simple and understand what the code is doing by recognizing if statement, for loops, and array constructs :
Collect the addresses of the nodes and store them in an array of type Node based on user input. Each node has an index corresponding to the input values. For example, if the user enters "1 2 3 4 5 6," the array will store the addresses of the nodes in the order of their respective offsets. The disassembly part responsible for this :
00007ff614da269e:
mov dword ptr [rbp+0C4h],0 // counter
jmp bomb!phase_6+0x108 (00007ff7180626b8)
00007ff7180626aa:
mov eax,dword ptr [rbp+0C4h]
inc eax
mov dword ptr [rbp+0C4h], eax
00007ff7180626b8:
if (dword ptr [rbp+0C4h] >= 6)
{
jmp 00007ff718062716 // end of loop
}
mov rax,qword ptr [rbp+8] // save head into rax
mov qword ptr [rbp+28h],rax // save head into rbp+28=current
mov dword ptr [rbp+0E4h],1
jmp 00007ff7180626e3
00007ff7180626d5:
mov eax,dword ptr [rbp+0E4h]
inc eax
mov dword ptr [rbp+0E4h],eax
00007ff7180626e3:
movsxd rax,dword ptr [rbp+0C4h] // rax=0
mov eax,dword ptr [rbp+rax*4+48h] // eax = input[0]
if (dword ptr [rbp+0E4h] >= eax) //
{
jmp 00007ff718062704 // go and store the node address
}
mov rax,qword ptr [rbp+28h] // save current into rax
mov rax,qword ptr [rax+8]
mov qword ptr [rbp+28h],rax // save current=current->next
jmp 00007ff7180626d5
00007ff718062704:
movsxd rax,dword ptr [rbp+0C4h]
mov rcx,qword ptr [rbp+28h] // save address of node
mov qword ptr [rbp+rax*8+78h],rcx // save the address of 3rd node
jmp 00007ff7180626aa
I will explain this part in details:
Initialization:
mov dword ptr [rbp+0C4h],0: Initializes a counter at rbp+0C4h to 0.
jmp bomb!phase_6+0x108 (00007ff7180626b8): Jumps to the main loop.
Main Loop:
Increment Counter:
mov eax,dword ptr [rbp+0C4h]
inc eax
mov dword ptr [rbp+0C4h], eax: Increments the counter.
Check Counter:
if (dword ptr [rbp+0C4h] >= 6): Checks if the counter is 6 or more. If true, jumps to the end of the loop (00007ff718062716)
Save Head Node:
mov rax,qword ptr [rbp+8]: Loads the head node address into rax.
mov qword ptr [rbp+28h],rax: Saves the head node address at current variablerbp+28.
mov dword ptr [rbp+0E4h],1: Initializes another counter at rbp+0E4h to 1.
jmp 00007ff7180626e3: Jumps to the nested loop.
Nested Loop:
Increment Counter:
mov eax,dword ptr [rbp+0E4h]
inc eax
mov dword ptr [rbp+0E4h],eax: Increments the nested loop counter.
Check Value:
movsxd rax,dword ptr [rbp+0C4h]: Sign-extends rbp+0C4h to rax.
mov eax,dword ptr [rbp+rax*4+48h]: Loads the input value into eax.
if (dword ptr [rbp+0E4h] >= eax): Compares the nested loop counter with the input value. If true, jumps to 00007ff718062704.
Update Node Address:
mov rax,qword ptr [rbp+28h]: Loads the current node address into rax.
mov rax,qword ptr [rax+8]: Loads current->next into rax.
mov qword ptr [rbp+28h],rax: current = current->next
jmp 00007ff7180626d5: Jumps back to increment the nested loop counter.
Store Node Address:
00007ff718062704:
movsxd rax,dword ptr [rbp+0C4h]: Sign-extends rbp+0C4h to rax.
mov rcx,qword ptr [rbp+28h]: Loads the current node address into rcx.
mov qword ptr [rbp+rax*8+78h],rcx: Stores the current node address into the array.
jmp 00007ff7180626aa: Jumps back to increment the main loop counter.
Below is the pseudocode I made for this part:
struct Node* nodes[6] = {0};for (i =0 ; i <6; ++i) { current = head;while (current) {if (current->index == nums[i]) { nodes[i] = current;break; } current =current ->next; } }
Reorder the original linked list:
While debugging, I tested the input "3 1 4 2 6 5," and the corresponding node addresses were stored at rbp+74h.
current = head;for (i =0; i <5; ++i)if (current->value < current->next->value)explode_bomb ();
Ordering them in descending mode 5 4 3 1 6 2 . Let’s try this sequence of input:
Full pseudocode Code
struct Node {int value;int index;struct Node *next;};voidphase_6(constchar* input){struct Node* list = .....; // Generated linked list of 6 nodesstruct Node* current;struct Node* head = list;int nums[6] = {0};struct Node* nodes[6] = {0};int i =0;read_six_numbers(input, nums);for (i =0; i <6; ++i) {if (nums[i] <1|| nums[i] >6) {explode_bomb(); }for (int j = i +1; j <6; ++j) {if (nums[i] == nums[j]) {explode_bomb(); } } }for (i =0; i <6; ++i) { current = head;while (current) {if (current->index == nums[i]) { nodes[i] = current;break; } current =current->next; } } i =1; head = nodes[0]; current = head;while (i <=5) {current->next = nodes[i]; current =current->next;++i; }current->next =NULL; current = head;for (i =0; i <5; ++i) {if (current->value <current->next->value) {explode_bomb(); } }}
Epilogue
This challenge required reverse engineering a linked list, including its operations such as creating, linking, and comparing nodes, as well as dealing with nested loops, if-else conditions, arrays, and struct code constructs. I thoroughly enjoyed working on this challenge as it really engaged my mind.
