Exploration

We are presented with a rather large binary called “bomberman” (around 210 MB) and a few assets. I started by firing up binary ninja and throwing the binary in there. This caused my fans to spin up into higher gear, as binja chugged through the 210 MB. Since disassembly output and cross reference are sometimes a bit messy during analysis i decided to also analyze the binary “dynamically”. I just ran it to see what it did. To my surprise it instantly crashed with an error indicating a missing GPU on stdout. However some interesting logging is also done to stdout:

2024-07-02T00:00:00.000000Z  INFO bevy_winit::system: Creating new window "App" (0v0)

Since i had taken an interest in the rust programming language, i immediately recognized the name bevy as a popular rust game engine. Rust reversing… this is gonna be fun.

However first i had to somehow run the binary without bevy complaining about a missing GPU. The issue was tied to the game being run in a virtual machine (VMWare Workstation Pro). It seems like the default VGA adapter is not compatible with bevy (at least that was suggested in some github issues mentioning this exact problem). After an hour of fruitless troubleshooting i opted to just set up a new Linux Mint VM in VirtualBox. The game ran without any issues.

So it is indeed a bomberman-like game. The first thing i noticed when running around was the horizontal line of bombs in the bottom and the vertical line directly in front of the player character (a dog, i assume).

Furthermore the stdout also gives a clue what our objective is:

Arrowkeys, space to place bombs (first column only)
I/O to zoom in and out
Goal: Explode the flag

While running around i also noticed that there were tower like structures scattered throughout the game world.

At this point i decided it would be beneficial to look at what binary ninja had accomplished in the time i was busy setting up a new VM. I was pleasantly surprised to see that the author had not stripped the debug information and thus function names were available! This helps a lot, especially when dealing with rust code.

My first naive approach was to patch out the restriction that a bomb can only be placed in the first column. Our goal is to explode the flag after all, and that would get the job done rather quickly. I did not take notes on the patch i did to achieve that, but since (in hindsight) this was not the correct solution, there is no necessity to show it. However to blow up the flag, one problem remains: Where is it?

Parsing the map

Due to the size of the binary, my conjecture was that the map is somehow stored inside of one of the data/resource sections. Searching the function names for bomberman:: filters out all framework functions from bevy and other packages and leaves us with jsut a few functions to analyze. The most interesting map related function seemed to be bomberman::map::setup::h7278b0151a8ac7b6.

Especially the load_cbor, as well as data_10d41d1 and 0xa560240 stuck out to me. For anyone not familiar with it, cbor stands for “Concise Binary Object Representation” and is basically a simple serialization format. The latter two, namely data_10d41d1 and 0xa560240 are the address of the cbor data and the lenght respectively. Now its just a matter of parsing the map data and looking for the (presumably unique) value that represents the flag.

Looking at the memory location, it seems like map structure also contains a “height” and “width” and the actual information on every map tile is in an array called “ground”.

To make this list parseable, i copied the whole array of length 0xa560240 to a separate file called “map.bin”. The “ground” field contains a byte array with different values, lets see if we can figure out which value corresponds to the flag.

from cbor2 import loads, dump, dumps

def read_map():
    f = open("map.bin","rb")

    buf = f.read()
    data = loads(buf)
    return data

if __name__ == "__main__":
    map_data = read_map()
    
    print(f"height: {map_data['map']['height']}")
    print(f"width: {map_data['map']['width']}")

    ground = map_data['map']['ground']
    frequency_count = [0]*6
    
    for i in range(len(ground)):
        frequency_count[ground[i]] += 1

        # this line uses knowledge obtained by the frequency count
        if ground[i] == 5:
            # 5 == flag
            print(f"flag_x: {i % map_data['map']['width']}")
            print(f"flag_y: {i // map_data['map']['width']}")

    for i in range(len(frequency_count)):
        print(f"{i}: {frequency_count[i]}")

This outputs:

height: 2919
width: 57057
flag_x: 57047
flag_y: 3
0: 563947
1: 6208
2: 2927
3: 165863941
4: 112359
5: 1

This provides us with several important bits of information. The height and widths of the map, as well as the value likely associated with the flag (“5” since there is only one instance of it). I went ahead an put also printed the location of the flag in the same script. Assuming the most bottom layer to be y = 0, the flag should be just to the right, all the way at the end. And indeed, after a solid minute of going left there it is.

So due to the previously mentioned modification that let me place bombs anywhere, i just put a bomb right next to the flag. This lead to the game closing immediately while printing “You win” to stdout. However there was no flag in sight, thus this approach did not seem to work.

A new plan

The cbor serialized data also contained all bomb locations in a different array accessible under map_data['bombs']. Playing around with that i realized that the vertical row of bombs at the start contained exactly 240 bombs. It dawned on me, that the whole playing field was likely a logical circuit with chains of bombs representing wires and convey inputs and outputs. So it was a reasonable assumption that the flag would be encoded into these input bombs in a way. Also dividing the 240 bombs by 8 yielded 30, which is a comfortable amount of characters for a flag.

So the challenge would be the following: Find out which input bombs need to be exploded/not exploded for the flag du be eventually blown up down the line.

In order to achieve this goal it is necessary to evaluate what logic is applied to the inputs. Remember the tower like structures mentioned above, lets take a closer look at them.

