Skip to content

Project 1: 🐚coding

Due: Wednesday 7 October, 11:59 PM

Goal

The goal of this assignment is to gain hands-on experience with shellcoding: writing executable exploit payloads subject to constraints on the bytes that make up the payload. The classic constraint is the exclusion of NUL (0) bytes imposed by C string functions like strcpy, but some target programs have more stringent security checks. For example, input might be checked that it’s all printable characters, or grammatical English, or hella sweet ASCII art.

In this assignment, you will be writing an encoder that takes an arbitrary 64-bit RISC-V payload and encodes it to a new 64-bit RISC-V executable payload that has the same effect but is not only free of NUL bytes but also valid UTF-8.

Because not every RISC-V instruction can be expressed using such characters, you cannot simply translate each instruction in the input payload to an equivalent instruction in the output payload. (As we’ve already noted, the ecall system call instruction contains three NUL bytes.) Instead, you will output a two-stage payload. The job of the first stage is to write the original arbitrary-byte payload onto the stack and to jump to it.

For inspiration, you can read the classic papers on x86 alphanumeric encoding by rix and SkyLined.

There is also a Phrack paper on UTF-8 (x86) shellcoding by greuff. This paper contains an excellent introduction to UTF-8 encoding, but keep in mind that it was written when many fewer Unicode codepoints were assigned. These days, there are assigned Unicode codepoints that require four UTF-8 bytes to encode, for example U+1F600 (😀), which has UTF-8 encoding f0 9f 98 80.

Now take a look at the paper on alphanumeric (plus one symbol) shellcoding for RISC-V by Hаdrien Ваrrаl, Rémi Géraud-Stewart, Georges-Axel Jaloyan, and David Naccache, and the paper on RISC-V emoji shellcoding by Hadrien Barral, Georges-Axel Jaloyan, and David Naccache.

Alphanumeric shellcoding for RISC-V is hard! Your task is considerably easier. To make it more fun, we encourage you to incorporate some emoji into your encoded payloads.

The payload your encoder produces may make the following assumptions:

  • You may assume that sp, the stack pointer, points to a memory region that is readable, writeable, and executable (that is, that noexec stack is not enabled).
  • You may assume that the memory region from which your payload is executing is likewise readable, writeable, and executable (meaning that self-modifying code is allowed, though it should not be necessary).

