The problem space

Pokémon is a franchise that needs no introduction. Millions upon millions of people have had some exposure thereto. I would like to focus on one tiny implementation detail of the games that formed the third generation of Pokémon: Ruby, Sapphire, FireRed, LeafGreen, and Emerald.

In this generation of the games, the developers of the series first started trying to discourage cheating. To understand what they did, I first need to introduce a few concepts.

A Pokémon is an individual member of a Pokémon species. Think of it like a specific individual, just like how there is a sheep that you encounter and there is the species of sheep, of which the aforementioned individual of a member.
Every Pokémon has a 32-bit personality value (also commonly called personality ID or PID for short).
A (Pokémon) trainer is a concept in the games: Trainers go around and make their Pokémon fight against other Pokémon. They hold contests to find out who is the strongest trainer. Supposedly, these little creatures like beating each other until they faint. The player in the games is a trainer.
A trainer identifier (trainer ID) is a 16-bit number that is assigned to every player. There is also another 16-bit number (a secret ID) that is not shown to the player, used to distinguish between identical trainer names with identical trainer IDs. Non-player character trainers generally do not have trainer IDs, but for in-game Pokémon originating from other trainers, Game Freak assigned some.
A player can have multiple Pokémon in their party, up to six Pokémon namely.

The studio of the developers of the games (Game Freak) do not want people to cheat. Usage of cheating devices like the GameShark ran rampant. A GameShark would normally accept codes that manipulate memory addresses while the game ran. You can think of a GameShark code like compiled binary code that the GameShark would interpret at runtime to make the desired modification at runtime. This would allow players to alter the information about their Pokémon. One crucial aspect of developing anti-cheating solution is to limit visibility into the goings-on in memory. If a cheat author cannot see what to change, they cannot make a cheat. Game Freak therefore turned to (crude) encryption and checksumming.

The Pokémon structure

The structure of a Pokémon is fairly complex. I will therefore be presenting a simplified model:

struct Pokemon {
    uint32_t pid;
    uint32_t trainerId;
    /* [...] */
    uint16_t checksum;
    /* [...] */

   uint32_t encryptedRegion[4 * 3];
};

The pid field contains the personality ID. This is generated at random when the Pokémon is first created and stays static throughout the existence of a Pokémon.

The trainerId field contains the trainer secret ID in the upper 16 bits and the trainer ID that is actually displayed to the user in the lower 16 bits.

The checksum contains a checksum over the decrypted values of the encryptedRegion.

The encryptedRegion consists of four separate structures that are decrypted on the fly every time the game needs to read or write data located therein, such as the current amount of experience points or the species of Pokémon. The order of the data is shuffled in 24 different ways depending on the personality ID.

Encrypting and checksumming

The encryption is primitive: Every 32-bit word in the encryptedRegion is bitwise exclusive-or'ed with the pid and trainerId fields. This is very fast, but it is also very easy to figure out. The shuffling of the data does more in terms of obfuscation than this encryption does.

In particular, since the output of the encrypted region stays entirely unchanged between two encryptions other than data that changed, it is possible to take a capture of memory before and after changing some information in order to glean information where critical information like experience points are stored, at least for each individual Pokémon. Furthermore, if the plaintext value is known, it is possible to recover the entire encryption key from just one piece of 32-bit information.

Similarly, the checksumming is equally primitive: It is just the sum of all words in the encryptedRegion (in canonical order) truncated to 16 bits. Every time any information in the encryptedRegion is accessed, the game decrypts the Pokémon and first checks the checksum. If it is invalid, the access does nothing and returns a dummy value, plus the Pokémon is marked as invalid.

Paper tape

In Pokémon Emerald, the game frequently queries whether a slot in a party is occupied. It does so by checking the species. If the species is zero, the slot is considered not occupied by a Pokémon. As noted above, the species is actually stored in the encrypted region.

Instead of doing the sensible thing and checking the number of party members, the game actually performs the whole decryption and checksumming process even for a slot that is not occupied to read the species.

An empty slot is a Pokémon struct filled with zeroes. Therefore, the only reason this works is because of how primitive the encryption is: The xor of zero with is zero. This means that an all-zero encryptedRegion stays zero after decryption because the pid and trainerId values are zero. The checksum also passes because the stored checksum value is zero and the sum of the all-zero decrypted region is also zero.