Assignment 2

Setup

This is an individual assignment. Indeed, it is customized to every student. You may discuss questions and potential solutions with your classmates, but you may not look at their code or their solutions. If in doubt, ask the instructor.

You will need to use the CSUG machines. Your assignment includes binaries that are only guaranteed to work on CSUG machines. They may work elsewhere, but we will ignore any issues that arise from not using the CSUG machines.

If you want to take a slip day, as permitted by your syllabus, your email request must be sent to the instructor before the deadline. The instructor will note it, but will not acknowledge it immediately.

Preliminaries

To obtain your assignment, log in to a CSUG machine, and execute:

wget https://cs.rochester.edu/~sree/courses/csc-252-452/fall-2019/a2/a2-URID.zip

Replace URID with your URID. This will download your assignment. Unpack it.

Setup

The purpose of this assignment to write three C files containing only standard C constructs and no goto statements. The code to be written in the C files must be inferred from looking at incomplete fragments of some supplied assembly language files.

To do a quick test, execute the following commands:

cd a2
touch a.c g.c s.c
make

The touch command creates empty files (if they do not exist) or changes the last modified data of the file if it exists. In this case, you should see the following errors from make (some of them will be different for you):

gcc -c -std=c99 -Wall a.c -o a.o
gcc -c -std=c99 -Wall g.c -o g.o
gcc -c -std=c99 -Wall s.c -o s.o
gcc -std=c99 -Wall genkey.o a.o g.o s.o -o genkey
genkey.o: In function `main':
genkey.c:(.text+0x12): undefined reference to `r'
genkey.c:(.text+0x23): undefined reference to `ask'
genkey.c:(.text+0x32): undefined reference to `NP'
genkey.c:(.text+0xc7): undefined reference to `s'
genkey.c:(.text+0xd9): undefined reference to `ncmp'
genkey.c:(.text+0x11b): undefined reference to `ncmp'
collect2: error: ld returned 1 exit status
Makefile:7: recipe for target 'genkey' failed
make: *** [genkey] Error 1

Next, type ./unlock, you should see:

Enter output from genkey for key length 7: ^C

Where ^C means you pressed CTRL+C. Note the key length.

If you see this, you're all set to begin solving the assignment.

The Goal

Prof. Pain is in a bit of a spot. He created an unbreakable combination lock scheme a long time ago, but lost the source code! He only has the following:

  1. unlock, a program to unlock his lab, which is demanding a combination that he no longer remembers.

  2. genkey.o, a program to generate combinations for unlock, whose source code is completely lost. Only the object file remains.

  3. a.asm, g.asm, and s.asm, three programs that must be combined with genkey.o to produce genkey. The source code for these programs is also lost, and the assembly files are damaged, so they cannot be reliably reassembled.

Prof. Pain thinks that he can read the assembly files and rewrite the C files (a.c for a.asm, g.c for g.asm, s.c for s.asm). Unfortunately, the assembly language files are for the new-fangled x64 architecture, and he has no time to learn a new ISA (VAX was good enough for him, and should be for everybody too!). So he's decided to create an assignment for CSC252 where he hears they're learning x64 assembly.

This is where you come in. Your job is to reverse engineer the C files that generated a.asm, g.asm, and s.asm. This means that you look at the assembly code, and write the C code that replicates what the assembly code was trying to achieve.

If you succeed, you'll have three files a.c, g.c and s.c. Once you have those files, run make. It should give you a binary genkey. Then:

./unlock
Enter output from genkey for key length 7: ^C

Where ^C means you pressed CTRL+C. Note the key length.

Run ./genkey, and type in the key length you saw:

Press CTRL+C to exit.
Enter a positive integer for key size: 7
7 is just right!
Your combination is:
7 9 9 52 64 117 167 160 193

Then type the combination into unlock:

./unlock
Enter output from genkey for key length 7: 7 9 9 52 64 117 167 160 193
YOU ARE IN!

You will get the above message if you succeed. If you did not succeed, you'll see this instead:

./unlock
Enter output from genkey for key length 7: 7 9 9 52 64 117 167 160 19
ERROR: Combination failed.

There are no limit to the number of times you can try, since the goal of this assignment is NOT to figure out the combination. It is to be able to demonstrate that you can manually reconstruct C code from assembly language.

The autograder has been setup to test if your reconstructed C code is the fully correct, not just if your reconstructed program can output the right combination. Make sure it is satisfied to ensure a full grade. (The autograder will be available starting Friday evening).

How to do this assignment

  1. Identify all global variables (including their types and default values) by looking at the assembly files. Put them in the correct C files (a.c, g.c or s.c).

  2. Identify all the functions from the assembly language files, including the parameters they take and their return types. Put empty functions with this information into the correct C files.

  3. At this point, you should be able to run make to compile and obtain genkey. You can run ./genkey, but it will not produce the right combination (and may not even run correctly), but it can only get better from this stage.

  4. Look at the assembly code for each function. Recall that it is damaged, and may be missing things you expect to find. It is generally believed the actual logic is unscathed.

    Now, for each function:

    1. Recover local variables and their types.

    2. Recover expressions.

    3. Recover conditionals and loops.

    4. Reconstruct the C code and write it in the correct place.

  5. Repeat Step 4 for all assembly files, run make, and genkey until the unlock program cracks.

None of the C functions are very long. Good luck!