ACS 2023: Maze

let's play a maze game

TL;DR

Simple maze game that can be beaten repeatedly by manipulating game logic to either move through walls or trick the game into thinking we have reached the destination coordinate.

Challenge Overview

This is a maze mini-game that challenges the player to solve it 111 times to receive the flag. Beating it manually is obviously time-consuming and not feasible during the CTF.

Solution 1: Patching Player Movement

Within the game logic, there are 3 large switch cases that are easily identifiable under Graph View. The 3rd and last switch statement controls player's movement by reading neighbouring elements of the maze layout. For example, when attempting to move in any direction, it will determine whether there is a wall boundary blocking it or an actual traversable path.

After some trial and error, we realized that it is possible to apply a Never Branch patch on the jne instruction for all four directions to allow free roam and movement through walls.

Now that there are no restrictions on player movement, we can play the game 111 times to get the flag, but this will take a long time (~10 minutes).

Be careful not to input too many keystrokes or you might over-click the message prompt and miss the flag. (I made this rookie mistake during the CTF and didn't manage to solve it 😢)

Flag: ACS{3e88fc35ac5b6011b6e7e32afd9552666db7bb21d30e83859665ea5e2cae99bc_I7s_funny_M@ze_Gam3!_C0n9r@tu1ation$_On_C13ar!}

Solution 2: Patching Coordinate Checks

Taking a further look at how the game decides to end a round, we observed that there are 2 possible paths that loop around wgetch - a function to receive button presses from the user. We came to a conclusion that the game would keep calling wgetch as long as our player location is not on the END pixel.

With that in mind, we can apply an Invert Patch on both je instruction, so that we can proceed to the next round without moving our player at all (essentially without playing the game!). This is possible because our starting position (X: 1, Y:1) will never be on the END pixel.

After 110 rounds, a stack trace was thrown, indicating that the flag array wasn't decoded properly despite us beating the game. This is perhaps due to certain conditions that weren't met.

Taking a wider look, we now understand that the flag is decoded character-by-character in the following order:

Finish Maze -> Prints SUCCESS -> Decode 1 Character -> Prints NEXT STAGE -> Generate New Maze

Taking a closer look at what the program is doing after printing the SUCCESS banner, we realized it is once again checking our player coordinates for a second time. Just like before, apply an Invert Patch on 3 of the jump statements and it should now bypass all the checks.

Finally, let the game run for 111 rounds and the flag will appear at the end. In conclusion, we applied 5 patches that alter the game logic to decode the flag without actually beating the game.

Flag: ACS{3e88fc35ac5b6011b6e7e32afd9552666db7bb21d30e83859665ea5e2cae99bc_I7s_funny_M@ze_Gam3!_C0n9r@tu1ation$_On_C13ar!}

Solution 3: Decode Values Manually

The encrypted flag is stored in DAT_001477a8. This allows us to decode it manually by replicating the bitwise and arithmetic operations.

After back-and-forth trial & error with some missing values, we managed to port the decompiled code from Ghidra over to Python:

flag = [
    0xd2ec76f5, 0x64b5d293, 0x8ed09885, 0x5ac2794d,
    0xc036ef85, 0x1664996d, 0xafd39aa9, 0xb4397299,
    0xadb89956, 0x458b73e4, 0xd68d2106, 0x675f77d6,
    0xeb109944, 0xd3739995, 0x0cc69b06, 0x9ab79c27,
    0x28887257, 0x5c687ae5, 0xe98f211a, 0xb7d57289,
    0x6d20792d, 0xc28c9bd3, 0x816872b0, 0xdf717054,
    0x04df73fd, 0x251a71fd, 0x32069bd9, 0xe6602776,
    0xbaf370a9, 0x22a771e3, 0x87d59ae6, 0x955a9935,
    0x31529b75, 0xa77e98f8, 0x2c689c35, 0xd16a7018,
    0x1dbe99b1, 0xc12824cd, 0xe882ef76, 0xeaa6980d,
    0xbd1a9c73, 0x4d6e7d14, 0xde669848, 0x10ba71c5,
    0x0dc1989e, 0x9b1e9af8, 0xb08b9cf1, 0xbf58711c,
    0xbc159c03, 0x93189b95, 0xca10ef3d, 0xb5db70b6,
    0x8a0b9a3a, 0x1ff59b48, 0x5781983e, 0xa9f2990e,
    0x5bc7e092, 0xb96071a9, 0xc34879a8, 0x116d9bb2,
    0x80589924, 0xe1d87432, 0x9c439aaa, 0x0b51712e,
    0x63b6779a, 0x24457192, 0x929e72f3, 0x85b871a2,
    0x8ff09817, 0xe2e977da, 0xbb4772f2, 0x60327aca,
    0xd5caef17, 0xd0db2396, 0x2e159c64, 0xb3c59a0c,
    0xcf44ef9b, 0x977b7020, 0x215972db, 0x1e1f9b39,
    0x268499fc, 0x3e327135, 0xec77703e, 0x19147213,
    0xc4e9ef38, 0xcbbe26d7, 0x4ce4e0cf, 0x474777a6,
    0xd46bd07e, 0xdd8d7a2c, 0xe52cef4e, 0xab2772ae,
    0x2a219851, 0x5899770d, 0x205d9b2d, 0xa3f89b51,
    0xc9507c1c, 0x02829ce7, 0x03049c0b, 0x88e8701b,
    0xb65b9a2a, 0xeee5d047, 0xcefa724e, 0x488f77e4,
    0xd9459c93, 0x94fa72b3, 0xc64d7ab8, 0x38dc99d1,
    0x89c171b0, 0x18017310, 0x869b99ea
]

output = [0x90] * 111
for i in range(111):
    # bVar23 = (byte)uVar16 >> 1;
    # bVar19 = (byte)(uVar16 >> 2);
    # uVar20 = (uVar12 & 0xff) + ((uVar12 >> (bVar19 & 0x1f) & 0xff) << (-bVar19 & 0x1f)) + ((uVar12 >> (bVar23 & 0x1f) & 0xffff) << (bVar19 & 0x1f));
    # uVar12 = (uVar20 & 0xffff) >> (bVar23 & 0x1f);
    # bVar19 = (byte)uVar12;
    # uVar20 = ((uVar20 >> 0x10) >> (bVar19 & 0x1f)) << (bVar19 & 0x1f);
    # puVar25 = (undefined *)(ulong)(uVar20 & 0x7f);
    # *(uint *)((long)local_130 + (long)puVar25 * 4) = uVar20 >> 7 & 0x7f;

    bVar23 = 32 >> 1
    bVar19 = 32 >> 2
    uVar20 = (flag[i] & 0xff) + ((flag[i] >> (bVar19 & 0x1f) & 0xff) << (-bVar19 & 0x1f)) + ((flag[i] >> (bVar23 & 0x1f) & 0xffff) << (bVar19 & 0x1f));
    uVar12 = (uVar20 & 0xffff) >> (bVar23 & 0x1f);
    bVar19 = uVar12;
    uVar20 = ((uVar20 >> 0x10) >> (bVar19 & 0x1f)) << (bVar19 & 0x1f);
    puVar25 = (uVar20 & 0x7f);
    output[puVar25] = uVar20 >> 7 & 0x7f;

print(b"ACS{" + bytes(output) + b"}")

Running the python script gives us the complete flag.

Flag: ACS{3e88fc35ac5b6011b6e7e32afd9552666db7bb21d30e83859665ea5e2cae99bc_I7s_funny_M@ze_Gam3!_C0n9r@tu1ation$_On_C13ar!}

Solution 4: Dynamic Coordinates Injection

This method is similar to Solution 2, which involves tricking the program into thinking we have reached the END coordinates. (Credits to Team Trailblazers for this neat trick)

To achieve this, we will inject the END coordinates (X: 1F, Y: 1F) into the relevant registers just before the comparison is made at this specific address.

Doing this manually by hand:

To automate the entire process with GDB:

import os
import sys
import time

### Run GDB Script
# gdb ./maze
# source gdb.py

### Run GDB Commands Manually
# r
# CTRL+C
# breakrva 0xabfc
# r <<< $(python -c 'print("A")')

# loop:
# set $rsi=0x1f
# set $rdx=0x1f
# c

def setup():
    gdb.execute("set pagination off")
    gdb.execute("set print pretty")
    gdb.execute('set logging enabled on')
    print('[+] Setup Completed!')
    gdb.execute("r&")           # run in background
    time.sleep(1)               # 
    gdb.execute("interrupt")    # CTRL+C SIGINT

def stop_handler(event):
    gdb.execute("set $rsi=0x1f")
    gdb.execute("set $rdx=0x1f")
    gdb.execute("c")

def set_breakpoints():
    try:
        gdb.execute("breakrva 0xabfc")
    except:
        print('Error inserting breakpoint')
    print('[+] Breakpoint Set Successfully!')

def register_stop_handler():
    gdb.events.stop.connect(stop_handler)
    print('[+] Stop Handler Registered!')

def run():
    gdb.execute("r <<< $(python -c 'print(\"A\")')")

def main():
    setup()
    set_breakpoints()
    register_stop_handler()
    run()

if __name__ == "__main__":
        main()

Flag: ACS{3e88fc35ac5b6011b6e7e32afd9552666db7bb21d30e83859665ea5e2cae99bc_I7s_funny_M@ze_Gam3!_C0n9r@tu1ation$_On_C13ar!}