The payload your encoder produces may not assume anything about the contents of any other register or of any part of memory, and you may not hardcode an address either for the stack or for the location of your payload. In addition, you should not overwrite or modify the already-allocated part of the stack (i.e., any memory location with address greater than or equal to whatever is in sp when your shellcode starts running.

Your payload should not have any 0 (NUL). It should not have any sequences disallowed by the UTF-8 specification, such as the byte ff.

Using UTF-8 it is possible to pad out a code point that fits in k bytes so that it takes k+1 or more bytes to encode, but these longer-than-necessary representations are not valid UTF-8, and you should not use them. For example, the uppercase letter A is supposed to be encoded only as the one-byte sequence 41; its longer encodings c1 81, e0 81 81, etc. are not valid UTF-8.

And your payload should not encode any symbol that isn’t an assigned Unicode code point. (For example, no assigned Unicode code point takes more than 4 UTF-8 bytes to encode, so you should not use any 5-byte or 6-byte UTF-8 sequences.)

The check utility included in the assignment environment will help you ensure that your payload includes only valid UTF-8 with only assigned Unicode code points.

The course virtual machine

Now that Debian has promoted RISC-V to an official port, we will be using a Debian virtual machine. We will use the Qemu emulator to run this machine. You should be able to get Qemu running in Linux (or a BSD), on a Mac, or in WSL.

For our first several projects, a precompiled Qemu distribution will be all you need; you can install it from you package manager. If you are running Debian (or a Debianalike such as Ubuntu), install the qemu-system-riscv package, if you don’t already have it. (If that package doesn’t exist, you may want qemu-system-misc instead.) On a Mac with Homebrew, brew install qemu should work. The Qemu site has installation instructions for other platforms and package managers.

Download and unpack the course VM. The download is several hundred megabytes, but the VM disk can grow to 10 GB, so make sure to put it somewhere you won’t run out of space.

Running the VM

Run the virtual machine with the command

    path/to/vm/runvm.sh

(where path/to/vm is replaced by the actual path from your current working directory to the directory containing the VM files). If all goes well, this will boot a VM all the way to a login prompt.

The runvm.sh script will boot a machine with two virtual cores and 8 GB RAM. If your host machine will have trouble delegating that many resources to the VM, you can boot single-core by removing the -smp 2 line, or the amount of RAM by editing the -m 8192M option to some smaller value.

To shut down the VM, log in as root, either directly on the console or by running su - on a user shell over ssh, and type poweroff If the VM isn’t shut off cleanly, its filesystem may become corrupted and you may lose work in progress. It’s always a good idea when you are developing in a VM to have a copy of the files elsewhere. If you set up ssh access and install the rsync package on the VM, you can easily sync files between the VM and host with rsync. (You’ll need to install rsync first: as root, apt install rsync. See below for more).

Logging in on the console

Our VM has a root (administrator) account with password root and a user account called user with password user.

Logging in from the host over SSH

Our runvm.sh script exposes the VM’s SSH server on port 8291 of the host. Rather than logging in directly on the console, we recommend you SSH in from the host; this will give you a terminal with more features than the console. You can use a command like ssh localhost -p 8291 -l user to log in over SSH as the user user.

This becomes even easier if you set up ~/.ssh/config on your host machine (not the VM) to add an entry like the following:

    Host riscv
        Hostname localhost
        Port 8291
        User user

If you do that, then typing

    ssh riscv

on the host should log you into the VM. If you copy an SSH public key to ~user/.ssh/authorized_keys on the VM, then you’ll be able to log in without typing a password.

If the key you usually use for SSH is password-protected, you could make a dedicated key just for accessing this VM (ssh-keygen -t ed25519 -f vm-key will do the trick), add the contents of the corresponding vm-key.pub file to authorized_keys, and add an IdentityFile /path/to/vm-key specifier to the Host riscv stanza in the config file on your host.

Once you have arranged for pubkey auth, you may wish to disable SSH logins via password. As root, edit /etc/ssh/sshd_config, uncomment the PasswordAuthentication line and replace yes with no, then ask sshd to reload its configuration (service sshd reload should do the trick) or just restart the VM.

Package management

Log in as root. Run

    apt update

It will update your package index. When your package index is up-to-date, you can install packages with the command

    apt install [package-name]

We created the VM specifically for this course, so you should already have many of the packages you need, but you might want to customize it by installing your preferred editor, version control system, code search tool, etc.

You may need to rerun apt update before installing new packages if it has been a while since you last did.

(You can also update already-installed packages with apt upgrade.)

Note that VSCode’s remote development extension pack does not work on RISC-V. If you have used VSCode in the past, now may be a good time to learn to use a programmer’s editor. (See also our prohibition on the use of AI tools!) You can install Emacs (Debian package emacs-nox), Vim (vim) Neovim (neovim), Kakoune (kakoune), Helix (hx), Micro (micro), or another editor packaged for Debian.

The VM clock

The VM should synchronize its clock each time it boots. If you suspend your host computer while the VM is running, the VM clock may end up wrong. As root, run

    ntpdate-debian

to update the clock.

Tips and useful utilities

In the VM, we have included the mg editor, which has Emacs-like keybindings but is tiny. You should install your favorite console programmer’s editor; a partial list is above.

We recommend that you not expose your Github credentials into the VM, because they are high value and we can’t guarantee that the VM is secure. We also recommend that you edit your project source on your host machine, where changes are less likely to be lost to filesystem corruption (but keep backups even then!). Both of these recommendations are easiest to follow if you sync a project working directory from the host into the VM over ssh, and the right tool for that is rsync, which you can install in the VM as package rsync and is probably already installed on your host machine.

For quickly moving a single small file between machines, it might not be necessary to figure out an rsync invocation or to fight with sftp. Install Magic Wormhole on both machines, then run wormhole send <file> on one and wormhole receive on the other; the send command will print a short code that you will need to supply to the receive command. In the VM, you can install any of three compatible implementations: magic-wormhole, wormhole-william, or wormhole-rs.

The environment

Download and unpack the project tarball in the VM using the command

    curl -O https://cseweb.ucsd.edu/classes/fa26/cse291Y-002/dist/proj1.tar.gz

and unpack the tarball using the command tar xavf proj1.tar.gz.

Run make in the proj1 directory to build the utilities util/dump and util/check.

Example payloads

In the payloads/ subdirectory, we have included four simple assembly programs: break.s, which when run will trigger a debugger breakpoint; exit1.s, which when run will exit with status code 1; hello.s, which when run will print a message; and shell.s, which when run will execve a shell as in the classic Aleph One shellcode.

These programs are all written simply, using whatever instructions are most convenient (including assembler pseudoinstructions like li and la). They are not written to avoid NUL bytes or be valid UTF-8; that is the job of the encoders described below.

The project Makefile includes rules to assemble these programs into binaries. You can type make payloads/break.bin, make payloads/exit1.bin, etc., to build the corresponding (RISC-V) binaries. To run the binaries, just type, e.g., payloads/exit1.bin.

The payload programs are intentionally written to bypass the usual C runtime, so that the only executable code present in the binaries is the payload routine itself. (By contrast, you saw in warmup 1 how many functions are present in a typical C executable besides main.) The dump utility will extract just this raw executable payload from the ELF binary. The Makefile will arrange to do this for you if you type make payloads/break.raw, etc. You can use od -t x1 or the hex viewer of your choice to examine these raw files, but without the ELF headers you can’t execute them on the command line.

Note that the Makefile is written using pattern-matching rules, and does not hardcode the names of the four example payloads we supply. If you write your own payload, say payloads/foo.s, then make payloads/foo.bin and make payloads/foo.raw should work, with no need to modify the Makefile.

The nonul encoder

In class, we described a strategy for encoding an arbitrary executable payload in a way that avoids any 0 (NUL) bytes: represent each word \(X_i\) in the payload using two words \(A_i\) and \(B_i\), chosen such \(X_i = A_i \oplus B_i\) but neither \(A_i\) nor \(B_i\) includes a NUL byte.

Using this strategy requires carefully writing a first-stage payload (carefully written because it can’t itself contain any NUL bytes) that reads each \(A_i\) and \(B_i\), computes their xor \(X_i\) and writes \(X_i\) to some location in memory that is both writable and executable and, when all words of the second stage have been written, transfers control to the second stage.

In nonul-template.s, we have supplied you with a concrete 42-byte first stage payload that implements this strategy. This payload expects to find the encoded second stage immediately after the first-stage payload.

You should study this payload carefully.

It first finds where it is executing and calculates the address of the byte immediately after the payload itself, using an auipc instruction and some arithmetic, and stores this address in the register s0. This allows the same shellcode to execute regardless of where in memory it is placed; the traditional shellcoding term for a code snippet like this is “getpc” code.

The payload then reads the first two words stored at s0 and xors them together to find \(n\), the number of payload words to write. This allows the same shellcode first stage to work regardless of the size of the second stage. The payload stores \(n\) in s1.

Now the payload starts the main decoding loop, which it will run \(n\) times (until s1 reaches 0). In each iteration, it loads two words from memory at address s0, xors them together, and pushes the result onto the stack. Note that the last word of the payload must be pushed first so it ends up last in memory (the RISC-V stack grows downward). In other words, this decoder expects the encoded payload to be stored as \(A_n, B_n, A_{n-1}, B_{n-1}, \ldots, A_1, B_1\).

Once the decoding loop has completed, the first stage transfers control to the instruction at sp, which (if all has gone well) is the first instruction of the second-stage payload.

How does the second-stage payload end up encoded in the format expected by the first stage? That is the job of encode-nonul.c, which you should likewise study carefully. This program reads a raw payload from a file (e.g., payloads/hello.raw), xor-encodes it into two arrays bufA and bufB along with its length, and then prints those words out in reverse order, formatted as an assembler snippet (in this case consisting of 64-bit words, preceded by the directive .dword).

A simple sed script (template.sed) will arrange to substitute the output of encode-nonul into the first-stage template nonul-template.s, in place of the line

# SECOND STAGE SUBSTITUTED HERE

(If you edit the template file nonul-template.s, make sure you don’t modify this line.)

The Makefile includes pattern rules that will take care of all of this substitution for you. If you run make nonul/hello.s, for example, the Makefile will generate the unencoded raw payload payloads/hello.raw as above, then run encode-nonul on that raw payload and substitute the output into nonul-template.s and write the resulting assembly program to nonul/hello.s. You can assemble this into a binary by running make nonul/hello.bin and extract the raw payload from that binary by running make nonul/hello.raw.

Like payloads/hello.bin, nonul/hello.bin, when run, should print a message and exit. But, unlike payloads/hello.raw, nonul/hello.raw should be free of NUL bytes, something you can check with od -t x1 or by running util/check nonul/hello.raw. When run without the -u flag, as here, the check utility looks for NUL bytes; if it finds any it will complain.

Indeed, when you run make nonul/hello.raw, the Makefile will automatically also run check for you.

You can try to modify the encoding in encode-nonul.c so it does produce NUL bytes to see what happens.

As before, the Makefile infrastructure uses pattern rules instead of hardcoding the names of the four example payloads we have supplied. If you create a new payload payloads/foo.s, then make nonul/foo.raw will assemble the new payload to a binary, extract the raw executable payload from that binary, encode that raw payload using encode-nonul and substitute the encoded output into the first-stage payload nonul-template.s to produce nonul/foo.s, then assemble that program into a binary, extract the raw payload from that binary, and finally run check on the extracted payload to make sure it is free of NUL bytes. All in one command. America!

The UTF-8 encoder

Here is where you come in.

The same infrastructure is in place for encoding payloads into NUL-free, valid UTF-8: There’s utf8-template.s, the first stage payload; there’s encode-utf8.c, the encoder for the second stage; and there’s Makefile infrastructure to let you run, say, make utf8/hello.raw to turn an arbitrary payload program payloads/hello.s into a raw payload in utf8/hello.raw and to check this raw payload using check -u. When run with the -u flag, the check command will make sure that its input is free not only of NUL bytes but also of invalid UTF-8 sequences and unassigned Unicode code points. (The check program gets this functionality courtesy of the utf8proc library.)

The second-state encoding program encode-utf8.c is similar to encode-nonul.c, but it implements a different encoding strategy that is guaranteed to produce all ASCII characters (and therefore valid UTF-8). It splits each byte of \(X_i\) into two 4-bit chunks (aka nibbles). The more significant nibble of \(X_i\) goes in the less significant nibble of \(A_i\); the less significant nibble of \(X_i\) goes in the less significant nibble of \(B_i\). The more significant nibble of both \(A_i\) and \(B_i\) is set to 1, which guarantees that each byte is non-NUL and a 7-bit ASCII character (and therefore valid UTF-8 by itself). For example, the byte 0x42 is split into the bytes 0x14 (encoding the more significant nibble of 0x42) and 0x12 (encoding the less significant nibble of 0x42).

You should not modify encode-utf8.c. No doubt other encoding strategies could be made to work, but it’s simplest if everyone sticks with this one for this assignment.

In utf8-template.s, we have supplied you with a first stage payload that decodes and then jumps to a second stage encoded according to the strategy described above. This payload expects to find the encoded second stage immediately after the first-stage payload.

There’s just one problem: The first-stage template in utf8-template.s doesn’t consist of valid UTF-8! It even includes some NUL bytes! We’ll have to fix that.

The assignment

You will modify utf8-template.s so that, when assembled, the first-stage payload is valid UTF-8. (Note that this does not mean that each instruction, in isolation, must be the UTF-8 encoding of some bytecode. Instruction boundaries and UTF-8 code point boundaries don’t have to line up; it’s okay, for example, for the last byte of an instruction to have most significant bits 110 and then have the first byte of the next instruction have most significant bits 10.)

You should not modify any file other than utf8-template.s. In particular, you should not need to modify encode-utf8.c, the Makefile, or the dump or check utilities.

Reconstituting \(X_i\) will require a sequence of bit operations including ors, ands, and shifts.

As you work on your first-stage payload, you will need to change the instructions you use.

Stay flexible about what registers to use! With 4-byte, uncompressed instructions, odd-numbered registers will tend to cause the most significant bit of a byte to be set; whereas many compressed instructions can access only the 8 registers x8 through x15 (aka s0, s1, and a0 through a5).

You may also need to add instructions that don’t have a useful effect but which have the right bit representation to cancel out the UTF-8 effect of some instruction you really need. However, by being flexible with registers selection and immediate value handling, it is almost always possible to avoid the need for dummy instructions. Your instructor’s UTF-8 first stage solution is just 5 instructions and 4 bytes longer than the starter code. A solution that sandwiches each instruction between dummy lui instructions just to get to valid UTF-8 will not receive full credit! More importantly, writing such a solution will not teach you as much about the RISC-V instruction set, which is the real goal of this assignment.

References

The RISC-V instruction set manual is refreshingly readable. The latest ratified version of the ISA manual is available to read on the Web and as a PDF.

You will want to spend most of your time with Chapter 35, “RV32/64G Instruction Set Listings”, for its tables of encodings of 32-bit instructions and with Section 27.1.8, “RVC Instruction Set Listings”, for its tables of encodings of 16-bit compressed instructions. (The section numbers may be different if you consult earlier versions of the spec.)

The Unicode Consortium maintains a site with lots of helpful technical information; the Unicode technical FAQ makes a good starting point. You may also want to consult the emoji table.

As you experiment with UTF-8 encodings, you may want to keep a Python 3 REPL open: You can, for example, use the decode method to check that a particular byte sequence is the valid UTF-8 representation of an assigned Unicode code point. Refer to the Python Unicode documentation for more.

Logistics

You will submit using Gradescope. You should submit just the file utf8-template.s, which contains your modified first-stage payload.

As noted above, you should not modify any file included in the project tarball except utf8-template.s. We will test your solution with an unmodified Makefile, an unmodified template.sed script, an unmodified encode-utf8.c encoder, and unmodified dump and check utilities.

You should not need to use any external libraries in your encoder. Please check with the course staff before using any such libraries.

You must not copy code from any shellcode encoders.

Grading

TBD.