Labyrinth

Task description

Somewhere on this port a server is talking in a language no tool has ever heard of. It has no manual and no patience for strangers, but it does answer, and every answer tells you a little more. Listen closely, learn to speak its tongue, and find your way out of the labyrinth behind it. Not every door that glows is an exit.

• Category: misc (medium)

The service is a TLS-wrapped TCP port (ncat --ssl <host> 1337) that speaks an undocumented binary protocol. You have to reverse-engineer the protocol, pass a small transform challenge, then walk a randomised 5x5 maze to a sealed gate and give it the shortest route from the entrance.

TL;DR

1. Frames are LBY\x7f + type + flags + len + body; the type byte is the opcode.
2. 0x01 gets a nonce, 0x10 <nonce> gets a transform challenge, and 0x30 <answer> enters the maze.
3. The transform is “reverse the 4 bytes, XOR each with key K”. K is read off the example pairs the server shows.
4. 0x20 <dir><token> moves. Each room reply gives an open-door bitmask, a cell kind and the token for the next move.
5. Map the maze depth-first in one connection, stop when you step onto the gate, compute the shortest entrance-to-gate path with BFS, and send it to the gate as raw direction bytes with 0x30. The gate replies with the flag.

Frame format

The banner, captured raw, shows the framing straight away:

4c 42 59 7f 80 00 24 01 4c 41 42 59 52 49 4e 54 48 ...   LBY.....LABYRINTH speaks in frames. listen.

Offset	Size	Field
0	4	magic LBY\x7f
4	1	type, which is the opcode (server replies have the high bit set, e.g. 0x80 banner, 0x81/0x82 replies, 0xa0 room, 0xee error, 0xf0 flag)
5	1	flags (always 0x00)
6	1	len, the length of the body
7	len	body

Client frames use the same layout: the opcode goes in type and the argument is the raw body. A first plain-text hello\n gets the reply bad magic; frames start with my banner's first 4 bytes, which confirms the magic.

The frame I/O layer:

import socket, ssl

HOST = "labyrinth-30a5c06bb250.chall.hiddeninvestigations.net"
PORT = 1337
MAGIC = b"LBY\x7f"

def connect(timeout=15):
    ctx = ssl.create_default_context()
    ctx.check_hostname = False
    ctx.verify_mode = ssl.CERT_NONE
    raw = socket.create_connection((HOST, PORT), timeout=timeout)
    return ctx.wrap_socket(raw, server_hostname=HOST)

def recv_frame(s, timeout=4.0):
    s.settimeout(timeout)
    def readn(n):
        buf = b""
        while len(buf) < n:
            c = s.recv(n - len(buf))
            if not c: break
            buf += c
        return buf
    hdr = readn(7)
    if len(hdr) < 7:
        return None, hdr
    ln = hdr[6]
    body = readn(ln)
    return {"magic": hdr[0:4], "type": hdr[4], "flags": hdr[5], "len": ln,
            "body": body, "op": body[0] if body else None,
            "payload": body[1:] if body else b""}, hdr + body

def build(type_b, flags, body):
    return MAGIC + bytes([type_b & 0xff, flags & 0xff, len(body) & 0xff]) + body

def send_frame(s, type_b, flags, body):
    s.sendall(build(type_b, flags, body))

Making the protocol learnable

The server’s errors carry the whole manual, and they do not reset the session:

• A malformed or unknown opcode gets unknown opcode; known: 01 02 10 20 30 40 50 60, which lists the whole verb set.
• A valid opcode in the wrong state gets wrong move for this state: <what you should do next>. The session stays in the same state, so you can keep trying different opcodes on one connection. That is how each step was found.
• A correct opcode with a bad argument gets a length hint, e.g. PROBE wants exactly 8 bytes or MOVE wants dir(1) + token(2).

So each step was found by sending a candidate frame to every known opcode, keeping the one that did not return “wrong move”, and reading the error text for the argument format.

Handshake

Step	Send	Reply
1	0x01 (empty)	0x81: 8-byte nonce + PROBE the nonce
2	0x10 + nonce (8 bytes)	0x90: 28 bytes of data + ANSWER T(challenge)
3	0x30 + T(challenge) (4 bytes)	0xa0: entrance room + entrance. MOVE dir+token

Gotcha: the server says “PROBE”, but 0x02 is not the probe opcode; 0x02 is a status query that repeats the current instruction. 0x10 is the probe.

