Throughout my autodidactic journey of studying Computer Systems: A programmer’s perspective (CSAPP, for short)1 I have stumbled upon a CS 61 course offered by Harvard. The course is divided in 6 units where the 2nd unit contains a problem set called Binary Bomb. The name of todays article.
Introduction
From the problem set specified here we are introduced to the concept of a binary bomb:
A binary bomb is a program that consists of a sequence of phases. Each phase reads a line from the standard input. If the line is correct, 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.
Now, I am not enrolled in this course but I managed to find a github repo with many binary bombs waiting to be defued which I cloned into my local machine. I randomly decided to go with the binary bomb in folder 1551025 and started getting to work.
In each folder with its respective problem set of binary bomb there is a stripped down source file: bomb.c. It has a simple and repetitive pattern:
input = read_line(); /* Get input */
phase_1(input); /* Run the phase */
phase_defused(); /* Drat! They figured it out!
* Let me know how they did it. */
printf("Phase 1 defused. How about the next one?\n");
We can simply break during each respective phase_* (function).
Now, there are some wise things to do. Such as running the following command:
strings bomb
objdump -t bomb # examines symbol table
objdump -d bomb # disassembles all code
And examining the output. However, I mainly used the GNU Debugger and then later on during Phase 4 switched to the GDB Enhanced Features which made debugging a breeze.
Phase 1
We break at phase_1 and run. Input test and then disassemble phase_1 to get the dump of assembler code of the function. Which is very small.
0x0000000000400e8d <+0>: sub $0x8,%rsp
0x0000000000400e91 <+4>: mov $0x4023b0,%esi
0x0000000000400e96 <+9>: call 0x401322 <strings_not_equal>
0x0000000000400e9b <+14>: test %eax,%eax
0x0000000000400e9d <+16>: je 0x400ea4 <phase_1+23>
0x0000000000400e9f <+18>: call 0x401421 <explode_bomb>
0x0000000000400ea4 <+23>: add $0x8,%rsp
0x0000000000400ea8 <+27>: ret
Before calling a function with the suspicious name of strings_not_equal we load an immediate value into the %esi register, which tends to be a 2nd argument register. Looking at our registers we see that our test input is loaded into %rdi (which tends to be a 1st argument register) but as well as %rax and %rdx. Upon returning from strings_not_equal the function checks that the returning register %eax is equal:
0x0000000000400e9b <+14>: test %eax,%eax
Clearly our input string is compared to a pre-determined string that is 0x4023b0. Running the following command in GDB displays that specific string:
gef➤ x/s 0x4023b0
0x4023b0: "The moon unit will be divided into two divisions."
Pro Tip
To make everything smoother we create a sol.txt file with our solutions. One solution for each row corresponds to each phase.
The moon unit will be divided into two divisions.
And in the same spirit we create a .gdbinit file and write down the following:
b phase_2
run <sol.txt
So that we break for the next function we are trying to solve and automatically run GDB and feeding our solutions file so we don’t have to manually input everything. This saves lots of time.
Phase 2
Once more, we break at phase_2 and try with some placeholder such as “0 1” as input. As we step through the assembly of the phase_2 function I notice:
0x0000000000400ec2 <+25>: call 0x401443 <read_six_numbers>
0x0000000000400ec7 <+30>: cmpl $0x0,(%rsp)
0x0000000000400ecb <+34>: jne 0x400ed4 <phase_2+43>
0x0000000000400ecd <+36>: cmpl $0x1,0x4(%rsp)
0x0000000000400ed2 <+41>: je 0x400ed9 <phase_2+48>
0x0000000000400ed4 <+43>: call 0x401421 <explode_bomb>
Which is a function named read_six_numbers, giving away its functionality. We can assume that it expects six numbers as input. What can those numbers be though? Let’s look inside of the read_six_numers as well.
0x40146a <read_six_numbers+0027> call 0x400bb0 <__isoc99_sscanf@plt>
0x40146f <read_six_numbers+002c> add $0x10, %rsp
0x401473 <read_six_numbers+0030> cmp $0x5, %eax
0x401476 <read_six_numbers+0033> jg 0x40147d <read_six_numbers+58>
0x401478 <read_six_numbers+0035> call 0x401421 <explode_bomb>
Well, if the given input is not more than 6 digits, then the bomb will explode. This is due to the cmp and the jg (jump greater) operations. Returning back to phase_2 we have cmpl operation which compares an immediate value with the (%rsp) register value. This happens to be our first digit input 0. So from the following assembly:
0x400ec7 <phase_2+001e> cmpl $0x0, (%rsp)
0x400ecb <phase_2+0022> jne 0x400ed4 <phase_2+43>
0x400ecd <phase_2+0024> cmpl $0x1, 0x4(%rsp)
0x400ed2 <phase_2+0029> je 0x400ed9 <phase_2+48>
0x400ed4 <phase_2+002b> call 0x401421 <explode_bomb>
We know that our first and second arguments passed into the function is expected to be 0 and 1, because 0x4(%rsp) points to the next digit we gave as input. Continuing a few steps forward we see the following code:
0x400ed9 <phase_2+0030> mov %rsp, %rbx
0x400edc <phase_2+0033> lea 0x10(%rsp), %rbp ; stores the end pointer so we know when to stop
0x400ee1 <phase_2+0038> mov 0x4(%rbx), %eax ; move 2nd digit to $eax
0x400ee4 <phase_2+003b> add (%rbx), %eax ; add 1st digit to $eax
0x400ee6 <phase_2+003d> cmp %eax, 0x8(%rbx) ; compare to 3rd digit
0x400ee9 <phase_2+0040> je 0x400ef0 <phase_2+71>
0x400eeb <phase_2+0042> call 0x401421 <explode_bomb>
0x400ef0 <phase_2+0047> add $0x4, %rbx ; next digit
0x400ef4 <phase_2+004b> cmp %rbp, %rbx ; are we there yet?
0x400ef7 <phase_2+004e> jne 0x400ee1 <phase_2+56>
The stack pointer $rsp is moved to $rbx so it can access the stack pointer. Then we store the 5th element of the user input with lea 0x10(%rsp), %rbp which is used as a marker of when to stop. The code then adds our 1st and 2nd digit we gave as input and compares it to the 3rd digit. If it adds up to be the same value as the 3rd digit we don’t set off the bomb and continue. We continue by incrementing $rbx and check whether we have reached the end of our input. If not, we continue in the same fashion by adding the first 2 digits and comparing it to the 3rd. You start to get the picture. It’s the Fibonacci sequence. Likely an iterative function and thus the need for saving the current stack pointer like so:
0x400ed9 <phase_2+0030> mov %rsp, %rbx
Phase 3
Once more we stumble upon sscanf:
0x400f31 <phase_3+001c> mov $0x4025af, %esi
0x400f36 <phase_3+0021> call 0x400bb0 <__isoc99_sscanf@plt>
gef➤ x/s 0x4025af
0x4025af: "%d %d"
It expects 2 digits as input. Lovely. As we continue stepping through the binary we encounter:
0x400f45 <phase_3+0030> cmpl $0x7, (%rsp)
0x400f49 <phase_3+0034> ja 0x400f86 <phase_3+113>
Our stack pointer $rsp points to our first value and expects it to be less than or equal to 7. That was easy to figure out. Moving forward we can see that in the assembly function we are jumping a lot:
0x0000000000400f4b <+54>: mov (%rsp),%eax
0x0000000000400f4e <+57>: jmp *0x402420(,%rax,8) ;we seem to be jumping based on our 1st digit
0x0000000000400f55 <+64>: mov $0x374,%eax
0x0000000000400f5a <+69>: jmp 0x400f97 <phase_3+130>
0x0000000000400f5c <+71>: mov $0x28d,%eax
0x0000000000400f61 <+76>: jmp 0x400f97 <phase_3+130>
0x0000000000400f63 <+78>: mov $0x22c,%eax
0x0000000000400f68 <+83>: jmp 0x400f97 <phase_3+130>
0x0000000000400f6a <+85>: mov $0x22f,%eax
0x0000000000400f6f <+90>: jmp 0x400f97 <phase_3+130>
0x0000000000400f71 <+92>: mov $0x282,%eax
0x0000000000400f76 <+97>: jmp 0x400f97 <phase_3+130>
0x0000000000400f78 <+99>: mov $0x26c,%eax
0x0000000000400f7d <+104>: jmp 0x400f97 <phase_3+130>
0x0000000000400f7f <+106>: mov $0x1f3,%eax
0x0000000000400f84 <+111>: jmp 0x400f97 <phase_3+130>
0x0000000000400f86 <+113>: call 0x401421 <explode_bomb>
0x0000000000400f8b <+118>: mov $0x0,%eax
0x0000000000400f90 <+123>: jmp 0x400f97 <phase_3+130>
0x0000000000400f92 <+125>: mov $0x154,%eax
0x0000000000400f97 <+130>: cmp 0x4(%rsp),%eax ;comparing the end product stored in %eax to our 2nd digit
Our first digit seems to decide which path the jumps take place and therefore decides the expected 2nd digit. If we simply follow $eax using 7 as our first digit we can see that the final stored value is 499.
gef➤ p $rax
$8 = 0x1f3
gef➤ p /d 0x1f3
$9 = 499
Thus, the expected input is 7 499 for phase_3. Let’s go! Using the same method we can see that using 6 as the first digit we expect the value 620 as our second expected value. Continuing our journey to the next phase…
Phase 4
With the help of converting the value in the register %esi to a string, as we have done previously, we can see that sscanf expects 2 digits.
0x401013 <phase_4+001c> mov $0x4025af, %esi
0x401018 <phase_4+0021> call 0x400bb0 <__isoc99_sscanf@plt>
gef➤ x/s $esi
0x4025af: "%d %d"
One more way of figuring this out is that the program explicitly checks to see if the return value by sscanf is 2. This is because sscanf returns the number of input items successfully matched and assigned.2
0x401018 <phase_4+0021> call 0x400bb0 <__isoc99_sscanf@plt>
0x40101d <phase_4+0026> cmp $0x2, %eax
0x401020 <phase_4+0029> jne 0x40102d <phase_4+54> ; jumps to below line if true
; Skipped for brevity
0x40102d <phase_4+0036> call 0x401421 <explode_bomb>
If it is not, the code will jump to a function call of explode_bomb. We dodged that bullet, now for the next one…
0x401022 <phase_4+002b> mov (%rsp), %eax
0x401025 <phase_4+002e> sub $0x2, %eax
0x401028 <phase_4+0031> cmp $0x2, %eax ; compares to check if it is within range
0x40102b <phase_4+0034> jbe 0x401032 <phase_4+59>
0x40102d <phase_4+0036> call 0x401421 <explode_bomb>
Here we are moving our 1st digit into %eax, subtracting it by 2 and compares to see if the number is within range. In this case the range accepted is 2, 3 and 4. However, you might have noticed something here. Our digits that we put in “1 2” seems to have swapped places.
gef➤ x $rsp
0x7fffffffdcc0: 2
gef➤ x $rsp+4
0x7fffffffdcc4: 1
This must have happened after the call to sscanf. Maybe this was intended in the exercise to try to throw us off. Either way, we’re not that easy to beat. Continuing…
0x401032 <phase_4+003b> mov (%rsp), %esi ; 2nd argument
0x401035 <phase_4+003e> mov $0x5, %edi ; 1st argument
0x40103a <phase_4+0043> call 0x400fbc <func4> ; function call
0x40103f <phase_4+0048> cmp 0x4(%rsp), %eax ; compare to returned value
0x401043 <phase_4+004c> je 0x40104a <phase_4+83>
0x401045 <phase_4+004e> call 0x401421 <explode_bomb>
The next few instructions are commented. We use one of our input (2nd digit) and another pre-determined integer as arguments to func4. I tried not to bother looking into func4. It happens not be necessary in order to solve this phase. %eax, which contains our return value, has the value that is expected by the program in order not to set off the bomb. Let’s examine it.
gef➤ p /d $eax
$6 = 24
Well, well, well… What do we have here? The decimal number 24. So that means if we use integer 2 as input into fun4 as the 2nd argument the output will be 24. Let’s quickly rerun the program with 24 2 as our input and lo’ and behold. Bomb defused.
Phase 5
Once again sscanf is expecting "%d %d", two digits.
0x401080 <phase_5+001c> mov $0x4025af, %esi
0x401085 <phase_5+0021> call 0x400bb0 <__isoc99_sscanf@plt>
gef➤ x/s $esi
0x4025af: "%d %d"
Initially I experimented with 1 2 as input. Stepping through the instructions I rather quickly realised that the function uses some kind of loop:
0x4010ac <phase_5+0048> add $0x1, %edx
0x4010af <phase_5+004b> cltq
0x4010b1 <phase_5+004d> mov 0x402460(, %rax, 4), %eax
0x4010b8 <phase_5+0054> add %eax, %ecx
0x4010ba <phase_5+0056> cmp $0xf, %eax
0x4010bd <phase_5+0059> jne 0x4010ac <phase_5+72>
as long as we didn’t load 0xf (15) into the %eax register. If we did, we would exit the loop. The %eax register was loaded by the following instruction:
0x4010b1 <phase_5+004d> mov 0x402460(, %rax, 4), %eax
This instruction took me far longer to figure out than I want to admit. Reading in the CSAPP1 book we can see that:
Memory (,ri,s) M[R[ri] · s] Scaled indexed
Which, if %rax is loaded with 1 gives us: 0x402460[R[1]*4] –> 0x402460 + 0x4. We can thus figure out that this instruction accesses an array using 4 bits as its index. And after executing the instruction we can see that %eax gets loaded with the integer 2.
Executing the following command:
gef➤ x/16wd 0x402460
0x402460 <array.3597>: 10 2 14 7
0x402470 <array.3597+16>: 8 12 15 11
0x402480 <array.3597+32>: 0 4 1 13
0x402490 <array.3597+48>: 3 9 6 5
Will give us the array table that the mov 0x402460(, %rax, 4), %eax instruction accesses. Which also confirms that 0x402460[R[1]*4] returns 2.
So, once 0x4010ba <phase_5+0056> cmp $0xf, %eax is true, we don’t jump and instead continue with the following assembly:
0x4010bf <phase_5+005b> movl $0xf, (%rsp)
0x4010c6 <phase_5+0062> cmp $0xf, %edx
0x4010c9 <phase_5+0065> jne 0x4010d1 <phase_5+109>
Now, the %edx keeps track of the number of iterations that we have completed in the for loop. It has to be exactly $0xf (15), otherwise the bomb will be set. So what does this tell us thus far? It means that we have to have accessed the array table exactly 15 times before hitting the number 15. Remember how we also added the loaded value to %ecx during each loop?
0x4010b8 <phase_5+0054> add %eax, %ecx
Well, apparently the total values accessed in the array table and added to %ecx has to be equal our second digit scanned by sscanf. Like so:
0x4010cb <phase_5+0067> cmp 0x4(%rsp), %ecx
0x4010cf <phase_5+006b> je 0x4010d6 <phase_5+114>
After some trial and error with the first input value being 5 I managed to satisfy the necessary conditions of hitting number 15 in the array table on exactly 15 tries and thus satisfying:
0x4010ba <phase_5+0056> cmp $0xf, %eax
0x4010bd <phase_5+0059> jne 0x4010ac <phase_5+72>
# and
0x4010c6 <phase_5+0062> cmp $0xf, %edx
0x4010c9 <phase_5+0065> jne 0x4010d1 <phase_5+109>
Stepping through the rest of the code I figured out that the first input 5 yielded a total of 0x73 (115) in %ecx I simply used that as my second input into the phase_5 function. Voíla! Bomb defused, like a boss.
Phase 6
Work in progress…
-
Computer Systems: A programmer’s perspective: 3rd edition by Bryant and O’Hallaron ↩︎ ↩︎
-
https://www.man7.org/linux/man-pages/man3/sscanf.3.html#RETURN_VALUE ↩︎