Did you understand House of Einherjar?

Prerequisites

• Do you know the C language? No -> Maybe it's too early to read this article
• Do you know what is the difference betweek stack and heap? No -> go here!
• Do you know what is a buffer overflow? No -> go here!
• Do you have a basic knowledge of malloc internals? No -> go here and then here!
• Do you know the tcache poisoning technique? No -> go here!

What is House of Einherjar?

House of Einherjar is an heap exploitation technique that exploits a single null byte overflow (or "off-by-one overflow") to force a malloc call into returning an arbitrary pointer.
It works with the most recent versions of the glibc and exploited in a proper way can lead to RCE.

Support Resources

• how2heap by shellphish: one of the best resource about heap exploitation
• malloc.c source code (glibc 2.32)
• heappy: a tool to visualize and compare snapshots of heap

Let's go!

Let's start considering the code offered by shellphish. This is the first snippet:

intptr_t stack_var[4]; // the last malloc will return this

intptr_t *a = malloc(0x38);
a[0] = 0;           // fake prev_size
a[1] = 0x60;        // fake size
a[2] = (size_t) a;  // fake fwd
a[3] = (size_t) a;  // fake bck

uint8_t *b = (uint8_t *) malloc(0x28);
uint8_t *c = (uint8_t *) malloc(0xf8);
...

The code above allocates dinamically a chunk(a) of 0x38 bytes (+ size of header) and prepares a fake chunk inside it immediately after the chunk header. Then it allocates the chunks b and c.

The reason why the fwd and bck fields of the fake chunk are set to a is to bypass a check that we can found in the code of the unlink_chunk function. In the following check, p is the address of the chunk to unlink and fd/bk are the next/previous nodes.

unlink_chunk (mstate av, mchunkptr p)
{
    ...
    mchunkptr fd = p->fd;
    mchunkptr bk = p->bk;
    if (__builtin_expect (fd->bk != p || bk->fd != p, 0))
        malloc_printerr ("corrupted double-linked list");
    ...

• fd->bk != p -> false: of course, the previous node of the next node of the fake chunk is the fake chunk itself
• bk->fd != p -> false: of course, the next node of the previous node of the fake chunk is the fake chunk itself

The heap snapshot in this moment is described by the left column below:

In order to overwrite the size+stat field of the chunk c, as described in the right column above, the shellpish code simulates an off-by-one overflow of a null byte in the chunk b.
In particular, the byte set to 0 is related to the prev in use (P) flag. Thus, from the point of view of c, the chunk b will result to be free.

...
b[0x28] = 0; // null byte overflow
...

The prev_size field at the end of the chunk b is considered only if the chunk b is freed and it should be equal to its size field.
Let's set this value to 0x60:
(if you want to verify this value remember that the size of b is 0x30 and not 0x31

)

...
size_t fake_size = (size_t)(c - 16 - (uint8_t*) a); // 0x60
*(size_t*) &b[real_b_size - sizeof(size_t)] = fake_size;
...

Our plan is to deallocate c in order to trigger the consolidation phase, but before doing that we have to avoid that c goes in the tcache bin.
Each tcache bin has 7 slots avaliable, thus to target the correct bin it is sufficient to use the same size of c (0xf8).

...
intptr_t *x[7];
for(int i=0; i<sizeof(x)/sizeof(intptr_t*); i++)
    x[i] = malloc(0xf8);

for(int i=0; i<sizeof(x)/sizeof(intptr_t*); i++)
    free(x[i]);
...

The tcache bin is full, now we can free the chunk c, in the following snippet. This will trigger the consolidation phase among c, b and the fake chunk. This happens thanks to the value 0x60 in the prev_size field.
The result is a free chunk of size 0x161 in the unsorted bin list, that is allocated in the following row.

...
free(c);
intptr_t *d = malloc(0x158);
...

At this point we have all the elements to apply the tcache poisoning attack.

🧪

[ Recap about tcache bins and the related poisoning ]

• tcache bin behavior:
  • The head, which is not a chunk, points to the last freed chunk
  • The bk field of each chunk points to the head
  • The fw field of the last freed chunk points to the chunk previously freed.
  • The fw field of the first freed chunk points to the head
  • When a chunk is allocated, the value in the head is returned and the fw field of the last freed chunk goes in the head
• tcache poisoning:
  • find a way to write the fw field of the last freed chunk an arbitrary location
  • allocate the poisoned chunk so that the arbitrary fw value goes in the head
  • perform a malloc that returns the value in the head that is the arbitrary

Let's return to House of Einherjar.
This is the right moment to show a general overview. In particular, the column (4) represents the situation after the last malloc.

So, we have an allocated block d that contains a freed chunk b. Supposing that it is possible to write arbitrarily in the allocated block d, we can overwrite the fw value of the chunk b. That is the main requirement to apply tcache poisoning.

The tcach bin for the size 0x28 (b size) is empty. Let's put a chunk inside it:

...
uint8_t *pad = malloc(0x28);
free(pad);
...

Now we can modify the value of the fw field of b (the poisoning):

...
d[6] = (long) stack_var;
...

To conclude, as described in the recap of tcache poisoning, we performs two malloc calls.

...
malloc(0x28);
intptr_t *e = malloc(0x28);
...

The value of e will be equal to stack_var!

General overview

The following picture shows a general overview of House of Einherjar:

Highlights

1. Allocate a, b, c and prepare a fake chunk in a.
2. Modify the prev_size of c and use an off-by-one overflow to write a NULL byte in the prev in use flag of c.
3. Free c to trigger the consolidation phase.
4. Allocate d.
5. Use d to write the fw field and apply tcache poisoning.
6. Perform 2 malloc calls.

Conclusion

Did you understand House of Einherjar? Yes, now you did.

Additional Resources

• https://github.com/st4g3r/House-of-Einherjar-CB2016
• http://phrack.org/issues/66/10.html

tags: heap exploitation tutorials security binary exploitation house of einherjar tcache poisoning shellphish