This repository is a data dump of some of the stuff I did when I reverse engineered the save password algorithm in the PSX game Crash Bandicoot. Don't really expect to find anything too useful here.
This whole thing came up on IRC apparently after a "Games Done Quick" run of Crash Bandicoot: Warped. The discussion somehow drifted to the first game of the series and its password system. Someone pasted this quote from http://crashbandicoot.wikia.com/wiki/Password :
There are passwords for save states that cannot arise by playing the game normally. [...] Such a save state cannot arise while playing the game normally because the Tawna bonus round in Rolling Stones saves at the Rolling Stones level, and there is no bonus round in Hog Wild. These passwords can be found by trial and error. Since there are too many save states that can arise with different combinations of gems, it must be the case that passwords are generated algorithmically, as opposed to being manually programmed by Naughty Dog. However, no one has ever discovered the algorithm.
Obviously I took the last sentence as a challenge.
The actual reverse engineering of the password algorithm was greatly hindered by the fact that it (as well as huge part of the game) was written in GOOL, an in-house Lisp variant (see for example http://all-things-andy-gavin.com/2011/03/12/making-crash-bandicoot-gool-part-9/). As I discovered, this Lisp code wasn't compiled to the MIPS R3000 machine code that the PSX uses, but into a custom stack-based virtual machine "byte"code. Which meant that before I would be anywhere close to the password generation algorithm, I'd first have to reverse engineer the Lisp virtual machine itself to find out the instruction encoding, what each opcode does and so on. After that I'd have to write tooling (such as a disassembler) to make any sense of the huge pile of hexadecimal slump.
The VM is a stack-based one, but a somewhat unusual one, as it permits quite complicated addressing modes as well: instead of all of the operands coming from the stack (like in say, JVM), most opcodes can act directly on immediate or global values. The result of the operation is most often pushed to the stack, though some opcodes will treat one of the operands as an l-value and store the result directly to some memory location.
Each instruction is a 32-bit aligned MIPS word. The top 8 bits form the opcode, which leaves 24 bits for the operands. There are several different addressing modes, some of them having even five operands. The most common one (used by e.g. ALU instructions) has two input operands, each having a 12-bit encoding, and pushes a result to the stack. A single input operand can be either one element popped from the top of stack, an 9 or 8 bit immediate value, a global variable (v_* in my disassembler), a value from a script-specific constant pool, or a value from an arbitrary stack location relative to start of the stack (g_* in my disassembler).
- notes.txt - generic notes. Contains stuff like interesting memory locations relevant to the password checking algorithm, a list of opcodes and encodings of some of the addressing modes.
- vm0.txt and vm2.txt: disassembly of the MIPS R3000 code implementing the first VM opcodes I reverse engineered, 0x00 and 0x02. If you compare them visually, it's quite easy to see that they are identical expect that the first one does 'addu $v0, $v1' at the very end while the latter does 'mult $v1, $v0; mflo $v0'. So these are the opcodes for doing addition and multiplication. Also instructions like 'srl $v1, $s1, 12' and 'andi $a0, $v1, 0xFFF' are a dead giveaway of the 12-bit operand structure. And sequences like 'lw $a0, 0xDC($s2); addiu $v0, $a0, 4; sw $v0, 0xDC($s2); sw $v0, 0($a0)' are quite obviously pushes to the operand stack.
- pcsx-1.9.92-vm-dump.patch: Hacks that I added to the PCSX emulator to dump the state of the virtual machine, including trace of every instruction executed by the VM and state of the operand stack. Emulator patching seems to be a really powerful technique for some kinds of reverse engineering, I've previously successfully used it for extracting the level data of the PSX game Devil Dice.
- disassembler.rb: A pretty crude ruby script that annotates the instruction trace generated by the PCSX hack patch with human-readable disassembly. It uses constant_pool.bin dumped from the game memory to resolve certain kinds of operands.
- vm-trace_correct-pass.txt and vm-trace_wrong-pass.txt: disassembled instruction traces for when a correct and a wrong password is entered in the main menu. These are from an older version of the hacks/scripts that don't contain the operand stack dump.
- pass-checks.txt: A detailed commentary of what VM code gets executed when the final character of the password is entered. From this text file I was able to create algo.cpp, a recreation of the password verification algorithm in C++.
- pwgen.html and pwgen.js: the final result, and most probably the only useful files around here: a password generator. Basically, I calculated the inverse function of the verification algorithm and did some experimentation to determine what bits affect which game variables. Go to https://cdn.rawgit.com/dezgeg/crash-bandicoot-password-cracking/master/pwgen.html for a directly usable one. Also note how awesome web designer I am.