# Reversing-II 100 (NES reverse engineering)
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:
```shell[~/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:
```cpp   // 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:
```diff   // 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: 0x94afNew PC: 0x94b1New PC: 0x92d7New PC: 0x92d9New PC: 0x9309New PC: 0x930bNew PC: 0x930eNew PC: 0x9311New PC: 0x9314New PC: 0x9315New 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:
```diff+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:
```cppprintf("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 = 02New PC: 0x94b1, [0x0031] = c0, Y = 02New PC: 0x92d7, [0x0031] = 00, Y = 00New PC: 0x92d9, [0x0031] = 00, Y = 00New PC: 0x9309, [0x0031] = 00, Y = 00New PC: 0x930b, [0x0031] = 00, Y = 00New PC: 0x930e, [0x0031] = 00, Y = 00New PC: 0x9311, [0x0031] = 00, Y = 00New PC: 0x9314, [0x0031] = 00, Y = 00New PC: 0x9315, [0x0031] = 00, Y = 00New 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:
```python>>> 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}```