The transform challenge

The 47-byte 0x10 reply always ends in the fixed 19-byte text ANSWER T(challenge). The 28 bytes before it are seven 4-byte blocks: three input -> output example pairs, then one challenge block with no output. Example from one session:

00 00 00 00 -> 79 79 79 79
01 02 03 04 -> 7d 7a 7b 78
04 be fb 64 -> 1d 82 c7 7d
55 4e cc ef -> ?            (challenge)

01 02 03 04 XOR 79 = 78 7b 7a 7d, and reversed that is 7d 7a 7b 78. So:

T(in)[i] = in[3 - i] XOR K

How K is derived: the all-zero input pair gives K directly, since every output byte equals K. K changes every session. The solver doesn’t hard-code it: for each output position it searches for the (source index, XOR key) that fits all three pairs, so it recovers both the byte order and the key:

SUFFIX = b'ANSWER T(challenge)'

def parse_challenge(payload):
    if payload.endswith(SUFFIX):
        blob = payload[:-len(SUFFIX)]
    else:
        idx = payload.find(b'ANSWER')
        blob = payload[:idx] if idx != -1 else payload
    assert len(blob) % 4 == 0
    blocks = [blob[i:i+4] for i in range(0, len(blob), 4)]
    pairs = []
    i = 0
    while i + 1 < len(blocks):
        pairs.append((blocks[i], blocks[i+1]))
        i += 2
    challenge = blocks[-1] if len(blocks) % 2 == 1 else None
    return pairs, challenge

def derive_transform(pairs):
    n = 4
    perm = [None]*n
    key = [None]*n
    for i in range(n):
        for j in range(n):
            for k in range(256):
                ok = all(out[i] == (inp[j] ^ k) for inp, out in pairs)
                if ok:
                    perm[i] = j; key[i] = k
                    break
            if perm[i] is not None:
                break
    assert all(p is not None for p in perm), 'could not derive transform'
    return perm, key

def apply_transform(block, perm, key):
    return bytes(block[perm[i]] ^ key[i] for i in range(len(perm)))

def solve_answer(payload):
    pairs, challenge = parse_challenge(payload)
    perm, key = derive_transform(pairs)
    return apply_transform(challenge, perm, key), perm, key, pairs, challenge

Gotcha: strip the trailing text by its fixed length, not with find(b'ANSWER'). A challenge byte can be 0x41 (A), and searching for the text would then cut the binary part short.

Moving through the maze

Move: opcode 0x20, body = dir(1) + token(2), where dir is 0=N (y-1), 1=E (x+1), 2=S (y+1), 3=W (x-1).

Room reply (type 0xa0, or 0xa1 for the gate). The body is:

Byte	Field
0	x
1	y
2	open-door bitmask: bit d set means direction d is open
3	cell kind (see below)
4-5	token for the next move
6..	optional text

Token chaining: each move must carry the token from the most recent room reply. Possible results:

• Wall: wall. token unchanged. You stay put, the token stays valid, and nothing is lost.
• Good move: a new room with a fresh token.
• Old token reused (for example, the previous room’s token after you have already moved): stale token; you lost the thread (reset). The session drops back to the start (say HELLO).

Moves are reversible: going in the opposite direction steps back. Combined with the bitmask, this means you never need to bump into walls and can backtrack freely.

At first I read bytes 2-3 as a 16-bit “distance” value; it was really two separate bytes (doors and kind). A first greedy solver bounced between two rooms forever because it took the first open door, which was often the way back.

Cell kinds

Kind	Frame type	Text	Meaning
0	0xa0	none (the entrance has entrance. MOVE dir+token)	normal room
2	0xa0	a light!	glowing room, a trap. On entry the server sends an extra decoy-flag frame (hiCTF{not_the_exit}), which must be drained or every later reply is off by one
1	0xa1	a sealed gate. it asks how you came, by the shortest way	the real exit. Once inside, the only valid move is ANSWER with the shortest route from the entrance; you cannot walk back out

“Not every door that glows is an exit” refers to the light rooms.

Decoys

Item	Behaviour
hiCTF{not_the_exit}	Fake flag (type 0xf0). Sent by opcode 0x40 in any maze state and on entering a light room. The first byte h is the body’s first byte, so a naive “op + payload” split shows it as iCTF{...}
0x40	Fake flag, as above
0x50	debug build stripped. f47e8bb0e33b5470, a red herring that was not needed
0x60	warp needs a key you will never have, a fake shortcut

