Writeup by celi0n for Nessie

Challenge description

A friend of yours, in his forties, spent his carefree youth playing a game called Nessie. He never managed to finish the game despite having spent long hours in front of his NES.

Will you be able to do better than him and win his undying gratefulness?

Overview

It was my first time reversing (and playing) at a NES game, so I picked randomly the fceux emulator. After skipping the welcome screen, the game interface looks like the following:

Some aquatic monsters spawn from time to time and we can move the red cursor to shoot them. It is difficult to shoot them before they disappear so we can use the boosts on top/left border of screen to teleport to the monster. However we have 5 teleport.

Where is the flag ?

I tried playing for a bit and whatever I was doing, nothing new was happening. So I guessed that some conditions has to be met to get the flag. I tried reversing the NES game with the ghidra NES plugin (https://github.com/kylewlacy/GhidraNes) but it was not loading the game, and I have no IDA pro or binary ninja pro so it was my only option.

I looked at some post on NES such as this one: https://medium.com/@henrique4win/reverse-engineering-a-nes-game-the-long-way-around-part-1-0df141f3ac3a and understood approximately the format. At first I decided to continue a bit with dynamic analysis and check from time to time the code via the debugger integrated in fceux.

Understanding the game variables

fceux provides an amazing hex viewer which colors the last values accessed / modified. It is really useful to understand the game logic.

Fortunately, as it is a NES game, most of the important values are packed close to the address 0. Also made to run on a small microprocessor (named MOS Technology 6502 i think), so the operations are simple, only a accumulator A and two registers x and y. Another online post told me that the memory looks like this:

• PPU Memory ($2000-$3FFF) holds sprite/tile maps, palettes, etc.

• Zero Page ($0000-$00FF) is frequently used for variables due to faster access.

• Watch Stack ($0100-$01FF) for return addresses and temp storage.

• The Reset Vector at $FFFC-$FFFD points to the game’s entry point.

• Game logic often lives in bankswitchable PRG-ROM regions (observe $8000-$FFFF).

By looking at the values updated for every operations and changing them in hex view, I was able to locate interesting variables (some of them were discovered later):

0x5 => Related to game's color
0x6 => Coordinate x of background sprite => 0xff = welcome page, 0 = level
0x6 => Coordinate y of background sprite
0xb => 3 if there is a monster, 6 when it has been shot, otherwise 1 if monsters left, 0 if all monsters killed
0xc => A 1 byte decreasing timer
0xd => Coordinate x of cursor (start at 1 and x8).
0xe => Coordinate y of cursor (start at 1 and x8).
0xf => Set to 1 when we don't kill a monster.
0x10-13 => Decreasing counter every time a monster appear.
0x16 => Number of bullet left. Start at the same value than monster counter.
0x1A => Number of teleport left.
0x1B-0x1F => State for random generator

0x1F8 and 0x1FB => pressed key

0x1814 => coord_x_monster ? 
0x1815 => coord_y_monster ?

A nice trick that I learned later is to slow down the emulator speed and stop the emulator in order to watch precisely what happens at every game operation without having to put a breakpoint.

We can extract 2 important information from this analysis:

• The number of monsters is really high. It explains why we were not able to finish the game manually.
• The number of bullet is equally high. So we have exactly one bullet for every monster.

Hack the game

The first thing to try is to set the monster counter to zero. We can do so via the hex editor view.

Well, it doesn’t look like a flag…

It looks like the games knows that we have cheated, or at least we broke the game logic.

At this point I tried different things like killing a few monsters by myself or setting the bullet left to zero to match the state if we had killed every monster. But I was still a bad hunter…

(Limited) static analysis

After doing finishing some slides for a work presentation, i decided to tackle the ghidra issue and followed another blog post which tells that the NES game is composed of multiple banks, and that we can load each bank into ghidra as raw binary with 6502 architecture. You need to remove the first 16 bytes and limit the length to the max for this architecture which is 16kb to get the first bank. According to the tutorial, the main code begin at 0x8000.

However, ghidra automated analysis doesn’t find anything so I had to manually decompile the code (by pressing ‘D’) after 0x8000 until I discovered a function that looks interesting. I cross-checked with the debugger too.

And we get our main function !

After renaming the static variables with the names we found in Understanding the game variables, we can find that this while loop is responsible for taking the user input and the sub-functions under ifs are actions like going right-left, teleporting, shooting … And the 3 functions after it are for updating the game state (like checking if there are monsters left, if the timer is at zero and a monster has to spawn, …). By doing this analysis I found that the variable at 0xf is set to 1 when we miss a monster. So I tried to freeze this variable to zero in the emulator and do again the set-monster-to-zero tricks. And TADA, I get the flag:

Easy challenge right ? Wait, the flag is incorrect ? Must be a typo…

Solving Nessie the right way

Unfortunately, the flag obtained via this method is random and not the correct one. It explains why this was the challenge with the less solves in reverse. So we need to find another, more legitimate way to solve it in order to not break the flag. At this point I guessed the generation of the flag was linked to some variables around 0x2000 that I was not able to reverse. It could also be linked the random generator state which is used every time a monster appears, to compute its position and how much times it would stay.

There was two way to solve this problem (and I think some players solved it both ways)

1. Cheat just enough to keep the game state legit, and get the flag.
2. Reverse the code printing the flag and simulate the game running full speed.

Option 1 looked more appealing to me as it could be an “easy win”, but I know other player tried it and failed. The second should ultimately works but require reversing the whole game in details (with the others code bank I haven’t loaded in ghidra yet). I explored it a bit, just in case it was really easy but my broken setup with ghidra was making everything slower.

Cheating nicely

Setting monsters to zero is not a subtle way to cheat, so as we are skilled gentleman, we can kill every monsters by ourself. After all, there is only 0x1e8480 = 2 000 000 of them.

But moving to the correct position to kill them is not easy, so I first tried to let the game run and force the monster missed to zero. I toggled the game speed to turbo (3200,0%), it tooks some time, I believe ~1h30, and the result was not successful.

So for the next try I decided to set every chance on my side:

• I patched the game to remove the if around the teleport code to teleport automatically to the monster at every frame, and removed the code decreasing the teleport counter.
• I forced the shoot action every time.
• I set the event timing counter of the game to 2 at every game loop so that every event takes almost no time (not 1 because i was afraid it will miss some events).
• I tried every emulator to find the fastest one (it was already fceux).
• I looked at fceux source code to see if I could increase turbo speed further than 3200,0% (unsuccessfully).
• I tried to remove a function that was setting the time between frame i believe (the game was not working anymore).
• I disabled game audio.
• I lowered game resolution.
• I removed some calls to 0xffxxx functions (other code banks ?) which I believed were for the game sprites.

After maybe 30 minutes running, I found that it was shooting too much and it won’t have enough bullet left. As it was getting late, I wanted to have all odds on my side:

• I set the event timing counter of the game to 1 at every game loop so that every event takes almost no time and no bullet is missed.
• I turned back on the calls to 0x7fxx functions because they might be useful after all.
• I decreased game resolution to 1 pixel per 1 pixel.
• I set “Frame Advance Delay” from 1 to 10. Whatever it is, I don’t want delay.
• I closed the hex viewer to be faster.
• I saved the game state multiple times (make sure to stop the turbo mode first while doing so, it almost crashed near the end).
• I loaded the initial game with the cheated state just before the last kill to defeat any self-check detecting code patches.
• I left my mouse in the game window and closed everything because every-time I was focusing something else the speed was decreasing a lot.
• I went on my professional computer to solve a crypto challenge in parallel.

And finally, I solved it !