20251031_SysPCA_bomb

Bomb Lab Write-up

The nefarious Dr. Evil has planted a slew of “binary bombs” on our machines. A binary bomb is a program that consists of a sequence of phases. Each phase expects you to type a particular string on stdin. If you type the correct string, then the phase is defused and the bomb proceeds to the next phase. Otherwise, the bomb explodes by printing "BOOM!!!" and then terminating. The bomb is defused when every phase has been defused.
There are too many bombs for us to deal with, so we are giving each student a bomb to defuse. Your mission, which you have no choice but to accept, is to defuse your bomb before the due date. Good luck, and welcome to the bomb squad

In the following explanation, all commands run in gdb will have the prefix gef➤, e.g.

gef➤  x/1s  0x5555555573b5

This is because I work with the GEF extension for the GNU debugger (gdb). Commands without the prefix are run in Bash.

You can stop the debugger at any time, either by stopping the execution (kill) or by exiting the debugger itself (exit).

Examining the program

Before we start with the task, let's first look at the structure of the program:

objdump -d bomb

Which reveals some functions. The most important ones, which can also be seen in the file bomb.c are:

main
phase_1
phase_2
phase_3
func_4
phase_4
phase_5
phase_6
fun_7
secret_phase

Because of the order, we will assume that the first function that will be run is phase_1. Let's start with inspecting it.

Phase 1

Run the debugger:

gdb -ex 'break phase_1' -ex 'break explode_bomb' -ex 'run' -args ./bomb

The breakpoints make sure that the bomb won't surprise us and will stop at phase_1. Let's see what phase 1 does:

gef➤  disas
Dump of assembler code for function phase_1:
=> 0x00005555555555e7 <+0>:	endbr64
   0x00005555555555eb <+4>:	sub    rsp,0x8
   0x00005555555555ef <+8>:	lea    rsi,[rip+0x1b5a]        # 0x555555557150
   0x00005555555555f6 <+15>:	call   0x555555555b16 <strings_not_equal>
   0x00005555555555fb <+20>:	test   eax,eax
   0x00005555555555fd <+22>:	jne    0x555555555604 <phase_1+29>
   0x00005555555555ff <+24>:	add    rsp,0x8
   0x0000555555555603 <+28>:	ret
   0x0000555555555604 <+29>:	call   0x555555555d91 <explode_bomb>
   0x0000555555555609 <+34>:	jmp    0x5555555555ff <phase_1+24>
End of assembler dump.

Clearly, this function runs <strings_not_equal> with the input value and # 0x555555557150. That is probably a string. Let's see what it contains:

gef➤  x/s 0x555555557150
0x555555557150:	"The future will be better tomorrow."

Great. Since <strings_not_equal> jumps to <explode_bomb> if true, we can assume that the first input has to be the same string as 0x555555557150.

input 1

Requires a string that is equal to a hardcoded string, in this case: The future will be better tomorrow.

Phase 2

In order not to have to type the inputs every time, we can write them into a file and then call gdb with the file as argument:

gdb -ex 'break explode_bomb' -ex 'run' -args ./bomb solutions.txt

Let's add a breakpoint at phase_2 and look at the second function:

gef➤ break phase_2
gef➤ disas phase_2

which returns:

