Introduction

Every year, a Pokemon games glitch researcher, known as TheZZAZZGlitch, hosts an event called “TheZZAZZGlitch’s April Fools Event.” This event features a custom game inspired by the Pokemon series, typically in the form of a save file, along with a short CTF challenge.

Below, you’ll find how I solved the challenges of this year’s event.

Please note that this article is a work in progress. It will be refined in the future, including the addition of the solutions to challenges 3 and 4.

Challenge 1 - Hall of Fame Data Recovery (Red/Blue)

Context

B1F is a truly amazing item. I used it to keep a small ACE payload which reminded me of my super secret password. But I encountered Missingno. in battle, and my payload got destroyed! Think it’s still possible to recover it? Here’s the save file I got after the incident.

In this challenge we are asked to recover a corrupted ACE payload of a glitch item inside a Pokemon Red save file.

Glitch items are items that have an item ID that is not associated with any existing in-game item, which can cause a variety of weird behaviors, and some of them allows to execute arbitrary code by using them.

In particular, the B1F item allows to execute code stored at $A7D0. To use it we need to enable SRAM access (for example, by displaying the trainer card) and select the “USE” option from the item menu.

To make following this writeup easier, I put symbols thorough the article: you can use them with BGB (or SameBoy if you’re on MacOS) and the Pokemon Red disassembly.

Save file details

Loading up the save file, we notice the following things:

  • The player name comes from an italian version of Pokemon Blue
  • The first item in the bag is indeed the B1F glitch item, crashing the game upon use

Does this mean that we have to look into the italian version of Missigno to complete this challenge?

Let’s find out by inspecting the memory:

  • The 6th item in the player’s bag (wBagItems+0B) has a quantity of 129
  • The area from $A498 to $A857 appears to be random bytes

Those two facts are both side effects of the english version of Missigno, so the answer to the previous question is “no”.

Missigno corruption

As said earlier, encountering Missigno corrupts the memory from $A498 to $A857, which is after the second sprite buffer (sSpriteBuffer2) and inside the Hall of Fame (sHallOfFame).

This corruption is caused by the sprite decompression routine: since the declared sprite dimension is 13x13 tiles and sSpriteBuffer2 has enough space for sprites up to 7x7 tiles, the decompressed tiles overflow into the Hall of Fame memory area.

Sprite decompression

I then decided to study how the sprite decompression algorithm works by looking at this video, which also includes some information about Missigno decompression at this timestamp. There’s also another video about Missigno sprite decompression from the same author here.

In short, what the decompression algorithm does for Missigno is:

  • Clear sSpriteBuffer1 and sSpriteBuffer2
  • RLE decode the sprite, which will set some bits inside the sprite buffers to 1
  • Apply delta decoding to the sprite buffers (SpriteDifferentialDecode)
  • Xor sSpriteBuffer2 with sSpriteBuffer1 (XorSpriteChunks)

Note that only the first operation doesn’t affect the corrupted area.

I then decided to look at the game’s implementation of the algorithm to get a few more details that will be useful later:

  • Decompression occurs by first iterating on the sprite columns
  • During delta decoding, the state (last decoded bit) gets reset to 0 after every row

Reverting the corruption

Since the area after the end of sSpriteBuffer2 doesn’t get zeroed out, we can still recover the payload by applying the inverse of the operations mentioned in the previous chapter.

To verify the correctness of every operation, I tested on a newly created save file with a known B1F payload instead of the one provided for the challenge.

Since the RLE decoding is a destructive operation, we cannot really undo its effects, but it won’t be a problem as we will see later, so we can ignore it.

First, we will have to xor everything from sSpriteBuffer2 up to the end of the corrupted memory area. Given that the provided save file has had its sprite buffers overwritten with data from other sprites, we will have to recover it by encountering Missigno and dumping sSpriteBuffer2 right after the XorSpriteChunks function has finished:

Then, we have to delta encode every byte. The game does delta decoding using a lookup table for speed, but it can also be done by iterating over the individual bits.