This cropped screenshot contains one pattern of bombs and blocks repeated vertically twice. This pattern contains two unknown blocks which the game calls “drywall” (same texture as the walls, but in a sand-like color). When a bomb hits this block, it blocks the explosions path but is destroyed in the process.

In conclusion, for this kind of pattern, both inputs i1 and i2 have to be activated (exploded) for the output o to be active once s is triggered. As a quick aside, s is triggered by the horizontal row of bombs at the bottom of the whole map. It can be seen in alls the screenshots above and ensures that every tower-like structure (i will call them “stages” from now on) is triggered well after one another, so the bombs acting as wires have enough time to propagate.

But in short, if both i1 and i2 are 1, then o is 1 aswell. If either i1 or i2 is 0, the output stays 0. This describes the thruth table for an AND gate. Thus i will call this an AND-pattern from now on.

Similarly the only other pattern can be examined.

This features a new kind of block which is called a “pillar” by the game. It lets the first explosion pass unhindered and then transforms into a wall, blocking any further explosions. This is effectively just a negation of the input (a NOT gate). However i will call it a XOR-gate throughout this writeup (and my code) for a reason that will become clear later on.

The solution

Now the the path to a solution is clear. Parse the whole map and all bombs, look for the two patterns and synthezise a row of equations to throw into z3 to solve them. But although the problem statement is fairly clear, this whole thing took me about 15 hours to implement due to multiple factors. The biggest factor was that i am a lousy programmer. I don’t write code, i reverse it.

That being said, my solution is quite convoluted and diving into every detail would bloat this writeup even more, thus i will just detail the steps i took to solve it and the general thinking behind it. In general i wanted to abstact all the bombs and patterns away to create the following representation for every pattern in the map.

Steps:

1. Parse the map into a 2D array. I wanted to index it like map[x][y]
2. Parse the bombs into a 2D array. Indexed with bombs[x][y]. If bombs[x][y] == 1, then a bomb is there
3. Generate an adjacency list for every bomb (other bombs in explosion distance). This step treats both drywall and pillars as impassable.
4. Find all instances of the patterns (XOR/AND) an mark the input and output bombs as “terminal” bombs. In this context “terminal” means, that those bombs terminate a path. Once the input of an AND-gate is reached, there is no need to trace the path further, as i know where the output is. Furthermore i marked the bomb at x = 57045, y = 3 as terminal aswell, since this is the “final” bomb before the flag. The patterns are named in order of their discovery with the naming conventions a_<id> and x_<id> for AND/XOR patterns respectively. The <id> is just an integer counted up for every distinct instance of a pattern found (e.g. x_0 for the first XOR pattern, x_1 for the second). Note that these IDs were not unique betweend patterns, so both x_0 and a_0 exist.
5. Enumerate over all output bombs of the patterns and walk the adjacency list to generate a path. The path is walked until all branches end in a terminal bomb (mostly inputs of subsequent AND/XOR patterns, or the one terminal bomb). This had to be done due to multiple 1-N connections present in the data.
6. Name the paths to be equal to the pattern instance name they originated from. For the reason, reconsider the image above, where the inputs of x_1 and x_0 are none other than the outputs of a_1 and a_0 respectively.
7. Save the information where the input originated from in meta-information about a pattern instance. For reference in the example shown above, the input of x_0 would be saved as a_0, thus the resulting equation for x_0 would be x_0 = NOT(a_0) or alternatively x_0 = a_0 ^ 1, as the truth table for NOT and XOR with 1 is the same. Thats why i named the patterns “XOR” previously. It seemed easier to generate equations with XOR rather than negation as the latter might be somewhat inintuitive to work with in python.
8. Generate all the equations and sort them by their corresponding pattern instances x coordinate. This is done so that the stages are defined “in order” which prevents variables from being used before they are defined. Or in simple terms for a_152 = a_76 & x_107 to be well defined, both a_76 and x_107 have to exist beforehand in order for python to solve it.

def func(i):
    x_0 = i[225] ^ 1
    x_1 = i[216] ^ 1
    x_2 = i[185] ^ 1
    # i cut the script here, because there are over 6000 equations here
    # these lines are just left to give an impression of how the function looked
    a_3101 = x_2925 & x_2926
    a_3102 = a_3100 & a_3101
    a_3103 = a_3099 & a_3102
    return a_3103

if __name__ == "__main__":

    s = Solver()
    solver_vals = [BitVec(f"x_{i}", 1) for i in range(0, 240)]

    s.add(func(solver_vals) == 1)


    if s.check() == sat:
        m = s.model()
        solution = sorted([(d, m[d]) for d in m], key=lambda x: int(str(x[0])[2:]))
        
        flag = ""
        binary_string = ""

        for p in solution:
            binary_string += hex(p[1].as_long())[2:]

        for i in range(len(binary_string)//8):
            flag += chr(int(binary_string[i*8:(i+1)*8][::-1],2))

        print(flag)

When run, this prints: CTF{NowWriteACPUInIt3727-5479}
Note that there is a bit of shuffling going on with the bits, in the resulting model. This is due to the fact, that i just numbered the input bombs from top to bottom. But after the model was solved it was just about dropping the output in cyberchef and playing around with it for a bit to see how it had to be done.

The whole python code of my solution will be uploaded to github in a few days.