0x000055555555560b <+0>:	endbr64
0x000055555555560f <+4>:	push   %rbp
0x0000555555555610 <+5>:	push   %rbx
0x0000555555555611 <+6>:	sub    $0x28,%rsp
0x0000555555555615 <+10>:	mov    %fs:0x28,%rax
0x000055555555561e <+19>:	mov    %rax,0x18(%rsp)
0x0000555555555623 <+24>:	xor    %eax,%eax
0x0000555555555625 <+26>:	mov    %rsp,%rsi
0x0000555555555628 <+29>:	call   0x555555555dd3 <read_six_numbers>
0x000055555555562d <+34>:	cmpl   $0x0,(%rsp)
0x0000555555555631 <+38>:	js     0x55555555563d <phase_2+50>
0x0000555555555633 <+40>:	mov    %rsp,%rbp
0x0000555555555636 <+43>:	mov    $0x1,%ebx
0x000055555555563b <+48>:	jmp    0x555555555650 <phase_2+69>
0x000055555555563d <+50>:	call   0x555555555d91 <explode_bomb>
0x0000555555555642 <+55>:	jmp    0x555555555633 <phase_2+40>
0x0000555555555644 <+57>:	add    $0x1,%ebx
0x0000555555555647 <+60>:	add    $0x4,%rbp
0x000055555555564b <+64>:	cmp    $0x6,%ebx
0x000055555555564e <+67>:	je     0x555555555661 <phase_2+86>
0x0000555555555650 <+69>:	mov    %ebx,%eax
0x0000555555555652 <+71>:	add    0x0(%rbp),%eax
0x0000555555555655 <+74>:	cmp    %eax,0x4(%rbp)
0x0000555555555658 <+77>:	je     0x555555555644 <phase_2+57>
0x000055555555565a <+79>:	call   0x555555555d91 <explode_bomb>
0x000055555555565f <+84>:	jmp    0x555555555644 <phase_2+57>
0x0000555555555661 <+86>:	mov    0x18(%rsp),%rax
0x0000555555555666 <+91>:	sub    %fs:0x28,%rax
0x000055555555566f <+100>:	jne    0x555555555678 <phase_2+109>
0x0000555555555671 <+102>:	add    $0x28,%rsp
0x0000555555555675 <+106>:	pop    %rbx
0x0000555555555676 <+107>:	pop    %rbp
0x0000555555555677 <+108>:	ret
0x0000555555555678 <+109>:	call   0x555555555250 <__stack_chk_fail@plt>

The second phase contains the following line near the top:

call   0x555555555dd3 <read_six_numbers>

When you look at <read_six_numbers> (or guess), it becomes clear that the second input should consist of six numbers.

At <+35>, the function compares and explodes, if the first number is $< 0$ . The rest of the function basically consists of a single loop, from <+57> to <+100>. The loop iterates through all input numbers (which were put on the stack) and checks them against a second condition, which is (<+57> to <+69>):

x_{i + 1} = x_{i} + i

Thus, we have found out the sequence which solves phase_2:

input 2

Input 2 consists of six numbers, $x_{i}, i \in [6]$ with:

x_{k} = x_{1} + \sum_{i = 1}^{k - 1} i, x_{0} \geq 0

One sequence that satisfies this conditions is 0 1 3 6 10 15

Phase 3