Navigation strategy

The maze is a 5x5 grid that is re-randomised for every session: entrance doors, walls, light rooms and the gate position all change. So it must be mapped and solved inside one connection, and nothing can be reused between connections.

The end-to-end solver does the handshake, DFS-maps the maze, BFS-routes the shortest path to the gate, and submits it:

import sys, os, time
from collections import deque

OPP = {0: 2, 2: 0, 1: 3, 3: 1}
DXY = {0: (0, -1), 1: (1, 0), 2: (0, 1), 3: (-1, 0)}

def room(fr):
    b = bytes([fr['op']]) + fr['payload']
    return {'x': b[0], 'y': b[1], 'doors': b[2], 'kind': b[3],
            'tok': b[4:6], 'text': b[6:], 'body': b, 'type': fr['type']}

# z = Sess() handles: connect with TLS, nonce, probe, transform answer, entrance
z = Sess()
cur = room(z.entrance)
start = (cur['x'], cur['y'])

def mv(d):
    global cur
    fr = z.cmd(0x20, bytes([d]) + cur['tok']); time.sleep(0.02)
    if fr is None or fr['type'] not in (0xa0, 0xa1):
        return False
    cur = room(fr)
    if cur['kind'] == 2:
        recv_frame(z.s, 2.0)   # drain the decoy flag frame from light rooms
    return True

cells = {}
def note():
    p = (cur['x'], cur['y'])
    if p not in cells:
        cells[p] = (cur['doors'], cur['kind'], cur['text'])
note()

# DFS exploration
path = []
gate = None
for step in range(500):
    pos = (cur['x'], cur['y'])
    if cur['kind'] == 1:
        gate = pos; break
    nxt = None
    for d in range(4):
        if cur['doors'] >> d & 1:
            np = (pos[0] + DXY[d][0], pos[1] + DXY[d][1])
            if np not in cells:
                nxt = d; break
    if nxt is None:
        if not path: break
        mv(OPP[path.pop()])       # backtrack
    else:
        mv(nxt); path.append(nxt) # forward
    note()

# BFS shortest path from entrance to gate
def bfs(src, dst):
    prev = {src: None}; q = deque([src])
    while q:
        p = q.popleft()
        if p == dst: break
        doors = cells[p][0]
        for d in range(4):
            if doors >> d & 1:
                np = (p[0] + DXY[d][0], p[1] + DXY[d][1])
                if np in cells and np not in prev:
                    prev[np] = (p, d); q.append(np)
    if dst not in prev: return None
    out = []; p = dst
    while prev[p]: p, d = prev[p][0], prev[p][1]; out.append(d)
    return out[::-1]

sp = bfs(start, gate)

# Submit the route as raw direction bytes via opcode 0x30
fr = z.cmd(0x30, bytes(sp))
if b'CTF{' in fr['body'] and b'not_the_exit' not in fr['body']:
    print('FLAG:', fr['body'])
z.close()

The winning run mapped 23 of 25 cells before landing on the gate at (3,4). The 21-move BFS route

02 02 02 01 02 01 00 00 00 03 00 01 01 01 02 02 03 02 01 02 03

was accepted on the first submission, and the gate replied (type 0xf0) with the flag.

Caveat: reaching the gate too early

You can’t tell which unexplored cell is the gate until you step into it, and you can’t leave it afterwards. If depth-first search reaches the gate before the true shortest route has been mapped, BFS only sees the explored part of the maze. It may then send a route that is valid but not the shortest. It did not happen in the winning run, and I didn’t test what the gate does with a wrong answer. If it happens, rerun: every connection gets a fresh maze, and the gate is usually reached after most of the 25 cells have been mapped.

Lessons

• An unknown binary protocol with verbose, non-resetting errors is effectively self-documenting. Brute the opcode byte and read what comes back.
• Check the field boundaries you assume. Treating two separate bytes (doors, kind) as one 16-bit value made the maze look meaningless.
• Watch for extra frames the server sends without being asked (the light-room decoy). One undrained frame shifts every later reply by one and makes the protocol look inconsistent.
• If the target state can’t be left, collect what you need for the final answer before you enter it, or at least before you commit to the answer.