0. Introduction:
Have you ever played a game which provides you with an option to enter a password to unlock certain features in the game (rare items, special characters, etc.), or to continue from where you fall? Have you ever played a game in which you have to push a crazy sequence of buttons to unlock a certain cutscene or event in the game? Let us call them “game password”.
1. Types of game password:
There are several types of game passwords. My limited knowledge about games only allows me to know 3 types of game passwords.
We can find the first type: button/keyboard sequences in Hayate no Gotoku! Ojō-sama Produce Daisakusen Bokuiro ni Somare! (NDS) (After completing the second game, to unlock voices in Omake Mode, use this code: ↑ ↑ ↓ ↓ ← → ← →), Dyna Blaster (PC) (type HUDSONSOFT at main menu for God mode), Harry Potter and the Sorcerer’s Stone (PC) (type harrydebugmodeon to turn on debug mode; visit here for the full list of commands). Games whose passwords fall into the first type do not have an explicit option for the player to enter the code, and normal player usually has to obtain the information from a game guide or even from a third party.
The second type is type is “plain” password. As its name suggested, the password is just a string assigned to a certain event in the game and it itself holds no deep meaning. Examples of this type are Chips Challenge (PC) (if the input from the player matches any of the password in this password list, the player is taken to the corresponding level) and Pokémon series from 3rd generation onward (player has to type in a specific combination of words in the supermarket questionnaire to unlock Mystery Gift in the main menu). In this type, there is usually an option for the player to enter the code and the password is usually obtainable during gameplay.
The third type of password is password with embedded information. The game reads the information encrypted in the password and triggers event according to the instruction in the password. Examples of this type are Pokémon Emerald (GBA) (type in a string of characters to the sick girl’s father in Rustboro City to get special box wallpaper; this is the tool to generate the string of characters) and Pokémon Mystery Dungeon series (to play a mission that has the same settings as your friend’s, ask your friend for the Wonder Mail password of the mission and enter it in the main menu). This type of password is only implemented in the case it requires multiple conditions for certain event(s)/effect(s) to happen. Since there are several different data fields in the password, the number of possible combinations is too immense to list out. Therefore, there are usually third parties who reverse-engineer the encryption process and create programs or scripts to generate the password based on the input from the user.
In the second half of this blog post, we will focus on the type of password with embedded information. What we can learn by looking at the process of generating a password with embedded information is much more than some simple comparisons between user input and a fixed list of triggers – events/effects.
2. Characteristics of game password with embedded information
A game password with embedded information should have the 2 characteristics below:
- Crypticness: It should be impossible, or at least very hard, to discern the position and extract the actual information embedded in the password by working on a large number of samples with pen and paper. Generally, there is no point in having an easy to crack password system.
- Brevity: A password with embedded information is usually as short as it can be. The longer the password, the higher the chance of mistyping it. Furthermore, typing a long password in a console with + pad and button A (the “confirm” button) is a real pain for the player.
Game password with embedded information is usually long enough to discourage any attempt to brute force. Therefore, brevity will not compromise the crypticness of the password.
Aside from the 2 standard characteristics, a good password system should have the following characteristics:
- Validation: A good password system should have a validation process to make it difficult to modify the password by just comparing 2 passwords and applying the changes. This validation process can be the checksum or simply a fixed value somewhere in the bit string.
- Non-ambiguous and typable character set: Ambiguous character set will give players hard time to recognize the character, which increases the risk of miscommunication. For example, O and 0, 2 and Z, 5 and S, 1 and ! are the pairs of characters that are easily mistaken for each other. A typable character set will make password sharing a lot easier since the player don’t have to try to type out something with Character Map.
- Limited acceptance: This is the last wall to guard certain features in the game. The game should impose a limit on what kind of password to accept and what not in order to prevent the misuse of password in the case the password creation process is cracked. Unlocking certain rare items or characters with password is technically a legitimate method of acquisition, so players tend to abuse the system once a password creation tool is made.
3. An example of password creating process:
In this section, I will use the Wonder Mail password system in Pokémon Mystery Dungeon (PMD) series to demonstrate the process of generating the password and how each step contributes to the characteristics of a good password. For an in-depth analysis of the password system in the first generation of the series, visit this page.
Before we start, on side note, each in-game generated mission will have a corresponding Wonder Mail password. The intention of the game developer is that players can share Wonder Mail passwords of easy missions with good reward or challenge each other with seemingly impossible missions.
The idea behind Wonder Mail password is quite similar to that of a game save: they both store just enough information that can be used to make the player re-experience certain effect, and the information is stored in a fixed pattern.
Step 1: Take only what is necessary
The first step involves in picking out the necessary pieces of information, then minimizing the number of bits required to represent the information.
In the memory, the unit of storage is byte. If a piece of information is too big for one byte to handle, we will use multiple bytes (usually 2i bytes) to represent the information. For example, when the game developer decides that there will be 1400 (0x578) kinds of items, he will use 2 bytes to store that piece of information in the memory. By storing information in this way, we wasted 5 bits of memory since we actually only need a maximum of 11 bits to store the number (if we start to count from 0, the largest number we will encounter is 0x577 and its binary representation is 00000101 01110111). In this way, we can effectively reduce the length of the password.
[Note: While clamping down the number of bits makes efficient use of the memory, it requires extra calculations to change or extract the data because the computer reads the memory byte by byte, not bit by bit. Therefore, the game will be slowed down significantly if we just blindly apply the idea to minimize the necessary amount of memory. On the other hand, because password is usually designed to be entered from the main menu where CPU is not as intensively used as inside the game, putting more loads on the CPU will be less of a problem. In practice, we will simply assign 2i bytes to store a piece of data in which i is the smallest number that enables us to store that given piece of data. We only need to read the data directly without wasting more CPU resources to process it. To use memory resource efficiently, we can also allocate the same section of the memory for different events if the data involves is not necessary in the game save and those events cannot happen at the same time.]
Step 2: Fitting in the mold
The next step involves in putting the collected data together in an order and adding confusing elements to the bit string.
Constant bits (bits representing the same data for every mail can be 0 or 0xFF or any value) might be added to lengthen the final password to the desired length.
Step 3: Checksum
The next step is creating a checksum for the binary string.
There are various methods of creating the checksum. In the first generation of PMD series, the game uses a simple algorithm to create the checksum. That is cutting up the bit stream into bytes starting from the least significant bit (sequentially take 8 bits from right to left), then adding the byte to a variable called sum. After every addition, we will perform bitwise AND operation between sum and 0xFF (255) (which is equivalent to type casting the number to byte type).
For the latest NDS game of Pokémon Mystery Dungeon series (Sky version), the size of the checksum has increased to 32-bit. The algorithm of calculating the checksum is still unknown as of now.
Step 4: Encryption
From the 2nd generation of the game, encryption is introduced to completely thwart any attempt to decode by observation. The actual algorithm was made known probably by using a disassembler to see the encryption process in the memory.
The game uses a 256 bytes table to do the encryption. The checksum calculated in the previous step is used as offset for the starting position in the encryption table. Starting from the least significant byte of the bit string, and starting from the offset in the encryption table, we shall add the value in the string and encryption table together and then perform type casting to byte type to create an encrypted bit string.
In the latest version of the series (Sky version), depending on the checksum, during the encryption process, the pointer to the encryption table may be reset to the original offset, which further increases the crypticness of the code.
Step 5: Mapping to character
In this next step, we will map the bit string to an equivalent representation in character set. By mapping to character, we can hide the actual value and confuse code crackers. Why? For example, we usually think of “nothingness” when we see the symbol "0". However, we have made a dangerous assumption that the “0” we see is related to with mathematics. In fact, nothing prevents us from denoting the symbol "0" for another meaning.
The number of character in the character set should be large enough to create a good challenge for decoders, but should be small enough to reduce the number of characters needed to map to. The games in PMD series use 5-bit character set, which uses 32 characters to mask the actual binary string. 5-bit character set is quite a good choice. If the characters are chosen properly, the player doesn't have to distinguish between uppercase and lowercase of alphabetical characters and other possible ambiguities, and 32 characters creates a big enough of an obstacle to code crackers.
In the 1st generation of the PMD series, the game uses the character numbered 11 (0x0B) [male symbol] and 12 (0x0C) [female symbol] in the character set, which causes trouble for players because these character cannot be typed normally. This issue is fixed in the 2nd generation of the game.
- The character set of the 1st generation of PMD series (the position denotes the number the character represents):
? 6 7 N P R 8 9 F 0 + … S T X Y 4 5 M C H J - K 1 2 ! ♀ 3 Q ♂ W
- The character set of the 2nd generation of PMD series (the position denotes the number the character represents):
& 6 7 N P R 8 9 F 0 + # S T X Y 4 5 M C H J – K 1 2 = % 3 Q @ W
From the least significant bit, we shall sequentially extract 5 bits and map it to the corresponding character. We will put the character mapped from the less significant bit in the front and the character mapped from the more significant bit in the back.
Step 6: Scramble the code
The last step of the password creation process is to scramble the characters according to a given order. This will add extra work for decoders for encrypted password. However, scrambling the character of a password which has not gone through the encryption process, and with a fixed scrambling order, cannot prevent code cracker from finding out what piece of information a character holds. With enough samples and keen observation, one can easily deduct the areas of a code that changes whenever some value differs if the code is not encrypted.
No comments:
Post a Comment