0x000055555555567d <+0>:	endbr64
0x0000555555555681 <+4>:	sub    $0x18,%rsp
0x0000555555555685 <+8>:	mov    %fs:0x28,%rax
0x000055555555568e <+17>:	mov    %rax,0x8(%rsp)
0x0000555555555693 <+22>:	xor    %eax,%eax
0x0000555555555695 <+24>:	lea    0x4(%rsp),%rcx
0x000055555555569a <+29>:	mov    %rsp,%rdx
0x000055555555569d <+32>:	lea    0x1d11(%rip),%rsi        # 0x5555555573b5
0x00005555555556a4 <+39>:	call   0x555555555300 <__isoc99_sscanf@plt>
0x00005555555556a9 <+44>:	cmp    $0x1,%eax
0x00005555555556ac <+47>:	jle    0x5555555556cc <phase_3+79>
0x00005555555556ae <+49>:	cmpl   $0x7,(%rsp)
0x00005555555556b2 <+53>:	ja     0x555555555750 <phase_3+211>
0x00005555555556b8 <+59>:	mov    (%rsp),%eax
0x00005555555556bb <+62>:	lea    0x1ade(%rip),%rdx        # 0x5555555571a0
0x00005555555556c2 <+69>:	movslq (%rdx,%rax,4),%rax
0x00005555555556c6 <+73>:	add    %rdx,%rax
0x00005555555556c9 <+76>:	notrack jmp *%rax
0x00005555555556cc <+79>:	call   0x555555555d91 <explode_bomb>
0x00005555555556d1 <+84>:	jmp    0x5555555556ae <phase_3+49>
0x00005555555556d3 <+86>:	mov    $0x43,%eax
0x00005555555556d8 <+91>:	sub    $0x36,%eax
0x00005555555556db <+94>:	add    $0x97,%eax
0x00005555555556e0 <+99>:	sub    $0x212,%eax
0x00005555555556e5 <+104>:	add    $0x212,%eax
0x00005555555556ea <+109>:	sub    $0x212,%eax
0x00005555555556ef <+114>:	add    $0x212,%eax
0x00005555555556f4 <+119>:	sub    $0x212,%eax
0x00005555555556f9 <+124>:	cmpl   $0x5,(%rsp)
0x00005555555556fd <+128>:	jg     0x555555555705 <phase_3+136>
0x00005555555556ff <+130>:	cmp    %eax,0x4(%rsp)
0x0000555555555703 <+134>:	je     0x55555555570a <phase_3+141>
0x0000555555555705 <+136>:	call   0x555555555d91 <explode_bomb>
0x000055555555570a <+141>:	mov    0x8(%rsp),%rax
0x000055555555570f <+146>:	sub    %fs:0x28,%rax
0x0000555555555718 <+155>:	jne    0x55555555575c <phase_3+223>
0x000055555555571a <+157>:	add    $0x18,%rsp
0x000055555555571e <+161>:	ret
0x000055555555571f <+162>:	mov    $0x0,%eax
0x0000555555555724 <+167>:	jmp    0x5555555556d8 <phase_3+91>
0x0000555555555726 <+169>:	mov    $0x0,%eax
0x000055555555572b <+174>:	jmp    0x5555555556db <phase_3+94>
0x000055555555572d <+176>:	mov    $0x0,%eax
0x0000555555555732 <+181>:	jmp    0x5555555556e0 <phase_3+99>
0x0000555555555734 <+183>:	mov    $0x0,%eax
0x0000555555555739 <+188>:	jmp    0x5555555556e5 <phase_3+104>
0x000055555555573b <+190>:	mov    $0x0,%eax
0x0000555555555740 <+195>:	jmp    0x5555555556ea <phase_3+109>
0x0000555555555742 <+197>:	mov    $0x0,%eax
0x0000555555555747 <+202>:	jmp    0x5555555556ef <phase_3+114>
0x0000555555555749 <+204>:	mov    $0x0,%eax
0x000055555555574e <+209>:	jmp    0x5555555556f4 <phase_3+119>
0x0000555555555750 <+211>:	call   0x555555555d91 <explode_bomb>
0x0000555555555755 <+216>:	mov    $0x0,%eax
0x000055555555575a <+221>:	jmp    0x5555555556f9 <phase_3+124>
0x000055555555575c <+223>:	call   0x555555555250 <__stack_chk_fail@plt>

Phase 3 looks quite intimidating, with the length of over 40 lines! However, we quickly notice that most of the function consists of jump statements. At the start, the function scanf is called.

0x000055555555569d <+32>:	lea    0x1d11(%rip),%rsi        # 0x5555555573b5
0x00005555555556a4 <+39>:	call   0x555555555300 <__isoc99_sscanf@plt>

Thankfully, gdb has marked the address which is being passed to scanf:

gef➤  x/1s  0x5555555573b5
0x5555555573b5:	"%d %d"

Now we know that the input for phase_3 consists of two numbers, $a$ and $b$ .

The condition after scanf is $a \leq 7$ :

0x00005555555556ae <+49>:	cmpl   $0x7,(%rsp)
0x00005555555556b2 <+53>:	ja     0x555555555750 <phase_3+211>

The rest of the function can be translated as a switch statement:

004016c9        switch (var_18)
004016d3            case 0
004016d3                rax_6 = 0x43
004016d8            label_4016d8:
004016d8                rax_10 = rax_6 - 0x36
004016d8                goto label_4016db
0040171f            case 1
0040171f                rax_6 = 0
00401724                goto label_4016d8
00401726            case 2
00401726                rax_10 = 0
004016db            label_4016db:
004016db                rax_11 = rax_10 + 0x97
004016db                goto label_4016e0
0040172d            case 3
0040172d                rax_11 = 0
004016e0            label_4016e0:
004016e0                rax_12 = rax_11 - 0x212
004016e0                goto label_4016e5
00401734            case 4
00401734                rax_12 = 0
004016e5            label_4016e5:
004016ef                rax_15 = rax_12 + 0x212
0040173b            case 5
004016ef                rax_15 = 0
00401742            case 6
004016ef                rax_15 = 0x212
00401749            case 7
00401749                rax_15 = 0

And at the end, there is a second condition: $a \leq 5$ . And then, we compare
$b = v a r_15 - 0 x 212$

input 3

the input consists of two numbers $a, b$ , where $0 \leq a \leq 5$ and $b = [switch case number] - 0 x 212$

Phase 4

Phase 4 consists of two functions: phase_4 and func4. Calling

gef➤  disas func4

we notice that func4 is recursive:

Dump of assembler code for function func4:
   0x0000555555555761 <+0>:	    endbr64
   0x0000555555555765 <+4>:	    push   %rbx
   0x0000555555555766 <+5>:	    mov    %edx,%eax
   0x0000555555555768 <+7>:	    sub    %esi,%eax
   0x000055555555576a <+9>:	    mov    %eax,%ebx
   0x000055555555576c <+11>:	shr    $0x1f,%ebx
   0x000055555555576f <+14>:	add    %eax,%ebx
   0x0000555555555771 <+16>:	sar    $1,%ebx
   0x0000555555555773 <+18>:	add    %esi,%ebx
   0x0000555555555775 <+20>:	cmp    %edi,%ebx
   0x0000555555555777 <+22>:	jg     0x55555555577f <func4+30>
   0x0000555555555779 <+24>:	jl     0x55555555578b <func4+42>
   0x000055555555577b <+26>:	mov    %ebx,%eax
   0x000055555555577d <+28>:	pop    %rbx
   0x000055555555577e <+29>:	ret
   0x000055555555577f <+30>:	lea    -0x1(%rbx),%edx
   0x0000555555555782 <+33>:	call   0x555555555761 <func4>
   0x0000555555555787 <+38>:	add    %eax,%ebx
   0x0000555555555789 <+40>:	jmp    0x55555555577b <func4+26>
   0x000055555555578b <+42>:	lea    0x1(%rbx),%esi
   0x000055555555578e <+45>:	call   0x555555555761 <func4>
   0x0000555555555793 <+50>:	add    %eax,%ebx
   0x0000555555555795 <+52>:	jmp    0x55555555577b <func4+26>

What does it do? There are three 4-byte argument registers at the start of the function (%edi, %esi, %edx). Therefore, func4 can be called with three int parameters (we will name them arg1, arg2, arg3). The calculation <+5> until <+20> computes the midpoint between arg2 and arg3, and then a recursion happens based on that value:

long int func4(int arg1, int arg2, int arg3) {
    int mid = (arg2 + arg3) / 2;

    if (mid > arg1)
        mid += func4(arg1, arg2, mid - 1);
    else if (mid < arg1)
        mid += func4(arg1, mid + 1, arg3);
	return mid;
}

With that understood, let's move to phase_4:

gef➤  disas phase_4

Same as in phase_3, this part takes two integers as input (we will call them a and b):

0x00005555555557b7 <+32>:	lea    0x1bf7(%rip),%rsi        # 0x5555555573b5
0x00005555555557be <+39>:	call   0x555555555300 <__isoc99_sscanf@plt>

The condition for a is $a \leq 14$ :

0x00005555555557c8 <+49>:	cmpl   $0xe,(%rsp)
0x00005555555557cc <+53>:	jbe    0x5555555557d3 <phase_4+60>

Then we call the function func4:

0x00005555555557d3 <+60>:	mov    $0xe,%edx
0x00005555555557d8 <+65>:	mov    $0x0,%esi
0x00005555555557dd <+70>:	mov    (%rsp),%edi
0x00005555555557e0 <+73>:	call   0x555555555761 <func4>

