Rating:
We are provided with a NES ROM (impossible_game.nes). The goal is simple - find a cheat code for walking through walls. The hints explain that we should flip only one bit in a data section of the ROM.
We would ideally avoid reversing the entire game, as that would take forever - especially for a 100 point challenge. I decided to instrument an emulator to find the instructions responsible for handling the collision.
After failing to figure out how to open a ROM in higan, I cloned the source for FCEUX. As the emulator is available in nixpkgs, building it was a piece of cake:
[~/ctf/2020/trendmicro/nes-re/fceux]$ nix-shell '<nixpkgs>' -A fceux
[nix-shell:~/ctf/2020/trendmicro/nes-re/fceux]$ $buildPhase
(unfortunately this includes a non-idempotent patch to SConstruct, repeated builds had to be done with git checkout SConstruct;$buildPhase)
Some strategic source spelunking quickly lead me to the code responsible for dispatching an instruction:
// x6502.cpp, in X6502_Run, around line 490
IncrementInstructionsCounters();
_PI=_P;
b1=RdMem(_PC);
ADDCYC(CycTable[b1]);
I added some quick-n-dirty logging to print a line each time an instruction at a specific address is reached for the first time:
// x6502.cpp, in X6502_Run, around line 490
IncrementInstructionsCounters();
_PI=_P;
+ static bool seenPC[0x10000] = {0};
+ if (!seenPC[_PC]) {
+ printf("New PC: 0x%04x\n", _PC);
+ seenPC[_PC]=1;
+ }
b1=RdMem(_PC);
ADDCYC(CycTable[b1]);
I recompiled the emulator and fired up the game, fully prepared to get spammed by a large amount of output. I made sure to move my character both ways, but avoid colliding with the wall. Then, I applied the age-old technique of marking a point in the output of a CLI program by pressing Enter a few times and finally walked into the wall. This yielded the following, quite short output:
New PC: 0x94af
New PC: 0x94b1
New PC: 0x92d7
New PC: 0x92d9
New PC: 0x9309
New PC: 0x930b
New PC: 0x930e
New PC: 0x9311
New PC: 0x9314
New PC: 0x9315
New PC: 0x9317
I've set out to obtain the disassembly of these addresses. Unfortunately, the Linux version of FCEUX includes only the most basic UI, but the Windows build runs just fine in wine, and contains an intuitive debugger. Trying not to get distracted by the code textbox using a non-monospace font (probably a Wine quirk :P), I used "seek PC" to find this code:
00:94A9:A5 31 LDA $0031 = #$C0
00:94AB:29 40 AND #$40
00:94AD:F0 04 BEQ $94B3 ------- jumps-.
00:94AF:E6 33 INC $0033 = #$00 \ <- only runs on collision
00:94B1:E6 34 INC $0034 = #$00 | <-
00:94B3:AD E9 04 LDA $04E9 = #$C4 <- here '
As we can see, the collision flags at this moment are stored in address $31 of the zeropage, and bit $40 corresponds to the collision we want to avoid. I've added a write watchpoint at $0031 to find that it's only written in these two places:
00:9739:A4 36 LDY $0036 = #$C4
00:973B:B9 F8 03 LDA $03F8,Y @ $04BC = #$00
00:973E:85 31 STA $0031 = #$C0 <-- useless write
00:9740:A4 31 LDY $0031 = #$C0 read it again immediately (ever heard about TAY?)
00:9742:B9 14 99 LDA $9914,Y @ $99D8 = #$00 index into a table
00:9745:85 31 STA $0031 = #$C0 <-- remember the flags
Looks like we need to overwrite the byte at $9914+Y. But what's Y when the collision occurs? When it finally happens, the register will surely have already been overwritten a hundred times over, and if we place a breakpoint around 00:9745, there's no way to know whether it's actually the interesting collision being evaluated (maybe it's just the floor?).
As FCEUX doesn't have any reverse-debugging features I know of, I decided to add another ad-hoc patch. First, whenever $0031 is written, I remember the value of Y:
+uint8_t p4writeCollY = 0;
static INLINE void WrRAM(unsigned int A, uint8 V)
{
+ if (A == 0x0031) {
+ p4writeCollY = _Y;
+ }
RAM[A]=V;
}
Then, I print it when a new instruction is executed:
printf("New PC: 0x%04x, [0x0031] = %02x, Y = %02x\n", _PC, RAM[0x31], p4writeCollY);
Repeating the same experiment, we obtain
New PC: 0x94af, [0x0031] = c0, Y = 02
New PC: 0x94b1, [0x0031] = c0, Y = 02
New PC: 0x92d7, [0x0031] = 00, Y = 00
New PC: 0x92d9, [0x0031] = 00, Y = 00
New PC: 0x9309, [0x0031] = 00, Y = 00
New PC: 0x930b, [0x0031] = 00, Y = 00
New PC: 0x930e, [0x0031] = 00, Y = 00
New PC: 0x9311, [0x0031] = 00, Y = 00
New PC: 0x9314, [0x0031] = 00, Y = 00
New PC: 0x9315, [0x0031] = 00, Y = 00
New PC: 0x9317, [0x0031] = 00, Y = 00
Looks like we need to patch $9916, then. Careful to take into account the iNES header and ROM load address, we try our modification out:
>>> d = open('impossible_game.nes', 'rb').read()
>>> d = bytearray(d)
>>> d[0x1926] = 0x80
>>> open('possible_game.nes', 'wb').write(d)
This lets us walk right through the wall. As a finishing stretch, we use the Game Genie Decoder/Encoder tool included in fceux.exe to turn our findings into a cheat code, which is also the flag:
TMCTF{EAOPVPEG}
