This challenge seemed simple (it was also tagged easy, but not many teams solved it): You have a “game” server you connect to and can move your character around. The game server then tells you whether you fell into a pit, smelled a flag character, were next to a pit or if you “caught” a flag character. All of the source code was available to download, including a docker file for launching your own instance. Additionally, you were provided with a “client”, that displayed graphically what you were experiencing in your terminal.

The client When standing close to a bit, you could feel a breeze: The client when close to a pit When falling into a pit, the following message appears and the program closes itself: Dying

To better visualize how the challenge worked, you can see an animation below. The wizard emoji is the “player” (i.e. us). Red are pits, white are fields with nothing (i.e. we can safely walk on them). At the beginning every character of the flag is nicely layed out on the map. However, as soon as we start moving, the characters also randomly move. Hence part of the difficulty of this challenge.

An Off by One Error⌗

Of course, solving this with the client would have been near impossible, so I started gutting the client (it is a single python file). My “new” version, did not have a fancy interface, in exchange it can automatically send commands to the server. However, here I made a major mistake: an off by one error. Unfortunately, I did not notice this mistake until after the CTF ended and so I was unable to finish the challenge in time. I had written the following function, for executing “one” iteration of the game loop (i.e. send one input and parse response):

# s is the socket, move is the move as a tuple, e.g. left is (1, 0)
def one_iter(s, move):
    mv_char = MOVE_LIST[move]
    again = True
    while again:
        data = recv(s)
        alive, again = parse_data(data, next_pos(move))
        if not alive:
            return False
    send(s, mv_char)
    current_pos = next_pos(move)
    return True

Clearly, this will falsely advance to the next position, if I step into a pit, since I do not wait for the response. The correct function looks as follows:

# s is the socket, move is the move as a tuple, e.g. left is (1, 0)
def one_iter(s, move):
    mv_char = MOVE_LIST[move]
    send(s, mv_char)
    again = True
    while again:
        data = recv(s)
        alive, again = parse_data(data, next_pos(move))
        if not alive:
            return False
    current_pos = next_pos(move)
    return True

Determining the Size of the Map⌗

The next thing we have to do, is determine the size of the map. This will make a few things easier. I also made the parse_data function save any information it receives about the map (i.e. did we die, then set next_pos to PIT, otherwise NOTHING). This is done, by writing into a global dictionary map_data what it found at position (x,y) (i.e. map_data[(x,y)] = PIT). A helper function map_pos(pos) will return the value at position pos if found in that dictionary, otherwise "".

To determine the size of the map, I wrote a very simple explore function (explore functions are functions I use to determine the next move to take):

def find_bounds():
    global current_pos
    right = (1, 0)
    down = (0, 1)
    n_pos = next_pos(down)
    nn_pos = add_pos(n_pos, right)
    if PIT in map_pos(nn_pos):
        nnn_pos = add_pos(next_pos(right), right)
        if PIT in map_pos(nnn_pos):
            return (0, -1)
        return right
    if PIT in map_pos(n_pos):
        return right
    return down

This rudimentary function just tries to go straight down. If it knows the next down is a pit, it will go right instead. If it knows that the next down then right is a pit, it will go left instead.

I let this run until I received iw (invalid move) from the server. This gave me, that the height of the map is 50. When I let it run against the width (i.e. just switching down and right in the above function), I got stuck at (42, 5). So I just guessed that the map must be squared and moved on.

Dumping the Whole Map⌗

Now I could dump the whole map. I did this by taking an A* path algorithm from the internet and iterating over all unknown fields on the map. Hence the explore function looks like this:

def find_next_unexplored():
    global map_data
    for y in range(50):
        for x in range(50):
            if (x, y) not in map_data:
                return (x, y)
    return None

def explore2():
    # next_explore is the next tile we want to explore
    global next_explore, current_pos
    if current_pos == next_explore:
        next_explore = find_next_unexplored()
    if next_explore is None:
        print("Nothing left to explore!")
        return (0, 0)
    path = make_path(next_explore) # uses A* from internet
    nxt = path[0]
    move = (nxt[0] - current_pos[0], nxt[1] - current_pos[1])
    return move

