Assignment 6: Binary bomb

Due: Sun May 27 11:59 pm
Ontime bonus 5%. Grace period for late submissions until Tue May 29 11:59 pm

Assignment by Michael Chang & Julie Zelenski
idea originated by Randal Bryant & David O'Hallaron (CMU)

Learning goals

Completing this assignment will give you:

  • solid practice in reading and tracing assembly code
  • an understanding of how data access, control structures, and function calls translate between C and asm
  • experience reverse-engineering
  • a little taste of the challenges in writing secure and robust systems
  • a compelling reason to invest in mastering the gdb debugger!

For the security exercise, you will work through the vulnerabilities in a uncarefully-written program by studying both the C source and its assembly translation. Then, it's on to the pièce de résistance: defusing a nefarious binary bomb -- all in assembly, no source!

The assignment tasks are presented as a sequence of C/assembly "puzzles" to solve. We think this is a fun way to explore the material and hope you enjoy solving our puzzles as much as we enjoy creating them!

Getting started

Check out a copy of your cs107 repository with the command:

    git clone /afs/ir/class/cs107/repos/assign6/$USER assign6

Do not start by running the bomb to "see what it will do..." You will quickly learn that "what it does" is explode :-) When started, it immediately goes into waiting for input and when you enter the wrong response, it will explode and deduct points. Thoroughly read the bomb information in this writeup and the advice page before attempting do anything with bomb!

1. Code study: security and robustness

The samples/atm program simulates the operation of a simplified ATM. The ATM program is invoked with a username and amount. If the user is properly authorized and their account has the necessary funds, the amount is withdrawn and dispersed in cash. The ATM is supposed to maintain bank security by rejecting unauthorized users and denying withdrawals in excess of the current balance.

Run samples/atm myname 40 (replacing myname with your myth login name) to make a $40 withdrawal from your account. Success! If you ask to withdraw $100 from your account, it is rejected because that would bring your current $107 balance below the required minimum. A request to sneak cash from my account instead of yours samples/atm zelenski 40 should also get turned down. So far, so good-- the ATM seems to be doing its job. (Note: Each time you run the program anew, all balances return to their original starting levels. No money actually changes hands in this ATM; which is a blessing given its security flaws.)

The bank recently updated the ATM software to a newer version with the latest in security improvements, including authentication passcodes. The IT team reviewed the new program and thought it all looked good, but having now installed it in production, the transaction log shows some anomalies that have the bank worried. The bank needs help to figure out what's gone wrong with the ATM. Your awesome combo of C and assembly knowledges make you the perfect fit for the job!

Skim the program samples/atm.c to understand the basic operation. The program is ~150 lines of C code very similar to what you have been writing all quarter. The code is nicely decomposed and reasonably readable (though sorely lacking in comments) and at first glance, it appears to do its job correctly. To provide an audit trail, the ATM program logs every successful transaction, including the username, customer id, the withdrawal amount, and account balance after withdrawal. A bank employee auditing the bank records after the new software was installed has identified three suspicious transactions that need your further investigation.

  1. Negative balance. When verifying that an account has sufficient funds, the previous ATM software verified the balance was greater than the withdrawal amount. A withdrawal could drain a customer's account to $0, but it never went negative. The updated ATM software now has a required minimum balance as noted in the samples/atm.c code. Although this change was supposed to raise the floor on an account balance, it seems to have had the opposite effect. There is a transaction logged where a customer has overdrawn their account and ended with a negative balance. Oops -- that's not supposed to happen!

  2. Unauthorized access to account of another user. The next anomaly was a customer complaint about a withdrawal made from their account without their authorization. You find the transaction in the log and see that it was logged as a successful withdrawal from the account with the customer's id, but the dispersal was given to a user whose name doesn't match the name on the account. What gives? A user should not be able to access a different customer's account!

    The flaws in the id/authorization code can be seen by reviewing the C source, but figuring out how they can be exploited requires looking beyond the C source and into the assembly translation. Hint: One possibly relevant detail of the suspicious transaction is that the victim account belongs to one of the course TAs. Also note that the logged transaction shows that the attacking user made the withdrawal from the TA's account but without impersonating the TA.

  3. Access to the vault. The most worrisome issue are suspicious $1000 withdrawals from the master account, customer id 0. The large balance maintained in the vault dictates that this account is managed as high-security. In place of the identity-based authorization used otherwise, a high-security account requires the user to authenticate with the account's secret passcode. At first the bank thought the vault passcode had been leaked, but changing the passcode did nothing to thwart the attack. In a fit of desperation, the bank removed the vault passcode entry altogether figuring this would disable all access to the vault. The unauthorized user continues to make large withdrawals from the vault. It seems that the high-security authorization may have its own security flaw, how ironic!

    For this one, pay special attention to the new code that was added to do the passcode authentication, as this code is all-new and relatively untested. Hint: It may help to diagram the memory being used for the stack frame. Use gdb and/or the disassembly to learn what data is stored at what location. How does the specific data layout lead to a security vulnerability in this case?

