PlaidCTF 2021 - minipokemon (450pt / 12 solves)

April 18, 2021
s1c88 rev

minipokemon

Description:

Enter the world of minipokemon!

Director: ubuntor

Cast: tylerni7

Files:


Overview

We are given a file called “minipokemon.min”. After a quick google, we can see that this is a ROM file for the Pokemon Mini.

The Pokemon Mini is a handheld game console running the S1C88 CPU. Here’s a manual.

game1

1. First Steps

Before this challenge I had never heard of the S1C88 architecture or even the Pokemon Mini. So I spent a fair bit of time reading the introduction in the maual linked above.

I’ll give a brief intro to the architecture here:

Registers

There are only a few registers:

  • BA (16-bit), B (8-bit), A (8-bit)
  • HL (16-bit), H (8-bit), L (8-bit)
  • IX (16-bit)
  • IY (16-bit)
  • PC (16-bit) (program counter)
  • SP (16-bit) (stack pointer)
  • XP (8-bit)
  • YP (8-bit)

Memory

Memory is banked so the first 0x8000 bytes are mapped to physical page 0 while the upper half of memory is mapped to the page specified by the 8-bit BR register (this ends up not being used).

Instructions

The instructions are Chip-8-like and mostly interpretable if you’re familiar with other 8-bit architectures.

  • LD a,b: mov between two points, there are many addressing modes, for example:
    • LD A,B
    • LD [HL],A
    • LD [0x1234],A
    • LD L,[0x4566]
    • LD B,[IX+0x20]
  • ADD/OR/XOR/SUB/MUL/INC/DEC: math operators
  • CP a,b: compare two values and set flags
  • CARL: a call instruction
  • JRL/JRS: jump long/short, this can also be conditional
  • RET/RETE: return from function and interrupt
  • DJR: decrement and jump if not zero (like x86 loop)

2. Disassembly

I typically use Binary Ninja for reversing problems and unfortunately there was no S1C88 plugin. So I decided to make one. I spent several hours with ehennenfent writing a disassembler plugin (with LLIL lifting!).

You can get it here: https://github.com/hgarrereyn/bn-pokemon-mini.

This gives us nice graphs like:

binja1

3. Reversing

The program itself is a simple flag checker. You enter a 24-character flag by moving a cursor left and right over the current string and incrementing and decrementing characters. When you press A it will check the flag and print out a “correct” or “incorrect” message.

Button presses are handled as interrupts in the S1C88. Due to ehennenfent adding symbols to the binary view, we were able to quite clearly see where those functions were called:

binja2

After reversing the interrupt handlers we were able to figure out where the input was stored in memory. Specifically, the program used a 5-line buffer like the following:

0x1380:       ^
0x1390: FLAG{AAAAAAA
0x13a0:       v
0x13b0: AAAAAAAAAAA
0x13c0:

Each line represents the current text draw on the screen. Graphics are handled by the PRC (program rendering chip). Specifically, the buffer here contains sprite indexes which are rendered as a map tileset with the tileset at 0x10000 which is simply an alphabet:

tiles

In the function handler for the “A” keypress, we see the following flag set:

func_a

Inside the main function, we see that it spinlocks on this flag:

main

Afterwards it calls a check_flag function and takes one of two control paths (presumably printing either “correct” or “incorrect”).

check_flag

The check_flag function (shown above) is a fairly massive piece of code and it took quite some time to reverse. The main control flow consists of 5 separate sections. In each section there are some conditionals that may cause it to exit with a failure case.

In short the check_flag function does the following:

  1. XOR user input with a magic string
  2. Convert the result to decimal and produce a large digit array that is interpreted as pairs of coordinates: [x0,y0,x1,y1,...,xn,yn]
  3. Neighboring coordinates can’t share values x[i] != x[i+2] and y[i] != y[i+2]
  4. Each consecutive pair of coordinates x1,y1 and x2,y2 specifies a line from x1,y1 to x2,y1 to x2,y2. Horizontal edges in the line are stored as value 5 in a path array while vertical edges are stored as 6. Corners in this path are stored as 1-4 depending on the orientation.
  5. If any component of the path is self-intersecting, the check fails.
  6. The path is validated using Masyu rules. Specifically there is a specified set of corner points (black dots) and edge points (white dots). Black dots must lie on a corner, white dots must lie on an edge and neighbor a corner:

masyu

The solution is obtained with the following path:

masyu

I’ve included a full python implementation of the flag checker at the end of this writeup.

To get the flag, we need to convert this path to a series of coordinates and then reverse the digit construction scheme:

magic = bytes([
    15,57,42,9,53,58,
    0,59,51,10,33,3,
    58,58,17,12,60,60,
    13,60,13,0,9,54])

charset = b'\
ABCDEFGHIJKLMNOPQRSTUVWXYZ\
abcdefghijklmnopqrstuvwxyz\
0123456789{}'

def decode(arr):
    d_str = ''.join([str(x) for x in arr])
    d = int(d_str[::-1])

    parts = [0] * 24
    for i in range(24):
        parts[i] = d & 0x3f
        d >>= 6

    parts = parts[::-1]

    out = bytes([a^b for a,b in zip(parts, magic)])
    a_out = bytes([charset[x] for x in out])
    return a_out

decode([
    1,4, 0,0, 2,2, 3,6, 4,2, 5,6, 
    6,2, 8,1, 3,0, 9,5, 8,3, 7,6, 
    9,9, 8,7, 6,8, 7,9, 2,8, 5,7, 
    1,9, 0,6, 2,3])
"PCTF{5EEth4tFURR3Tw4lcc}"

Entering this in the original game reveals the furret:

Timeline

I’ve included a timeline of the reversing process (including parts where we got stuck and deadends). Usually CTF writeups are just a highlight of the good parts but this should be an accurate description of exactly what steps we took:

(Times are in EST)

  • 8:00 PM - Started working on the problem. Lots of searching, figured out the cpu version and started looking for disassemblers.
  • 8:30 PM - Tried using mindis2 to disassemble which produced good looking instructions.
  • 9:00 PM - After looking through the mindis2 output for a while, started working on a Binary Ninja plugin.
  • 9:30 PM - Repurposed the mindis2 instruction encodings to get instructions displayed in Binary Ninja (no LLIL yet).
  • 12:30 AM - Most instructions lifted in Binary Ninja. ehennenfent starts working on adding a binary view with symbols for known addresses.
  • 2:00 AM - ehennenfent adds binary view support for Pokemon Mini ROMs.
  • 3:00 AM - Fixed up a few instruction lifting details, plugin is mostly complete. We start trying to figure out how to emulate the ROM.
  • 3:20 AM - We identify some tilesets present in the rom at addresses 0x10000 and 0x20000.
  • 3:45 AM - ehennenfent gets the ROM running in an emulator. We start reversing the control flow.
  • 4:00 AM - After finding the key control interrupts, we figure out where the flag input data is stored in memory.
  • 4:20 AM - ehennenfent gets a debugger running.
  • 4:25 AM - We identify 0x2c95 as the “flag checker” function and start going through it in detail.
  • 4:35 AM - Flag input is xored with a magic string.
  • 5:20 AM - We figure out that it does hex -> decimal conversion and stores the digits in a separate array.
  • 5:40 AM - Consecutive digit constraint.
  • 5:50 AM - Brief discussion about getting symbolic execution or fuzzing working.
  • 6:20 AM - 2:00 PM - Asleep
  • 2:10 PM - Setup a z3 script with the constraints we’ve identified.
  • 3:00 PM - Identify the first big loop that fills out the coordinate array (we don’t fully realize that these are coordinates by this point).
  • 3:15 PM - ehennenfent finds a typo in the C1S88 manual regarding flag conditions.
  • 3:30 PM - Get the coordinate array implemented in the z3 script.
  • 4:30 PM - Get the corner checker part impelmented in z3. Realize that the z3 script is going to be way too slow (too many symbolic array lookups).
  • 5:30 PM - Finally realize that it’s tracing a path in a 10x10 array based on coordinates you provide.
  • 5:50 PM - Post a graph of the magic coordinates in discord.
  • 6:20 PM - Realize that some of the target points are corner constraints while some are edge constraints. At this point we mistakenly think the edge constraints can’t neighbor a corner on either side while in reality they have to neighbor a corner.
  • 6:30 PM - Post a new graph in discord and jschnei immediately identifies it as a Masyu puzzle.
  • 6:35 PM - Aplet123, chaosagent and falafel2222 start helping with the puzzle component.
  • 7:30 PM - Some progress on the puzzle, but due to the edge constraint mistake, the puzzles are too constrained.
  • 8:30 PM - falafel2222 realizes that solving with regular Masyu rules obtains a unique solution of the right size.
  • 9:00 PM - After fiddling around with coordinate permutations we finally solve!

In total, we spent 7 hours writing the Binary Ninja plugin, 8 hours reversing the program itself and 2.5 hours solving the puzzle.

Python version

Here is more-detailed, python equivalent code for the flag checker:

magic = bytes([
    15,57,42,9,53,58,
    0,59,51,10,33,3,
    58,58,17,12,60,60,
    13,60,13,0,9,54])

charset = b'\
ABCDEFGHIJKLMNOPQRSTUVWXYZ\
abcdefghijklmnopqrstuvwxyz\
0123456789{}'

def check_flag(inp):
    # inp is a bytestring like "AAA..."

    # convert from hex to index
    x = bytes([charset.index(a) for a in inp])

    # xor with magic string
    x = bytes([a^b for a,b in zip(x, magic)])

    # convert to digit array
    val = 0
    for j in range(len(x)):
        val <<= 6
        val += x[j]

    s_val = str(val)
    if len(s_val) > 42:
        # flag is too big (numerically)
        return False

    s_digit = str(s_val).zfill(42)[-42:][::-1]
    digits = [int(x) for x in s_digit]

    # digits are interpreted as coordinate pairs:
    # (x0,y0,x1,y1,x2,y2,...,xn,yn)

    # copy two coordinates
    digits += digits[:4]

    # duplicate coordinate constraint
    for i in range(0,42,2):
        if digits[i] == digits[i+2]:
            return False
        if digits[i+1] == digits[i+3]:
            return False

    # first coordinate must be the smallest
    # (this is coord[1] for some reason...)
    p0 = (digits[2] * 10) + digits[3]
    
    for i in range(2,44,2):
        if (digits[i+1] * 10) + digits[i] < p0:
            return False
        if (digits[i+1] * 10) + digits[i+2] < p0:
            return False
       
    # trace coordinates in the 10x10 array
    path = [[0]*10 for i in range(10)]
    
    for i in range(2,44,2):
        y0 = digits[i-1]
        x1 = digits[i]
        y1 = digits[i+1]
        x2 = digits[i+2]
        y2 = digits[i+3]
        
        # no collisions
        if path[y1][x1] != 0: return False
        
        
        # corner map:
        #
        # 1,2,3,4 are corners
        # 5,6 are edges
        #
        #   6  6
        #   6  6
        # 553  155
        #
        # 554  255
        #   6  6
        #   6  6
        
        # trace x-component of line
        if x1 < x2:
            # right
            path[y1][x1] = (
                1
                if y1 > y0 else
                2
            )
            
            for i in range(1,x2-x1):
                if path[y1][x1+i] != 0:
                    return False
                path[y1][x1+i] = 5
        else:
            # left
            path[y1][x1] = (
                3
                if y1 > y0 else
                4
            )
            
            for i in range(1,x1-x2):
                if path[y1][x1-i] != 0:
                    return False
                path[y1][x1-i] = 5
    
        # trace y-component of line
        if y1 < y2:
            # up
            path[y1][x2] = (
                2
                if x1 > x2 else
                4
            )
            for i in range(1,y2-y1):
                if path[y1+i][x2] != 0:
                    return False
                path[y1+i][x2] = 6
        else:
            # down
            path[y1][x2] = (
                1
                if x1 > x2 else
                3
            )
            for i in range(1,y1-y2):
                if path[y1-i][x2] != 0:
                    return False
                path[y1-i][x2] = 6
            
    # check for target coordinates
    corners = [0,0,2,0,6,2,2,6,7,6,1,7,8,7]
    edges = [
        4,0,0,3,3,3,4,3,2,4,7,4,8,4,
        3,5,5,5,6,5,3,8,4,8,3,9,6,9]
    
    # check corners
    for i in range(0,len(corners),2):
        x,y = corners[i:i+2]
        
        if path[y][x] == 1:
            # bottom left
            if path[y][x+1] != 5: return False
            if path[y-1][x] != 6: return False
        elif path[y][x] == 2:
            # top left
            if path[y][x+1] != 5: return False
            if path[y+1][x] != 6: return False
        elif path[y][x] == 3:
            # bottom right
            if path[y][x-1] != 5: return False
            if path[y-1][x] != 6: return False
        elif path[y][x] == 4:
            # top right
            if path[y][x-1] != 5: return False
            if path[y+1][x] != 6: return False
        else:
            return False
    
    # check edges
    for i in range(0,len(edges),2):
        x,y = edges[i:i+2]
        
        if path[y][x] == 5:
            # horizontal
            if path[y][x-1] == 5 and path[y][x+1] == 5:
                return False
        elif path[y][x] == 6:
            # vertical
            if path[y-1][x] == 6 and path[y+1][x+1] == 6:
                return False
        else:
            return False
    
    return True
comments powered by Disqus