Binary Bomb Lab :: Phase 6
Prologue
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>
typedef struct Node{
int data;
struct Node* next;
}Node;
Node* head = NULL;
void insertNode(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;
}
}
void printNodeValue()
{
Node* temp = head;
int i = 1;
while (temp!=NULL)
{
printf("Value of Node:%d is:%d\n",i,temp->data);
temp = temp->next;
++i;
}
}
int main()
{
insertNode(1);
insertNode(2);
insertNode(3);
insertNode(4);
insertNode(5);
insertNode(6);
printNodeValue();
return 0;
}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 8 bytes 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.
0:000> uf phase_6
bomb!phase_6
284 00007ff7`180625b0 48894c2408 mov qword ptr [rsp+8],rcx
284 00007ff7`180625b5 55 push rbp
284 00007ff7`180625b6 57 push rdi
284 00007ff7`180625b7 4881ece8010000 sub rsp,1E8h
284 00007ff7`180625be 488d6c2420 lea rbp,[rsp+20h]
284 00007ff7`180625c3 488bfc mov rdi,rsp
284 00007ff7`180625c6 b97a000000 mov ecx,7Ah
284 00007ff7`180625cb b8cccccccc mov eax,0CCCCCCCCh
284 00007ff7`180625d0 f3ab rep stos dword ptr [rdi]
284 00007ff7`180625d2 488b8c2408020000 mov rcx,qword ptr [rsp+208h]
284 00007ff7`180625da 488b0577d10000 mov rax,qword ptr [bomb!_security_cookie (00007ff7`1806f758)]
284 00007ff7`180625e1 4833c5 xor rax,rbp
284 00007ff7`180625e4 488985b8010000 mov qword ptr [rbp+1B8h],rax
15732480 00007ff7`180625eb 488d0d183a0100 lea rcx,[bomb!_NULL_IMPORT_DESCRIPTOR <PERF> (bomb+0x2600a) (00007ff7`1807600a)]
15732480 00007ff7`180625f2 e8f6edffff call bomb!ILT+1000(__CheckForDebuggerJustMyCode) (00007ff7`180613ed)
286 00007ff7`180625f7 488d0552ca0000 lea rax,[bomb!node1 (00007ff7`1806f050)]
286 00007ff7`180625fe 48894508 mov qword ptr [rbp+8],rax
292 00007ff7`18062602 488d5548 lea rdx,[rbp+48h]
292 00007ff7`18062606 488b8de0010000 mov rcx,qword ptr [rbp+1E0h]
292 00007ff7`1806260d e8c0eaffff call bomb!ILT+205(read_six_numbers) (00007ff7`180610d2)
295 00007ff7`18062612 c785c400000000000000 mov dword ptr [rbp+0C4h],0
295 00007ff7`1806261c eb0e jmp bomb!phase_6+0x7c (00007ff7`1806262c) Branch
bomb!phase_6+0x6e
295 00007ff7`1806261e 8b85c4000000 mov eax,dword ptr [rbp+0C4h]
295 00007ff7`18062624 ffc0 inc eax
295 00007ff7`18062626 8985c4000000 mov dword ptr [rbp+0C4h],eax
bomb!phase_6+0x7c
295 00007ff7`1806262c 83bdc400000006 cmp dword ptr [rbp+0C4h],6
295 00007ff7`18062633 7d69 jge bomb!phase_6+0xee (00007ff7`1806269e) Branch
bomb!phase_6+0x85
296 00007ff7`18062635 486385c4000000 movsxd rax,dword ptr [rbp+0C4h]
296 00007ff7`1806263c 837c854801 cmp dword ptr [rbp+rax*4+48h],1
296 00007ff7`18062641 7c0e jl bomb!phase_6+0xa1 (00007ff7`18062651) Branch
bomb!phase_6+0x93
296 00007ff7`18062643 486385c4000000 movsxd rax,dword ptr [rbp+0C4h]
296 00007ff7`1806264a 837c854806 cmp dword ptr [rbp+rax*4+48h],6
296 00007ff7`1806264f 7e05 jle bomb!phase_6+0xa6 (00007ff7`18062656) Branch
bomb!phase_6+0xa1
297 00007ff7`18062651 e860edffff call bomb!ILT+945(explode_bomb) (00007ff7`180613b6)
bomb!phase_6+0xa6
299 00007ff7`18062656 8b85c4000000 mov eax,dword ptr [rbp+0C4h]
299 00007ff7`1806265c ffc0 inc eax
299 00007ff7`1806265e 8985e4000000 mov dword ptr [rbp+0E4h],eax
299 00007ff7`18062664 eb0e jmp bomb!phase_6+0xc4 (00007ff7`18062674) Branch
bomb!phase_6+0xb6 [
299 00007ff7`18062666 8b85e4000000 mov eax,dword ptr [rbp+0E4h]
299 00007ff7`1806266c ffc0 inc eax
299 00007ff7`1806266e 8985e4000000 mov dword ptr [rbp+0E4h],eax
bomb!phase_6+0xc4 [
299 00007ff7`18062674 83bde400000006 cmp dword ptr [rbp+0E4h],6
299 00007ff7`1806267b 7d1f jge bomb!phase_6+0xec (00007ff7`1806269c) Branch
bomb!phase_6+0xcd
300 00007ff7`1806267d 486385c4000000 movsxd rax,dword ptr [rbp+0C4h]
300 00007ff7`18062684 48638de4000000 movsxd rcx,dword ptr [rbp+0E4h]
300 00007ff7`1806268b 8b4c8d48 mov ecx,dword ptr [rbp+rcx*4+48h]
300 00007ff7`1806268f 394c8548 cmp dword ptr [rbp+rax*4+48h],ecx
300 00007ff7`18062693 7505 jne bomb!phase_6+0xea (00007ff7`1806269a) Branch
bomb!phase_6+0xe5
301 00007ff7`18062695 e81cedffff call bomb!ILT+945(explode_bomb) (00007ff7`180613b6)
bomb!phase_6+0xea
302 00007ff7`1806269a ebca jmp bomb!phase_6+0xb6 (00007ff7`18062666) Branch
bomb!phase_6+0xec
303 00007ff7`1806269c eb80 jmp bomb!phase_6+0x6e (00007ff7`1806261e) Branch
bomb!phase_6+0xee
306 00007ff7`1806269e c785c400000000000000 mov dword ptr [rbp+0C4h],0
306 00007ff7`180626a8 eb0e jmp bomb!phase_6+0x108 (00007ff7`180626b8) Branch
bomb!phase_6+0xfa
306 00007ff7`180626aa 8b85c4000000 mov eax,dword ptr [rbp+0C4h]
306 00007ff7`180626b0 ffc0 inc eax
306 00007ff7`180626b2 8985c4000000 mov dword ptr [rbp+0C4h],eax
bomb!phase_6+0x108
306 00007ff7`180626b8 83bdc400000006 cmp dword ptr [rbp+0C4h],6
306 00007ff7`180626bf 7d55 jge bomb!phase_6+0x166 (00007ff7`18062716) Branch
bomb!phase_6+0x111
307 00007ff7`180626c5 48894528 mov qword ptr [rbp+28h],rax
308 00007ff7`180626c9 c785e400000001000000 mov dword ptr [rbp+0E4h],1
308 00007ff7`180626d3 eb0e jmp bomb!phase_6+0x133 (00007ff7`180626e3) Branch
bomb!phase_6+0x125
308 00007ff7`180626d5 8b85e4000000 mov eax,dword ptr [rbp+0E4h]
308 00007ff7`180626db ffc0 inc eax
308 00007ff7`180626dd 8985e4000000 mov dword ptr [rbp+0E4h],eax
bomb!phase_6+0x133
308 00007ff7`180626e3 486385c4000000 movsxd rax,dword ptr [rbp+0C4h]
308 00007ff7`180626ea 8b448548 mov eax,dword ptr [rbp+rax*4+48h]
308 00007ff7`180626ee 3985e4000000 cmp dword ptr [rbp+0E4h],eax
308 00007ff7`180626f4 7d0e jge bomb!phase_6+0x154 (00007ff7`18062704) Branch
bomb!phase_6+0x146
309 00007ff7`180626f6 488b4528 mov rax,qword ptr [rbp+28h]
309 00007ff7`180626fa 488b4008 mov rax,qword ptr [rax+8]
309 00007ff7`180626fe 48894528 mov qword ptr [rbp+28h],rax
309 00007ff7`18062702 ebd1 jmp bomb!phase_6+0x125 (00007ff7`180626d5) Branch
bomb!phase_6+0x154
310 00007ff7`18062704 486385c4000000 movsxd rax,dword ptr [rbp+0C4h]
310 00007ff7`1806270b 488b4d28 mov rcx,qword ptr [rbp+28h]
310 00007ff7`1806270f 48894cc578 mov qword ptr [rbp+rax*8+78h],rcx
311 00007ff7`18062714 eb94 jmp bomb!phase_6+0xfa (00007ff7`180626aa) Branch
bomb!phase_6+0x166
313 00007ff7`18062716 b808000000 mov eax,8
313 00007ff7`1806271b 486bc000 imul rax,rax,0
313 00007ff7`1806271f 488b440578 mov rax,qword ptr [rbp+rax+78h]
313 00007ff7`18062724 48894508 mov qword ptr [rbp+8],rax
314 00007ff7`18062728 488b4508 mov rax,qword ptr [rbp+8]
314 00007ff7`1806272c 48894528 mov qword ptr [rbp+28h],rax
316 00007ff7`18062730 c785c400000001000000 mov dword ptr [rbp+0C4h],1
316 00007ff7`1806273a eb0e jmp bomb!phase_6+0x19a (00007ff7`1806274a) Branch
bomb!phase_6+0x18c
316 00007ff7`1806273c 8b85c4000000 mov eax,dword ptr [rbp+0C4h]
316 00007ff7`18062742 ffc0 inc eax
316 00007ff7`18062744 8985c4000000 mov dword ptr [rbp+0C4h],eax
bomb!phase_6+0x19a
316 00007ff7`1806274a 83bdc400000006 cmp dword ptr [rbp+0C4h],6
316 00007ff7`18062751 7d22 jge bomb!phase_6+0x1c5 (00007ff7`18062775) Branch
bomb!phase_6+0x1a3
317 00007ff7`18062753 486385c4000000 movsxd rax,dword ptr [rbp+0C4h]
317 00007ff7`1806275a 488b4d28 mov rcx,qword ptr [rbp+28h]
317 00007ff7`1806275e 488b44c578 mov rax,qword ptr [rbp+rax*8+78h]
317 00007ff7`18062763 48894108 mov qword ptr [rcx+8],rax
318 00007ff7`18062767 488b4528 mov rax,qword ptr [rbp+28h]
318 00007ff7`1806276b 488b4008 mov rax,qword ptr [rax+8]
318 00007ff7`1806276f 48894528 mov qword ptr [rbp+28h],rax
319 00007ff7`18062773 ebc7 jmp bomb!phase_6+0x18c (00007ff7`1806273c) Branch
bomb!phase_6+0x1c5
320 00007ff7`18062775 488b4528 mov rax,qword ptr [rbp+28h]
320 00007ff7`18062779 48c7400800000000 mov qword ptr [rax+8],0
323 00007ff7`18062781 488b4508 mov rax,qword ptr [rbp+8]
323 00007ff7`18062785 48894528 mov qword ptr [rbp+28h],rax
324 00007ff7`18062789 c785c400000000000000 mov dword ptr [rbp+0C4h],0
324 00007ff7`18062793 eb0e jmp bomb!phase_6+0x1f3 (00007ff7`180627a3) Branch
bomb!phase_6+0x1e5
324 00007ff7`18062795 8b85c4000000 mov eax,dword ptr [rbp+0C4h]
324 00007ff7`1806279b ffc0 inc eax
324 00007ff7`1806279d 8985c4000000 mov dword ptr [rbp+0C4h],eax
bomb!phase_6+0x1f3
324 00007ff7`180627a3 83bdc400000005 cmp dword ptr [rbp+0C4h],5
324 00007ff7`180627aa 7d25 jge bomb!phase_6+0x221 (00007ff7`180627d1) Branch
bomb!phase_6+0x1fc
325 00007ff7`180627ac 488b4528 mov rax,qword ptr [rbp+28h]
325 00007ff7`180627b0 488b4008 mov rax,qword ptr [rax+8]
325 00007ff7`180627b4 488b4d28 mov rcx,qword ptr [rbp+28h]
325 00007ff7`180627b8 8b00 mov eax,dword ptr [rax]
325 00007ff7`180627ba 3901 cmp dword ptr [rcx],eax
325 00007ff7`180627bc 7d05 jge bomb!phase_6+0x213 (00007ff7`180627c3) Branch
bomb!phase_6+0x20e
326 00007ff7`180627be e8f3ebffff call bomb!ILT+945(explode_bomb) (00007ff7`180613b6)
bomb!phase_6+0x213
328 00007ff7`180627c3 488b4528 mov rax,qword ptr [rbp+28h]
328 00007ff7`180627c7 488b4008 mov rax,qword ptr [rax+8]
328 00007ff7`180627cb 48894528 mov qword ptr [rbp+28h],rax
329 00007ff7`180627cf ebc4 jmp bomb!phase_6+0x1e5 (00007ff7`18062795) Branch
bomb!phase_6+0x221
347 00007ff7`180627d1 488d4de0 lea rcx,[rbp-20h]
347 00007ff7`180627d5 488d15e4990000 lea rdx,[bomb!`string'+0x428 (00007ff7`1806c1c0)]
347 00007ff7`180627dc e899ebffff call bomb!ILT+885(_RTC_CheckStackVars) (00007ff7`1806137a)
347 00007ff7`180627e1 488b8db8010000 mov rcx,qword ptr [rbp+1B8h]
347 00007ff7`180627e8 4833cd xor rcx,rbp
347 00007ff7`180627eb e809eaffff call bomb!ILT+500(__security_check_cookie) (00007ff7`180611f9)
347 00007ff7`180627f0 488da5c8010000 lea rsp,[rbp+1C8h]
347 00007ff7`180627f7 5f pop rdi
347 00007ff7`180627f8 5d pop rbp
347 00007ff7`180627f9 c3 ret
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 :
0:000> dq bomb!node1 L2
00007ff7`1806f050 00000001`00000212 00007ff7`1806f040This give us a hint that we're dealing with a linked list where :
the 1st four bytes represent the value.
the 2nd four bytes represent the index.
the last 8 bytes represent the address of the next node.
Let's assume that the C Node structure looks like:
struct Node {
int value;
int index;
struct Node *next;
}; So I think there is an initial linked list that was created where its head get stored at rbp+8.
I'm going to traverse the linked list manually to collect the values :
0:000> dq 00007ff7`1806f000 LC
00007ff7`1806f000 00000006`00000200 00000000`00000000
00007ff7`1806f010 00000005`000003a7 00007ff7`1806f000
00007ff7`1806f020 00000004`00000393 00007ff7`1806f010
00007ff7`1806f030 00000003`00000215 00007ff7`1806f020
00007ff7`1806f040 00000002`000001c2 00007ff7`1806f030
00007ff7`1806f050 00000001`00000212 00007ff7`1806f040The 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().
The phase_6() can be broken down into 5 part:
Check if the input contains 6 integers
292 00007ff7`18062602 488d5548 lea rdx,[rbp+48h]
292 00007ff7`18062606 488b8de0010000 mov rcx,qword ptr [rbp+1E0h]
292 00007ff7`1806260d e8c0eaffff call bomb!ILT+205(read_six_numbers)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;
};
void phase_6(const char* input)
{
struct Node* list = ..... // Generated linked list of 6 nodes
struct 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 :
mov dword ptr [rbp+0C4h],0 // it's a counter
jmp bomb!phase_6+0x7c (00007ff614da262c)
00007ff71806261e:
mov eax,dword ptr [rbp+0C4h]
inc eax
mov dword ptr [rbp+0C4h],eax
00007ff614da262c:
if (dword ptr [rbp+0C4h] >= 6) // make sure (1 <= input[i] <= 6) and input[i] != input[i+1]
{
jmp 00007ff614da269e //end main loop
}
movsxd rax,dword ptr [rbp+0C4h] // rax = 0
if (dword ptr [rbp+rax*4+48h] < 1) // input[rax] < 1, there is an array with base address stored at rbp+48h
{
jmp bomb!phase_6+0xa1 (00007ff6ec2b2651) // explode
}
movsxd rax,dword ptr [rbp+0C4h] // rax = 0
if (dword ptr [rbp+rax*4+48h] > 6) // input[rax] > 6
{
jmp bomb!phase_6+0xa6 (00007ff6ec2b2656)
}
00007ff6ec2b2656:
mov eax,dword ptr [rbp+0C4h]
inc eax
mov dword ptr [rbp+0E4h],eax // [rbp+0E4h] is a counter
jmp 00007ff614da2674
00007ff614da2674:
if (dword ptr [rbp+0E4h] >= 6)
{
jmp 00007ff6ec2b269c --> jmp bomb!phase_6+0x6e (00007ff71806261e) // end of the sup loop
}
movsxd rax,dword ptr [rbp+0C4h]
movsxd rcx,dword ptr [rbp+0E4h]
mov ecx,dword ptr [rbp+rcx*4+48h]
if (dword ptr [rbp+rax*4+48h] != ecx compare index[rax] != index[rcx]
{
jmp 00007ff6ec2b269a
}
00007ff6ec2b269a:
jmp 00007ff614da2666
00007ff614da2666:
mov eax,dword ptr [rbp+0E4h]
inc eax
mov dword ptr [rbp+0E4h],eax
if (dword ptr [rbp+0E4h] >= 6)
{
jmp 00007ff6ec2b269c --> jmp bomb!phase_6+0x6e (00007ff71806261e)
}
movsxd rax,dword ptr [rbp+0C4h]
movsxd rcx,dword ptr [rbp+0E4h]
mov ecx,dword ptr [rbp+rcx*4+48h]
if (dword ptr [rbp+rax*4+48h] != ecx) compare index[rax] != index[rcx]
{
jmp 00007ff6ec2b269a
}
Below is the pseudocode I made for this part:
//i = dword ptr [rbp+0C4h]
//j = dword ptr [rbp+0E4h]
//num = dword ptr [rbp+48h]
for ( i = 0; i < 6; ++i )
{
if ( nums[i] < 1 || nums[i] > 6 )
explode_bomb();
for ( j = i + 1; j < 6; ++j )
{
if ( nums[i] == nums[j] )
explode_bomb();
}
}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 atrbp+0C4hto 0.jmp bomb!phase_6+0x108 (00007ff7180626b8): Jumps to the main loop.
Main Loop:
Increment Counter:
mov eax,dword ptr [rbp+0C4h]inc eaxmov 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 intorax.mov qword ptr [rbp+28h],rax: Saves the head node address at current variablerbp+28.mov dword ptr [rbp+0E4h],1: Initializes another counter atrbp+0E4hto 1.jmp 00007ff7180626e3: Jumps to the nested loop.
Nested Loop:
Increment Counter:
mov eax,dword ptr [rbp+0E4h]inc eaxmov dword ptr [rbp+0E4h],eax: Increments the nested loop counter.
Check Value:
movsxd rax,dword ptr [rbp+0C4h]: Sign-extendsrbp+0C4htorax.mov eax,dword ptr [rbp+rax*4+48h]: Loads the input value intoeax.if (dword ptr [rbp+0E4h] >= eax): Compares the nested loop counter with the input value. If true, jumps to00007ff718062704.
Update Node Address:
mov rax,qword ptr [rbp+28h]: Loads the current node address intorax.mov rax,qword ptr [rax+8]: Loads current->next intorax.mov qword ptr [rbp+28h],rax: current = current->nextjmp 00007ff7180626d5: Jumps back to increment the nested loop counter.
Store Node Address:
00007ff718062704:movsxd rax,dword ptr [rbp+0C4h]: Sign-extendsrbp+0C4htorax.mov rcx,qword ptr [rbp+28h]: Loads the current node address intorcx.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.
0:000> dq rbp+78h
000000000014fb88 (3)00007ff71806f030 (1)00007ff71806f050
000000000014fb98 (4)00007ff71806f020 (2)00007ff71806f040
000000000014fba8 (6)00007ff71806f000 (5)00007ff71806f01000007ff718062716:
mov eax, 8
imul rax, rax, 0
mov rax,qword ptr [rbp+rax+78h]
mov qword ptr [rbp+8],rax // store first address of the array rbp+74 node 3 // head = node3
mov rax,qword ptr [rbp+8] //
mov qword ptr [rbp+28h],rax // current = head
mov dword ptr [rbp+0C4h],1
jmp bomb!phase_6+0x19a (00007ff71806274a)
00007ff71806273c:
mov eax,dword ptr [rbp+0C4h]
inc eax
mov dword ptr [rbp+0C4h],eax
00007ff71806274a:
if (dword ptr [rbp+0C4h] >= 6)
{
jmp 00007ff718062775
}
movsxd rax,dword ptr [rbp+0C4h] // rax = i
mov rcx,qword ptr [rbp+28h] // rcx = current
mov rax,qword ptr [rbp+rax*8+78h] // rax = nums[i]
mov qword ptr [rcx+8],rax // current->next = nums[i]
mov rax,qword ptr [rbp+28h] // rax = current
mov rax,qword ptr [rax+8] // rax = current->next
mov qword ptr [rbp+28h],rax // current = current->next
jmp 00007ff71806273c
00007ff718062775:
mov rax,qword ptr [rbp+28h] // make sure last node is pointing to NULL
mov qword ptr [rax+8],0
Below is the pseudocode I made for this part:
i = 1;
head= nodes[0];
current= head;
while (i <= 5) {
current->next = nodes[i];
current= current->next;
++i;
}
current->next = 0;Finally, the updated list is checked to ensure that the value elements are arranged in decreasing order:
mov rax, qword ptr [rbp+8] // save new head into rax
mov qword ptr [rbp+28h], rax // current = head
mov dword ptr [rbp+0C4h], 0 // counter
jmp 00007ff7180627a3
00007ff718062795:
mov eax, dword ptr [rbp+0C4h]
inc eax
mov dword ptr [rbp+0C4h], eax
00007ff7180627a3:
if (dword ptr [rbp+0C4h] >= 5)
{
jmp 00007ff7180627d1
}
mov rax, qword ptr [rbp+28h] // rax = current
mov rax, qword ptr [rax+8] // rax = current->next
mov rcx, qword ptr [rbp+28h] // rcx = current
mov eax, dword ptr [rax] // eax = (current->next)->value
if (dword ptr [rcx] >= eax) // (current->value) >= ((current->next)->value)
{
jmp 00007ff7180627c3
}
explode_bomb();
00007ff7180627c3:
mov rax, qword ptr [rbp+28h] // rax = current
mov rax, qword ptr [rax+8] // rax = current->next
mov qword ptr [rbp+28h], rax // current = current->next
jmp 00007ff718062795
Below is the pseudocode I made for this part:
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;
};
void phase_6(const char* input)
{
struct Node* list = .....; // Generated linked list of 6 nodes
struct 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.
References
Last updated