TL;DR: Cave Story for HaikuOS go SEGV.

BGGP3

The Binary Golf Grand Prix is an annual competition (three years now, that counts) where you Golf (do fun stuff to) Binary files. The first year had people create tiny ambigram binaries. The second year involved polyglots. This year’s Binary Golf Grand Prix (BGGP3) is all about finding tiny crashes. We want to find the smallest possible input to a program that will crash it and, ideally, let us take over control flow.¹

At around the same time BGGP3 was announced, a friend of mine mentioned that Cave Story had been ported to HaikuOS². I thought aloud, “wouldn’t it be hilarious to find a tiny crash in the Cave Story port to HaikuOS?” And so it was. I ended up finding a crash in both the HaikuOS version (the original NXEngine), and the version that gets bundled into most Linux distributions (nxengine-evo).

Fuzzing Cave Story

The first step was to find an appropriate source and sink in Cave Story to target with fuzzing. By playing the game a little bit and downloading a local copy of the source code, I decided to use the player.dat savegame files as an input, with the target being the profile_load function which parses and loads the profile files. To hit this function directly, I simply modified the start of the main function in main.cpp to attempt to load any profile we pass in on the command line.

#include "profile.h"
#include "profile.fdh"

int main(int argc, char *argv[])
{
    Profile p;
    profile_load(argv[1], &p);
    return 0;

Next, I created afi/ and afo/ folders for AFL++ to store input and output files, respectively. I copied some of the legitimate profile.dat files into afi/ and let it run with afl-fuzz -t 5000 -n -i afi -o afo ./nx @@. This just happened to be the format of the afl-fuzz command most recently in my history, I can’t even remember what the options all mean. I didn’t expect this to work, but it found several crashes almost immediately.

Analyzing the Crash(es)

There were two crashes found, a 60 byte crash (the “large” crash) and an 8 byte crash (the “small” crash). I’ll be using the source code from the original NXEngine to demonstrate, but the vulnerable profile_load function is the same in both the NXEngine and nxengine-evo repositories.

The Large Crash (60 bytes)

Download Here

Let’s start with the large crash, since it’s more robust. The beginning of the file, the Do041220 string, is a magic value that the loader uses to determine if this is even a valid profile.dat save file. We can go ahead and ignore all the intermediary bytes up until that last 0x5C.

00000000: 446f 3034 3132 3230 0d00 0000 0800 0000  Do041220........
00000010: 2de6 0100 20e0 0000 0200 0000 0300 0000  -... ...........
00000020: 0300 0000 0000 0000 0000 0000 0000 0000  ................
00000030: 0000 0000 0000 0000 0000 005c            ...........\

Let’s look at the original section of the code that loads the player’s weapons from this file. As you can see, there’s a u32 that gets read from the file and stored in the int type. This ends up being our 0x5C value, but as a little endian u32, thus it gets read as 0x5C000000. Further down, when we try to access file->weapons[type] we end up trying to write to a memory location way out of bounds, and we segfault.

// load weapons
fseek(fp, PF_WEAPONS_OFFS, SEEK_SET);
for(i=0;i<MAX_WPN_SLOTS;i++)
{
	int type = fgetl(fp);
	if (!type) break;
	
	int level = fgetl(fp);
	int xp = fgetl(fp);
	int maxammo = fgetl(fp);
	int ammo = fgetl(fp);
	
	file->weapons[type].hasWeapon = true;
	file->weapons[type].level = (level - 1);
	file->weapons[type].xp = xp;
	file->weapons[type].ammo = ammo;
	file->weapons[type].maxammo = maxammo;
	
	if (i == curweaponslot)
	{
		file->curWeapon = type;
	}
}

The Small Crash (8 bytes)

Download Here

This crash isn’t as reliable, but I think it’s more fun. I can only replicate this crash in the original NXEngine version of the code, and only if calling profile_load directly from main. It won’t work if we let the game launch normally and pick up the corrupt profile.dat file. As you can see, this crash file consists of only the magic value.

00000000: 446f 3034 3132 3230                      Do041220

How does this lead to a crash? Easy! The original code doesn’t do any end of file checking or error checking when reading the profile.dat file. When this file is loaded, the fgeti and fgetl wrappers start returning random garbage stack values instead. This is likely why the crash is inconsistent. For whatever reason, when invoking the function directly, the garbage returned by fgeti and fgetl leads to a crash, similar to the large crash, with a large positive or negative type value. When loading the profile normally, it only reads null bytes, which doesn’t cause a crash, until the parser fails and rejects the file because of a lack of secondary magic value (the string “FLAG”) further down in the file.

If we allow execution of this small crash to proceed until fgetl is called to determine type, we can see the following in gdb.

(gdb) info locals
value = 32767

(gdb) p &value
$1 = (uint32_t *) 0x7fffffffc594

If we dump memory at that address, we see it’s just whatever garbage was previously on the stack there.

(gdb) x/16bx &value
0x7fffffffc594:	0xff	0x7f	0x00	0x00	0x00	0x27	0x5f	0x5e
0x7fffffffc59c:	0xaa	0x5b	0x49	0x7c	0x00	0xdf	0x55	0x55

Absent of any checks, the fgetl and fgeti functions just return information off the stack. I’m speculating here, but this could be used as a memory leak which could be combined with the arbitrary write in the weapon slots to do some fun stuff, maybe.

Fixing the Crash

First off, we check the results of the fread call and use that to determine if we should bail early. If we hit an error or end of file when we don’t expect it? Just stop trying to parse the file. Nothing good can come of it. In the below example, you see we check that the amount of data read from the file is what we expect and if not, we error out.

uint32_t fgetl(FILE *fp)
{
    uint32_t value;
    int ret = fread(&value, 4, 1, fp);
    if (ret != 1) {
        staterr("fgetl: error reading uint32_t from file");
        fclose(fp);
        exit(0);
    } else {
        return value;
    }
}

Next, we want to make sure the weapon type is something we expect before we start blinding writing memory. The fix here is to check if type is within the bounds of MAX_WPN_SLOTS and, if not, skip it. I didn’t include any logic to keep chewing through the file, so it’s possible a corrupted save will cause the file to get off by one byte, which would cause the wrong thing to be loaded. But it shouldn’t crash anymore, so that’s probably fine.

for(i=0;i<MAX_WPN_SLOTS;i++)
{
    int type = fgetl(fp);
    if (!type) break;
    if (type < 0 || type >= MAX_WPN_SLOTS) {
        staterr("profile_load: invalid weapon type %d", type);
        break;
    }

Tallying the Score

So we have two scores here, I’d say. One for the large crash (that works out of the box on the current package for both Linux and HaikuOS) and the other, smaller, crash which takes some luck to get going.

Large Crash

+4096 - 60 = +4036 points for the binary size
+1024 writeup
+4096 patches merged (³, ⁴, ⁵, ⁶)

Total: 9156

Small Crash

+4096 - 8 = +4088
+1024 writeup
+4096 patches merged

Total: 9208

Do I win?

The small crash probably doesn’t count, and I don’t know if crashing the Cave Story port on HaikuOS is more or less comical than crashing GnuCOBOL, so I may need another way to beat Remy’s score of 9176.⁷

Results Update

The official results are in!⁸ The scorer accepted by smaller crash, giving me a slight edge over Remy and putting me in fourth place! Shoutout to retr0id for his first place chip8 bug. While you’re there, check out his MD5 PNG hashquine. It makes a great phone background!

Never Stop Reading: Crashing the HaikuOS Port of Cave Story