## X-MAS CTF 2020 Writeup: Ken Kutaragi's Secret Code### Or, How to Reverse-Engineer a PS1 Game
[X-MAS CTF 2020](http://web.archive.org/web/20201219210007/https://xmas.htsp.ro/home) was my first CTF – I do ROM hacking, fan translation, and hardware modding, but I haven't done much hacking related to modern systems, so I was a wee bit worried there wouldn't be many challenges suited to my skillset. Imagine my surprise and delight, then, when I saw the challenge *Ken Kutaragi's Secret Code*, which consists of a PlayStation executable! And wouldn't you know it? I've hacked away at quite a few PS1 games in my day! Not many people solved it, likely because it requires quite niche skills – so let me share those with you!
---
## Identifying our goal
The challenge description is as follows.
![Ken Kutaragi's Secret Code. We found this exe in a time capsule from the 90s! Santa told us that it's signed with a secret code by Ken Kutaragi himself. The gnome department has tried [Up Up Down Down Left Right Left Right B A Select Start] and it didn't work, so this is why we have come to ask you for your engineering help.Note: Replace '()' with '{}'. Author: Milkdrop. Files: COMPAC.EXE.](https://i.imgur.com/j1psrTI.png)
Ken Kutaragi is the name of “The Father of the PlayStation” – an executive who spearheaded the development of the PlayStation, so already, we have a hint that the challenge concerns the PS1. This is further confirmed by taking a closer look at the file: although it's an EXE, Windows can't run it, and taking a look at it in a hex editor reveals the following:
![The file starts with the signature “PS-X EXE”!](https://i.imgur.com/VoWTQ7R.png)
So there we go! **It's a PlayStation 1 program!** Let's try booting this baby up in an emulator! The state of PS1 emulation is a bit dire – and especially, emulators with debuggers are few and far in between. When I can, **I use [No$psx](https://problemkaputt.de/psx.htm): it has the most full-featured debugger!** It *does* often have problems loading from disc, making it a non-option for many games, but what we're dealing with is a naked executable rather than a disc image. Let's take a look!
![A copyright screen, followed by a flashy demo.](https://i.imgur.com/JSA4Rd7.png)
It seems to be a modified demo, with some random characters at the top – characters that change every single frame. The challenge description hinted that there's a secret code, so let's mess around with some buttons – in this screenshot, I've just mashed square:
![The random letters are looking less random, and now it says “WRONG!” beneath them.](https://i.imgur.com/VQfMibv.png)
Every time a button is pressed, a letter in that mess of characters stops randomizing, and turns into a fixed letter! Resetting and messing around with the buttons a bit more allows you to narrow down what the behavior displayed really is: what character it stops on seems to partly depend on the button pressed. For example, for the very first character, pressing square always turns it into `E`, pressing left on the D-pad produces `B`, and pressing R1 makes `X`. We can also see that the string doesn't seem to be random: it starts with `E50Y#IGHT-HECARII` appears. Could this be a corrupted version of `COPYRIGHT-HECARII`, as in *Hecării, Ţuica şi Păunii*, the team organizing the CTF? As a side note, running the Linux command `strings COMPAC.EXE` – good practice when reverse-engineering anything where you might expect to find ASCII strings – shows us the promising bit of text `COPYRIGHT-HECA  I-TUI`. It's somewhat nonsensical – it seems like they're using some kind of compression – but it confirms our suspicions. Early in the executable, the strings `WRONG!` and `Correctus.` also appear.
And indeed: one more important piece of information we obtain here is that after 44 button presses, the text `WRONG!` appears below the text we just produced. A-ha! Now what we must do is clear: **we must deduce a button code that decrypts a string** and produces a “correct” response. If there was no confirmation whether we've done it right or not, this challenge might be prohibitively difficult – but that “WRONG!” turns out to be the lynchpin that busts this challenge wide open. Let's get to work.
---
## Digging into the code
ROM hacking is all about dynamic analysis. There are two reasons for this. For one, historically, static analysis tools haven't been properly usable with obscure and/or old CPU architectures and banking systems. That's changing a bit lately: nowadays, both IDA and Ghidra can be helpful for certain old consoles – and indeed, I heard that some people solved this challenge using static analysis tools like those. However, more saliently, dynamic analysis is perfectly suited to “finding a needle in a haystack”: generally when ROM hacking, you don't want to disassemble or decompile an entire program, but just figure out select little parts here and there – and for that, read/write breakpoints and live memory analysis are a beautiful boon!
To start with, we need to know where to look. We're trying to decode a string, so… let's start by finding where in memory that string is, shall we? The easiest way to find something in memory is to do a string search for it. Do we have a string to search for? We absolutely do! Our wrong decoded string up there: `E580Y#IGHT-HECARIA-. IC O└I  IU  /-< OT--ZLPJ`! There are some weird characters in there, and we don't know if perhaps some of this corrupted text could be an artifact of the text display routine, so let's just search for the part that seems “right”: `IGHT-HECARI`. No$psx doesn't have a string search feature, so let's dump the RAM to a file and search in a hex editor. Here, a memory map helps – googling “ps1 memory map” nets you one in the very documentation of the emulator.
```Memory map  KUSEG     KSEG0     KSEG1  00000000h 80000000h A0000000h  2048K  Main RAM (first 64K reserved for BIOS)  1F000000h 9F000000h BF000000h  8192K  Expansion Region 1 (ROM/RAM)  1F800000h 9F800000h    --      1K     Scratchpad (D-Cache used as Fast RAM)  1F801000h 9F801000h BF801000h  8K     I/O Ports  1F802000h 9F802000h BF802000h  8K     Expansion Region 2 (I/O Ports)  1FA00000h 9FA00000h BFA00000h  2048K  Expansion Region 3 (whatever purpose)  1FC00000h 9FC00000h BFC00000h  512K   BIOS ROM (Kernel) (4096K max)        FFFE0000h (KSEG2)        0.5K   I/O Ports (Cache Control)```
“Main RAM” sounds about right! Ctrl+G in the memory view of the debugger, go to `80000000`, click “Utility” → “Binarydump to .bin file”, 2048 KiB is `0x200000` so let's enter that as the number of bytes to dump; save that somewhere… And wouldn't you know it? Searching through that in a hex editor – in old games it's far from a guarantee that the text is encoded in ASCII, but it seems to be the case here – it's revealed that **at `0x6B8A8`, we find the string we're decrypting!** That's `0x8006B8A8` in the RAM, and indeed, in the bottom left memory view section of the debugger:
![It's there!](https://i.imgur.com/IKHn5II.png)
Our string is there! Twice! Looking at this change live as we're playing, it seems that the first instance is the underlying string that we actually care about, and the second instance is the one that gets characters randomized before printing. Resetting the program and looking in this memory location reveals its original state:
![More debugger.](https://i.imgur.com/xdAK0g7.png)
`COPYRIGHT-HECARII-TUICA-SI-PAUNII-(NOT--RLY)`! And it's 44 characters long, too. Looks like this is our ciphertext – this is what's being “decrypted” as we press buttons. This can be confirmed by overwriting it with something else and trying to press buttons again – the decrypted text changes as well, confirming that the final message is dependent on this. And we haven't even had to read any disassembly yet!
But that's about to change. Now we need to figure out how it checks if the button code is correct or not. To do this, let's use one of the most powerful tools a ROM hacker has: the **write breakpoint.** By setting a breakpoint at `0x8006B8A8` (the syntax of which is `[0x8006B8A8]!`, according to the help menu in No$psx), **the program will stop whenever our first character is written to.** And so it does!
![A bunch o' disassembly.](https://i.imgur.com/OTaquuP.png)
Here's where the magic happens! MIPS (the PlayStation's processor architecture) disassembly might look intimidating, but really, [it's not that different from any other assembly language](https://archive.org/details/mips-reference-sheet). Since No$psx's write breakpoints trigger *after* the write happens, the previous instruction `sb v1, $0(a1)` (**s**tore **b**yte in register `v1` at address `a1 + 0`) there is what wrote our decrypted byte. At this point, you can step back in the code to figure out exactly how this decryption is done – but what we're interested in here is what the button code is, and not the exact algorithm, so let's not do that. (…I did that, but although interesting, it didn't help.) Instead, let's look ahead!
See that `beq v0, a0, $8001129C` instruction? That **b**ranches to `0x8001129C` if `v0` is **eq**ual to `a0`. A branch – that's equivalent to an `if` statement. Could this be where the code goes one way if our input was correct, and another if it wasn't? We can easily find out: by right-clicking on the `beq`, choosing “Change instruction”, and changing to a `nop` (**n**o **op**eration) we can make it never branch, or by changing it to a `j $8001129C` (**j**ump) we can make it always branch. One of these should make any button code be marked as correct. The `nop` change does nothing, but change it to a `j`, and…
![“CORRECTUS!”](https://i.imgur.com/lRLu280.png)
“Correctus!” Wouldn't you know it! By this, we've confirmed that **that `beq` is mighty interesting – whatever's in `v0` and `a0` at that point is what determines whether your input was correct or not.** Judging by the preceding instructions, `a0` is loaded from an address in `v1`, and `v0` is obtained from… an `xori` (**XOR** **i**mmediate) between `t0` and `6`? Hmmm! XOR is a classic obfuscation / encryption technique! Let's find out what `v1` points at, and what in the world `t0` contains, shall we?
One of the easiest solutions for a case like this is to break on the same bit of code under several different circumstances, and see how values change – often, you don't even need to look into the disassembly to surmise exactly what something is simply based on patterns.
For `t0`, it's simple: it corresponds to the button we press! Every time we press any given button, `t0` here takes on the same value. By breaking here after pressing each different button, we can make a neat li'l table:
```Button constants:Left:      0Down:      1Right:     2Up:        3Start:     4Select:    5Square:    6Cross:     7Circle:    8Triangle:  9R1:       10R2:       11L1:       12L2:       13```
As for `v1`, we notice that it starts at `0x8006B930`, and *increases by 1* for every time we press a button. `a0`, as a result, just sequentially loads bytes from a buffer in memory!
So `v0` is from a list of bytes, and `a0` corresponds to a button. Reasoning about this, it is now plain to see what's happening here: **at `0x8006B930`, there's a list of the buttons we need to press**, XORed with 6 for some light obfuscation! We know the code is 44 (or `0x2C`) inputs long, so dumping `0x2C` bytes from `0x8006B930` lets us extract that list of values to use in our solution program.
---
### Putting it all together
Now we've reverse-engineered exactly what's happening, and we have the data required to brute-force the code. I'm a Python kind of guy, so I wrote a li'l Python (3, naturally) script to loop through every possible button constant, XOR it with 6, and check if it's equal to the next byte in the “correct inputs” buffer.
```python3should_be = (    b'\x0C\x03\x0E\x0D\x06\x02\x07\x0F\x0B\x04\x0B\x0B\x06\x01\x02\x02\x03'    b'\x0D\x0A\x0B\x0C\x0F\x04\x0A\x05\x0E\x0F\x06\x0F\x02\x00\x00\x0F\x03'    b'\x0A\x05\x07\x00\x04\x06\x07\x07\x0D\x0E')
buttons = {     0: "Left",    1: "Down",    2: "Right",  3: "Up",      4: "Start",     5: "Select",  6: "Square",  7: "Cross",  8: "Circle",  9: "Triangle",    10: "R1",     11: "R2",     12: "L1",    13: "L2",}
for x in should_be:    for n, name in buttons.items():        if n ^ 6 == x:            print(name)            break```
And finally… the fruits of our labor unravel before us. A list of buttons is printed, we press them in that order, and…
![My setup when I solved the challenge.](https://i.imgur.com/9QePJBV.png)
Don't screenshots of hacking setups like this feel… *idyllic*, somehow?
Turns out, both lower-case characters and upper-case characters are printed as upper-case in the program, so looking in the memory view where we know the string to be, we find…
**`X-MAS{Th4nk-Y0u-Kut4r4g1-f0r-7h3-PSX-412487}`!**
The flag, to be submitted for those delightful 500-ish points.
---
Didja enjoy the writeup? Didja learn something? Follow me [@obskyr on Twitter](https://twitter.com/obskyr)! I tweet about ROM hacking, hardware modding, obscure video games…! Good stuff, all in all!