Reverse Engineering for Dabblers

A book by Arnaud "red" Rouyer

Introduction

For as long as I can remember, I have always been a tinkerer.

As a child, my fingers were playing with LEGO bricks, and obtaining my first personnal computer¹ when I was barely six years old led me to another type of tinkering. My father taught me to use it, install softwares (games), configure and run them, play around with their files,... But without access to the Internet, all I could learn was on my own.

Little Big Adventure 2

One of my earliest memories was a demo of Little Big Adventure 2² contained on a CD. The demo only contained three areas: an island, a cave, and a company building looking like a bank. Doing any action to exit one area, such as entering a house on the island, would lead to the next area: it felt strange to me that entering a building on an island would get me into a cave. By looking at the game files on my desktop, I found a solution: as they were three areas, there were three files in a SAVE folder: DEMO0.LBA, DEMO1.LBA, and DEMO2.LBA.

I renamed DEMO2.LBA to DEMO1.LBA, copied DEMO0.LBA to DEMO2.LBA, and restarted the demo: I entered the first building on the island and found myself in the bank. I shortly made the character walk backwards to exit the building, and he was on the island again. I felt satisfied with myself and forgot about the demo, until I bought the full game a few years later.

Still got it to this day!

As I grew older, I tried to open my Tomb Raider save games, but the Windows Notepad would only show me a lot of spaces and strange characters, with the only readable part being the level name right in the middle. I tried to change it to another level name, and booted the game: my savegame did indicate the name of that other level, but loading it still sent me to the original level. I was missing something.

Thankfully, I had the luck to stumble on a game cheats magazine³ that contained game solutions, cheats, and codes, but, more importantly, a full lesson on how those codes worked. In those few pages, I learned how data worked, what hexadecimal was and why 0x0A came after 0x09 instead of 0x10.

The ZSNES cheats searcher

What this magazine never taught me was how to look for cheats: I learned with the Internet. Discovering Super Nintendo emulation with ZSNES, I spent a lot of time playing with its cheats searcher.

Discovering myself to be a huge fan of Japanese RPG games, the Super Nintendo quickly became my favourite console, and I would often play games, search for various ways to cheat, and learn about romhacking. While I never used that knowledge to work on my own romhack, a huge part of it would subconsciously make its way in my brain....

Years later, as an adult, I ended up working in the IT industry.

My curiosity and the breadth of knowledge I had acquired over the years led people to label me their "in-house hacker" and I've often been the go-to employee for insane solutions: How is our concurrent's product working? Can we retrieve informations from this proprietary database? Could we hook our own process on this website's database? Did you just drop a 0-day for our payment processor? We've been scraped by a concurrent, you got something to prevent that?

While all of these feats sounded "amazing" to my friends and work peers, imposter syndrome got the better of me. For a long time, that knowledge and know-how just felt "normal" to me, and even "subpar" when comparing it to more dedicated hackers I admired.

My first vision of the Internet was with a 14.4K dial-up modem with a Formula 1-looking device on the box⁴. I've been online for close to 30 years, reading and consuming content about my passion for "hacking" and reverse-engineering. While there exists a lot of people and projects dedicated to the preservation of knowledge online, I feel that the Web 2.0 trend and rise of social networks is slowly putting knowledge behind paywalls.

This book intends to work on those two problems.

I hope you will have as much fun reading and learning from this book, as I'm taking solace in sharing the way my knowledge and working process were formed.

Basic knowledge

This book is written with dabblers in mind.

While more experienced bounty hunters are already used to most of the techniques I will discuss, describe, and use in this book, they may appreciate the storytelling, or see how reverse engineering is used in other fields they may be unfamiliar with.

This book expects some basic programming knowledge, not in any specific language, but at least some familiarity with one.

Bits, binary, decimal, hexadecimal, and bytes

Human beings use the decimal system because it's clearer to them.

Computers, however, function in binary (bits: one or zero), and use the hexadecimal system to access and represent data as bytes. Hexadecimal, composed of "hexa" (6), and "decimal" (10), is a different numeral system using base 16: counting up goes from 0 to 9, then from A to F, and to 10. The mental gymnastic is a bit hard to get to, but easy to understand.

