Starless-Rev-LaCTF26
INITIAL ANALYSIS
The challenge file included an ELF binary which accepted input via standard input (stdin). It was also hosted as a remote netcat service, meaning the binary couldn’t be patched directly to get the flag.
I performed some initial triage by running strings on the binary and conducting some basic tests. Finally, I opened it in IDA, my trusty tool, and started looking.
After a bit of cleaning, we can see that the start function registers the address of a function I named WRONG to execute when SIGSEGV (signal 11) is triggered.
11 SIGSEGV Dump Invalid memory reference
This is conveniently an invalid memory reference.
Lastly, as expected, the Wrong function just prints a message and exits.
SEARCH FUNCTION
The decompilation of the search function is really messed up, so we stick to disassembly.
As I analyzed the challenge, checks were performed on one of 4 inputs: ‘W’, ‘A’, ‘S’, ‘D’, and occasionally ‘F’. The program processes input byte-by-byte and transitions to the next node.
I tried visualizing the entire search program as a graph structure where each node has edges corresponding to the input provided. There were 4 broad types of input outcomes that I found:
- WRONG (sigaction)
- CORRECT (Next STATE)
- OPERATION (MOV OPERATION in certain Functions)
- REPEAT (loops back to some state)
Each node had one of these operations depending on the input. As you can see from the first node, if we entered ’d’ we went to the next node. ‘a’ and ‘w’ led to jumps which would cause the sigaction, while ’s’ performed some mov operations (we will talk about them later) and sent us to node 5.
‘F’ is our final function. It was the one we had to trigger to win, but not directly, as you will see in my screenshots.
1.
Each function points to the next function but contains:
xor eax, eax
mov [rax], al
This instruction sequence leads to a segfault and ultimately the Wrong function.
We have to avoid these instructions. Since we can’t patch the binary, the author has provided us with small pieces of code reachable between functions that modify the memory to bypass this check.
mov eax, dword ptr cs:n8962097_0
cmp al, 90h
jnz short loc_67681075
mov dword ptr cs:n8962097_0, 88C031h
mov dword ptr cs:correct3, eax
loc_67681075:
jmp loc_6768900C
Snippets like these are distributed throughout the code, accessible from various nodes. They patch certain functions of the code, which are then checked by other functions. This mechanism allows us to patch the 6 correct functions and eventually call the final correct function to reach CORRECTPRINT.
From here, all we had to do was model the state machine and solve it.
EXTRACT NODES
I exported the cleaned disassembly from IDA and used a parser to extract the graph nodes (DISASSEMBLY).
Code to extract from disassembly: (dump.py)
Here is the clean graph for Visualization: (GRAPH)
Compressed version: 
The extracted graph appeared to have all paths defined, except for certain DWORDs that were meant to be changed during execution.
So, I extracted those address values separately using IDA.
The extracted nodes are saved into this file: (Tile_init).
Finally, now that we have the graph and the list of addresses we need to visit to apply all patches, we can proceed with a BFS search to find the solution.
BFS SEARCH
Finally, we have all the pieces to perform the BFS search and find the correct input sequence that will modify the necessary instructions (replacing them with NOPs) to ensure safe execution.
import json
import os
import re
from collections import deque
from dataclasses import dataclass
from typing import Dict, Iterable, List, Optional, Tuple
@dataclass(frozen=True)
class Move:
node: int
key: str
case: int
src: Optional[int]
dst: Optional[int]
nxt: int
def load_tile_init(path: str) -> Dict[int, int]:
with open(path) as f:
raw = json.load(f)
# keys are strings in json
out: Dict[int, int] = {}
for k, v in raw.items():
out[int(k, 0)] = int(v, 0) if isinstance(v, str) else int(v)
return out
def bfs_solve(nodes: List[int], moves: List[Move], tile_init: Dict[int, int]) -> Optional[str]:
# Identify target dword for "safe" (NOP4) from correct4.
correct2 = 0x67692000
correct3 = 0x67691000
correct4 = 0x6768A000
correct5 = 0x67682000
correct6 = 0x6767A000
required = [correct6, correct5, correct4, correct3, correct2]
missing = [a for a in required if a not in tile_init]
if missing:
raise SystemExit(f"tile_init missing required addresses: {[hex(a) for a in missing]}")
nop_dword = tile_init[correct4]
# Build address universe from all src/dst plus required.
addr_set = set(required)
for m in moves:
if m.src is not None:
addr_set.add(m.src)
if m.dst is not None:
addr_set.add(m.dst)
addrs = sorted(addr_set)
addr_index = {a: i for i, a in enumerate(addrs)}
if len(addrs) > 60:
raise SystemExit(f"Too many addresses to bitmask-pack: {len(addrs)}")
start_mask = 0
for a in addrs:
if tile_init.get(a) == nop_dword:
start_mask |= 1 << addr_index[a]
if start_mask == 0:
raise SystemExit("No initial NOP tiles found; tile_init may be incomplete")
goal_mask = 0
for a in (correct6, correct5, correct4, correct3, correct2):
goal_mask |= 1 << addr_index[a]
nop_count = start_mask.bit_count()
if goal_mask.bit_count() != nop_count:
raise SystemExit("Goal NOP count differs from initial NOP count")
# Node packing
node_list = sorted(set(nodes))
node_index = {a: i for i, a in enumerate(node_list)}
idx_node = {i: a for a, i in node_index.items()}
def pack(node_addr: int, mask: int) -> int:
return (node_index[node_addr] << 60) | mask
def unpack(state: int) -> Tuple[int, int]:
node_i = state >> 60
mask = state & ((1 << 60) - 1)
return idx_node[node_i], mask
per_node: Dict[int, List[Tuple[int, int, int, str]]] = {}
rev_node: Dict[int, List[Tuple[int, int, int, str]]] = {}
for m in moves:
if m.nxt not in node_index:
continue
assert m.src is not None and m.dst is not None
src_i = addr_index[m.src]
dst_i = addr_index[m.dst]
per_node.setdefault(m.node, []).append((src_i, dst_i, m.nxt, m.key))
rev_node.setdefault(m.nxt, []).append((src_i, dst_i, m.node, m.key))
start_node = 0x6767900C
if start_node not in per_node:
raise SystemExit("Did not parse start node 0x6767900C")
# Bidirectional BFS
start_state = pack(start_node, start_mask)
f_front = deque([start_state])
f_prev: Dict[int, int] = {start_state: 0}
f_key: Dict[int, str] = {}
# Backward frontier starts from *all* nodes with goal_mask (since you can press 'f' anywhere)
b_front = deque()
b_next: Dict[int, int] = {}
b_key: Dict[int, str] = {}
b_seen: Dict[int, int] = {}
for n in node_list:
st = pack(n, goal_mask)
b_front.append(st)
b_seen[st] = 0
def reconstruct(meet: int) -> str:
# forward: meet -> start
left: List[str] = []
cur = meet
while cur != start_state:
k = f_key[cur]
left.append(k)
cur = f_prev[cur]
left.reverse()
# backward: meet -> some goal
right: List[str] = []
cur = meet
while cur in b_next:
right.append(b_key[cur])
cur = b_next[cur]
return "".join(left + right) + "f"
# Expand smaller frontier each iteration
max_total_seen = 5_000_000
while f_front and b_front:
if len(f_prev) + len(b_seen) > max_total_seen:
break
if len(f_front) <= len(b_front):
# forward step
for _ in range(len(f_front)):
st = f_front.popleft()
node, mask = unpack(st)
if st in b_seen:
return reconstruct(st)
for src_i, dst_i, nxt, key in per_node.get(node, []):
new_mask = mask
src_bit = 1 << src_i
dst_bit = 1 << dst_i
if mask & src_bit:
if mask & dst_bit:
continue
new_mask = (mask & ~src_bit) | dst_bit
if new_mask.bit_count() != nop_count:
continue
nst = pack(nxt, new_mask)
if nst in f_prev:
continue
f_prev[nst] = st
f_key[nst] = key
f_front.append(nst)
else:
# backward step: generate predecessors
for _ in range(len(b_front)):
st = b_front.popleft()
node, mask = unpack(st)
if st in f_prev:
return reconstruct(st)
for src_i, dst_i, prev_node, key in rev_node.get(node, []):
src_bit = 1 << src_i
dst_bit = 1 << dst_i
# Case 1: forward move did NOT trigger (src was not empty), mask unchanged.
if not (mask & src_bit):
pst = pack(prev_node, mask)
if pst not in b_seen:
b_seen[pst] = 0
b_next[pst] = st
b_key[pst] = key
b_front.append(pst)
# Case 2: forward move triggered (src empty -> dst empty), so current mask has dst but not src.
if (mask & dst_bit) and not (mask & src_bit):
pmask = (mask & ~dst_bit) | src_bit
if pmask.bit_count() != nop_count:
continue
pst = pack(prev_node, pmask)
if pst not in b_seen:
b_seen[pst] = 0
b_next[pst] = st
b_key[pst] = key
b_front.append(pst)
return None
TILE_INIT_PATH = "tile_init.json"
GRAPH_OUT_PATH = "graph_resolved.json"
with open(GRAPH_OUT_PATH, "r") as f:
loaded_graph = json.load(f)
moves = [Move(**m) for m in loaded_graph["moves"]]
nodes = loaded_graph["nodes"]
tile_init = load_tile_init(TILE_INIT_PATH)
sol = bfs_solve(nodes, moves, tile_init)
if sol is None:
raise SystemExit("No solution found under current constraints")
print(sol)
When we run the script, we get the input sequence:
sddddswaasdwaaasdssawwdwddsawasassdddwsddwasaaaawwdwdddsawaasassdddwwdwasssaaawwdwwassdddssddwasaaawwddwdsaaawdasssddwsddwawaawasdddssawdwaaddwaaf
FINAL FLAG
lactf{starless_c_more_like_starless_0xcc}