You vs. The Moose: defusing a binary bomb

This assignment is an adaptation of Aaron Bauer's adaptation of this lab developed for the Carnegie Mellon University's 15-213 (Introduction to Computer Systems) course, which is the course for which our textbook was written.

Goals

• Experience the beginnings of reverse engineering: using debugging tools (especially gdb) to study executables at the assembly language level.
• Deepen your understanding of the x86_64 assembly language

Rubric

Scoring on this one is a little complicated, and this rubric won't make a lot of sense until you read the rest of the assignment.

Maximum score: 16 + ε points

That is, there are 12 points for defusing bomb phases, and 12 points available for explaining bomb phases, but your maximum score is 16. Want to try to get all the defusings and all the explanations? Go wild. But I'll cap your score at 16 anyway.

Good explanations will be succinct paragraphs describing what the phase is computing with your input at a high level of abstraction, plus notes about key features of the assembly code that correspond to the high-level computation.

If you are unable to defuse a phase, your explanation of that phase is unlikely to be clear or persuasive.

The upshot of this weird scoring system is that there are several ways to try to get the full 16 points. For example, you could defuse and explain phases 1-4. Or you could defuse all six phases and explain just two.

(By the way, by "ε"—i.e., the Greek lowercase epsilon—I mean what mathematicians doing real analysis mean. That is, an arbitrary but typically extremely small positive number. That is, you'll get my admiration but no points by identifying the source of the quote.)

Although phases get progressively harder to defuse, the expertise you gain as you move from phase to phase should offset this difficulty. However, the later phases will likely take quite a bit of time to work through, so don't wait until the last minute to start.

Background

The nefarious supervillain The Moose, working (and grazing on foliage) in her secret mountain lair, is plotting world domination. With her legendary team of cyber-ungulates, she has planted a collection of "binary bombs" on our class server.

Each of The Moose's bombs is a program that consists of a sequence of phases. Each phase expects you to input a particular string. 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. You can fully defuse the bomb by defusing every phase.

There are too many bombs for us to deal with, so I am giving each student a different bomb to defuse. Your mission, should you choose to accept it (i.e., should you wish to acquire the associated points and enhance your knowledge of assembly language and debugging in the process), 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 filling out the form at http://cs208.mathcs.carleton.edu:55057/.

You will need to be on campus or connected to the Carleton VPN to access this page. Once you have filled out and submitted the form, the server will build your bomb and and return it to your browser in a file named bombN.tar, where N is the unique ID of your bomb.

Upload bombN.tar to your account on mantis.mathcs.carleton.edu using whatever file transfer technique you prefer. This could be drag-and-drop onto VS Code when you're logged into mantis. As a dedicated command-line user, I often use scp ("secure copy"), like so:

where "wherever" is the path to whatever directory you want to store the file in. On Windows, I personally always set up WSL where scp is installed, but if you're not so inclined, the WinSCP application is ancient and effective.

Put bombN.tar wherever you want to work with it, and then un-tar it in the usual way:

(x=extract, v=verbose, f=filename)

This will create a directory called bombN with the following files:

• README: Identifies the bomb and its owner.
• bomb: The executable binary bomb. It will automatically submit your progress. Note that you can run this program on any Linux computer on the Carleton network (including connections via the Carleton VPN), but it's probably best to do your work on mantis.
• bomb-quiet: An offline version of the executable binary bomb. You can work on this one without an internet connection. You just need to run bomb once while connected to have your progress recorded.
• bomb.c: Source file with the bomb's main function and a friendly greeting from The Moose, Supervillain.
• descriptions.txt: File in which you briefly explain the functionality of each phase you defuse, and how you defused it. (See below for further discussion of this file.
• defuse.txt: File in which you record defusing inputs, one line per phase.

If for some reason you request multiple bombs from the web form, this is not a problem. Choose one bomb to work on and delete the rest.

Step 2: Defuse your bomb

Your job for this lab is to defuse your bomb. What this means in practice is that you will accumulate a sequence of input strings, one per phase, that defuses that phase.

For each defusing string you discover, put it in your defuse.txt file. If you defuse all six phases, defuse.txt should have six non-blank lines (note that the bomb ignores blank lines, so you may space out your defusing strings if you wish).

You must do the assignment on Linux. The Moose is evil enough to have tamper-proofing devices into the bomb.

You can use many tools to help you defuse your bomb. See the Suggestions section below for details.

Step 3: Write your descriptions

See the Rubric section above for a description of descriptions. As noted there, you're looking for a short description of "what is this code doing".

Put your descriptions in descriptions.txt. (Please do *not* write your descriptions in .docx, .pdf, .rtf, or other formatted text file types. Just give me the text of what you want to say, with clear headings for each described phase.)

Step 4: Submit your work

• While connected to the Carleton network, run your bomb and defuse as many phases as you can. This will cause your successful defusings to get logged on the grading server. You can check to make sure your defusings got logged properly by going to http://cs208.mathcs.carleton.edu:55057/progress.
• Submit descriptions.txt and defuse.txt via Moodle.

Suggestions and hints

• If you run your bomb with a command line argument, like:

  ./bomb defuse.txt

  the bomb will read the input lines from defuse.txt until it reaches EOF (end of file), and then switch over to reading from the command line. In a moment of weakness (compassion! bah!), The Moose added this feature so you don't have to keep retyping the solutions to phases you have already defused.

• The bomb ignores blank input lines, both from the keyboard and from the input file. So you can space your defuse.txt lines out if you want to. But note that the order of the defuse.txt lines needs to correspond to the phases.
• You'll have to defuse phases in order.
• 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 this assignment is that you will get very good at using a debugger. This is a crucial skill that will pay big dividends dealing with buggy software in the future.
• If you don't want to have the server record all your abortive attempts to make sense of your debugging efforts, you can debug the bomb-quiet program instead of bomb. You just need to make sure that eventually, you run bomb once while connected to the Carleton network (e.g. on mantis) so your defusings get logged.
• 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.
• The Moose may be evil, but she has a sense of fair play. As a result, you may assume that functions do what their name implies. For example, phase1() is most likely the first phase, printf() is just printf(), and a function named strings_not_equal() probably takes two strings and returns whether they are not equal. If there is an explode_bomb() function, it would probably help to set a breakpoint there!
• Most cryptic function calls you'll see (e.g. callq ... <_exit@plt>) are calls to C library functions. (You can safely ignore the @plt as that refers to dynamic linking (whatever that is).)
• Most phases use the C library function sscanf to parse the input string, so you will want to understand how this function works.
• Avoid going through the assembly for C library functions—reading the documentation and writing your own small experimental C programs will be much easier path to understanding them!

Tools you can use

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. Here is a list of some of the tools you may find useful in analyzing your bomb, and hints on how to use them.

• gdb: the GNU debugger

  This is a command line debugger tool available on virtually every platform. You can trace through a program line by line, examine memory and registers, look at both the source code and assembly code (which will be important, since I am not giving you the source code for most of your bomb), set breakpoints, set memory watch points, and write scripts.

  • Here's a good tutorial on gdb.
  • Here's a handy quick reference sheet.
  • To keep the bomb from blowing up every time you type in a wrong input, you'll want to learn how to set breakpoints.
  • For documentation, type help at the (gdb) command prompt.

• objdump -t

  This will print out the bomb's symbol table. The symbol table includes the names of all functions and global variables in the bomb, the names of all the functions the bomb calls, and their addresses. You may learn something by looking at the function names!

• objdump -d

  Use this to disassemble all of the code in the bomb. You can also just look at individual functions. Reading the assembler code can tell you how the bomb works.

  Although objdump -d gives you a lot of information, it doesn't tell you the whole story. Calls to system-level functions are displayed in a cryptic form. For example, a call to sscanf might appear as:

  8048c36: e8 99 fc ff ff call 80488d4 <_init+0x1a0>

  To determine that the call was to sscanf, you would need to disassemble within gdb.

• strings

  This utility will display the printable strings in your bomb.

Have fun!