The Fish - LA CTF 2025 Reverse Engineering Writeup

Category: Reverse Engineering Difficulty: Medium Points: 133 Solves: 165 Flag: lactf{7h3r3_m4y_83_50m3_155u35_w17h_7h15_1f_7h3_c011472_c0nj3c7ur3_15_d15pr0v3n} Solved by: Smothy @ 0xN1umb

"The Collatz conjecture has been unsolved for 87 years. This Fish program has been unsolved for 87 seconds."

Challenge Description

The fish asks you for the flag. Unfortunately, it can only describe it to you in its own words.

We're given a single Python file fish.py — a full interpreter for the ><> (Fish) esoteric programming language, with an embedded one-liner Fish program that validates the flag. The fish speaks in stack operations and Collatz sequences. Time to learn fish.

TL;DR

Flag gets converted to a big integer, then the program runs an accelerated Collatz sequence on it, encoding the entire path (even/odd decisions) into a binary counter. We reverse the counter back through the Collatz steps to recover the original integer, convert to bytes, get the flag. Math go brrr.

Initial Recon

One file. 416 lines. Let's see what we're dealing with.

The file is a complete ><> (Fish) interpreter — a 2D stack-based esoteric language where the instruction pointer moves in four directions, bounces off mirrors, and processes single-character instructions. Think Befunge's aquatic cousin.

The key parts:

• Standard interpreter for ><> with all the usual instructions
• One custom instruction n — pops the stack and compares against a 1,300-digit target number
• The Fish program itself — a single line of 90 characters

The entry point converts our flag to ASCII values on the stack, then lets the Fish program do its thing:

flag = input("><> ><>. (Enter the flag): ")
fisherator = """r0!&4:*:**+&5:*0l2=?.~~20."W"01&:&1=}@{?.{2*"E"0&:&2%0=?.&3*1+&}}1+{{.&2,:&}@{1=?.{56*0.n;"""
interpreter = Interpreter(fisherator)
interpreter._stack = [int(ord(c)) for c in flag]

Step 1: Dissecting the Fish Program

The 90-character Fish program packs a surprising amount of logic. I traced through it instruction by instruction to understand the algorithm.

Phase 1: Base-256 Accumulation

This is a loop that converts the flag characters into a single big integer:

This is equivalent to int.from_bytes(flag.encode(), 'big') — converts the entire flag string to one massive integer in big-endian byte order.

Phase 2: Collatz Path Encoding

This is where it gets spicy. The stack is initialized as [87, 0, 1] (base=87/"W", result=0, counter=1), and the program runs an accelerated Collatz sequence:

For each iteration:

1. Check if acc == 1 → if so, exit loop
2. *counter = 2 (left-shift the counter)
3. Check if acc is even or odd:
   • Even: acc = acc // 2
   • Odd: acc = (3 * acc + 1) → counter += 1 → acc = acc // 2
4. Loop back

The n instruction then checks if counter equals the target.

Step 2: Understanding the Encoding

The counter is a binary encoding of the Collatz path. Each step doubles the counter (shift left), and odd steps set the LSB. So the binary representation is:

For the homies who haven't touched the Collatz conjecture: it says that starting from ANY positive integer, repeatedly applying n → n/2 (even) or n → 3n+1 (odd) will ALWAYS eventually reach 1. It's been verified up to 2⁶⁸ but never proven. The flag is a cheeky reference to this.

Step 3: Reversing the Path

To recover the flag, we reverse the entire process:

1. Take the 1,300-digit target number
2. Convert to binary, strip the leading 1 marker
3. Read bits right-to-left (undo the last Collatz step first)
4. For each bit:
   • 0 (was even): undo n/2 → acc *= 2
   • 1 (was odd): undo (3n+1)/2 → acc = (2*acc - 1) / 3
5. Convert the resulting integer to bytes → flag!

The key insight: since the Collatz path is deterministic for any starting number, the binary encoding is a perfect, reversible fingerprint. We just walk backwards through 2,999 steps.

Step 4: The Solve

target = 9965663476834296889619619643...  # 1300-digit number

