Highway

Platform: spbctf | Category: Reversing | Type: Challenge | Difficulty: Easy | OS: Linux | Author: XESXOR | Date: 2026-07-02 | Status: Solved Techniques: base64_index_reversal, control_flow_recovery_from_trace, instruction_trace_analysis, loop_iteration_counting

Summary

Task: recover a flag passed as argv[1] from a captured instruction trace of main in an i386 ELF that produces no output. Solution: disassemble main to find a nested loop that finds each input char's base64-alphabet index, then count inner-loop iterations per character in the trace to reconstruct each index and rebuild the flag.

Highway — spbctf

Description

Мы сняли трассу функции main этого бинаря. Вроде, этого достаточно чтобы получить флаг, который был передан ему аргументом.

English summary: We are given an i386 ELF binary and a plain-text instruction trace of its main function (a list of executed instruction addresses). The binary takes the flag as its command-line argument argv[1] and produces no visible output. The goal is to recover that argument from the trace alone.

Provided files:

• highway_wow.elf — ELF 32-bit LSB, Intel 80386, dynamically linked, not stripped.
• highway_itrace.out — instruction trace of main, 13203 lines, each line one executed instruction address (e.g. 0x8048426). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Recon

 bash read-only • copy allowed Copy
file highway_wow.elf
# ELF 32-bit LSB executable, Intel 80386, dynamically linked, not stripped

head highway_itrace.out
# 0x8048426
# 0x804842a
# ...
wc -l highway_itrace.out   # 13203

The trace is just a sequential list of the addresses main executed. Since the binary prints nothing, the flag is never written anywhere — but the control flow recorded in the trace depends on the input, so the trace itself leaks the flag.

Disassembly analysis

objdump -d -M intel highway_wow.elf, structure of main (base ~0x8048426): ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

1. Requires argc > 1, otherwise puts("not enough args!") and exit.
2. Loop A (body at 0x8048475): copies argv[1] byte-by-byte into a buffer at 0x804a040; input length saved in [ebp-0x18]. Terminates on NUL (test dl,dl; jne 0x8048475).
3. Nested Loop B: outer index i in [ebp-0x10], inner index j in [ebp-0xc] from 0 to 0x40 (64). Inner body at 0x80484ba loads table[j] and compares it to input[i]. The table address is computed as lea ecx,[eax-0x1a40] with eax = 0x804a000 (via get_pc_thunk + add 0x1bc3) → table at 0x80485c0. On a match (cmp ecx,edx; jne 0x80484f4 not taken → falls through to 0x80484e0), it stores j into an output buffer at 0x804a140[i]. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

So for each input character the program finds its index in a 64-entry table.

The table

objdump -s highway_wow.elf at 0x80485c0 dumps the standard Base64 alphabet:

ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/

Loop B therefore computes the base64-alphabet index of every input character.

Key insight

The program yields no output, but the instruction trace encodes the argument:

• The number of Loop A body executions (0x8048475) equals the flag length: 21.
• For each character, the inner search loop body (0x80484ba) executes once per candidate index j. When the match is found, the jne at 0x80484de is not taken and control reaches 0x80484e0. Counting inner-body executions up to each match marker gives j = the base64 index of that character. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

So walking the trace, incrementing a counter on every 0x80484ba and reading it off at each 0x80484e0, reconstructs the base64 indices of all characters — and thus the flag.

Trace-based recovery

 python read-only • copy allowed Copy
#!/usr/bin/env python3
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'
lines = [l.strip() for l in open('highway_itrace.out') if l.strip()]

inner = '0x80484ba'   # each inner-loop iteration (candidate j)
match = '0x80484e0'   # jne not taken -> match found, j = current count - 1
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

result, count = [], 0
for l in lines:
    if l == inner:
        count += 1
    elif l == match:
        result.append(count - 1)
        count = 0

print('indices:', result)
print('flag:', ''.join(alpha[i] for i in result))

Output:

indices: [26, 39, 32, 43, 62, 28, 26, 39, 62, 29, 40, 62, 44, 40, 38, 30, 45, 33, 34, 39, 32]
flag: REDACTED

21 recovered indices, matching the Loop A count. The + characters are base64 index 62 and stand in for spaces — the phrase reads "angr can do something", a nod to the fact that a symbolic-execution engine (angr) could also have solved this from the binary/trace. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