Which can be translated to

int ret = func4(a, 0, 14);

The last condition compares two things: $b == 21$ and $r e t == 21$ :

0x00005555555557e5 <+78>:	cmp    $0x15,%eax
0x00005555555557e8 <+81>:	jne    0x5555555557f1 <phase_4+90>
0x00005555555557ea <+83>:	cmpl   $0x15,0x4(%rsp)
0x00005555555557ef <+88>:	je     0x5555555557f6 <phase_4+95>

Now the only difficulty is to find an a so that func(a, 0, 14) == 21.

input 4

The input for phase 4 consists of two integrers $a, b$ ; $b$ must be equal to a hardcoded value, and $a$ has to be chosen s.t. a recursive function $func4 (a, 0, 14) == b$ .

Phase 5

This part of the bomb looks short, but do not let that deceive you - there is quite a lot going on:

0x0000555555555810 <+0>:	endbr64
0x0000555555555814 <+4>:	push   rbx
0x0000555555555815 <+5>:	mov    rbx,rdi
0x0000555555555818 <+8>:	call   0x555555555af5 <string_length>
0x000055555555581d <+13>:	cmp    eax,0x6
0x0000555555555820 <+16>:	jne    0x55555555584e <phase_5+62>
0x0000555555555822 <+18>:	mov    rax,rbx
0x0000555555555825 <+21>:	lea    rdi,[rbx+0x6]
0x0000555555555829 <+25>:	mov    ecx,0x0
0x000055555555582e <+30>:	lea    rsi,[rip+0x198b]        # 0x5555555571c0 <array.0>
0x0000555555555835 <+37>:	movzx  edx,BYTE PTR [rax]
0x0000555555555838 <+40>:	and    edx,0xf
0x000055555555583b <+43>:	add    ecx,DWORD PTR [rsi+rdx*4]
0x000055555555583e <+46>:	add    rax,0x1
0x0000555555555842 <+50>:	cmp    rax,rdi
0x0000555555555845 <+53>:	jne    0x555555555835 <phase_5+37>
0x0000555555555847 <+55>:	cmp    ecx,0x3a
0x000055555555584a <+58>:	jne    0x555555555855 <phase_5+69>
0x000055555555584c <+60>:	pop    rbx
0x000055555555584d <+61>:	ret
0x000055555555584e <+62>:	call   0x555555555d91 <explode_bomb>
0x0000555555555853 <+67>:	jmp    0x555555555822 <phase_5+18>
0x0000555555555855 <+69>:	call   0x555555555d91 <explode_bomb>
0x000055555555585a <+74>:	jmp    0x55555555584c <phase_5+60>

First, we notice that there is an array of length 16:

gef➤  x/16dw 0x5555555571c0
0x5555555571c0 <array.0>:       2	10	6	1
0x5555555571d0 <array.0+16>:	12	16	9	3
0x5555555571e0 <array.0+32>:	4	7	14	5
0x5555555571f0 <array.0+48>:	11	8	15	13

At the start, the function takes an input in the form of a string and checks whether the length is == 6 (<+13>).

After that, it sets up a loop over the 6 bytes of the input

<+37>: movzx reads in the current input byte
<+40>: add masks the last 4 bits of the input byte (we will call them i)
<+43>: this is a tricky line! The second add adds the value of the array from <+30> at the index i to a sum %ecx.

The sum of all array entries has to be 58 at <+55>, otherwise the bomb explodes.

input 5

Expects a string of 6 characters. For each char, we mask the lowest 4 bits, and then sum up the array value at that index. The sum has to be $== 58$ .

In this example, we could use the string aaaaam:

value	index	hex	char
10	1	0x61	a
10	1	0x61	a
10	1	0x61	a
10	1	0x61	a
10	1	0x61	a
8	13	0x6d	m

Phase 6

This is quite a long phase! At the start, we see the now already known function:

0x000055555555588b <+47>:	call   0x555555555dd3 <read_six_numbers>

So, the function takes in 6 arguments $x_{1}, \dots, x_{6}$ .
Further down the list, we see a loop:

