Tags: pwn heap tree 

Rating:

The bug

The bug is a very obvious OOB that exists in the select function.

unsigned long select(sp *tree, int idx)
{
  struct node *e;

  e = tree->vector[idx];                          // OOB
  sp_select(tree, &e->tree_metadata);
  return e->y;
}

Basically, the select function takes the idx'th element from the vector and places it on top of the tree. By faking a node on a tree we can manipulate the entire tree structure.

Heap Leak

Each node looks like this:

struct node {
    unsigned long x;
    unsigned long y;
    unsigned long unk1;
    unsigned long unk2;
    unsigned long idx;

    struct tree_metadata {
        struct tree_metadata *parent;
        struct tree_metadata *lchild;
        struct tree_metadata *rchild;
        unsigned long size;
    } meta;
};

And by using the given features we can get the contents of x and y in the nodes. This can be used for an infoleak. However, in order to fake a node we need to store a pointer pointing to it. I did this by using the freed chunks of tcache. In each freed chunk of tcache there is a pointer pointing to its prev chunk. By using this, we can get the x value of a freed chunk faked to a node, which is a heap address.

for i in range(5):
        add(i,i)

delete(0)
delete(1)
delete(2)
delete(3)
delete(4)

idx = (0x7fc6681fc370 - 0x7fc6681fb260)//8

select(idx)
HEAP = getnth(0)

log.info("HEAP: 0x%x"%HEAP) # 0x7f68373c72d0

LIBC Leak and arbitrary write

After a long time of thinking, I decided to use a section of memory that has lots of NULLs but also contains some important pointers. It is important that the section has an abundance of NULLs so that the select function does not attempt to recurse to its parent or children. The ideal memory section that I thought of was the tcache structure, located in the heap base.

void find_and_add(struct sp *tree, unsigned long incr, unsigned long x, unsigned long y)
{

  struct node *node = sp_isolate(tree, x, y);
  if ( node )
    *(_QWORD *)(node - 0x18) += a2;
}

By using this functionality, we can get a write primitive. By overwriting the tcache head to a pointer we can get a node allocated at an unsorted bin, and when we get the x value of it we get a libc address.

Getting a shell

Afterwards everything is easy, we can use the primitives discussed to get arbitrary write, overwriting __free__hook with system and calling free("/bin/sh")

Original writeup (https://github.com/pr0cf5/CTF-writeups/tree/master/2019/pctf-2019/splaid-birch).