Saturday, September 29, 2012

Reverse Engineering

Why?

Reverse engineering a system (for whatever reason) can be fun and challenging. I recently found myself in need of changing the contents of an 8KB file with no format information whatsoever. I had been playing Final Fantasy 6 on my phone during my morning commute and had accidentally killed off a favorite character of mine in a permanent way. I knew I only needed to flip one or two bits to correct this, but which ones?

Part 1 - Tools:

Tools can make or break an attempt at reverse engineering, some can be as simple as a hex table taped to the side of your monitor, or as complex as a full-fledged debugger. I had the advantage of both :)

  • Something to take notes with
  • Programming calculator (even calc.exe will suffice)
  • Backups of whatever it is you're working on
  • Debugger (if available)
  • Some way of testing your changes
  • Some way of generating new changes
  • A diff tool (diff, windiff, etc)

Part 2 - Poking around:

Getting started can be daunting. 8 KB is a tiny file, but massive when you're trying to figure which single bit is the important one. Start by making a map to narrow your search space.
I opened up the save file and found two-thirds of it mostly empty, given that I was only using the first 'save slot' in the game, it was safe to assume saves were made sequentially in the file. I created a second save in slot 2 and verified this.

So now I have a rough idea of where I'm looking. To test the boundaries of each 'save slot' I flipped a single bit and tested the changes... when I went to test, the game claimed I had zero saves! Good thing for backups. Turns out the game also checksums its data to prevent corruption (and likely also tampering as I was attempting).

Knowing that flipping bits randomly definitely wasn't going to work, it was time for differential analysis:
  1. Backup the file
  2. Make a single change in game
  3. Save
  4. Diff the two files
To my surprise, loading and saving the file without changing anything caused several bytes to change! Upon further inspection, the game has a timer which clocks how many seconds the user has been playing for. This corresponded to 3 bytes somewhere in the middle of the save file. It took a few minutes to realize the game stores its values with the least significant bytes first. So 45 23 01 in memory is 012345 in hex. In addition to the timer bits changing, the last 4 bytes of the save slot also changed an equivalent amount... the checksum!

Part 3 - Mapping data:

Once I had a basic understanding of how the file was organized, I began creating a map of the file and assigning names to blocks of memory. Having a debugger to rapidly make changes and test the results was especially helpful.

Guess and check: One technique to speed up mapping is to pick a value in the game, such as amount of money  then searching the whole file for that exact value. Then change it slightly to see if it's correct.

Differential reverse engineering: Another is to change a value several times within the game, saving after each change and backing up the file, then diffing the files to see which location changed each time and by how much.

Pattern matching: Certain data tends follow a logical pattern, such as text, and can easily be searched for. The unix 'strings' command is great for this. Since this game originated in Japan and was later translated to English, the text turned out to be in some other format than ASCII. Text still follows a pattern though, 'A' is usually one less then 'B'. Applying that to one of the games heroes names, I found that the data for each hero in the game is stored at the very front of the file.

Part 4 - Intuition:

Programmers tend to think alike (even across the ocean). Data that belongs together, is usually grouped together. Data that only requires 1 bit to store, is usually compressed into a single byte with related data. A well written piece of software will always attempt to be organized and efficient.

Data that can be stored statically in ROM and referenced with just an index (or pointer) can be tricky to find. In game 'items' are stored in an inventory as pointers in a table, followed by a second table of integer quantities. Moving items around in game made it very easy to see the link between these two tables since each change in game corresponded to 2 changes in the file (separated by exactly 0xFF bytes).

Final thoughts

Any system can be reverse engineered regardless of how large, complex, or foreign it may be. If I had the source code to this game, tracking down this bit would have taken minutes rather than hours. Closed source projects require more time to understand than their open source counterparts, but they aren't any more secure.

Here is an almost complete mapping of the saved game format for Final Fantasy 6: http://r4v3n.net/files/ff6_saved_game_v1.txt