---
# System prepended metadata

title: Did you understand House of Einherjar?
tags: [binary exploitation, tcache poisoning, heap exploitation, house of einherjar, shellphish, security, tutorials]

---

# Did you understand House of Einherjar?
## Prerequisites
* Do you know the C language? No -> Maybe it's too early to read this article :man-shrugging:
* Do you know what is the difference betweek stack and heap? No -> [go here](https://www.guru99.com/stack-vs-heap.html)!
* Do you know what is a buffer overflow? No -> [go here](https://en.wikipedia.org/wiki/Buffer_overflow)!
* Do you have a basic knowledge of malloc internals? No -> [go here](https://azeria-labs.com/heap-exploitation-part-1-understanding-the-glibc-heap-implementation/) and then [here](https://azeria-labs.com/heap-exploitation-part-2-glibc-heap-free-bins/)!
* Do you know the tcache poisoning technique? No -> [go here](https://github.com/shellphish/how2heap/blob/master/glibc_2.31/tcache_poisoning.c)!

## 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](https://github.com/shellphish/how2heap) by shellphish: one of the best resource about heap exploitation 
* [malloc.c](https://sources.debian.org/src/glibc/2.32-1/malloc/malloc.c) source code (glibc 2.32)
* [heappy](https://github.com/gand3lf/heappy): a tool to visualize and compare snapshots of heap


## Let's go!
Let's start considering the [code](https://github.com/shellphish/how2heap/blob/master/glibc_2.31/house_of_einherjar.c) offered by shellphish.
This is the first snippet:
```c
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](https://sources.debian.org/src/glibc/2.32-1/malloc/malloc.c/#L1471) 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.
```c
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 :heavy_check_mark:
* bk->fd != p -> **false**: of course, the next node of the previous node of the fake chunk is the fake chunk itself :heavy_check_mark:

The heap snapshot in this moment is described by the left column below:
<center>
<img src="https://i.imgur.com/9xiAxGb.png" width="500">
</center>

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. 
```c
...
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 :wink:)_
```c
...
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](https://sources.debian.org/src/glibc/2.32-1/malloc/malloc.c/#L321) avaliable, thus to target the correct bin it is sufficient to use the same size of **c** (_0xf8_).
```c
...
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.

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

At this point we have all the elements to apply the **tcache poisoning** attack.:smiling_imp:🧪

:books: \[ Recap about tcache bins and the related poisoning \] :books:

> * 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.

<center>
<img src="https://i.imgur.com/mCtnH3I.png" width="500">
</center>

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:
```c
...
uint8_t *pad = malloc(0x28);
free(pad);
...
```
Now we can modify the value of the _fw_ field of **b** (the poisoning):
```c
...
d[6] = (long) stack_var;
...
```
To conclude, as described in the recap of tcache poisoning, we performs two malloc calls.
```c
...
malloc(0x28);
intptr_t *e = malloc(0x28);
...
```
The value of **e** will be equal to **stack_var**! :tada:

## General overview

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

<center>
<img src="https://i.imgur.com/K8cYVti.png">
</center>

:star: **Highlights** :star:
1. Allocate **a**, **b**, **c** and prepare a <ins>fake chunk</ins> in **a**.
2. Modify the prev_size of **c** and use an <ins>off-by-one overflow </ins> to write a NULL byte in the _prev in use_ flag of **c**.
3. Free **c** to trigger the <ins>consolidation phase</ins>.
4. Allocate **d**.
5. Use **d** to write the _fw_ field and apply <ins>tcache poisoning</ins>.
6. Perform 2 malloc calls.

## Conclusion
Did you understand House of Einherjar? Yes, now you did. :punch:

## 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`