18ab:	48 83 c3 01          	add    $0x1,%rbx
18af:	83 fb 05             	cmp    $0x5,%ebx
18b2:	0f 8f a7 00 00 00    	jg     195f <phase_6+0x103>
18b8:	41 8b 44 9d 00       	mov    0x0(%r13,%rbx,4),%eax
18bd:	39 45 00             	cmp    %eax,0x0(%rbp)
18c0:	75 e9                	jne    18ab <phase_6+0x4f>
18c2:	e8 ca 04 00 00       	call   1d91 <explode_bomb>
18c7:	eb e2                	jmp    18ab <phase_6+0x4f>

This loop compares all numbers and makes sure that all number are unique.

1967:	4c 89 f5             	mov    %r14,%rbp
196a:	41 8b 06             	mov    (%r14),%eax
196d:	83 e8 01             	sub    $0x1,%eax
1970:	83 f8 05             	cmp    $0x5,%eax
1973:	0f 87 28 ff ff ff    	ja     18a1 <phase_6+0x45>
1979:	41 83 ff 05          	cmp    $0x5,%r15d
197d:	0f 8f 46 ff ff ff    	jg     18c9 <phase_6+0x6d>

Now we know: Each number $1 \leq x_{1}, \dots, x_{6} \leq 6$ ( $0 \leq x - 1 \leq 5$ ).

#todo finish

entering secret phase

#todo finish

phase 7

Phase 7, the secret phase, consists of two functions: secret_phase and fun7. secret_phase is quite simple:

0x0000555555555a0a <+0>:	endbr64
0x0000555555555a0e <+4>:	push   %rbx
0x0000555555555a0f <+5>:	call   0x555555555e18 <read_line>
0x0000555555555a14 <+10>:	mov    %rax,%rdi
0x0000555555555a17 <+13>:	mov    $0xa,%edx
0x0000555555555a1c <+18>:	mov    $0x0,%esi
0x0000555555555a21 <+23>:	call   0x5555555552e0 <strtol@plt>
0x0000555555555a26 <+28>:	mov    %eax,%ebx
0x0000555555555a28 <+30>:	sub    $0x1,%eax
0x0000555555555a2b <+33>:	cmp    $0x3e8,%eax
0x0000555555555a30 <+38>:	ja     0x555555555a58 <secret_phase+78>
0x0000555555555a32 <+40>:	mov    %ebx,%esi
0x0000555555555a34 <+42>:	lea    0x3715(%rip),%rdi        # 0x555555559150 <n1>
0x0000555555555a3b <+49>:	call   0x5555555559c9 <fun7>
0x0000555555555a40 <+54>:	cmp    $0x2,%eax
0x0000555555555a43 <+57>:	jne    0x555555555a5f <secret_phase+85>
0x0000555555555a45 <+59>:	lea    0x172c(%rip),%rdi        # 0x555555557178
0x0000555555555a4c <+66>:	call   0x555555555220 <puts@plt>
0x0000555555555a51 <+71>:	call   0x555555555f50 <phase_defused>
0x0000555555555a56 <+76>:	pop    %rbx
0x0000555555555a57 <+77>:	ret
0x0000555555555a58 <+78>:	call   0x555555555d91 <explode_bomb>
0x0000555555555a5d <+83>:	jmp    0x555555555a32 <secret_phase+40>
0x0000555555555a5f <+85>:	call   0x555555555d91 <explode_bomb>
0x0000555555555a64 <+90>:	jmp    0x555555555a45 <secret_phase+59>

On line +5 the functions reads a string input, and converts it to a long int on line +23 (see C strtol). We check that the $input - 1 \leq 0 x 3 e 8 = 1000$ (lines +30, +33).

-> The input has to be between 1 and 1001

Then we call the function fun7 with the input and a memory address (line +42). The result of the function has to be equal to $2$ :

0x0000555555555a40 <+54>:	cmp    $0x2,%eax
0x0000555555555a43 <+57>:	jne    0x555555555a5f <secret_phase+85>

secret input

