---
description: let's play a maze game
---

# ACS 2023: Maze

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

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2Fb0Rii35aBcXZBC5spOib%2Fimage.png?alt=media&#x26;token=e63cf218-3762-4b4b-917f-eda32e266178" alt=""><figcaption></figcaption></figure>

## 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.&#x20;

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2Fc2wybet5BAMYQWr3W6rB%2Fimage.png?alt=media&#x26;token=ea6f6f78-dcce-418a-b003-e67f36c563e8" alt=""><figcaption></figcaption></figure>

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.

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FRDMnOU2y3bWZmUbn0ut2%2Fimage.png?alt=media&#x26;token=703490d6-d1c9-4834-a77f-2a3ed06db54b" alt=""><figcaption></figcaption></figure>

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

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FAXkcGfhJvceLMiiEZDr4%2FAnimation.gif?alt=media&#x26;token=69ea8cbf-44cd-49a5-b5b6-98adc498188e" alt=""><figcaption></figcaption></figure>

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 :cry:)

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2Ftosvf1pFXpcChG63KAnm%2F2023-11-29%2016_32_50-Window.png?alt=media&#x26;token=1d1f0a3a-9208-49ad-a8ad-ff2c510d223d" alt=""><figcaption></figcaption></figure>

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

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2Fz73u79bFzO2irJ9hz5ss%2Fimage.png?alt=media&#x26;token=5dd46337-754b-4401-adbd-4d75e78a3285" alt=""><figcaption></figcaption></figure>

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.

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FjbU8SxTtCngucJzxq5Cb%2FAnimation.gif?alt=media&#x26;token=9cedddc4-bcca-4349-ad4c-a6aa177d6f04" alt=""><figcaption></figcaption></figure>

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.

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FVWHPUyWLCCPv0nmrDYh6%2Fimage.png?alt=media&#x26;token=35da1b24-1932-4ffd-96bf-c279354d3afc" alt=""><figcaption></figcaption></figure>

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**

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FmTHnnKwAJApj4RN5kmUz%2Fimage.png?alt=media&#x26;token=e1050261-4b0b-45d9-94ae-4bc33653a8a8" alt=""><figcaption></figcaption></figure>

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.

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FcWNUH4QLAoTDuAZhZlsO%2Fimage.png?alt=media&#x26;token=fcfb2b00-32ff-430e-aba3-0dfb41cac5d3" alt=""><figcaption></figcaption></figure>

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.

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2Ftosvf1pFXpcChG63KAnm%2F2023-11-29%2016_32_50-Window.png?alt=media&#x26;token=1d1f0a3a-9208-49ad-a8ad-ff2c510d223d" alt=""><figcaption></figcaption></figure>

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

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FBE3EpPRhfAdtFx0ixUaM%2Fimage.png?alt=media&#x26;token=05d26690-0935-4b79-a3f3-51d3f8e863b3" alt=""><figcaption></figcaption></figure>

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

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

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FqHbIjbCnQYhRPAxupKy5%2Fimage.png?alt=media&#x26;token=265ac7a9-08e7-4163-b491-6cdc0b9effcf" alt=""><figcaption></figcaption></figure>

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

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FhMY30uD1uJW3HQ8nf2rJ%2Fimage.png?alt=media&#x26;token=4773ad42-45bc-42af-a1ae-87de823e8b08" alt=""><figcaption></figcaption></figure>

Doing this manually by hand:

<figure><img src="https://80158427-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FkoydBBkDRRSxCLl1Wpgr%2Fuploads%2FQfqrgz5Aj1LaEXf63UJG%2FAnimation.gif?alt=media&#x26;token=6e4c6bf6-20bc-4f02-933b-ba94d8cffc7d" alt=""><figcaption></figcaption></figure>

To automate the entire process with GDB:

```python
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!}
