As is probably already abundantly clear, I am a fan and advocate for Rust. When given the opportunity to create a challenge for a CTF, I wanted to set out to not only build a challenging Rust CTF challenge, I wanted to defy expectations, teach something novel, and reshape a participant’s understanding of Rust even for long-time Rustaceans.
The Premise
You’re presented with a brainfk interpreter written in Rust and its source code. You can pass it a brainfk program and it will run exactly as it should. It will also ignore non-brainfk program characters as if they didn’t exist. There is a maximum program size, though, at around 80 characters.
Investigation
Taking a look at the source code, we can immediately note a couple of interesting things.
First of all, unsafe code is forbidden. This means it’s not going to be as easy as searching for unsafe code blocks and finding the vulnerability there.
Secondly, programs have a maximum length of 80.
And lastly, this program uses Jemalloc seemingly because it’s“faster” than glibc’s heap allocator.
The code works in the following way:
Read in the program from stdin
After filtering out newlines, make sure the number of characters in the program is less than the MAX_PROGRAM_LENGTH
Create a brainfk program object from the program
Call the interpreter macro to create an interpreter with the brainfk program
Read the flag from the flag file and call set_flag on the interpreter
Run the interpreter
Two things really stand out here: the interpreter macro and the flag.
Set Flag on Interpreter
Looking at the set flag call we immediately see it’s a dead end. It’s not even implemented!
Interpreter Macro
It seems a little odd that a macro is needed to create the interpreter when we were able to clearly create and call a function to instantiate a BrainFkProgram just fine. Macros can often hide complexity so this seems like a good place to start.
So this macro expands out to a Vector allocation that is as-large as our program(via this instruction_count call). We then call a method to instantiate a BrainFkInterpreter with our program and the result of calling box_and_apply_lower_bound_to_memory. We’ll also notice that this method takes a mutable reference to our Vector.
Box And Apply Lower Bound To Memory
Looking at this method we see it get complicated fast. Thankfully there is a nice helpful comment to explain the intent.
We understand that this code is there to ensure that if the program is very large, we allocate a large amount of memory for the BrainFkProgram to run the program in. If it’s too small, we apply a lower bound to the size. It’s confusing why it’s written in such a convoluted way which should make you suspicious, but let’s see if we can understand under what conditions does the behavior change.
Following the data flow, we see that if the memory we allocated back in the interpreter macro is less than or equal to the maximum program length then we’ll call this closure we passed in instead and use that memory. If our memory is larger in size than the max program length, then we’ll use the memory we passed in.
What’s curious though is that the memory we pass in is an immutable reference(&Vec<u8>) which you can think of as similar to a read-only pointer to some memory. Rust is memory safe so if we allocate some memory and hold a reference to it, that memory should not be deallocated.
Let’s look back at the interpreter macro a little more closely.
Interpreter Macro, Again
I like to use the cargo expand command to look at how macros expand into Rust. It helps make it clearer what the end-product Rust looks like if it’s hard to reason about. You don’t necessarily need this, but it helps.
Something stands out here now that we have additional context on how box_and_apply_lower_bound_to_memory works. If we were able to create a Vec<u8> that was larger than MAX_PROGRAM_SIZE, then box_and_apply_lower_bound_to_memory would return it as a reference(think: pointer). However, in Rust, memory that is not returned at the end of a block is“dropped”(and deallocated).
We’re running into an impossibility in the Rust language.
The Premise
Investigation
Set Flag on Interpreter
Interpreter Macro
Box And Apply Lower Bound To Memory
Interpreter Macro, Again