# babyllvm
# Summary
The challenge is RCE-as-a-service, with a twist, that what's executed is pure[brainfuck](https://en.wikipedia.org/wiki/Brainfuck), and execution environmentis a JIT based on [llvmlite](https://github.com/numba/llvmlite), whichimplements sandboxing by emitting bounds checks. The goal is to find a bug inJIT and/or runtime library, and use it to escape the sandbox.
# JIT logic
## Step 1 - Parsing
A brainfuck program is represented as a tree. Each node is either a linear node,or a loop node. Loop nodes consist of the part before the loop, the loop, andthe part after the loop.
## Step 2 - Optimization
Linear nodes are converted to `shortened_code` form, which uses the followingopcodes:
1. `ptr += imm`2. `*ptr += imm`3. `imm.times { print(*ptr); }`4. `imm.times { read(ptr); }`
## Step 3 - Runtime
Runtime is implemented as a shared library. It contains data area, which is0x3000 byte large, and is preceded by `data_ptr` and `start_ptr` pointers, aswell as function used to perform bounds checking. `checksec` shows only partialRELRO, which hints at the potential to overwrite GOT.
## Step 4 - JIT
Codegen of linear nodes tries to be smart regarding optimizing away boundschecks. opcode 1 allows arbitrary changes, but also tracks the position of datapointer relative to what it was at the start of the block (`rel_pos`). Opcodes2-4 compare this relative position to the statically tracked range, for whichbounds checks were already emitted (`whitelist`), and emit the check only whenit's outside of that range. Each generated check extends the range in orderto avoid unnecessarily repeating checks in the future.
Codegen of non-linear nodes recursively generates code for its three nestedprograms, and glues them together.
Codegen returns `(entry, exit)` tuple, where entry and exit are either basicblocks, or tuples of similar shapes. `exit` may be `None`, which means there isjust one linear basic block.
# Vulnerability
The bug is here:
```			br1b = self.br1.codegen(module, (0, 0))			br2b = self.br2.codegen(module, (0, 0))```
When generating the loop body, we assume that we don't need to generate thebounds check for the initial pointer position, since it's already a part of thecode that glues together three parts of the loop node.
However, generation of the glue itself is guarded by:
```			if not is_safe(0, whitelist):```
Which means that the nested loop will have no bounds checks whatsoever.Therefore we can move the data pointer to an unsafe position in the parent loop,since it's not checked anyway, and then dereference it in the nested loop.
# Pwn
Here is the safe leak of the `start_ptr`'s least significant byte:`+[<<<<<<<<[.>>>>>>>>>]]`. It works by storing `1` to `data[0]` in order to enterthe parent loop, positioning the data pointer on `data[-8]`, dumping it in thechild loop, and then going to `data[1]` in order to exit both child and parentloops.
This cannot be used to dump bytes equal to `0`, because we won't enter the childloop and the program will trip on the parent loop's bounds check, butfortunately we know that interesting pointers are of the form`0x0000xxxxxxxxxxxx`, so we can limit ourselves to reading just 6 bytes.
GOT is located close to the beginning of the data area. By using the leak above,we can read any slot and locate libc. By replacing `.` with `,` we can overwriteany slot with one_gadget address. I went with overwriting `write` with`libc + 0x10a38c`, which gave me the shell.
# Flag
`CODEGATE2020{next_time_i_should_make_a_backend_for_bf_as_well}`
I wanted to try doing just that a few years back, but never managed to find thetime :-(