For each of three attacks, your job is to identify how this vulnerability has come about and how to fix it. Your investigation can use a combination of techniques such as studying the C and assembly, running the program on different inputs, and using gdb or Valgrind to spy on it.

Once you understand it, architect a reproducible test case. You will use these test cases prove to the bank how each attack works:

  • case a: make a withdrawal as yourself that overdraws your account
  • case b: pilfer $40 from a TA account as a user other than the owning TA

    • choose your favorite TA as the victim in a twisted show of appreciation. Include a haiku about their awesomeness as redress for targeting them.
  • case c: steal $1000 from the bank vault despite its disabled passcode

For each of the three vulnerabilities, you are to provide an explanation, a reproducible test case, and a recommended fix. Add your reproducible test case to the custom_tests file. The rest of the information goes into your readme.txt. You should provide a concise description of the underlying security vulnerability, a precise explanation of how you constructed your input to exploit the vulnerability, and a recommendation for what the bank can change in the code to plug the security hole.

There may be more than one way to trigger a vulnerability or alternative remedies. Furthermore, your investigations may find additional vulnerabilities and bugs in this ATM program distinct from the original three. For full credit, you do not need to go beyond the stated deliverables for the three identified vulnerabilities, but we are prepared with a stash of bonus points to reward submissions that go on to report on other problematic issues in the ATM code. The bank wants to know everything they should be fixing to step up their security, they are depending on you!

Pro-tip: If you enjoyed this little taste of security, you'll love CS155!

2. Binary bomb

Those nefarious Cal students have broken into our myth machines and planted some mysterious executables we are calling "binary bombs." These programs are believed to be armed and dangerous. Without the original source, we don't have much to go on, but we have observed that the programs seem to operate in a sequence of levels. There are 4 levels in total. Each level challenges the user to enter a string. If the user enter the correct string, it defuses the level and the program proceeds on. But given the wrong input, the bomb explodes by printing an earth-shattering KABOOM! and terminating. To deactivate the entire bomb, one needs to successfully defuse each of its levels.

The Cal students have littered our systems with these landmines and we need your help. Each of you is given a bomb to disable. Your mission is to apply your best asm detective skills to work out the input required to pass each level and render the entire bomb harmless.

Your bomb is given to you as an executable, i.e. as compiled object code. From the assembly, you will work backwards to construct a picture of the original C source in a process known as reverse-engineering. Once you understand what makes your bomb "tick", you can supply each level with the input it requires and defuse it. The levels get progressively more complex, but the expertise you gain as you move up from each level should offset this difficulty. One confounding factor is that the bomb has a hair trigger, prone to exploding at the least provocation. Each time your bomb explodes, it notifies the staff, which deducts from your score. Thus, there are consequences to detonating the bomb-- you must tread carefully!

Reverse-engineering requires a mix of different approaches and techniques and will give you an opportunity to practice with a variety of tools. The most powerful weapon in your arsenal will be the debugger and an important learning goal of the assignment is to expand your gdb prowess. Building a well-developed gdb repertoire can pay big dividends the rest of your career!

Bomb logistics

