PlaidCTF 2020 - The Watness 2 (450pt)

reversing a cellular automata puzzle in HyperCard

April 19, 2020
rev HyperCard

The Watness 2 (450pt)

Rev

Story

You think you’ve found everything in the back of the library, so you head back to the front, and find yourself in a section far more traditional than the one in which you started. You’re not really sure where to begin, so you just pull a random book off the shelf to see if there’s any useful information inside.

Flipping to the first page, you’re not greeted with words, but what you can only describe as a window to another location entirely. It looks like some kind of garden? You’re not completely certain, but for some reason you feel compelled to place your palm to the image.

At one moment, you’re in the library, holding a book. The next, you’re in a dark tunnel, with no books in sight. Confused, you wander towards the light, only to find the garden you were looking at only seconds ago.

A few steps away, you see an older man dressed in plain robes running his finger against a panel. He seems troubled by something. Curious, you approach him.

“Hi there”, you say.

“Hello my friend”, he responds. He doesn’t look at you; he’s completely engrossed in what he’s doing.

The card in front of him has a grid on it, and he seems to be drawing paths along the edges to connect certain points. It looks like he’s almost done, but then he shakes his head and backtracks almost all the way to the start. There must be some rules you’re not getting here. But, you feel certain that if you can figure those rules out, a flag will be yours.

Files:

Extra:

Overview:

Last year at PlaidCTF 2019, there was a challenge called The .Wat ness which was a grid-puzzle game inspired by the game The Witness written in WebAssembly.

So going into this challenge, I expected some sort of similar puzzle.

We are given a .rc1 file which doesn’t seem too familiar. After some inspection with my teammates we figured out it was a HyperCard stack. I had never encountered this technology before (mainly because it is super old) but it basically consists of a bunch of cards that can handle user interactions, transition to other cards and run scripts. It even has support for extensions in the form of native executables (that will be important later).

The first step is to get it running:

Step 0: Getting it running

I’m currently running macOS 10.15 but we need to go back to Mac OS 9 to get this to run. After some Googling, I found this really helpful post by James Friend that includes a download link to a prebuilt SheepShaver emulator.

Once we get that running, we can view the HyperCard stack in all it’s glory:

intro

Step 1: Exploration

I was surprised to find that we can actually move around! We are presented with two simple tutorial puzzles (from the real Witness game):

puzzle

Then we are released into the courtyard where we find three much harder looking puzzles of this format:

big

Step 2: Source

So how does the program actually check our solution? I found a program called HyperCardPreview that (while not actually able to preview the cards), it was able to dump the scripts for each card.

If we look at the card script of one of the larger puzzles, we see these lines:

...
put 1 into puzzle_id
put -1 into cursor_x
put 0 into cursor_y
put "" into path
put "rbrr rgb rb  r brgrbrgb  grrgbbg grg bgrg  bbgrbg" into constraints
...

If we examine the gridpoints, they just manage the current coordinate:

on mouseUp
  global active_2_3,cursor_x,cursor_y
  put cursor_x into prev_x
  put cursor_y into prev_y
  put abs(cursor_x-2) into dx
  put abs(cursor_y-3) into dy
  if (active_2_3 = "") and ((dx = 1 and dy = 0) or (dx = 0 and dy = 1)) then
    put true into active_2_3
    send "updateState 2,3" to this cd
    addcolor colorButton, cd, 172, "65535,65535,30000"
  end if
end mouseUp

However, the final point in the bottom right has a different script:

on mouseUp
  global cursor_x, cursor_y
  if (cursor_x = 7) and (cursor_y = 7) then
    addcolor colorButton, cd, 40, "65535,65535,30000"
    send "checkYoSelf" to button path_extension
    send "checkSolution" to this cd
  end if
end mouseUp

Specifically we see it call checkSolution on the card context. That function is defined in the main script scope:

on checkSolution
global puzzle_id,path,constraints,flag_1,flag_2,flag_3
watnesssolver constraints,path
put the result into success
if success = "true" then
if puzzle_id = 1 then
decoder path,"clrtffxpry"
put the result into flag_1
end if
if puzzle_id = 2 then
decoder path,"nyghq7xksg"
put the result into flag_2
end if
if puzzle_id = 3 then
decoder path,"ppyyvn}1{7"
put the result into flag_3
end if
else
send opencard to this cd
end if
end checkSolution

It seems to call watnesssolver and then possibly decode, however neither of those seem to be defined anywhere.

After some more investigating, it turns out those are both XCMD native modules written in 68k assembly. I used HyperCardPreview to dump the binaries and started reversing in Binary Ninja.

Step 3: Binaries

Luckily it seems like the binaries were compiled with symbols as each function is followed by an ascii string that seems to correspond to its function:

bin

After a few solid hours of reversing (and a bit of guessing the XCMD translation api), I figured out that the solver is actually simulating a 4 color cellular automota (Red, Green, Blue, Empty).

After each path step in the grid, the cellular automata progresses. The only constraint is that we must always be touching a red square.

I would normally share my Binary Ninja database file but I accidentally deleted it :(

Step 4: Emulation

Here are the cellular automata update rules encoded in python:

def choose_empty(blue, green, red):
    if blue == 0 and green == 0: return 0
    else:
        if blue < green: return 2
        else: return 3

def choose_red(blue, green, red):
    if red != 2 and red != 3: return 0
    else:
        if blue == 0 or green == 0: return 0
        else: return 1

def choose_green(blue, green, red):
    if red > 4: return 0
    else:
        if blue > 4: return 3
        else:
            if red == 2 or red == 3: return 1
            else: return 2

def choose_blue(blue, green, red):
    if red > 4: return 0
    else:
        if green > 4: return 2
        else:
            if red == 2 or red == 3: return 1
            else: return 3

At each timestep, a cell is updated based on its current color and number of colored neighbors. For example, a blue cell would call choose_blue and pass the number of blue neighbors, green neighbors and red neighbors to figure out its new color.

Here is an animation of all three levels:

level1 level2 level3

Step 5: Solution

To solve, we can use a simple depth first search on the automata states until we reach the end ensuring that each move touches a red square.

We end up with three unique solutions that we can enter in the game to reveal the flag:

flag

comments powered by Disqus