On March 31st 2017, TheZZAZZGlitch released his April Fools 2017 event.
The event being a crafted save file for Pokémon Blue, it being a small game where you need to use memory patching or debugging techniques to beat it.
After you beat the game, a password is generated which allowed you to submit your score to the event website.
The best score (naturally, that score is 31337) can only be obtained by either patching the key-generation routine ("crackme"), or making your own keygen ("keygenme").
I, personally, did the latter.
The first thing that has to be done in any keygenme challenge like this is actually finding the key-generation routine.
There are a couple of different ways that you can go about this.
Either you could search the save file for the text strings (in the proprietary encoding used by Pokémon Blue) that you would expect to see at the end, or, you can beat the game.
I beat the game, using bgb's excellent debugger to help; I got through the first two rooms by NOPping out the opcodes that corrupted parts of the map, and got through the battle in the third room by using the debugger to set the instruction pointer to the function that faints the enemy's Pokémon, when it was originally at a conditional return statement inside the battle loop function. From there, I finished the game "as usual" using the 4F item that you're given.
There's plenty of ways to beat the game, I just wanted to mention the unusual strategies I used.
Anyway, after beating the game, head into the debugger, step out of the vblank function and see the infinite loop at 3:A273.
If you searched for text strings instead, the text strings are also in the same SRAM bank 3 (0x2000 bytes at .SAV offset 0x6000).
I do like IDA, so I personally opened the save file into IDA, being sure to set the "Game Boy" processor type, and making sure that the file load happened from offset 0x6000 into memory address 0xA000.
Now, if you take a look around that infinite loop, you'll see a few instructions before, a call to a function at 0xA6AE. This function does a few things, including, if you look at the function calls, a string copy of the congratulations text.
One of the functions it calls is at 0xA6EC. If you look at it, you can see this is the key-generation routine.
Take a look at the function at 0xA6EC. You can see it does a bunch of XORs, and sets some bits in a bitfield. Note that the bits are set based on the value of a function that actually sets up a small ROP chain to get the value from another SRAM bank (bank 2).
Right at the end of the function, it calls two functions and then returns.
Let's look at the second function first, the one at 0xA7CC. It sets two registers -- hl gets set with the address of the achievements bitfield -- then calls the same function 6 times.
The function that is called, basically calls another function twice, but first time, the a register contains the low nibble of the byte pointed to by the hl register, and the second time, the a register contains the high nibble of that byte (gets the byte, shifts it right by 4 bits, ANDs with 0xF). After both function calls, the hl register is incremented.
This second function called twice, gets a byte from an array, using the a register as the index. So, this array contains 16 bytes, as follows:
0x67, 0x61, 0x64, 0x60, 0x69, 0x6B, 0x66, 0x65, 0x62, 0x6A, 0x63, 0x68, 0x6C, 0xF8, 0xFC, 0xFD
If you look at the emulated Game Boy's VRAM, or just GCL's BIG LIST, you'll notice something.
These characters correspond to printable text characters in the game's proprietary encoding! In fact, they correspond to the bold variants of the characters -- the ones used when displaying the password, in fact!
So, the final password is just hex digits (but with the nibbles reversed in each byte), put through a substitution cipher.
Here is the conversion table:
0123456789ABCDEF
HBEAVLGFCSDIM267
Now we know what the final password is, let's take a look at the first function, at 0xA76D, located right after the main keygen function ends. We can see that it seems to obfuscate each byte, XORing it and then calling a function at 0xA830.
This function is a substitution cipher too, it grabs and returns a value from a 256-length array located after the function, using the passed value (ie, the XORed byte) as the index.
The array is listed below in its entirety:
0xB4, 0x6B, 0xCB, 0xDE, 0xB8, 0x74, 0xE1, 0x51, 0x59, 0x3D, 0x66, 0xDD, 0xF3, 0xDA, 0x9D, 0x3F,
0x08, 0x0A, 0xE6, 0xBB, 0x68, 0x21, 0x79, 0xF1, 0xF2, 0xC3, 0x69, 0xF5, 0x44, 0x9F, 0xAA, 0x77,
0x62, 0xD1, 0x2E, 0x00, 0x82, 0x52, 0xBD, 0x57, 0x86, 0x76, 0x34, 0x84, 0x64, 0x31, 0x10, 0xFD,
0xAD, 0xA9, 0xEA, 0x01, 0x9A, 0x53, 0xE8, 0x7B, 0x9B, 0x0D, 0x56, 0x22, 0x50, 0xB1, 0x61, 0xF7,
0x94, 0xCE, 0x16, 0xD5, 0x90, 0x91, 0xC7, 0xD8, 0xF9, 0x3A, 0xC5, 0x36, 0x8B, 0x73, 0x03, 0xAF,
0x37, 0x38, 0xA1, 0x7A, 0x72, 0xC8, 0xB0, 0x02, 0x43, 0x63, 0xD7, 0x1D, 0x24, 0x85, 0x25, 0xA8,
0x46, 0xE4, 0xE0, 0x33, 0xAC, 0xC0, 0xA7, 0x6D, 0xF4, 0x95, 0x0F, 0x4E, 0xD6, 0x41, 0xB6, 0x99,
0x1B, 0x2D, 0x78, 0x8C, 0x97, 0xE9, 0x28, 0x4F, 0xE3, 0x6C, 0x1E, 0x9E, 0xB5, 0x11, 0xCC, 0x87,
0x7C, 0xA2, 0x47, 0x8D, 0xEB, 0x70, 0x8E, 0xA3, 0x81, 0xFE, 0x4C, 0x5A, 0x8F, 0x5E, 0x4A, 0x5B,
0xEC, 0x15, 0x20, 0xD0, 0x13, 0xFC, 0x92, 0x58, 0x7E, 0x4B, 0x49, 0x05, 0x09, 0x88, 0x30, 0x89,
0x5F, 0xAB, 0x75, 0x26, 0x80, 0xD2, 0x17, 0x8A, 0x60, 0xAE, 0xCF, 0xBE, 0x96, 0x55, 0x54, 0x07,
0xED, 0x0C, 0x9C, 0xCD, 0xBA, 0xA5, 0x32, 0x2A, 0x29, 0x35, 0x12, 0x83, 0x27, 0xEE, 0xC9, 0x7F,
0x98, 0xE5, 0xB9, 0x19, 0xC6, 0x3E, 0x0E, 0x42, 0x0B, 0xB7, 0x1A, 0xA4, 0x6A, 0x2C, 0xE2, 0xD3,
0xF8, 0xCA, 0x18, 0xF0, 0xDF, 0xDC, 0x23, 0x1C, 0x3B, 0x48, 0xBC, 0xFB, 0xB2, 0x65, 0xEF, 0x6E,
0xFA, 0xDB, 0xF6, 0x14, 0x71, 0x6F, 0xD4, 0x5D, 0x5C, 0x4D, 0x93, 0xFF, 0xD9, 0x39, 0x45, 0x40,
0x2F, 0xE7, 0x67, 0x04, 0xC4, 0xB3, 0xA6, 0x7D, 0xC2, 0x2B, 0xC1, 0xBF, 0x1F, 0x06, 0x3C, 0xA0
After the obfuscation, there's some slightly convoluted code. If you look closer, after the initial setup there's the same block of code repeated four times (for each of the four bytes of the main serial).
This code basically does, for each byte:
b += serial_byte
c ^= serial_byte
...where bc is initialised to 0xC78A. After that, it calls the same function for b and c, and uses the first output of that function for byte 5 of the serial, and the second output for byte 6.
Looking at that function (it's at 0xA820), you can see it returns the low 8 bits of 0x41A7 + (0x72D4 * (!byte ? 0x100 : byte)), where byte is the function input.
(If you're not sure where the 0x100 comes from, you can see it decrements the a register then checks if it's zero; so if the a register is already zero, it'll underflow and roll around to 0xff.
This basically is a second substitution cipher, but the array is essentially calculated at runtime instead of being hardcoded.
I calculated all the possibilities, and here's the resulting array:
0xd4, 0x7b, 0x22, 0xc9, 0x70, 0x17, 0xbe, 0x65, 0x0c, 0xb3, 0x5a, 0x01, 0xa8, 0x4f, 0xf6, 0x9d,
0x44, 0xeb, 0x92, 0x39, 0xe0, 0x87, 0x2e, 0xd5, 0x7c, 0x23, 0xca, 0x71, 0x18, 0xbf, 0x66, 0x0d,
0xb4, 0x5b, 0x02, 0xa9, 0x50, 0xf7, 0x9e, 0x45, 0xec, 0x93, 0x3a, 0xe1, 0x88, 0x2f, 0xd6, 0x7d,
0x24, 0xcb, 0x72, 0x19, 0xc0, 0x67, 0x0e, 0xb5, 0x5c, 0x03, 0xaa, 0x51, 0xf8, 0x9f, 0x46, 0xed,
0x94, 0x3b, 0xe2, 0x89, 0x30, 0xd7, 0x7e, 0x25, 0xcc, 0x73, 0x1a, 0xc1, 0x68, 0x0f, 0xb6, 0x5d,
0x04, 0xab, 0x52, 0xf9, 0xa0, 0x47, 0xee, 0x95, 0x3c, 0xe3, 0x8a, 0x31, 0xd8, 0x7f, 0x26, 0xcd,
0x74, 0x1b, 0xc2, 0x69, 0x10, 0xb7, 0x5e, 0x05, 0xac, 0x53, 0xfa, 0xa1, 0x48, 0xef, 0x96, 0x3d,
0xe4, 0x8b, 0x32, 0xd9, 0x80, 0x27, 0xce, 0x75, 0x1c, 0xc3, 0x6a, 0x11, 0xb8, 0x5f, 0x06, 0xad,
0x54, 0xfb, 0xa2, 0x49, 0xf0, 0x97, 0x3e, 0xe5, 0x8c, 0x33, 0xda, 0x81, 0x28, 0xcf, 0x76, 0x1d,
0xc4, 0x6b, 0x12, 0xb9, 0x60, 0x07, 0xae, 0x55, 0xfc, 0xa3, 0x4a, 0xf1, 0x98, 0x3f, 0xe6, 0x8d,
0x34, 0xdb, 0x82, 0x29, 0xd0, 0x77, 0x1e, 0xc5, 0x6c, 0x13, 0xba, 0x61, 0x08, 0xaf, 0x56, 0xfd,
0xa4, 0x4b, 0xf2, 0x99, 0x40, 0xe7, 0x8e, 0x35, 0xdc, 0x83, 0x2a, 0xd1, 0x78, 0x1f, 0xc6, 0x6d,
0x14, 0xbb, 0x62, 0x09, 0xb0, 0x57, 0xfe, 0xa5, 0x4c, 0xf3, 0x9a, 0x41, 0xe8, 0x8f, 0x36, 0xdd,
0x84, 0x2b, 0xd2, 0x79, 0x20, 0xc7, 0x6e, 0x15, 0xbc, 0x63, 0x0a, 0xb1, 0x58, 0xff, 0xa6, 0x4d,
0xf4, 0x9b, 0x42, 0xe9, 0x90, 0x37, 0xde, 0x85, 0x2c, 0xd3, 0x7a, 0x21, 0xc8, 0x6f, 0x16, 0xbd,
0x64, 0x0b, 0xb2, 0x59, 0x00, 0xa7, 0x4e, 0xf5, 0x9c, 0x43, 0xea, 0x91, 0x38, 0xdf, 0x86, 0x2d
The second output of this function (byte 6 of the serial) is then used as a XOR key to obfuscate the main serial (first 4 bytes).
So what is the point of last 2 bytes? Think about it... it's a checksum of course! So the serial checking code can know if the serial is valid!
Plus, half of the checksum is used to further obfuscate the serial by XOR, so if you change 1 byte of the serial, the entire password will change.
So, now we know how the final serial gets generated. We know how it gets obfuscated. We know that the first byte of it is a bitfield. But what about the other 3 bytes?
Go back to the function at 0xA6EC. See what it does at initialisation: it sets first byte to 0, second byte comes out of a function at 0xA6D6 (if you look at that function, it just calls 0x3E5C, which is the game's function to get a psuedo-random number, so second byte is effectively random).
Third and fourth bytes are deobfuscated from a buffer at 0xDD00. But what are those bytes? We still don't know.
I'm going to assume you don't want to set a breakpoint after the deobfuscation and check manually. So I'll give you an example.
The four bytes 01 EE 08 35 give the password DVCDD76GISCA.
If you plugged that into the AJAX script to check a password, you get this JSON back:
{"success":1,"data":{"time":[8,53],"achievements":[true,false,false,false,false,false,false],"achievement_bitfield":1,"rand_val":238,"previous_entry":false,"score":14670}}
We know the first byte is the achivements bitfield. The "rand_val" element is decimal 238, or hex 0xEE. So that's the second byte.
And the third and fourth bytes turn out to be... the time. 0x35 is decimal 53.
So, the serial structure is as follows (C format):
typedef struct {
BYTE achievements;
BYTE random;
BYTE minutes;
BYTE seconds;
WORD checksum;
} serial;
The contents of the serial having been put through several stages of obfuscation.
But what about the super secret 31337 achievement?
Well, several times during the creation of the password, bit 6 of the achievements are unset, and there are 6 other achievements.. Take a guess at what that bit does ;)
So, that's basically all you need to know to make a keygen. The only thing that hasn't been mentioned is some of the XOR keys, but those can easily be obtained if you're following along with a disassembly of savebank 3.
I made my keygen in PHP, and hardcoded the values inside it. Here's my code:
<?php
$obf = array(
array(
0xB4, 0x6B, 0xCB, 0xDE, 0xB8, 0x74, 0xE1, 0x51, 0x59, 0x3D, 0x66,
0xDD, 0xF3, 0xDA, 0x9D, 0x3F, 8, 0xA, 0xE6, 0xBB, 0x68, 0x21,
0x79, 0xF1, 0xF2, 0xC3, 0x69, 0xF5, 0x44, 0x9F, 0xAA, 0x77, 0x62,
0xD1, 0x2E, 0, 0x82, 0x52, 0xBD, 0x57, 0x86, 0x76, 0x34, 0x84,
0x64, 0x31, 0x10, 0xFD, 0xAD, 0xA9, 0xEA, 1, 0x9A, 0x53, 0xE8,
0x7B, 0x9B, 0xD, 0x56, 0x22, 0x50, 0xB1, 0x61, 0xF7, 0x94, 0xCE,
0x16, 0xD5, 0x90, 0x91, 0xC7, 0xD8, 0xF9, 0x3A, 0xC5, 0x36, 0x8B,
0x73, 3, 0xAF, 0x37, 0x38, 0xA1, 0x7A, 0x72, 0xC8, 0xB0, 2, 0x43,
0x63, 0xD7, 0x1D, 0x24, 0x85, 0x25, 0xA8, 0x46, 0xE4, 0xE0, 0x33,
0xAC, 0xC0, 0xA7, 0x6D, 0xF4, 0x95, 0xF, 0x4E, 0xD6, 0x41, 0xB6,
0x99, 0x1B, 0x2D, 0x78, 0x8C, 0x97, 0xE9, 0x28, 0x4F, 0xE3, 0x6C,
0x1E, 0x9E, 0xB5, 0x11, 0xCC, 0x87, 0x7C, 0xA2, 0x47, 0x8D, 0xEB,
0x70, 0x8E, 0xA3, 0x81, 0xFE, 0x4C, 0x5A, 0x8F, 0x5E, 0x4A, 0x5B,
0xEC, 0x15, 0x20, 0xD0, 0x13, 0xFC, 0x92, 0x58, 0x7E, 0x4B, 0x49,
5, 9, 0x88, 0x30, 0x89, 0x5F, 0xAB, 0x75, 0x26, 0x80, 0xD2, 0x17,
0x8A, 0x60, 0xAE, 0xCF, 0xBE, 0x96, 0x55, 0x54, 7, 0xED, 0xC,
0x9C, 0xCD, 0xBA, 0xA5, 0x32, 0x2A, 0x29, 0x35, 0x12, 0x83, 0x27,
0xEE, 0xC9, 0x7F, 0x98, 0xE5, 0xB9, 0x19, 0xC6, 0x3E, 0xE, 0x42,
0xB, 0xB7, 0x1A, 0xA4, 0x6A, 0x2C, 0xE2, 0xD3, 0xF8, 0xCA, 0x18,
0xF0, 0xDF, 0xDC, 0x23, 0x1C, 0x3B, 0x48, 0xBC, 0xFB, 0xB2, 0x65,
0xEF, 0x6E, 0xFA, 0xDB, 0xF6, 0x14, 0x71, 0x6F, 0xD4, 0x5D, 0x5C,
0x4D, 0x93, 0xFF, 0xD9, 0x39, 0x45, 0x40, 0x2F, 0xE7, 0x67, 4,
0xC4, 0xB3, 0xA6, 0x7D, 0xC2, 0x2B, 0xC1, 0xBF, 0x1F, 6, 0x3C,
0xA0
),
array(
0xd4, 0x7b, 0x22, 0xc9, 0x70, 0x17, 0xbe, 0x65, 0xc, 0xb3, 0x5a,
0x1, 0xa8, 0x4f, 0xf6, 0x9d, 0x44, 0xeb, 0x92, 0x39, 0xe0,
0x87, 0x2e, 0xd5, 0x7c, 0x23, 0xca, 0x71, 0x18, 0xbf, 0x66,
0xd, 0xb4, 0x5b, 0x2, 0xa9, 0x50, 0xf7, 0x9e, 0x45, 0xec,
0x93, 0x3a, 0xe1, 0x88, 0x2f, 0xd6, 0x7d, 0x24, 0xcb, 0x72,
0x19, 0xc0, 0x67, 0xe, 0xb5, 0x5c, 0x3, 0xaa, 0x51, 0xf8, 0x9f,
0x46, 0xed, 0x94, 0x3b, 0xe2, 0x89, 0x30, 0xd7, 0x7e, 0x25, 0xcc,
0x73, 0x1a, 0xc1, 0x68, 0xf, 0xb6, 0x5d, 0x4, 0xab, 0x52, 0xf9,
0xa0, 0x47, 0xee, 0x95, 0x3c, 0xe3, 0x8a, 0x31, 0xd8, 0x7f, 0x26,
0xcd, 0x74, 0x1b, 0xc2, 0x69, 0x10, 0xb7, 0x5e, 0x5, 0xac, 0x53,
0xfa, 0xa1, 0x48, 0xef, 0x96, 0x3d, 0xe4, 0x8b, 0x32, 0xd9, 0x80,
0x27, 0xce, 0x75, 0x1c, 0xc3, 0x6a, 0x11, 0xb8, 0x5f, 0x6, 0xad,
0x54, 0xfb, 0xa2, 0x49, 0xf0, 0x97, 0x3e, 0xe5, 0x8c, 0x33, 0xda,
0x81, 0x28, 0xcf, 0x76, 0x1d, 0xc4, 0x6b, 0x12, 0xb9, 0x60, 0x7,
0xae, 0x55, 0xfc, 0xa3, 0x4a, 0xf1, 0x98, 0x3f, 0xe6, 0x8d, 0x34,
0xdb, 0x82, 0x29, 0xd0, 0x77, 0x1e, 0xc5, 0x6c, 0x13, 0xba, 0x61,
0x8, 0xaf, 0x56, 0xfd, 0xa4, 0x4b, 0xf2, 0x99, 0x40, 0xe7, 0x8e,
0x35, 0xdc, 0x83, 0x2a, 0xd1, 0x78, 0x1f, 0xc6, 0x6d, 0x14, 0xbb,
0x62, 0x9, 0xb0, 0x57, 0xfe, 0xa5, 0x4c, 0xf3, 0x9a, 0x41, 0xe8,
0x8f, 0x36, 0xdd, 0x84, 0x2b, 0xd2, 0x79, 0x20, 0xc7, 0x6e, 0x15,
0xbc, 0x63, 0xa, 0xb1, 0x58, 0xff, 0xa6, 0x4d, 0xf4, 0x9b, 0x42,
0xe9, 0x90, 0x37, 0xde, 0x85, 0x2c, 0xd3, 0x7a, 0x21, 0xc8, 0x6f,
0x16, 0xbd, 0x64, 0xb, 0xb2, 0x59, 0x0, 0xa7, 0x4e, 0xf5, 0x9c,
0x43, 0xea, 0x91, 0x38, 0xdf, 0x86, 0x2d
)
);
function hextoobf($s) {
$ret = '';
for ($i = 0; $i < strlen($s); $i += 2) {
$ret .= $s[$i+1] . $s[$i];
}
// get around order of replacement problems
$ret = str_replace(
array('0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'),
array('H','%','*','#','V','L','G','(','^','S','&','I','M','!','@','£'),
$ret
);
$ret = str_replace(
array('!', '@', '£', '#', '%', '^', '&', '*', '('),
array('2', '6', '7', 'A', 'B', 'C', 'D', 'E', 'F'),
$ret
);
return $ret;
}
function arrtoobf($arr) {
array_unshift($arr,'C6');
$hex = array_values(unpack('H*',call_user_func_array('pack',$arr)));
return hextoobf(strtoupper($hex[0]));
}
function obf_key_part_1($arr) {
global $obf;
$arr[0] = $obf[0][$arr[0] ^ 0x55];
$arr[1] = $obf[0][$arr[1] ^ 0xaa];
$arr[2] = $obf[0][$arr[2] ^ 0xf0];
$arr[3] = $obf[0][$arr[3] ^ 0x0f];
return $arr;
}
function obf_key_part_2($arr) {
for ($i = 0; $i < 4; $i++) {
$arr[$i] ^= $arr[5];
}
return $arr;
}
function checksum($arr) {
$chk = array(0xc7,0x8a);
for ($i = 0; $i < 4; $i++) {
$chk[0] = ($chk[0] + $arr[$i]);
$chk[1] = ($chk[1] ^ $arr[$i]);
}
$chk[0] &= 0xff;
return $chk;
}
function obf_checksum($chk) {
global $obf;
$chk[0] = $obf[1][$chk[0]];
$chk[1] = $obf[1][$chk[1]];
return $chk;
}
function keygen($flags,$rand,$min,$sec) {
$arr = array($flags,$rand & 0xfe,$min,$sec);
$arr = obf_key_part_1($arr);
$arr = array_values(array_merge($arr,obf_checksum(checksum($arr))));
$arr = obf_key_part_2($arr);
return arrtoobf($arr);
}
echo keygen(0xff,239,0,0);I'd like to thank TheZZAZZGlitch for making an awesome little reversing challenge.
I also noticed the plug for his upcoming ROM hack p0k3m0n #00f -- I hope that's more of the same, based on the single tease, it definitely seems to be :)
Finally, I'd like to say, I've been saying for a while how Pokémon reversers seem to be doing more talented stuff than some infosec guys these days, and this reversing challenge just shows it even more. I think this may even be the first Game Boy keygenme!
Oh, please follow me on Mastodon!
For those who want a python version :P
Anyway, your writeup is so good that mine is basically a link to this (hope you don't mind).