Assignment 2: Defusing a Binary Bomb

Introduction

The nefarious Dr. Evil has planted a slew of “binary bombs” on our class 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 of you 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!

Step 1: Get Your Bomb

You can obtain your bomb by entering the following commands from your Linux account exactly as shown.

cd ~/cs224
curl -o bomb.tar -k -L "https://cs224.cs.vassar.edu/bomblab?username=$USER&usermail=$USER%40vassar.edu&submit=Submit"

Note you only should run the above command once! If you run the command multiple times, you will download multiple binary bombs and the bomb server will get confused. If you happen to download multiple bombs, just delete all the bombs except one, and use that one.

After running the above command, you should see tar file called bomb.tar.

ls 
bomb.tar

To extract the tar file, run the following command:

tar -xf bomb.tar

This will create a directory called ./bombXX (where XX is your unique bomb number) with the following files:

Step 2: Defuse Your Bomb

Your job for this lab is to defuse your bomb.

You must do the assignment on one of the class machines. In fact, there is a rumor that Dr. Evil really is evil, and the bomb will always blow up if run elsewhere. There are several other tamper-proofing devices built into the bomb as well, or so we hear.

You can use many tools to help you defuse your bomb. Please look at the hints section for some tips and ideas. The best way is to use a debugger to step through the disassembled binary.

The first three phases are worth 25 points each and phase 4 is worth 15 points, for a total of 90 points. In addition, you will document how you solved each stage in the file How_I_Solved_It.txt. This file is worth 10 points, so this lab is worth a total of 100 points.

Although phases get progressively harder to defuse, the expertise you gain as you move from phase to phase should offset this difficulty. However, the last phase can be a bit of a challenge, so please don’t wait until the last minute to start.

The bomb reads passwords from stdin (i.e., standard input, a.k.a. the terminal). To save your self some typing, you can use file redirection to read passwords from the file passwords.txt instead.

qemu-riscv32 ./bomb < passwords.txt

The bomb will then read the input lines from passwords.txt instead of from the terminal.

To avoid accidentally detonating the bomb, you will need to learn how to single-step through the assembly code and how to set breakpoints. You will also need to learn how to inspect both the registers and the memory states. One of the nice side-effects of doing the lab is that you will get very good at using a debugger. This is a crucial skill that will pay big dividends for the rest of your career.

Using gdb to defuse the bomb

Defusing bombs is a high-skill job. There are a number of tools you can use to help you. The most important of them is gdb The GNU debugger. This debugger allows you to trace through a program line by line, examine memory and registers, look at both the source code and assembly code (we are not giving you the source code for most of your bomb), set breakpoints, set memory watch points, and write scripts. You’ll find in the resource section of the class website.

To debug your bomb using gdb, first you need to run your bomb using the QEMU emulator in debug mode. In your bomb directory, run the following command:

qemu-riscv32 -g 1234 bomb < passwords.txt

Now that the bomb is loaded and ready to run in QEMU, we can now start our our debugger, gdb. In another terminal window and also in your bomb directory, run the following command:

riscv32-none-elf-gdb -tui bomb

This starts the debugger in “text UI mode”. The screen is divided into two parts. The top part shows you the the C code that we have provided for you, and the bottom half shows you the command interface to the debugger. This window allows you to enter gdb commands to run and step through your program. Let’s set a breakpoint and run our program.

(gdb) break main

This tells gdb to stop the program execution when it hits the main function. We can now run our bomb program. Now we can run our bomb in the debugger.

(gdb) continue

This will run our program and stop at main. You can step through the program one line at a time with the next command. Try it. As you see, the next command treats a function call as a single line of code. If you want to ‘step into’ a function call, you would use the step command, which goes into a function.

Try putting in a break point in phase_1, using the break command that we described above. Now to start the program running again, type the continue command at the gdb prompt.

(gdb) continue

When you hit the breakpoint for phase_1 no source is shown, because we haven’t given that to you! Fear not, you can use gdb to look at the assembly code, and step through that, just like you did with the C code.

To see the registers and assembly code, you need to change the layout with the following gdb command:

(gdb) layout asm

To see the contents of registers use the gdb command layout regs. This will bring up a register window.

