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!
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!
April 2, 2025 at 8:50 PM
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!
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!
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!
[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!
April 2, 2025 at 8:50 PM
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!
[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!
If you translate this to pseudocode, it basically implements this check:
April 2, 2025 at 8:50 PM
If you translate this to pseudocode, it basically implements this check:
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.
Here's a screenshot from the Binary Ninja plugin
@hgarrereyn.bsky.social independently wrote as part of his solve.
April 2, 2025 at 8:50 PM
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.
Here's a screenshot from the Binary Ninja plugin
@hgarrereyn.bsky.social independently wrote as part of his solve.
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)
April 2, 2025 at 8:50 PM
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.
April 2, 2025 at 8:50 PM
And here's the instruction set.
Here's the full processor state. It also implements binary heaps built in which is very very quirky.
Again, keep in mind every name here used to be the name of a fish🫠 This is all manually renamed
Again, keep in mind every name here used to be the name of a fish🫠 This is all manually renamed
April 2, 2025 at 8:50 PM
Here's the full processor state. It also implements binary heaps built in which is very very quirky.
Again, keep in mind every name here used to be the name of a fish🫠 This is all manually renamed
Again, keep in mind every name here used to be the name of a fish🫠 This is all manually renamed
Guess what! It's a virtual machine.
April 2, 2025 at 8:50 PM
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.
RISC processors often fetch operand values during the instruction decode stage, and that's what's going on here.
April 2, 2025 at 8:50 PM
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.
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?
But then my heart sank when I saw this.
Can you guess what this does?
April 2, 2025 at 8:50 PM
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?
But then my heart sank when I saw this.
Can you guess what this does?
Here is how they index into a list. They do this by recursively skipping every other element based on the bits of the index (!!!)
April 2, 2025 at 8:50 PM
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!
April 2, 2025 at 8:50 PM
We can even build a multiplier!
What about bitwise arithmetic?
April 2, 2025 at 8:50 PM
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 :-)
Well...using a full adder of course :-)
April 2, 2025 at 8:50 PM
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 :-)
Well...using a full adder of course :-)
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!
To make this concrete, let me give an example.
Correct computations typecheck!
April 2, 2025 at 8:50 PM
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!
To make this concrete, let me give an example.
Correct computations typecheck!
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:
Then they use Car and Cdr with tail recursion to accomplish iteration. This is how they check if two binary numbers are equal:
April 2, 2025 at 8:50 PM
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:
Then they use Car and Cdr with tail recursion to accomplish iteration. This is how they check if two binary numbers are equal:
Next is how they implement Car and Cdr from Lisp.
Here's how Car and Cdr work. Given a pair (tuple of 2 elements), Car gives you the first element. Cdr gives you the second element.
Can you see how it works?
Here's how Car and Cdr work. Given a pair (tuple of 2 elements), Car gives you the first element. Cdr gives you the second element.
Can you see how it works?
April 2, 2025 at 8:50 PM
Next is how they implement Car and Cdr from Lisp.
Here's how Car and Cdr work. Given a pair (tuple of 2 elements), Car gives you the first element. Cdr gives you the second element.
Can you see how it works?
Here's how Car and Cdr work. Given a pair (tuple of 2 elements), Car gives you the first element. Cdr gives you the second element.
Can you see how it works?
Uh oh. I have a bad feeling about this.
April 2, 2025 at 8:50 PM
Uh oh. I have a bad feeling about this.
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:
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:
April 2, 2025 at 8:50 PM
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:
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.
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.
April 2, 2025 at 8:50 PM
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.
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.
Let's break this down into individual lines, at least.
April 2, 2025 at 8:50 PM
Let's break this down into individual lines, at least.
In 2020, I solved a gnarly reverse engineering challenge in PlaidCTF. Only 9 teams solved.
It's a huge pile of Typescript. Everything is named after a fish.
The catch? There's no code, only types. How do they perform computation using just the type system?
(Spoiler: Circuits!)
It's a huge pile of Typescript. Everything is named after a fish.
The catch? There's no code, only types. How do they perform computation using just the type system?
(Spoiler: Circuits!)
April 2, 2025 at 8:50 PM
In 2020, I solved a gnarly reverse engineering challenge in PlaidCTF. Only 9 teams solved.
It's a huge pile of Typescript. Everything is named after a fish.
The catch? There's no code, only types. How do they perform computation using just the type system?
(Spoiler: Circuits!)
It's a huge pile of Typescript. Everything is named after a fish.
The catch? There's no code, only types. How do they perform computation using just the type system?
(Spoiler: Circuits!)