Consists of a single string (long int) $x$ , $1 \leq x \leq 1001$ , and fun7(x) has to be equal to $2$ .

With that done, we can now move on to the helper function:

gef➤  disas fun7
Dump of assembler code for function fun7:
   0x00005555555559c9 <+0>:	endbr64
   0x00005555555559cd <+4>:	test   %rdi,%rdi
   0x00005555555559d0 <+7>:	je     0x555555555a04 <fun7+59>
   0x00005555555559d2 <+9>:	sub    $0x8,%rsp
   0x00005555555559d6 <+13>:	mov    (%rdi),%edx
   0x00005555555559d8 <+15>:	cmp    %esi,%edx
   0x00005555555559da <+17>:	jg     0x5555555559e8 <fun7+31>
   0x00005555555559dc <+19>:	mov    $0x0,%eax
   0x00005555555559e1 <+24>:	jne    0x5555555559f5 <fun7+44>
   0x00005555555559e3 <+26>:	add    $0x8,%rsp
   0x00005555555559e7 <+30>:	ret
   0x00005555555559e8 <+31>:	mov    0x8(%rdi),%rdi
   0x00005555555559ec <+35>:	call   0x5555555559c9 <fun7>
   0x00005555555559f1 <+40>:	add    %eax,%eax
   0x00005555555559f3 <+42>:	jmp    0x5555555559e3 <fun7+26>
   0x00005555555559f5 <+44>:	mov    0x10(%rdi),%rdi
   0x00005555555559f9 <+48>:	call   0x5555555559c9 <fun7>
   0x00005555555559fe <+53>:	lea    0x1(%rax,%rax,1),%eax
   0x0000555555555a02 <+57>:	jmp    0x5555555559e3 <fun7+26>
   0x0000555555555a04 <+59>:	mov    $0xffffffff,%eax
   0x0000555555555a09 <+64>:	ret

The first thing that we notice is that this function is recursive. The second input never gets changed and is used for comparing with value at (%rdi) (line +15). The first input (%rdi) is an address and gets changed every function call. The new addresses are always at +8 or +16 bits (line +31, +44).

This structure is suspiciously similiar to a binary tree with three entries:

    (%rdi)    value
 0x8(%rdi)    address of left child
0x10(%rdi)    address of right child

If we interpret the address structure like this, we can rewrite the function in c:

int fun7(int *node, int value) {
	if(!node->value) return -1;
	if(node->value > input)
		return 2*fun7(node->left, input);
	if(node->value < input)
		return 2*fun7(node->right, input) + 1;
	return 0;
}

This means the nodes not only form a binary tree, but a binary search tree! To get the value 2, we first have to go left once (because going right would return $2 a + 1 \neq 2, n \in N$ ). Going left returns a number $2 a, a \in N$ . This means $a$ has to be 1. To get 1 at depth 1, we would have to recursively go to the right, and the function at depth 2 has to return zero in order to get 1 ( $2 \cdot 0 + 1 = 1$ ).

Thus, the only possible solution that returns 2 is to go

root->left->right

and we have to know the value

root->left->right->value

In order for the function at depth 2 to return 0. We can find that value using gdb, since we know the address of the first node from the function secret_phase:

gef➤  x/3gx 0x555555559150
0x555555559150 <n1>:	0x0000000000000024	0x0000555555559170
0x555555559160 <n1+16>:	0x0000555555559190

The value of the root node is 36, and the left node is at 0x0000555555559170.

gef➤  x/3gx 0x0000555555559170
0x555555559170 <n21>:	0x0000000000000008	0x00005555555591f0
0x555555559180 <n21+16>:	0x00005555555591b0

The value of the left node at depth 1 is 8, and the right node at depth 2 is at 0x00005555555591b0.

gef➤  x/3gx 0x00005555555591b0
0x5555555591b0 <n32>:	0x0000000000000016	0x00005555555590b0
0x5555555591c0 <n32+16>:	0x0000555555559070

The value of the node root->left->right is 22. This is the value we have to input into secret_phase for this bomb.

All 7 phases of the bomb are now solved!