To properly differentiate numerical systems used in this book, prefixes 0b and 0x will be used for binary and hexadecimal values respectively, as shown in the quick recap table below.

File editors

Look at these patterns!

To view a file as hexadecimal data, there are many "hex editors" available online, but my personal preference goes to WerWolv's ImHex.

While the software is very recent, and the UI can be a bit hard to get used to, it is the software that comes closest to my dream hexadecimal editor. Its powerful pattern language puts it MILES ahead of any competition, and had it existed ten years earlier, I would have used it instead of manually coloring cells in Windows Excel to spot repeating patterns in a file...

For code edition, any text editor will do¹. I personally use Visual Studio Code but nothing in this book requires it, so you're free to go with Sublime Text or Atom if those are your preferences.

Memory

In computer terms, "memory" stands for a lot of things, but there are only a few we really care about:

• RAM: Random Access Memory, is the one that will often comes first. While the "Random Access" part may sound strange², just remember that it's the "moving" part of memory, where programs are allowed to read and write to as much as they want.

• ROM: Read-Only Memory, which you probably already know from the "CD-ROM", is data you can read but cannot write to. Since games have historically been sold on proprietary cartridges that cannot be written to, this is why game files have been called "roms".

• VRAM: Video RAM, which is just a fancy term for RAM dedicated to video display.

• WRAM: Work RAM, an alternative name for RAM.

All types of memory are "byte-addressable", which means any position can be expressed as a byte.

| Address | Value | +---------+--------| | 0x00 | 0xDE | | 0x01 | 0xAD | | 0x02 | 0xBE | | 0x03 | 0xEF |

In the above example, byte 0x02 got value 0xBE, and value 0xAD can be found in byte 0x01.

Technically, hard drive storage is ALSO a kind of memory (even more today with SSDs, which physically work like memory banks), but data is accessed through a file system.

Data types

Letters and numbers and everything else that is shown to users is an abstraction of what happens inside the computer. Depending on the programming language, and the level of abstraction, different types will be available to the developer.

In this book, the types will be tied to basic C data types, which are mostly about data size.

The smallest data type is the u8, short for "unsigned integer of 8 bits", which is a single-byte long. Going by the above table, this means this variable can include values going from 0x00 to 0xFF (or from 0 to 255). Next types in order of size are u16 (0x0000 to 0xFFFF, or 0 to 65535) and u32 (0x00000000 to 0xFFFFFFFF, or 0 to 4294967295).

Signedness isn't used much, since we are often dealing with raw data, but it's useful to keep in mind that it exists.

A special data type is the array: it is used to group together multiple values of the same data type and is noted by brackets indicating its maximum length, if relevant.

For instance: u8[4] will occupy the same size in memory as u32[1], with one containing four elements, while the other only contains one. If the array is of unknown length, the notation (data_type)[] will be used.

Endianness

Endianness is a hell we must all go through.

For performance reasons, different hardwares over history had different ways to access data, and data alignement plays a big part of that. For instance, it's easier for a microprocessor to read either two bytes (u16) or four bytes (u32) of data at once, but not three bytes of data (very few systems actually implement something that could be called an u24, and I've never seen one in action).

For that reason, on some hardware, it is more advantageous to access data in a backwards fashion when it spans more than one byte, which is called little-endianness. However this backwardness only applies to bytes, and not to bits. Therefore, the data would be stored as follows in memory:

Functions

Functions are the base of all programming languages.

While they can come in all sort of syntaxes, depending on the language, this book will try its best to describe them only as "pseudo-C" prototypes, reducing them to their most basic elements: a function is described by a prototype, has a name, take ordered values as arguments, and it may return a value.

For instance, the following prototype addTwoNumbers(u8, u8) -> u8 means "the function named addTwoNumbers must be provided two arguments of type u8, and returns an u8 value". For further clarification, arguments can be named, so that divideNumbers(u8 base, u8 divider) -> u8 makes it easy for the reader to understand which argument is the base number, and which is the divider.