Now we have all the pieces we need to recover the original payload:

WIDTH  = 13
HEIGHT = 13
TILE_SIZE = 8
BUFFER_SIZE = (7 * 7) * TILE_SIZE
BUFFER_OFFSET = 0x310

def read_file(fname):
    with open(fname, 'rb') as f:
        return f.read()

def delta_encode(b, state):
    # carry over the state bit
    b |= state << 8
    res = 0

    for i in range(7, -1, -1):
        # is the current bit different from the previous one?
        if ((b >> i) & 0b11) in (0b10, 0b01):
            # if so, encode it as 1
            res |= (1 << i)

    return res

def main():
    data = bytearray(read_file('pokered.sav'))
    
    # recover sSpriteBuffer2
    start = BUFFER_OFFSET
    end = BUFFER_OFFSET + BUFFER_SIZE
    data[start:end] = read_file('patch.bin')

    res = bytearray(data)

    for row in range(HEIGHT * TILE_SIZE):
        state = 0

        for col in range(WIDTH):
            i = BUFFER_OFFSET + row + (col * WIDTH * TILE_SIZE)
            b = data[i] ^ data[i - BUFFER_SIZE]

            res[i] = delta_encode(b, state)
            state = b & 1
    
    with open('solution.sav', 'wb') as f:
        f.write(res)

if __name__ == '__main__':
    main()

This script generates a save file with the following B1F payload:

ld hl, Text_A7D6
jp PrintText

Text_A7D6:
    text "Good job!"
    line "Za9W4uOnYy5Q"
    prompt
    done

Challenge 2 - The Sus-file (Crystal)

Context

I got this Pokémon Crystal save file from a friend, but it’s really strange. Sometimes weird colored artifacts appear on the screen, and sometimes the game just straight up crashes. I’m sure there’s something hidden in it. Maybe you’ll be able to figure it out? Here’s the save file I got.

This time we’re asked to investigate a suspicious Pokemon Crystal save file that causes some glitches, hinting that there’s something hidden in it.

For this challenge, we’ll make use of the symbols from the Pokemon Crystal disassembly and the same emulator we used earlier.

Finding the hidden code

I assumed the hidden thing mentioned in the challenge description was caused by some code stored in SRAM that was executing at a certain point. Since SRAM access is disabled most of the time while the game is running, I expected the payload to be copied to WRAM at some point, so I put a watchpoint on jumps and executions happening on the WRAM address space instead:

When I pressed “CONTINUE” from the save loading menu, I got a hit inside the function RunMobileScript:

This is happening due to a bug known as 0x1500 control code arbitrary code execution, which will trigger every time the player name is displayed: the player’s name is an unterminated string, and after some bytes it contains the sequence $15 $00, which will cause the text engine to jump to the address $CD52 due to a lookup table calculation oversight.

You can find a more detailed expanation of what’s up the player’s name in Kuruyia’s writeup.

At $D48B we can see the actual code that will be executed:

I cleaned it up a bit, and replaced some code with macros to make it easier to read:

Start: ; D48B
    ld de, $12A3
    ld b, d
    ld c, e
    jp CheckTiles

CheckTiles: ; DEF6
    lda_coord 0, 12 ; C590
    cp a, $79
    jr nz, .l_DF42
    lda_coord 11, 0 ; C4AB
    cp a, $05
    jr nz, .l_DF42
    lda_coord 7, 6 ; C51F
    cp a, $23
    jr nz, .l_DF42
    hlcoord 3, 2 ; C4CB
    ld a, [hli]
    cp a, $02
    jr nz, .l_DF42
    ld a, [hli]
    cp a, $04
    jr nz, .l_DF42
    lda_coord 12, 11 ; C588
    cp a, $01
    jr nz, .l_DF42
    xor a
    call f_DF4D
    cp a, $35
    jr nz, .l_DF42
    ld c, $0A
    ld hl, $DF7A
