cts

Ooh thanks let me fix this

Add progressive web app support and I'll switch back

Living with autism really be like

- 5 reps eye contact
- 10 reps considering others’ viewpoints and feelings
- 3x60 seconds tolerating uncomfortable sensations
- Remembering names and faces until failure

Lastly:

We're sponsoring PlaidCTF this year at Zellic. This is a lifelong dream of mine. Thank you so much to the organizers for putting on such an excellent CTF each year!

PlaidCTF will be running starting this Friday. Sign up here: plaidctf.com

Cheers!

I really enjoyed this challenge. This thread was excerpted from the full writeup, which you can find here: blog.perfect.blue/Lot-of-Fish-...

This is a NP complete problem, but luckily we can attack this with dynamic programming. My teammate Sampriti wrote a solver and it gave the solution
[0,9,15,2,1,4,3,8,10,5,13,11,14,6,7,12,0]

And if we feed this into the challenge, we actually get our flag!

This is asking us to find a permutation of (xs, ys) that results in the Manhattan distances between consecutive points sums to 0x470.

This is essentially finding a Hamiltonian cycle of specified length!

Now, if you disassemble the bytecode, you'll realize there's control flow... even subroutines and functions!

Here's a screenshot from the Binary Ninja plugin
@hgarrereyn.bsky.social independently wrote as part of his solve.

It initializes a VM state using our input, then applies StepVM until the VM halts and returns a scalar. This scalar is the VM’s exit code (halt state). This final state is asserted to be zero. So our flag needs to satisfy this whole circuit.

Essentially, this entire VM is used as a type constraint on our input!

Meaning, the type system, not any interpreted code, checks our input! The computation is done in this circuit, that is executed through type checking.

And here's how they actually launch the VM and check the flag with it. They pass the flag as input to the VM (the VM code is parameterized by the input; the VM is parameterized by the code)

And here's the instruction set.

Guess what! It's a virtual machine.

Yup... this is implementing computing the operand value for an instruction. Oh boy... this is probably going to be an entire RISC CPU.

RISC processors often fetch operand values during the instruction decode stage, and that's what's going on here.

I was feeling pretty good at this point. I was understanding what everything was doing.

But then my heart sank when I saw this.

Can you guess what this does?

Keep in mind, all of these identifiers and strings were just names of fish.

So I was sitting there discovering how "Tuna" is actually a ripple-carry adder.

Here is how they index into a list. They do this by recursively skipping every other element based on the bits of the index (!!!)

We can even build a multiplier!

What about bitwise arithmetic?

Now you may be wondering... that's great but how can we do arithmetic? How do we add two BinNums?

Well...using a full adder of course :-)

So this is basically building up bit-level computation. The types set up a circuit, and valid evaluations of the circuit type check.

The flag checker is implemented in this circuit, and we need to (1) reverse how logic is implemented in circuit form; then (2) reverse the logic.

Remember everything is actually a type: our functions are conditional types. Our parameters are actually type parameters. Our numbers are actually just types representing arrays of binary digits.

To make this concrete, let me give an example.

Correct computations typecheck!

Our BinNums are essentially representations of integers in binary form, with LSB at the front of the array and MSB at the end.

So this “function” takes in two BinNums, and returns if they are equal by iterating through the bits in order and checking if they are all equal.

There’s a lot going on here.

It creates a dict and then indexes into it. It’s kind of like a switch statement. The dict part is responsible for either recursing or returning the base case. The index does combinatorial logic for what to do based on the current recursion level.

If you thought that was crazy, wait till you see this.

Then they use Car and Cdr with tail recursion to accomplish iteration. This is how they check if two binary numbers are equal:

What they're doing is extremely clever. It's pattern matching on the args of a dummy functional type. That's how they represent a tuple. Then, Car (Cdr) peels off the first (second) arg of a "…" expansion. The ... is like Python *args.

That's how they destructure a tuple.

Aha: They're using the type system itself to do computation. The types constrain what values belong to them. By doing computations on types, we can do arbitrary computation!

So this challenge is (ab)using the type system's Turing-completeness to build a flag checker!

Now look at Dogfish. It's the first non-trivial type that isn't a constant.

Swordfish is true, Ponyfish is false, and Dogfish is an algebraic type that must satisfy both True and False; e.g., the null type never.

We can check this in a REPL:

That's better. We can even see some constants. But almost every type uses other types, that we still don't understand.

Let's try sorting all the lines by length, shortest to longest. That should put the simplest definitions first, so we can reverse it from the bottom up.