Structures

Structures are mostly used in C-like languages, but are used in some sort in all languages to hold multiple datas values together and pack them as a whole

A simple example of a struct would be the following:

#![allow(unused)]
fn main() {
struct Book {
  name:          String,
  release_year:  u16,
  release_month: u8,
  release_day:   u8,
  pages_count:   u16,
  rating:        u8
}
}

Something to keep in mind with struct elements is that they are often padded by the system so that they can be aligned together for easier access. In our "Book" example, (and ignoring the String type which is a bit special), we can see the struct is composed of two u16 and three u8, making it 56-bits (7 bytes) long. Since it would be easier for a system to align its data on 64 bits (8 bytes), there is a huge chance the structure will be padded, making it actually look like the following in memory:

#![allow(unused)]
fn main() {
struct Book {
  name:          String,
  release_year:  u16,
  release_month: u8,
  release_day:   u8,
  pages_count:   u16,
  rating:        u8,
  padding:       u8
}
}

Depending on the language, the system architecture, and many other variables, padding can play out in a lot of ways. Therefore, while it's useful to know and think about, it's not a deterministic element.

Programming

I will try my best to make this book accessible to non-programmers.

However, when code is REQUIRED to illustrate something, it will be written in the most accessible way possible, making it easy for non-programmers to understand this code, or to port it to another language if they want to test it on their own.

Languages come into two flavors: interpreted or compiled. The first kind means the human-readable source code is read by an interpreter program, and then ran; these are usually the easier languages to learn. The second kind means the human-readable source code will be transformed into a program called a binary that the user can run anytime they want; since we don't have access to the source code, these are the ones we will be working on.

If you are not a programmer yet, and would like to pick up a language to learn, I recommend either Ruby or Python: they are interpreted languages and good starting points for beginners, can be equally powerful when you will be used to them, and will help you cover all the basics you need to quickly and easily understand other languages. While my own personnal preference goes towards the former, I encourage you to look at code written in both languages to see which one feels the more appealing and readable to you: there is no point in learning a language you don't like.

Terminal

The Terminal, the CLI (Command-Line Interface), the PowerShell,...

This book can be enjoyed without using it, but if you want to run some of the binaries included with it, it can be useful to familiarize yourself with one. Most modern systems come with one, whether you are on MacOS (Terminal), Windows (PowerShell), or Linux (too many to choose).

When describing command-line programs, I will make sure to explain them, or keep them simple enough so that the command is easy to understand.

ActionReplay Antics

"Your very own Pokémon legend is about to unfold! A world of dreams and adventures with Pokémon awaits! Let's go!"
― Professor Oak, in Pokémon Red, Blue, and Yellow

A history of cheating

Originally made for the Commodore 64 computer around 1986, and later adapted and released for many other game consoles along the years, the Action Replay¹ was a device users would plug into their game console, enabling them access to the console's internal memory, reading and writing through it, as they were playing.

Soon after, other manufacturers would follow and publish their own devices, most famously Game Shark¹ and Game Genie[^1], and gaming magazines would include pages full of codes. With the Internet, the codes were liberated and these three brands became generic terms² online for "cheat code".

Thanks to the tremendous work of emulator developers, many of them began to allow users to access the game console memory to use codes, and, more interestingly,in order to find them. Soon enough, even modded consoles got free softwares implementing similar functionalities.

Mechanisms of infinite money

Regardless of their name, all cheat devices work in the same way: they write values to the memory.

For instance, if one were to look up an "Infinite Money" code for the GameBoy game Pokémon RED, the very first result would be the following list of numbers:

Not just rich, infinitely rich!

019947D3
019948D3
019949D3

Using these as a GameShark code in an emulator, and starting a new game, we get the desired outcome: our character is now rich and will stay that way until we disable the code.

Codes for some consoles may have sophisticated specifications, some even including actual programming code in them, but the GameShark for Gameboy is simple: an eight-number code is meant to be split into the arguments for a function with the prototype writeValueToOffset(u8 rombank, u8 value, u16 offset), giving us the following pseudo-code:

writeValueToOffset(0x01, 0x99, 0x47D3)
writeValueToOffset(0x01, 0x99, 0x48D3)
writeValueToOffset(0x01, 0x99, 0x49D3)

But now this code just drives more questions: what would happen if we only used one of those three codes? Let's try again with something else:

Another kind of rich

011247D3 # writeValueToOffset(0x01, 0x12, 0x47D3)
013448D3 # writeValueToOffset(0x01, 0x34, 0x48D3)
015649D3 # writeValueToOffset(0x01, 0x56, 0x49D3)

After disabling the previous code, and trying this one, we can see the results and make our deductions: each of the three memory addresses from 0xD347 to 0xD349 is responsible for two digits of the player money.

Actually, we could just write 99 in 0xD347 and make our hero very close to being a millionaire, but a pretty number is way more satisfying, isn't it?

Another interesting thing to notice is that as long as the code is enabled, our money will stay fixated on the same number no matter how many times we decide to go on a shopping spree. This is because the ActionReplay devices work by writing values to memory each time a frame is rendered², resetting our money around 60 times per second.

The quest for immortality

More than four thousand years ago¹, in the very first litterary Epic of history, Gilgamesh, the king of kings, went on a quest for immortality. Since then, mankind has been looking for ways to cheat death, but the results have never been very satisfactory.

Thanksfully, to make our Pokémon immune to death, we don't need to go down the crossroads at midnight, hide their aging portrait in our attic, or other deals that turn sour only to teach the reader a lesson on the benefits of seizing every day.

Thinking like a programmer

Gently close your eyes.

You are back in the summer of 1993, and you smile shyly as your Sony MZ-1 MiniDisc starts playing the notes of Yumi Matsutoya's hit song "VOYAGER²" in your ears. You are sitting, comfortably numb, in a good chair in the middle of your Tokyo office. Nintendo has greenlit the game you are currently working on, and things are looking good, so you don't pay too much attention when Satoshi Tajiri sits next to your office, and pitches you an idea.

"I got an idea, how about we make the wild Pokémon fight back?"
― Satoshi Tajiri, in your 1993 dream, probably thinking it takes 5 minutes to do

You think it quickly: the game's already got "attacks" and an idea of "hit points" when you are attacking a wild Pokémon, but they don't attack back, so your animal friends are in no danger of seeing their own HP count go down. As you ponder all the ramifications of this strange idea from the co-founder, he asks:

"You got an idea on how you would implement it?"
― Satoshi Tajiri, having no patience in your dream

You think back³ of that time when you played Dragon Quest on the NES some years ago: each combattant get a turn to attack, the opponent's HP go down, and the first one to zero is defeated. You jolt down some notes (in Japanese) for the boss that history will remember:

PLAYER TURN
-> Choose an attack
-> DAMAGE = CALCULATE(Player ATK - Enemy DEF)
-> Enemy HP = CALCULATE(Enemy HP - DAMAGE)
-> IF Enemy HP < 0
  -> Victory
ENEMY TURN
-> Attack
-> DAMAGE = CALCULATE(Enemy ATK - Player DEF)
-> Player HP = CALCULATE(Player HP - DAMAGE)
-> IF Player HP < 0
  -> Defeat
REPEAT

As you hand him the note so he can give you some observations, a lightbulb goes in your head, you wake up, and are whisked back to this book: you now KNOW what happens.

Yes, there is nothing too complicated in here: you know there are "attacks", you know there is "damage", and you know this "damage" is whittling down the Pokémon's "hit points". All you need now to achieve Poké-Immortality is make sure this "hit points" value never reaches zero, and why not use the same method as the one that made you rich? If only you knew where this value is stored in the game's memory...

Which way now, fellow hacker?

• For an easy way that won't require work, go to the next page.

• For a normal way, go two pages in the future.

The easiest way

You could look up online something like "Unlimited HP", but this book is not about search engines, so let's pretend for a second that nobody in the history of humanity ever put this code online.

Go back to learning now, dear reader!

• For the normal way, go to the next page.

The way of the cheat finder

The cheat finder from VBA-M.

All cheat engines perform the same work for you: you give them a number to look for, and they will scan the whole memory to look for it.

Unfortunately, things are not so easy: a GameBoy got "8Kbytes" of RAM¹, which means precisely 8192 bytes (or addresses). Given that a byte can have only one of 256 values, it means that on average, the number you're looking for could be found in 32 bytes... we're still not close to finding our magic byte!

Picking a Bulbasaur starting with 20 HP, we're lucky that our cheat finder reports only 16 bytes contain the decimal value "20". We could modify all of these one by one, probably breaking the game many times in the process, but our cheat finder can still help us.

An attack from our rival's Pokémon will change the value of our HP to 16. Let's run the cheat finder again with that new value: the cheat finder will reduce the number of results for us, and this time only 4 bytes remain.

Let's continue fighting and running the cheat finder with new values, until only one byte remains.

Congratulations!

If you find 0xD016 (or rather 0x16D0 in little endian), you can now set it to the arbitrary value of your choice, and your Pokémon will never again have to suffer from fainting in battle. Pull back a few pages to see how a GameBoy GameShark code is formed and you should come up with the following code:

019916D0

You are about to add this cheat in the game straight away, but suddenly, a question pops in your head:

"What if this code was wrong and it were to damage my Pokémon?"
― You, dear reader, suddenly overcome by fear and self-doubt

Sure, you may trust the methodology. After, all, you read it in a book, and you know science in books is always true. But you're not sure you did input the correct values at the right time, or maybe you didn't click the correct button in the cheat finder. You're not a hacker (yet), and you don't feel confident enough to make your beloved Pokémon partner the subject of a four bytes code.

Another question pops in your head:

"Is there a way to find this result on my own in a firesure way?"
― You, my reader, about to get a happy surprise on the next page

Well, guess what? There is a way to do it on your own, like a hacker.

The way of the hacker

Either the cheat finder didn't feel "real" enough for you, or you want to get some "hands-on" knowledge, but you feel you're now ready to call yourself a Hacker. You pull out a black hoodie over your head and write your plan on a whiteboard:

SCAN THE RAM
-> Look up for HP value in RAM
-> Flag all bytes with the HP value

CHANGE HP VALUE IN GAME
SCAN THE RAM
-> Check the flagged bytes in RAM
-> Keep the flagged bytes that got the new HP value
IF MORE THAN ONE FLAGGED BYTE
  -> Repeat from "CHANGE HP VALUE IN GAME"
ELSE IF NO FLAGGED BYTE
  -> Clearly we did something wrong
ELSE
  -> The last flagged byte is the result

PRINT THE LAST FLAGGED BYTE

You feel like you could humanly do most of these things, but the part about scanning the RAM suddenly feels like you may have ordered more than you can chew: you came for reverse-engineering, not for writing a GameBoy emulator¹!

You run your favorite emulator again. You would like to run the same as me because a voice in your head tells you that I've probably got an emulator that can dump the RAM². The voice in your head is so annoying that you just missed something while playing, and your Pokémon fainted. You look around the menus: your emulator got a "Savestate" feature that allows you to restore your game as it was a few minutes ago. You click on "Load Savestate", and the game goes back to its previous state, restoring all the emulated parts of the GameBoy. A lightbulb goes on in your head, and you thank the voice for helping you find a solution. As the voice confirms the pleasure was all hers, you make many savestates, and add the value to look for next to each of them. You add new lines to your whiteboard:

SAVESTATE_1 => 19 HP => 0x13
SAVESTATE_2 => 15 HP => 0x0F 
SAVESTATE_3 => 11 HP => 0x0B
SAVESTATE_4 =>  7 HP => 0x07
SAVESTATE_5 =>  3 HP => 0x03
SAVESTATE_6 => 19 HP => 0x13

That should be enough! Now, how about writing some code?

ColdSteel Cheating

1. Advance by a few seconds... USER019: Base USER020: Wait a few seconds