.l_DF2C
    nop
    ld a, c
    call f_DF4D
    and a, $1F
    add a, $84
    add c
    ld [hli], a
    dec c
    jr nz, .l_DF2C
    ld hl, sp+$0C
    ld bc, $DF67
    ld [hl], c
    inc hl
    ld [hl], b
.l_DF42
    ld hl, sp+$08
    ld c, [hl]
    inc hl
    ld b, [hl]
    inc bc
    inc bc
    inc bc
    ld h, b
    ld l, c
    ret

f_DF4D:
    push hl
    push bc
    ld hl, [wTileMap]
    add l
    ld l, a
    ld c, $78
    xor a
.l_DF57
    ld b, [hl]
    add b
    swap a
    inc hl
    ld b, [hl]
    xor b
    swap a
    inc hl
    dec c
    jr nz, .l_DF57
    pop bc
    pop hl
    ret

Plaintext flag oversight

In the code above, there is a reference to address $DF67. If you load the game and inspect the memory at that address, you will find these bytes:

51 51 92 84 82 91 84 93 7F 8F 80 92 92 96 8E 91 83 9C 4F 91 A3 98 A4 99 8B 88 94 91 A3 57

This inconspicuous series of bytes is actually the message that will show the flag, encoded using the game’s character encoding:

Text_DF67:
    para
    para "SECRET PASSWORD:"
    line "RdYeZLIURd"
    done

The author of the challenge probably forgot to clear this memory area after testing it and saved afterwards, thus embedding the text in the released file too.

For the rest of the article, we will assume this memory area has been zeroed out beforehand.

Tile checking

What the previous code is trying to do is checking for some specific tiles appearing on the screen, and if all of them match the expected ones, it will call $DFD4, which will generate the flag based on the content of wTileMap.

Here’s a visual representation of the tiles checked by the code:

Tile $79 is the textbox upper right corner, whereas the others are all map tiles.

How Pokemon Crystal maps work

To save space, maps in Pokemon Crystal are made of groups of 4x4 tiles called blocks (or metatiles). Each blockset has a corresponding tileset, which defines how the tiles actually looks like.

You can use Polished Map to see the blocksets and tiles for maps in the disassembly:

Each blockset is just a sequence of 16 tile IDs. For example, the block $08 shown the image above is stored as this:

02 02 02 02  02 02 20 21  01 01 30 31  11 11 40 41

