I recently discovered a popular reverse engineering assignment in many university CS programs called the Binary Bomb. I didn’t have it at my school, but it looked like a fun project so I decided to try it.
The binary bomb is a simple command line program that asks you to enter a particular secret string. If type the incorrect string, the program explodes by printing out BOOM!!! and terminating. If you enter the correct string, the program proceeds to the next phase, which expects another particular string. In a typical classroom setup, each explosion will automatically notify your professor and deduct a small percentage from your final assignment grade.
The goal is to use a debugger to reverse engineer the executable in order to find the expected string for each phase and prevent the bomb from blowing up.
I completed the project over a few days, and have written a detailed walkthrough below.
If you’d like to play along at home, the original executable is up on the Internet Archive. Make sure you are running the executable on a 64-bit Linux box or VM.
I fired up gdb, added some breakpoints before and after the first input string required for the bomb. Then I stepped through the disassembled instructions to find a function called
Note that between the beginning and end of
phase_1 there is a call to the function
So we have two options here to beat phase 1:
je(jump if equal instruction) to be a
jne(jump if not equal), which will skip over
explode_bombto take us to the next phase. This method is easy to do, but it doesn’t actually give us the pass code for the first phase. So we would have to do this jump every time.
Dive into the
strings_not_equalcall and explore the code. There will likely be a string comparison in there that will reveal the string for this phase. In this way we can simply type in the string to beat phase 1 and go into phase 2 in the expected way.
Notice that there are two calls to a function called
string_length, followed by a jump depending on the the result of these function calls. Furthermore, notice that the registers
edi are pushed onto the stack before their respective
string_length calls. This tells us that these registers are used as function arguments.
These instructions tell us that the function first compares the length of the input string before even checking if the user’s input matches the password.
Let’s examine the argument passed to the first
Note that we are looking for the value of the register
esi, which is stored at
0x804b680. Let’s examine it as a string:
In this case,
esi points to
123 which is what I typed in for my attempt for this phase.
Now let’s take a look at
edi which is the register used in the second
string_length call, we will see what the program is comparing our input string against, which should be the password to phase 1.
Let’s run the binary bomb and try it out:
Phaes 1 complete!
We can start by disassembling the
phase_2 function just like we did for
read_six_numbers function hints that this round will be looking for 6 numbers of input, it doesn’t really tell us anything about the values of these numbers. Notice the two
explode_bomb calls in
phase_2. Let’s add some breakpoints throughout the function and enter
012345 as our input.
explode_bomb call is after a comparison between the constant
0x1 and the value at address
(%ebp - 0x18). Examining the memory location reveals that the value is
0. After some trial and error I discovered that this is the first number of my attempted password
012345. We can prove this by examining the values in memory of offsets other than
Now we know
(%ebp - 0x18) corresponds to the first element of our input. If we want to avoid the first
explode_bomb call, then the first
cmpl (comparison instruction) must consider the values at the two addresses to be equal. This means the first digit of this password must be
Now if we restart the bomb and use this new knowledge, we can bypass the first comparison and make it to the second one.
The second comparison is slightly more complicated and depends on the result of a (signed) multiplication. First we multiply
(%esi - 0x4 + 4*%ebx) by
%eax, and then store the result in
%eax. In our case it gives us the following:
Now we meet the second comparison statement. The right hand side is simply an index to the current element of our input. This iteration it’s comparing the value in
%eax to the second input value. If this comparison is not-equal, then the bomb will explode. Since the value of
eax is 2, this means that the second digit of our input should be
This time instead of re-running the program, we can just set the value directly in memory.
Now we reach the third round of the
phase_2 loop. Let’s take a look at
%eax again to see the expected digit.
Doing this one more iteration reveals that the program expects the first 4 digits of the 6 digit password to have values
1 2 6 24. These are not arbitrary numbers. The pattern looks like increasing factorial digits. Notice that
1 2 6 24 is
1! 2! 3! 4!
Based on the function name, we can make the guess that the required password is just 6 numbers, and each one is the factorial of its 1-based index. This would be
1! 2! 3! 4! 5! 6! or
1 2 6 24 120 720
I restarted the program in gdb, set a breakpoint at the
phase_3 function, and entered the passwords we’ve found so far for phase 1 and 2. Then I entered an initial guess for phase 3 of
try one try.
Looking at the first dozen lines of the disassembled
phase_3 function, note the call to sscanf. If we examine the arguments passed to this function, then we can figure out the input format of the password.
Notice that our input string and a format string was passed into
sscanf. The format string is in the format
%d %c %d, so it expects an integer, a character, and another integer.
Since I entered `
ry one tryas my initial guess, this does not fit the format that this call to
sscanfexpects. This will cause
sscanfto return and set
%eax to 0
This would result in the comparison of
0x2 NOT taking the corresponding jump, and cause the bomb to explode.
So now I restarted the application with a better guess. Now that jump after the
%eax comparison will succeed, we run into another conditional check. Examining the value in memory at
(%ebp - 0xc) shows that the program is comparing the first number of our input to the value 7, and jumping (to avoid an explosion) if the number is less than or equal to 7. Since our input number was 1, this condition is true and we skip this call to
explode_bomb. So far so good.
The next line of interest is a
jmp statement which will jump to the offset of the value stored at
(0x80497e8 + %eax*4).
At this point
%eax is set to the first number in our input string, so our jump takes us to the following position:
The next comparison examines our third input value (an integer) stored at
(%ebp - 0x4) and checks it against the value
214 in decimal.
In order to beat this comparison, we can restart the app again with the following input:
Then, the final comparison checks our second input value (of type char) against
%bl. Examining the value of
%bl reveals that the application is expecting a
b character for this situation
So we run the application one final time including everything we’ve learned about the
phase_3 function, and we have now successfully completed phase 3!
Lets disassemble the
phase_4 function next. Once again there is a call to sscanf, so let’s peek at the format string to see what kind of input this phase expects.
Notice that in the second highlighted segment our input value is passed into the function
func4, and the result of this function is compared against
55 in decimal).
Now let’s look at func4 in chunks in order to simplify it. First looking at section A, if the input value (located at
[%ebp + 0x8] and then copied into
%ebx) is less than or equal to
1, then the function jumps down to section B and sets
1, which will become the return value.
Otherwise, the function steps into section C which will call
func4 recursively, passing in the original input decremented by one. This is followed by another call to
func4, passing in the original input decremented by two. Then the result of these two function calls is summed and copied into
%eax to become the return value of the function.
After stepping through a few iterations, I realized that the function was defined as
func4(x) = func4(x-1) + func4(x-2), which looks like the Fibonnaci sequence of the input number.
However, notice that
func4 will return
1 if the input is
0. Therefore if we have an input of
x = 2,
func4 would return
1 for both the
x - 1 = 1 and
x - 2 = 0 calls.
Remember that the
phase_4 function succeeds if the output of
55 in decimal). Since the
Fib(10) = 55 and we know that
func4(0) = func(1) = 1,
func4(2) = 2, then we just need to find an input x such that
Fib(x + 1) = 55. Since
Fib(10) = Fib(9 + 1) = 55, we know that the solution for this phase is
Let’s look at the first chunk of the disassembled
Notice the call to the
string_length function, and the resulting jump away from
explode_bomb if the return value is
6. Now we know that our input string must contain exactly 6 characters.
Looking down to the location of the jump, we have the following block of code that forms a loop. In this test run I’ve entered
123456 as my input.
Notice that my input string is stored at
In the loop above, the code takes our input value
%ebx plus some offset
%edx and copies it into
%al. Then it performs a binary
AND operation between
%al, and stores the result in
%al and subsequently into
%eax. Finally, it copies the character at
[%esi + %eax] into
%al, and into an initially empty string stored at
[%ecx + %edx].
To start, let’s look at what is being stored at
So there seems to be an array of characters stored at
%esi. Each character from our input string is binary
0xf. Then this resulting value is used as a lookup index in
%esi to find the final character mapping.
Now that we understand how the function works, we can examine the jump that avoids the final
explode_bomb call. This code checks to see if the result of the logic above is equal to the string stored at
Now we know that the transformed version of our input string must equal
giants. All we need to do is reverse engineer an input string that ends up as
giants in the algorithm.
Taking another look at the substitution array stored at
Notice that ‘g’ has an index of 15. Therefore we must find a character that when
0xf will result in
15 decimal which is also
0xf hex. This type of operation is called a bitwise mask. To succeed here, we need to find a character that has
1111 as the least significant 4 bits. The 4 most significant bits don’t matter here. For example, the hex ASCII value for the letter
6F, which has a binary value of
0110 1111, so it fits our requirement.
We can continue in a similar fashion and find characters which match for remaining “iants”. My solution was the string
opekmq, but there are many solutions for this phase.
Notice the function call on the last line of the excerpt above reads six numbers from standard input, so now we know the first requirement of the password for this phase. I’ll enter the input
1 2 3 4 5 6 to satisfy the 6 digit requirement.
Next let’s look a little further down the function:
And after the jump:
Notice that in the above block of code we have a loop. The counter for the loop is
%edi, which is initially set to
0 using the
XOR trick above, and the loop continues until
%edi has reached a value of 6. Since
%ebp - 0x18 is the location of the first input, this block of code is just iterating through all of the input values.
While iterating through all numbers, the function ensures that each number is less than
5. Notice that this comparison uses the
jbe command, which does not test for the sign of the number. Keeping this in mind, this process can be summarized as the second requirement: Each of the six numbers must be between 1 and 6 inclusive.
Next, let’s examine the nested loop below:
The loop has iterators
%edi. We’re comparing each number against every other number, and only jumping over the
explode_bomb call if the numbers are not equal. Essentially this code is ensuring that the password consists of unique numbers 1-6.
The next restriction is the most complicated. Let’s go down near the final
This part seems complicated initially. Ignore the early
lea instruction since it’s a
NOP to ensure code alignment. Skipping over that, I’ve highlighted the relevant loop above in red. After an initial
%esi is set, the code is comparing the value at
%esi, with the value at
%esi + 0x8, and the bomb explodes if the value at
%esi + 0x8 is less than the value at %esi.
But what are
%esi + 0x8?
%esi points to a node data structure. Since debugging information is not included in this executable, we can’t find the definition of a node. But looking at what is given above we can gain some intuition about it. Let’s start by looking at what
%esi + 0x8 leads to:
Notice that each of these nodes contain at least three things:
- Firstly some numerical value
- The input value corresponding to the node number (from the original
1 2 3 4 5 6input)
- A pointer to the next node.
This phase uses the common linked list data structure.
Some trial and error of input reveals two things. The first and second values in the above screenshot are identical for any order of input. So
node1 will always have a first value of
0xfd and a second value of
0x2, and so on. The only thing that changes is the pointer to the next node, which depends on the order of input values. For example, an input of
6 5 4 3 2 1 will result in
node6 -> node5 -> node4 -> node3 -> node2 -> node1.
So now to beat this phase let’s take a closer look at conditions surrounding the
At this point
%edx contains the pointer to the next node, and
%eax contains the value of the current node’s first column number. Let’s call this first column number
X. So this code compares if the current node’s
X value is greater than the next node’s
X value, and skips the
explode_bomb call if this is the case.
So we have the following nodes and associated
Since we are iterating over all nodes, and a node’s next pointer is related to the order of input, we just need to find the correct arrangement of numbers such that the current node’s
X is always greater than its next node’s
X value. More generally, we need to sort the numbers in decreasing order with respect to their
Now the nodes are sorted in order of decreasing
X value. We can use the node indices as the password for this phase
Although the bomb seems to be defused, poking around the disassembled
main() reveals a function called
Like before, there are two ways to jump to this function call.
- Alter a
jmpinstruction to go directly to the call to
secret_phase(). This is simple but is risky since we don’t know if
secret_phase()relies on any other logic in order to run successfully, that we would skip by jumping directly to it.
- Take the time to figure out the true nature of the
phase_defusedfunction in order to enter the secret phase legitimately.
The analogy here is deciding whether to bash down a door and risk destroying anything behind it, or picking the lock and entering safely.
Once again, let’s go with the second option.
We’ll begin by looking at the
sscanf call at the top of the code shown above. Let’s examine the format string and input:
The first input to this
sscanf call is the string
9, which we know is is the correct password for phase 4. The second part of the format string expects a string input. But what should this string be?
Let’s take a look at the inputs to the
strings_not_equal call a little further down to get an idea of the string we need.
Now we know that to get into the secret phase, we need to add
austinpowers to the end of the password for phase 4.
The secret phase takes a string input, converts it to an integer and checks that this integer is less than or equal to
0x3e9. If this is true, then it calls
fun7 and expects the return value to be
1001 decimal, I entered
1001 as my first guess for the secret phase password. Amazingly, this was the correct answer to the secret phase. At this point it was getting late and I didn’t spend the time to understand how
Be that as it may, this bomb has now been defused, and the world is safe once more.
If you are interested in the details of how
fun7 works, I found a great write up by someone with more patience than me.
Thanks for reading along!