headofstate

Platform: CUSTOM | Category: Reversing | Type: Challenge | Difficulty: Easy | OS: N/A | **Author: XESXOR Techniques: bfs_accepting_path, dfa_graph_modeling, dynamic_execution_for_flag, elf_section_parsing, transition_table_extraction

Summary

Walkthrough of the CUSTOM Reversing headofstate. Task: 64-bit PIE ELF implementing a table-driven DFA; the right input string drives the machine from state 1 to accepting state 1337, after which it prints the flag. Solution: statically extract the 9

Description

Mr. Head of State, state your program:

English summary: a 64-bit PIE ELF headofstate.elf (x86-64, not stripped) reads a string with scanf. On the correct input it prints Congratulations, Mr. Head of State! You've lead your state to leetness and then calls obfuscated_print_the_flag, which prints the flag. The pun in the name — "Head of STATE" — is the hint: it is a finite STATE machine (DFA).

Analysis

Loading main in Ghidra reveals a classic table-driven DFA: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

• A transition table is copied from .rodata (vaddr 0x14c0) onto the stack with rep movsq of 0x78 qwords = 960 bytes. Each transition is a 9-byte struct:

   c read-only • copy allowed Copy
  struct transition {
      int  cur_state;   // @0
      char input_char;  // @4
      int  next_state;  // @5
  };

  960 / 9 ≈ 106 entries.
• A global ACTIVE_STATE (.bss) is initialized to 1.
• An outer loop runs up to 0x1f3 times; for each input character input[k] an inner loop scans all ~0x6b transitions. If transition.cur_state == ACTIVE_STATE && transition.input_char == input[k], then ACTIVE_STATE = transition.next_state.
• There are also epsilon transitions (input_char == 0) that lead to the dead state 0 — these must be ignored when searching for an accepting path.
• The accept check is ACTIVE_STATE == 0x539 (= 1337) → print congrats and call obfuscated_print_the_flag(). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

So the input is a string that drives the DFA from state 1 to accepting state 1337. Crucially, the flag is not the input path — it is whatever obfuscated_print_the_flag outputs. The right move is to find any accepting input, then run the binary so it prints the real flag, rather than reversing the obfuscation by hand.

Solution

1. Statically extract the transition table. Parse the ELF64 section headers to map vaddr 0x14c0 to a file offset, then unpack the 9-byte entries. Because the struct is {int; char; int} with no padding inside the 9 bytes, read cur (4 bytes), char (1 byte), next (4 bytes) sequentially per entry.
2. Build a graph: state -> [(char, next_state), ...], ignoring epsilon edges (char == 0) into the dead state 0.
3. BFS from state 1 to state 1337 to recover any accepting input.
4. Run the binary with that input under Docker (--platform linux/amd64 ubuntu:22.04 ./headofstate.elf); it prints the flag. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import struct, collections

DATA = open("headofstate.elf", "rb").read()

# --- minimal ELF64 section-header parse: map vaddr -> file offset ---
e_shoff   = struct.unpack_from("<Q", DATA, 0x28)[0]
e_shentsize = struct.unpack_from("<H", DATA, 0x3a)[0]
e_shnum     = struct.unpack_from("<H", DATA, 0x3c)[0]

def vaddr_to_off(vaddr):
    for i in range(e_shnum):
        base = e_shoff + i * e_shentsize
        sh_addr   = struct.unpack_from("<Q", DATA, base + 0x10)[0]
        sh_off    = struct.unpack_from("<Q", DATA, base + 0x18)[0]
        sh_size   = struct.unpack_from("<Q", DATA, base + 0x20)[0]
        if sh_addr <= vaddr < sh_addr + sh_size and sh_addr != 0:
            return sh_off + (vaddr - sh_addr)
    raise ValueError("vaddr not in any section")
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

TABLE_VADDR = 0x14c0
N = 0x6b                      # number of transitions to read
off = vaddr_to_off(TABLE_VADDR)

# --- unpack 9-byte transitions: cur(int) char(byte) next(int) ---
graph = collections.defaultdict(list)
for i in range(N):
    p = off + i * 9
    cur  = struct.unpack_from("<i", DATA, p)[0]
    ch   = DATA[p + 4]
    nxt  = struct.unpack_from("<i", DATA, p + 5)[0]
    if ch == 0:               # epsilon edge -> dead state, skip
        continue
    graph[cur].append((ch, nxt))

# --- BFS from state 1 to accepting state 1337 ---
START, ACCEPT = 1, 1337
q = collections.deque([(START, b"")])
seen = {START}
solution = None
while q:
    state, s = q.popleft()
    if state == ACCEPT:
        solution = s
        break
    for ch, nxt in graph.get(state, []):
        if nxt not in seen:
            seen.add(nxt)
            q.append((nxt, s + bytes([ch])))
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

print("accepting input:", solution.decode())
# -> hojyfgeufvoljemjrztzmxwqnl

Running the solver yields the accepting input:

hojyfgeufvoljemjrztzmxwqnl

(state trace: 1 6 7 8 5 4 11 12 15 13 19 16 18 24 22 23 26 27 25 101 106 110 115 118 114 103 1337)

Feed it to the binary (Docker is used so the x86-64 ELF runs on an arm64 host):

 bash read-only • copy allowed Copy
echo 'hojyfgeufvoljemjrztzmxwqnl' | \
  docker run --rm -i --platform linux/amd64 \
    -v "$PWD:/w" -w /w ubuntu:22.04 ./headofstate.elf

Output:

Mr. Head of State, state your program:
Congratulations, Mr. Head of State! You've lead your state to leetness
flag: REDACTED

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The flag reads as the pun "so is it hard to be a Head of State?". The server accepted the bare value (and the flag{...} wrapped form). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key Takeaways / Lessons

• Mastering bfs_accepting_path, dfa_graph_modeling, dynamic_execution_for_flag, elf_section_parsing, transition_table_extraction was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-06-15 • CUSTOM • headofstate • Difficulty: Easy