For reference, here’s some of the locations used in the pokecrystal repository to store map data:

  • data/tilesets/*_metatiles.bin: blocksets
  • gfx/tilesets/: tilesets
  • data/maps/attributes.asm: map attributes
  • constants/map_constants.asm: map constants
  • data/maps/maps.asm: map headers
  • maps/: map objects, events and scripts

Finding the needle in the haystack

To solve the challenge you need to:

  • find the right map
  • find the right X and Y coordinates on the map
  • trigger a dialogue that displays the player’s name

One way to accomplish this is to write a map renderer and check the positions of the expected tiles relative to each other. This solution works, but coding a map renderer for the game can be quite time consuming.

I instead opted to filter out all tilesets that couldn’t be used to generate the map we are looking for, then look for the target map manually.

Since the player moves in units of 2x2 tiles each step, a individual tile could be in different positions inside a block, depending on the player’s position:

In addition to that, two adjacent tiles could either be on the same block or part of two adjacent blocks, which might affect tiles $02 and $04.

With those two caveats in mind, I wrote this script to scan all the blocksets for the individual tiles:

import glob
import io
import os

POKECRYSTAL_DIRECTORY = '~/pokecrystal'
TILESETS_DIRECTORY = POKECRYSTAL_DIRECTORY + '/data/tilesets'

class Color:
    GREEN = '\033[1;32m'
    RESET = '\033[0m'

tile_01 = [
    '00 00 00 00  00 00 00 00  00 00 00 00  00 00 01 00',
    '00 00 00 00  00 00 00 00  00 00 00 00  01 00 00 00',
    '00 00 00 00  00 00 01 00  00 00 00 00  00 00 00 00',
    '00 00 00 00  01 00 00 00  00 00 00 00  00 00 00 00'
]

tile_05 = [
    '00 00 00 05  00 00 00 00  00 00 00 00  00 00 00 00',
    '00 05 00 00  00 00 00 00  00 00 00 00  00 00 00 00'
]

tile_23 = [
    '00 00 00 00  00 00 00 00  00 00 00 23  00 00 00 00',
    '00 00 00 00  00 00 00 00  00 23 00 00  00 00 00 00',
    '00 00 00 23  00 00 00 00  00 00 00 00  00 00 00 00',
    '00 23 00 00  00 00 00 00  00 00 00 00  00 00 00 00'
]

tile_02 = [
    '00 00 00 00  00 00 00 00  00 00 00 02  00 00 00 00',
    '00 00 00 02  00 00 00 00  00 00 00 00  00 00 00 00'
]

tile_04 = [
    '00 00 00 00  00 00 00 00  04 00 00 00  00 00 00 00',
    '04 00 00 00  00 00 00 00  00 00 00 00  00 00 00 00'
]

tile_0204 = [
    '00 00 00 00  00 00 00 00  00 02 04 00  00 00 00 00',
    '00 02 04 00  00 00 00 00  00 00 00 00  00 00 00 00'
]

# Used to select only the tilesets that have all the required tiles
valid_results = [
	[1, 1, 1, 1, 1, 0],
	[1, 1, 1, 0, 0, 1],
	[1, 1, 1, 0, 1, 1],
	[1, 1, 1, 1, 0, 1],
	[1, 1, 1, 1, 1, 1]
]

# Check whether a candidate matches with a block
def check_candidate(candidate, block):
    for i in range(16):
        if candidate[i] != 0 and candidate[i] != block[i]:
            return False

    return True

# Return True if at least one candidate tile has been found inside a blockset
def check_tile(candidates, fname):
    found = False

    with open(fname, 'rb') as f:
        blockset = io.BytesIO(f.read())

    while True:
        block = blockset.read(16)
        if block == b'': break

        for candidate in candidates:
            candidate = bytes.fromhex(candidate)
            found |= check_candidate(candidate, block)

    return found

# Generate a list of checkboxes for each tileset previously marked as valid
def display_valid_tilesets(tileset):
    s = ''

    for v in tileset:
        if v == 1:
            checkmark = Color.GREEN + '*' + Color.RESET
            s += f'[{checkmark}] '

        else:
            s += '[ ] '
    
    return s[:-1]

def main():
    os.chdir(TILESETS_DIRECTORY)
    blocksets = glob.glob('*_metatiles.bin')
    tilesets = {}

    for blockset in blocksets:
        tileset_name = blockset[:-14]
        tilesets[tileset_name] = [0, 0, 0, 0, 0, 0]
        tileset = tilesets[tileset_name]

        for i, tile in enumerate([tile_01, tile_05, tile_23, tile_02, tile_04, tile_0204]):
            if check_tile(tile, blockset):
                tileset[i] = 1

        if tileset in valid_results:
            line = f'{tileset_name}: '.ljust(22)
            line += display_valid_tilesets(tileset)
            print(line)
    
if __name__ == '__main__':
    main()

After running this script, we get the following output. Each checkbox signals the presence or absence of tiles $01, $05, $23, $02, $04 and $02+$04 respectively:

mansion:              [*] [*] [*] [*] [*] [ ]
pokecom_center:       [*] [*] [*] [*] [*] [ ]
tower:                [*] [*] [*] [*] [*] [*]
underground:          [*] [*] [*] [*] [*] [ ]

After inspecting each tileset individually, I found out the most promising one was tower, and after checking a few maps, I found that the Pewter Gym rendered tiles matched the expected ones:

At this point all that was left was finding the right X and Y coordinates and triggering the dialogue, which can be done by trial and error: