Pathfinder

Challenge Type

Reverse Engineering - x86-64 ELF binary (dynamically linked, stripped)

Tools Used

• file, strings - initial recon
• radare2 - disassembly and static analysis
• Python 3 - maze decoding, BFS pathfinding, hash verification

Analysis

Initial Recon

$ file pathfinder
pathfinder: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked,
            interpreter /lib64/ld-linux-x86-64.so.2, stripped

Running the binary:

$ ./pathfinder
Are you a pathfinder?
[y/n]: y
Ok, tell me the best path: test
Better luck next time.

Program Flow (main @ 0x16d0)

1. Asks "Are you a pathfinder?" and reads y/n
2. If 'y', prompts for a path (up to 64 bytes)
3. Calls validate_path(input) at 0x1444
4. If valid, calls generate_flag(input, buf) at 0x1602 and prints the flag
5. Otherwise prints "Better luck next time."

Maze Initialization

The maze is a 10x10 grid stored at address 0x40a0, initialized before main runs by constructor function init1 at 0x11ee.

Each cell is XOR-decrypted from encoded data at 0x2020:

def key(i):
    return (((i << 5) - i + 0x11) ^ (i << 3) ^ 0xFFFFFFa5) & 0xFF

maze[i] = encoded[i] ^ key(i)

Cell values are direction bitmasks:

• Bit 0 (0x01): South-related passage
• Bit 1 (0x02): East-related passage
• Bit 2 (0x04): North-related passage
• Bit 3 (0x08): West-related passage

Direction Table (init2 @ 0x12ce)

Four valid direction characters are initialized in a lookup table at 0x4120:

Char	dx	dy	Valid
N	-1	0	Yes
S	+1	0	Yes
E	0	+1	Yes
W	0	-1	Yes
n,s,e,w	various	various	No (traps)

Lowercase directions are traps -- their "valid" byte is set to 0, causing immediate failure.

Path Validation (0x1444)

For each character in the path:

1. Look up direction entry (dx, dy, flags) from table
2. Compute XOR-based direction masks from character and flags
3. Calculate new position: (row + dx, col + dy)
4. Bounds check: both coordinates must be 0-9
5. Validate move using: (maze[current] & d4) | (maze[target] & d5) != 0
6. Update position

After processing all characters:

• Final position must be (9, 9)
• A custom hash of the path string must equal 0x86ba520c

Hash Function (0x126b)

Modified MurmurHash-style:

h = 0xDEADBEEF
for c in path:
    h ^= ord(c)
    h = rotate_left(h, 13)
    h = (h * 0x045d9f3b) & 0xFFFFFFFF
h ^= (h >> 16)
h = (h * 0x85ebca6b) & 0xFFFFFFFF
h ^= (h >> 13)

Decoded Maze

Row 0:   8  10  12   .   .   .   .   .   .   .
Row 1:   .   .   5   .   .   8  10  10  12   .
Row 2:   .   .   3   .   .   5   .   .   5   .
Row 3:   8  10  10  10  10   1   .   .   5   .
Row 4:   5   .   .   .   .   .   8  10   1   .
Row 5:   5   .  12  10  12   .   5   .   .   .
Row 6:   5   .   5   .   5   .   5   .   .   .
Row 7:   5   .   1   .   3  10   9   .   8  12
Row 8:   5   .   .   .   .   .   .   .   5   5
Row 9:   3  10  10  10  10  10  10  10   1   3

Visual (# = wall, . = passable):
  ..........
  ##.##....#
  ##.##.##.#
  ......##.#
  .#####...#
  .#...#.###
  .#.#.#.###
  .#.#...#..
  .#######..
  ..........

Solving

BFS from (0,0) to (9,9) respecting the directional bitmask rules finds the unique valid path:

EESSSWWSSSSSSEEEEEEEENNESS

This path's hash matches the target 0x86ba520c.

Flag Generation (0x1602)

The flag function applies Run-Length Encoding (RLE) to the path:

• EE → 2E, SSS → 3S, WW → 2W, SSSSSS → 6S
• EEEEEEEE → 8E, NN → 2N, E → E, SS → 2S

Note: The binary uses EHAX{...} prefix rather than the standard EH4X{...} format.