Gorbino's quest of life — pingCTF 2026

Description

Gorbino's quest of life

Files provided:

• ELF 64-bit LSB PIE executable, x86-64, not stripped

The binary reads a string with scanf and validates it through a complex multi-threaded cellular automaton simulation. The challenge name hints at Conway's Game of Life, but the actual implementation is a second-order reversible variant.

Analysis

Binary overview

$ file chall
chall: ELF 64-bit LSB pie executable, x86-64, not stripped

$ nm chall | grep -E "thrd_|mtx_|cnd_"
                 U cnd_broadcast
                 U cnd_wait
                 U mtx_lock
                 U mtx_unlock
                 U thrd_create
                 U thrd_join

The binary uses C11 thread primitives for parallel simulation. Main reads input with scanf and calls TheStrongDecideTheNatureOfSin to validate.

Input encoding (AGoodPartyRequiresABloodSacrifice)

The function AGoodPartyRequiresABloodSacrifice allocates a 48x64 byte grid and encodes the input:

• First up-to-64 input characters become columns (column index = character position)
• Rows 0..7 store bits 0..7 of each byte (LSB at row 0)
• Rows 8..47 are initialized to zero
• Task statement hints input is <64 characters including the ping_ prefix

This creates a bit-plane representation where each character occupies one column, with its 8 bits spread vertically across rows 0-7.

Rule extraction (GAME table at 0x3100)

The GAME table contains ASCII '0' and '1' values encoding a totalistic Life-like rule:

Index:  0  1  2  3  4  5  6  7  8
Birth:  0  0  0  1  0  0  0  0  0   (birth on exactly 3 neighbors)
Survive: 0  0  0  1  1  0  0  0  0  (survive on 3 or 4 neighbors)

This gives the first-order rule B3/S34 — similar to standard Life (B3/S23) but with survival extended to 4 neighbors.

Critical insight: second-order reversible automaton

The function BlueHouseGTechExec does NOT implement plain Life. It runs a second-order reversible cellular automaton:

next = life34(current_neighbors, current) XOR previous

Where:

• current = generation N
• previous = generation N-1 (starts as all-zero for generation -1)
• next = generation N+1

This is the standard technique for making any CA reversible: XOR the new state with the state from two generations ago.

Target bitmaps

Each worker thread compares the final simulation states against two embedded 48x64 bitmaps:

Symbol	Address	Meaning
KRILLYOUSELF	embedded	Generation N-1 (penultimate)
TheOnePieceIsReal	embedded	Generation N (final)

Where N = 0x537a = 21370 generations.

Both bitmaps use # for 1 and space for 0 in ASCII art format.

Non-standard topology

The neighborhood is NOT standard step-1 Moore. Function TheStrongDecideTheNatureOfSin builds edges using:

x-2, x+2  // column offsets
y+2       // row offsets

The effective neighborhood is Moore-like with step 2:

• Neighbors at positions: (x±2, y±2), (x±2, y), (x, y±2)
• 8 neighbors total, but spaced 2 cells apart
• Boundary cells are treated as dead (zero)

This topology splits the 48x64 board into 4 independent parity sublattices (even-even, even-odd, odd-even, odd-odd coordinates).

Reversal strategy

Since the automaton is second-order reversible, we can run it backwards:

prev = life34(curr_neighbors, curr) XOR next

Starting from:

• curr = generation N-1 (KRILLYOUSELF bitmap)
• next = generation N (TheOnePieceIsReal bitmap)

After reversing 21370 generations:

• Generation -1 becomes all zeros (as expected for initial previous state)
• Generation 0 contains the encoded flag in rows 0-7

Decoding columns of generation 0 back into bytes yields the flag.

Solution

#!/usr/bin/env python3
"""
Solver for 'Gorbino's quest of life' - pingCTF 2026

Second-order reversible cellular automaton with B3/S34 rule
and step-2 Moore neighborhood on a 48x64 grid.
"""

import numpy as np

# Grid dimensions
ROWS, COLS = 48, 64
GENERATIONS = 21370  # 0x537a

def parse_bitmap(ascii_art: str) -> np.ndarray:
    """Convert #/space ASCII art to binary grid."""
    lines = ascii_art.strip().split('\n')
    grid = np.zeros((ROWS, COLS), dtype=np.uint8)
    for y, line in enumerate(lines[:ROWS]):
        for x, ch in enumerate(line[:COLS]):
            grid[y, x] = 1 if ch == '#' else 0
    return grid

def count_neighbors_step2(grid: np.ndarray, y: int, x: int) -> int:
    """Count live neighbors using step-2 Moore neighborhood."""
    count = 0
    for dy in [-2, 0, 2]:
        for dx in [-2, 0, 2]:
            if dy == 0 and dx == 0:
                continue
            ny, nx = y + dy, x + dx
            if 0 <= ny < ROWS and 0 <= nx < COLS:
                count += grid[ny, nx]
    return count

def life34_step(grid: np.ndarray) -> np.ndarray:
    """Apply B3/S34 rule with step-2 neighborhood."""
    new_grid = np.zeros_like(grid)
    for y in range(ROWS):
        for x in range(COLS):
            neighbors = count_neighbors_step2(grid, y, x)
            cell = grid[y, x]
            # B3/S34: birth on 3, survive on 3 or 4
            if cell == 0:
                new_grid[y, x] = 1 if neighbors == 3 else 0
            else:
                new_grid[y, x] = 1 if neighbors in (3, 4) else 0
    return new_grid

def reverse_step(curr: np.ndarray, next_gen: np.ndarray) -> np.ndarray:
    """Reverse one generation: prev = life34(curr) XOR next."""
    life_result = life34_step(curr)
    return life_result ^ next_gen

def decode_flag(grid: np.ndarray) -> str:
    """Decode bit-plane columns back to characters."""
    flag = []
    for x in range(COLS):
        byte_val = 0
        for bit in range(8):
            if grid[bit, x]:
                byte_val |= (1 << bit)
        if byte_val == 0:
            break
        flag.append(chr(byte_val))
    return ''.join(flag)

# Target bitmaps (extracted from binary)
# KRILLYOUSELF = generation N-1
# TheOnePieceIsReal = generation N
KRILLYOUSELF = """
# ... (48 lines of 64 chars each with # and space)
""".strip()

THE_ONE_PIECE_IS_REAL = """
# ... (48 lines of 64 chars each with # and space)
""".strip()

def main():
    # Parse target bitmaps from binary
    gen_n_minus_1 = parse_bitmap(KRILLYOUSELF)
    gen_n = parse_bitmap(THE_ONE_PIECE_IS_REAL)
    
    # Reverse 21370 generations
    curr = gen_n_minus_1.copy()
    next_gen = gen_n.copy()
    
    for i in range(GENERATIONS):
        prev = reverse_step(curr, next_gen)
        next_gen = curr
        curr = prev
        if i % 1000 == 0:
            print(f"Reversed {i} generations...")
    
    # After reversal:
    # curr = generation -1 (should be all zeros)
    # next_gen = generation 0 (contains encoded flag)
    
    assert np.sum(curr) == 0, "Generation -1 should be all zeros"
    
    # Decode flag from generation 0
    flag = decode_flag(next_gen)
    print(f"Flag: {flag}")
    
    # Verify by forward simulation
    print("Verifying with forward simulation...")
    gen0 = next_gen.copy()
    gen_minus1 = curr.copy()
    
    curr = gen0
    prev = gen_minus1
    for i in range(GENERATIONS):
        next_state = life34_step(curr) ^ prev
        prev = curr
        curr = next_state
    
    assert np.array_equal(prev, gen_n_minus_1), "Forward sim mismatch at N-1"
    assert np.array_equal(curr, gen_n), "Forward sim mismatch at N"
    print("Verification passed!")

if __name__ == "__main__":
    main()

Verification

Forward-simulating 21370 generations from the recovered initial grid reproduces both target bitmaps exactly, confirming the solution.