# 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.

# 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:

# 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:

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:

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

Inside the `main`

function, we see that it spinlocks on this flag:

Afterwards it calls a `check_flag`

function and takes one of two control paths (presumably printing either “correct” or “incorrect”).

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:

- XOR user input with a magic string
- Convert the result to decimal and produce a large digit array that is interpreted as pairs of coordinates:
`[x0,y0,x1,y1,...,xn,yn]`

- Neighboring coordinates can’t share values
`x[i] != x[i+2]`

and`y[i] != y[i+2]`

- 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. - If any component of the path is self-intersecting, the check fails.
- 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:

The solution is obtained with the following path:

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:

now that plaidctf is over i can finally share this furret (with 1-bit accumula town music) pic.twitter.com/dJmHN548P2

— /^\/j?ub⦋uʌ⦌nt(ɔɹ|ɚ)\/$/ (@ubuntor) April 18, 2021

# 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
```