# Strip the leading '1' marker from binary representation
bits = bin(target)[3:]  # Remove '0b1'

# Reverse the Collatz sequence step by step
acc = 1
for bit in reversed(bits):
    if bit == '0':
        acc = acc * 2           # undo even step (n/2)
    else:
        acc = (2 * acc - 1) // 3  # undo odd step ((3n+1)/2)

# Convert big integer back to flag string
flag = acc.to_bytes((acc.bit_length() + 7) // 8, 'big').decode()
print(flag)

Running it:

The Flag

Decoded from l33tspeak: "there may be some issues with this if the Collatz conjecture is disproven"

Verified with the original interpreter:

Indeed it is, little fish. Indeed it is.

The Solve Script

#!/usr/bin/env python3
"""
The Fish - LA CTF 2025 Reverse Engineering
Solver by Smothy @ 0xN1umb

Reverses a Collatz path encoding to recover the flag.
"""

target = 996566347683429688961961964301023586804079510954147876054559647395459973491017596401595804524870382825132807985366740968983080828765835881807124832265927076916036640789039576345929756821059163439816195513160010797349073195590419779437823883987351911858848638715543148499560927646402894094060736432364692585851367946688748713386570173685483800217158511326927462877856683551550570195482724733002494766595319158951960049962201021071499099433062723722295346927562274516673373002429521459396451578444698733546474629616763677756873373867426542764435331574187942918914671163374771769499428478956051633984434410838284545788689925768605629646947266017951214152725326967051673704710610619169658404581055569343649552237459405389619878622595233883088117550243589990766295123312113223283666311520867475139053092710762637855713671921562262375388239616545168599659887895366565464743090393090917526710854631822434014024

bits = bin(target)[3:]  # Remove '0b1'
acc = 1
for bit in reversed(bits):
    if bit == '0':
        acc = acc * 2
    else:
        acc = (2 * acc - 1) // 3

flag = acc.to_bytes((acc.bit_length() + 7) // 8, 'big').decode()
print(f"Flag: {flag}")

The Graveyard of Failed Attempts

1. "Maybe the big number IS the flag as base-256?" — Nope, the target is 1,300 digits (~4,319 bits). An 80-char flag is only 640 bits. There's clearly more computation happening after the base-256 conversion.

2. Manual tracing without understanding the big picture — I traced about 90 instructions by hand before recognizing the Collatz pattern. The }@{ stack shuffling in Fish is absolutely cursed for manual analysis. The @ instruction (rotate top 3) combined with { and } (stack shifts) is like doing a Rubik's cube blindfolded.

3. Almost reversed the bit order wrong — The counter encodes bits MSB-first (first step = most significant bit after the leading 1). To undo, you read LSB-first. Getting this backwards would have produced garbage. The small test case with n=3 (counter=56) saved me.

Key Takeaways

1. ><> (Fish) is a real language — 2D, stack-based, with mirrors, string mode, and self-modifying code. Learning the basics took 10 minutes; understanding the algorithm took much longer.

2. The Collatz conjecture makes great crypto — The forward direction (number → Collatz path) is deterministic and unique. The path length is unpredictable but always finite (assuming the conjecture holds). Perfect for a one-way-ish encoding.

3. Binary path encoding is elegant — Using a counter that doubles each step (with +1 for odd) to create a binary fingerprint of the entire Collatz trajectory is genuinely clever challenge design.

4. Manual ><> tracing is pain — The }@{ stack gymnastics in Fish are brutal to follow. For anyone facing a similar challenge: trace with a concrete small example first, then generalize.

5. The flag itself is meta — If the Collatz conjecture were disproven (a number that loops forever without reaching 1), this program would hang on certain inputs. The challenge is mathematically contingent on an unproven conjecture. Respect to the challenge author.

Tools Used

• Python 3 (solving + verification)
• A whiteboard for manual ><> tracing
• Wikipedia article on the Collatz conjecture
• Way too much caffeine

Writeup by Smothy from 0xN1umb team. 2,999 Collatz steps walked backwards, one bit at a time. The fish has spoken. GG.