To move through the program we can use the nexti and stepi commands. They work just like next and step but work at the assembly language level.

To quit gdb, you can use the quit command, or press <ctrl-d>.

For online documentation, type help at the gdb command prompt, or type man gdb, or info gdb at a Linux prompt and the section on TUI mode in the GDB manual.

Run scripts

To assist you debugging your code, there are two scripts in the bomb directory to help you start QEMU and gdb. To run the bomb with QEMU in debug mode and the passwords.txt as input, run the following command in one terminal.

./qemu_run.sh

To run gdb, go in another terminal and run the following command.

./gdb_run.sh

This script looks at the file init_gdb, which has a list of gdb commands, one per line. These gdb commands will automatically get run when you start gdb. This is a useful place to add any breakpoints or change your layout to assembly, etc. Feel free to modify that file and add any commands you like. Here’s the init_gdb file that I used when I was solving phase_1.

set tcp connect-timeout unlimited
target remote :1234
layout asm
break phase_1
continue

Submitting your assignment

This is an individual project. Clarifications and corrections will be posted to the class website.

In your directory where your binary bomb is located, there is a file called How_I_Solved_It.txt. In this file you will describe how you solved each stage. Discuss how you reverse engineered each stage to get your solution and describe what you think each stage is doing. It is a good idea when you solve a stage, to immediately fill out that stage’s section in How_I_Solved_It.txt when it is fresh in your mind. Don’t wait till the end to write this file or you might have to solve it again just to remember what you did!

To submit your assignment upload your passwords.txt file and your How_I_Solved_It.txt file to Gradescope.

Hints: Please read this!

There are many ways of defusing your bomb. You can examine it in great detail without ever running the program, and figure out exactly what it does. This is a useful technique, but it not always easy to do. You can also run it under a debugger, watch what it does step by step, and use this information to defuse it. This is probably the fastest way of defusing it.

We do make one request, please do not use brute force! You could write a program that will try every possible key to find the right one. But this is a bad idea and goes against the purpose of this assignment, which is to give you practice on understanding how assembly code works. Furthermore, we haven’t told you how long the strings are, nor have we told you what characters are in them. Even if you made the (incorrect) assumptions that they all are less than 80 characters long and only contain letters, then you will have 2680 guesses for each phase. This will take a very long time to run, and you will not get the answer before the assignment is due.

Use any function calls you see in assembly code as an anchor point to help you understand what is going on in the code. The first 8 arguments for a function are placed in the a0 through a7 registers, but convention. So if you see instructions using those registers right before a function call, it is likely setting up the registers correctly for the call. If a function returns a value, it is stored in a0.

You can assume any function that has a descriptive name, such as read_six_numbers or explode_bomb, does exactly what it says it does. It is probably not worth your time stepping into a function like this to understand exactly how those functions work. However, if a function call has a generic name such as func3, you are going to figure out how that function works to be able to solve that phase.

If you see a function with a strange name, such as <sscanf> this is a function in the standard C library (libc). This example is a call to sscanf(), and knowing how this function works will help you understand any phase that uses it. To see the documentation for any system call you can use the man command (short for manual pages). sscanf() takes a conversion string as its first argument (remember that in C, a string is just a pointer to a list of characters). The conversion string has conversion characters (which start with a %). See understanding how sscanf works for more details.

Having trouble seeing the big picture for one of your phases? One thing that I found helpful is to print out the code for the phase you are trying to solve and draw arrows on one side of the page for every forward jump (a jump to a larger memory address). These jumps represent branches. On the other side of the page draw every backward jump (a jump to a smaller memory address). These jumps represent loops. This can help you understand the overall structure of the function, which will be useful in understanding the structure of phase_6.

There are many tools which are designed to help you figure out both how programs work, and what is wrong when they don’t work. We described gdb above, and here is a list of some of the tools you may find useful in analyzing your bomb, and hints on how to use them.

Looking for a particular tool? The commands apropos, man, and info are your friends. In particular, man ascii might come in useful. info gas will give you more than you ever wanted to know about the GNU Assembler. If you get stumped, feel free to ask me or the Coaches for help.

Good luck!