The difference is SMALL, which is good. Only five bytes, which is weird.

The test was to find the value which would be used for the time counter, or worse: a checksum. In any case, we have no idea yet, but we know of a field that will ALWAYS be modified, so we can ignore it safely in future diffs.

Lessons:

• Fields are static in offset.
• We know where time/checksum is.

2. Fill a character profile USER020: Base USER021: Talk to Casper to fill his character profile

The difference this time is huge. I was expecting a single byte to change, but I forgot another part: conversation archive.

Lessons:

• None

3. Feed Celine in the Library USER022: Base USER023: Feed Celine

I would like to find a single trigger check. I am not sure I did. However, I did find how items are stored.

For a reason I don't get, items are padded to a size of 36 bytes.

Lessons:

• Found items.
• Since this save was on a second playthrough, I found a counter of NG+.

4. Can I find difficulty? USER024: Easy USER025: Normal USER026: Hard USER027: Nightmare

I cannot parse the playtime and it's infuriating me. Therefore, I decided to go and look for the difficulty, since I was pretty sure it could be around the same place, and affecting the. Good news: I found it. Bad news: it's not where I was expecting it.

Lessons:

• Found difficulty
• It's not stored with the playtime.

5. Move to RPCS3 Using my own physical PS3 to test for these things is a pain, so I'm moving my "editing table" to rpcs3.Fiddling around to confirm that the saves worked, and trying to restore some JP-only DLCs, I managed to find something interesting: a table of ALL items, that actually matches the one I got. https://fearlessrevolution.com/viewtopic.php?t=4467&start=285

Lessons:

• All items.

Acknowledgements

Writing this book, I have merely been standing on the shoulders of giants.

All the research or digging that I could do and describe in this book has been learned from a lot of talented people who made the choice to share their knowledge publicly on the internet. While I could not always quote or point to specific projects in the middle of a chapter because I felt it would break the flow of reading, or because said project was only tangentially related to the topic at hand, I wanted to devote a chapter to many of them that helped me and my understanding.

Actionreplay Antics

Pan Docs

The Pan Docs are a document, dating back to 1995, that has served as THE technical reference for the GameBoy system architecture. Originally a single .TXT file, it has since evolved into a full online book, with many contributions, and is widely used by hobbyist emulator developers.

Thanks to their chapter on Game Genie/Shark Cheats, I had a definitive answer on the format of Game Shark cheats on the GameBoy: an incorrect source had separated the 4-bytes code (01 99 47 D3) as follows:

The misconception most likely stems from ActionReplay/GameShark for other consoles actually using opcodes, with 01 often being the simplest instruction: "write data to address".

Shonumi

While the Pan Docs are the reference documentation for the GameBoy system, it lacks in documentation on the non-official peripherals, making perservation of games using some of these hardware very difficult. Shonumi, the developer for the GBE+ GameBoy emulator started writing the Dan Docs to study them.

That research is documented on Shonumi's blog, in the "Edge of Emulation" series, where obscure GameBoy peripherals are reverse-engineered to properly document and emulate them.

ares

Originally started by developer near, ares is a multi-system game emulator.

Just as the above Pan Docs are the reference for the GameBoy architecture, near has been instrumental in the documentation and preservation of his favourite machine, the Super Famicom (aka Super Nintendo). Frustrated with the shortcuts used by emulators of the time (famously, ZSNES, and Snes9x to a lesser degree) to achieve greater compatibility, to the detriment of accuracy, near began bsnes, an emulator meant to accurately replicate all hardware parts of the console.

While their work was initially contested because it required high-end computers to emulate a "simple" system, the benefits it brought to game hacking (many old fan translations having only been tested on non-accurate emulators, they wouldn't work properly on real hardware), combined with the evolution of consumer computers performances, made their emulation approach de facto nowadays.

Pokémon Red decompilation project

Started by iimarckus in 2010, this project has since taken a life on its own, and is your best source to understand any question you may have on how the original Pokémon worked.

For instance, did you know that the reason there are 8 badges in the game is because they were easier to store in the player inventory as 8 bits?