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