Letting this run for about 300 times (i.e. exploring until we fall into a pit), we can easily dump the whole map. It looks as follows (.: nothing, ##: pit):

Map Dump

Finding the Flag Length⌗

What does the map dump exactly do for us? Well firstly, we can now easily navigate the whole map without dying. Using A* we can always find a path to the tile we want to go to.

How do we actually get the flag now though? When looking through the source code, I saw that every character of the flag was placed on the map at the beginning of the game. So we just have to walk around the board and “catch” every character. However, it was not that easy, since the individual characters randomly moved around on the map. Hence, I first focused on finding the length of the flag.

To do this, I wrote an explore function, that chooses a random spot on the map and walks there. Once it reaches the spot it chooses a new random spot and so on. The parse_data function automatically adds any flag characters it finds to the global flag_chars array. Thus, I just had to hope my explore function would find all flag characters before the server timed out and then I could check the length of the array. Luckily the server will respond with an error Congrats, you caught the whole flag., so we know when we got every character. The explore function is:

my_rand = random.Random()

def new_location():
    global my_rand
    while True:
        rand_pos = my_rand.randint(2, 47), my_rand.randint(10, 40)
        if map_pos(rand_pos) != PIT:
            return rand_pos

def explore4():
    global exp_next_location, current_pos
    if exp_next_location == current_pos:
        exp_next_location = new_location()
    path = make_path(exp_next_location)
    nxt = path[0]
    move = (nxt[0] - current_pos[0], nxt[1] - current_pos[1])
    return move

And it worked! After letting it run, it “errored” out and I knew that the flag was 42 characters long.

Actually Getting the Flag⌗

To actually get the flag, I tried a lot of different methods. Trying to come up with a meaningful flag by hand (since I had all the characters). Just moving to the initial spot of that character and then moving around a bit till I caught a flag. Then tallying up how many of each character I found at this spot and then choose the most common one for that position in the flag string.

Both of these and others I tried didn’t really work out, so I took a look at the source code again. Then I realized that the random number generator was seeded with time.time(). This means, that I could predict where the flag characters would move! (This is also why I am using my own random object above. using random.randint would interfere with this.)

So I gutted the game.py file and picked out only the things necessary for simulating everything locally. I then set the flag to ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnop. This allows me to easily get an index from a flag char, without having to modify any code in flag_char.py. Next, I setup the following function (mostly copied from game_loop):

def tick_game(next_position):
    global updated_map, flag, cnt, player_pos
    player_pos = next_position
    check_catch() # check for flag catch
    cnt += 1
    if cnt % 2 == 0:
        move_flag()
    # build map with current flag positions
    updated_map = mapp.copy()
    for i in flag:
        updated_map[index(i.x, i.y)] = FLAG_CHAR

I ran this function, every time I received a response from the server. Now I was able to predict the positions of every flag character.

To now get the flag, I used the same explore method as above, for finding out how many characters are in the flag. However, I setup the parse_data function, to figure out the index of a flag character we hit according to the game server, by querying our “local” game:

# data is text from server, n_pos is new position if move is successful
def parse_data(data, n_pos):
    if data[0] == b"iw":
        # invalid move
    ...
    elif data[0] == b"f":
        # flag char
        remote_char = data[1].decode("utf8")
        # I named the file for simulating the local game testing
        local_char = testing.flag_char_for_pos(n_pos)
        idx = testing.flag_char_to_index(local_char)
        print(f"According to local game, position of {remote_char} is {idx}")
        update_flag(remote_char, idx)
        print(f"Currently recovered flag: {actual_flag}")
        flag_chars.append(remote_char)
    elif data[0] == b"i":
    ...

    return True, False

After fixing a few bugs with the implementation, I was finally able to read out the flag hxp{and_n0w_try_t0_c4tch_m3_w1th0ut_dy1ng}:

According to local game, position of } is 41
Currently recovered flag: Axp{and_n0w_trA_t0_c4tch_m3_w1thAut_dy1ng}
found flag char: 0
According to local game, position of 0 is 32
Currently recovered flag: Axp{and_n0w_trA_t0_c4tch_m3_w1th0ut_dy1ng}
found flag char: y
According to local game, position of y is 14
Currently recovered flag: Axp{and_n0w_try_t0_c4tch_m3_w1th0ut_dy1ng}
found flag char: h
According to local game, position of h is 0
Currently recovered flag: hxp{and_n0w_try_t0_c4tch_m3_w1th0ut_dy1ng}
Had an error:  [b'e', b'Congrats, you caught the whole flag.']
Died after 0 0
hxp{and_n0w_try_t0_c4tch_m3_w1th0ut_dy1ng}

Not sure what the flag is about though, I didn’t die a single time while reading out the flag ;). If you want to see the full source code of my exploit, see here: https://gist.github.com/galli-leo/51acf1d0e35e056c502e2cef84d9e61a.