Our counter-intelligence efforts been able to confirm a few things about how the bombs operate:

  • If you start the bomb with no command-line argument, it reads input typed at the console.
  • If you give an argument to the bomb:

    ./bomb input.txt
    

    the bomb will read lines from input.txt until it reaches EOF (end of file), and then switch over to reading from the console. This feature allows you to store inputs for solved levels in input.txt and avoid retyping them each time.

  • Explosions can be triggered when executing at the shell or within gdb. However, gdb offers you tools you can use to intercept explosions, so your safest choice is to work under gdb and employ protective measures.

  • The bomb in your repository was lovingly created just for you and is unique to your id. It is said that the bomb can detect if an impostor attempts to execute your bomb and won't play along.
  • The bombs are designed for the myth computers (running on the console or logged in remotely). There is a rumor that the bomb will refuse to run anywhere else.
  • The bombs were compiled from C code using gcc. Apparently Cal students don't know how to edit a Makefile to change the flags to achieve much obfuscation of the object code.
  • The Cal students also weren't aware the function names would be visible in the object code, so they didn't take pains to disguise them. Thus, a function name of initialize_bomb or read_five_numbers can be a clue. Similarly, they played it straight with use of the standard C library functions, so if you encounter a call to qsort or sscanf, it is the real deal.
  • Direct modification of the binary bomb executable can change its behavior, but be forewarned that we will test your submission against your original unmodified binary, so while hacking the executable is great fun, it won't be of much use as a strategy for solving the levels. (Although it can be an entertaining and educational exercise in suppressing explosions...)
  • There is one important restriction: Do not use brute force! You could write a program to try every possible input to find a solution. But this is trouble for several reasons:

    • You lose points on every incorrect guess which explodes the bomb.
    • A notification is sent on each bomb explosion. Wild guessing will saturate the network, creating ill will among other users and attracting the ire of the system administrators who have the authority to revoke your privileges because you are abusing shared resources.
    • We haven't told you how long the strings are, nor have we told you what characters they can contain. Even if you made the (wrong) assumptions that they all are less than 80 characters long and only contain lowercase letters, you will have 2680 guesses for each level. Trying them all will take an eternity, and you will not have an answer before you graduate.
    • Part of your submission requires answering questions that show your understanding of the assembly code, which guessing will not provide. :-)

Bomb readme

The bulk of your effort on bomb goes into defusing the levels, but we have a few follow-up questions. Answer these questions in your readme.txt file.

  1. What tactics did you use to suppress/avoid/disable explosions?
  2. level_1 contains an instruction of the form mov $<hex>,%edi. Explain how this instruction fits into the operation of level_1. What is this hex value and for what purpose is it being moved? Why can this instruction reference %edi instead of the full %rdi register?
  3. level_2 contains a jle that is not immediately preceded by a cmp or test instruction. Explain how a branch instruction operates in such a context. Under what conditions is this particular jle branch taken?
  4. Explain how the loop in the winky function of level_3 is exited.
  5. The read_array function used in level_4 declares a local variable that is stored on the stack at 0x8(%rsp). What is the type/size of this variable? Explain how can you discern its type from following along in the assembly, even though there is no explicit type information in the assembly instructions. Within read_array there is no instruction that writes to this variable. Explain how the variable is initialized (what value it is set to and when/where does that happen?).
  6. Explain how the mycmp function is used in level_4. What type of data is being compared and what ordering does it apply?

Advice/FAQ

Don't miss out on the good stuff in our companion document!
Go to advice/FAQ page

Grading

For this assignment, we expect a total number of points around 85, apportioned as follows:

  • custom_tests (15 points) Each successful attack test case earns 5 points. We will test by running tools/sanitycheck custom_tests on your submission. Your custom_tests should contain 3 test cases, one for each ATM attack.
  • readme.txt (35 points) The ATM and bomb questions will be graded on the understanding of the issues demonstrated by your answers and the thoroughness and correctness of your conclusions.
  • Input.txt (32 points) Each bomb level you have solved earns 8 points. We will test by running ./bomb input.txt on your submission. The input.txt file in your submission should contain one line for each level you have solved, starting from level 1. Malformed entries in your input.txt or wrong line-endings (see FAQ at end of advice page) will cause grading failures. To avoid surprises, be sure that you have verified your input.txt in the same way we will in grading (i.e. ./bomb input.txt).
  • Bomb explosions (up to -6 points deducted) Each bomb explosion notification that reaches the staff results in a 1 point deduction, capped at -6 points total.

Finish and submit

How to Submit is same as for previous assignments. The assignment deliverables consist of three text files (custom_tests, readme.txt and input.txt). Review the grading info above to confirm your files have the necessary contents in the proper format.

How did it go for you? Review the post-task self-check.