Flash CTF – Final State

Overview

Flag: MetaCTF{st4t3s_4r3_jus7_gr4phs}

We get a stripped binary that reads a “token” and prints ACCESS GRANTED or ACCESS DENIED. No source code 🙁

$ ./final_state
Token: test
ACCESS DENIED
$ file final_state
final_state: ELF 64-bit LSB pie executable, x86-64, stripped

Load it in Ghidra. The binary is small, only really one interesting function. After stripping away the standard library setup, the main logic is roughly:

1. Calls an initialization function that populates a int[64][128] array (the transition table).
2. Reads input with fgets.
3. Loops through each character, looking up table[current_state][char] to get the next state.
4. After the loop, checks if the state equals a specific constant. If yes, “ACCESS GRANTED.”

This is a deterministic finite automaton (DFA), a sort of state machine! The transition table tells you: “if you’re in state X and you read character Y, move to state Z.” One specific sequence of characters leads to the accept state; presumably, that sequence is the flag.

The init function is a series of assignments like table[7][77] = 12 (77 is ASCII ‘M’). We can extract them all from Ghidra.

From there, it’s graph traversal. Each state is a node; each non-zero transition is an edge labeled with a character. Find the path from the start state (7) to the accept state (51).

from collections import deque

graph = {}  # built from the extracted transitions

queue = deque([(START, "")])
visited = {START}
while queue:
    state, path = queue.popleft()
    if state == ACCEPT:
        print(path)  # this is the flag
        break
    for ch, nxt in graph.get(state, {}).items():
        if nxt not in visited:
            visited.add(nxt)
            queue.append((nxt, path + ch))

BFS finds the unique path in milliseconds!

There’s a pattern to recognize: The binary has a 2D table, loops over input characters, uses the current state and character as indices, and compares the final state to a constant. That’s the textbook DFA implementation.

A DFA that accepts exactly one string is just a path graph. There’s no branching. Every state has at most one valid outgoing transition (everything else goes to the dead state). BFS is overkill, but it works on any DFA regardless of structure.

Solve

solve.py

#!/usr/bin/env python3
"""
BFS over the extracted DFA transition table to find the unique accepted string.
Run this from the dist/ directory alongside the binary.
"""
from collections import deque

# Transition table extracted from Ghidra (binary: final_state)
# Only non-zero (non-dead) transitions are listed.
# Format: (from_state, char, to_state)
TRANSITIONS = [
    ( 7, 'M', 12), (12, 'e',  3), ( 3, 't', 45), (45, 'a', 29),
    (29, 'C', 18), (18, 'T', 55), (55, 'F', 62), (62, '{',  8),
    ( 8, 's', 34), (34, 't', 17), (17, '4', 41), (41, 't',  2),
    ( 2, '3', 60), (60, 's', 25), (25, '_', 11), (11, '4', 47),
    (47, 'r',  5), ( 5, '3', 38), (38, '_', 20), (20, 'j', 56),
    (56, 'u',  9), ( 9, 's', 33), (33, '7', 16), (16, '_', 44),
    (44, 'g', 27), (27, 'r', 63), (63, '4', 13), (13, 'p', 48),
    (48, 'h',  6), ( 6, 's', 39), (39, '}', 51),
]

START  = 7
ACCEPT = 51

graph = {}
for (src, ch, dst) in TRANSITIONS:
    graph.setdefault(src, {})[ch] = dst

queue = deque([(START, "")])
visited = {START}

while queue:
    state, path = queue.popleft()
    if state == ACCEPT:
        print(path)
        break
    for ch, nxt in graph.get(state, {}).items():
        if nxt not in visited:
            visited.add(nxt)
            queue.append((nxt, path + ch))