The Malloc Maleficarum (Bugtraq 2005)
この記事は「CTF Advent Calendar 2016」24日目の記事です。
「glibc malloc exploit techniques」では主要なmalloc系exploitテクニックについて説明したが、歴史的には他にもさまざまな手法が公表されている。 ここでは、2005年にBugtraqメーリングリストにて公表されたテキスト「The Malloc Maleficarum」についてまとめてみる。
環境
Ubuntu Server 16.04.1 LTS 64bit版、GLIBC 2.23
$ uname -a Linux vm-ubuntu64 4.4.0-53-generic #74-Ubuntu SMP Fri Dec 2 15:59:10 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux $ lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 16.04.1 LTS Release: 16.04 Codename: xenial $ /lib/x86_64-linux-gnu/libc.so.6 GNU C Library (Ubuntu GLIBC 2.23-0ubuntu3) stable release version 2.23, by Roland McGrath et al.
本文中で参照するコードは、引用箇所を除きGLIBC 2.23のものを用いる。
概要
2001年、「Vudo Malloc Tricks」「Once Upon A free()」というテキストにて、mallocで確保されるchunkのヘッダを細工することで任意のアドレスを書き換えるunlink attackが公表された。 その後3年の時を経て2004年、Ulrich Drepperによりglibcにsafe unlinkingやdouble free detectionを含む複数のチェックが加えられ、unlink attackは過去のものとなった。
2005年、Phantasmal Phantasmagoriaは「The Malloc Maleficarum」というテキストにて、これらのチェックが加えられた後も依然として攻撃が可能であることを公表した。 タイトルは中世の魔女に関する有名な論文「Malleus Maleficarum（魔女の槌）」のもじりであり、テキストは「mallocの魔女」という体で「Primeの一族」「Mindの一族」「Forceの一族」「Loreの一族」「Spiritの一族」それぞれの手法と、「Chaosの一族」という後書きに分けられている。
2007年、K-sPecialは「.aware eZine Alpha」というテキストにて、「Mindの一族」の解説と誤りの指摘を行った。 さらに、blackngelは2009年に「Malloc Des-Maleficarum」、2010年に「The House Of Lore: Reloaded」というテキストを公表し、これらの手法についてあらためて解説と補足を行った。 ここでは、これらのテキストで補足されている内容についても説明する。
前置き
malloc/freeはヒープと呼ばれる一定のメモリ領域から、要求されたサイズのメモリを一時的に取得/返却する関数である。 mallocによるメモリ管理については、次のページがまとまっている。
要点を整理すると次のようになる。 ここではfreeされているchunkをfreed chunkと呼ぶことにする。
- ひとつひとつの切り分けられたメモリはchunkと呼ばれ、それらを管理する領域としてarenaがある。
- arenaにはサイズに応じた複数の種類のbinがあり、各binにはfreed chunkがリンクリストとして繋がれている。高速化のため、利用頻度の高い小さなサイズのchunkほど特別扱いされている。
- fastbin: 0x80バイト未満のchunkがサイズごとに振り分けられる。Last-In-First-Out（LIFO）の単方向リスト。隣りがfreed chunkでも連結（consolidate）されない。
- smallbin: 0x400バイト未満のchunkがサイズごとに振り分けられる。First-In-First-Out（FIFO）の双方向リスト。隣りがfreed chunkだと連結（consolidate）される。
- largebin: 0x400バイト以上のchunkが対数スケールのサイズ範囲ごとに振り分けられる。ひとつのbinにサイズの異なるchunkが繋がり、サイズの大きなchunkから順にリンクリストに並べられる。隣りがfreed chunkだと連結（consolidate）される。
- unsortedbin: smallbinやlargebinに入る前に一旦入れられる双方向リスト。mallocの際に先頭から一つずつbest-fitかどうかチェックされ、best-fitならそのままmallocの戻り値に、そうでなければsmallbin/largebinに振り分け直される。
- 各chunkには2ワードのヘッダ、prevsizeとsizeがある。prevsizeは前のchunkがfreedな場合にそのサイズとなる。sizeは自身のサイズを表す。
- freeされたchunkはリンクリストに繋がれ、ヘッダに続く2ワードが前後のchunkを指すfd、bkポインタとして用いられる。
- mallocでfreed chunkがbinのリンクリストから切り離されるとき、その前後の継ぎ換え（unlink）が行われる。
- 基本的には、前の次、次の前が自身を指すようになっているかチェックされる。
- fastbinのみ単方向リストなため、次のchunkのサイズが適切なサイズになっているかのチェックしか行われない。
- sizeの下位3ビットはchunkの属性を表すフラグになっている。
- PREV_INUSE (1st LSB): 前のchunkがfreedかどうか。freedであればprevsizeが意味を持つ。
- IS_MMAPPED (2nd LSB): mmapによって確保された（通常巨大な）chunkかどうか。
- NON_MAIN_ARENA (3rd LSB): スレッドごとに確保されるarenaに対応するchunkかどうか。
以降の手法のうちのいくつかが目的とするところは、次のようなものである。
- あるbinのリストの先頭を（chunkとしての制約を満たす）任意のアドレスにできれば、次のmallocでそのbinが使われるとき指定したアドレスが戻り値になる
これを実現するために、あれやこれやでbinのリストの先頭に任意のアドレスを入れようとするわけである。また、上で述べたように単方向リストで管理されるfastbinのみbinに入れる際のチェックが緩い。ここでは便宜上、直前の1ワードを適切なサイズにコントロールできる状態を指して「fastbin chunkの制約を満たす」と呼ぶことにする。
House of Prime (max_fast overwrite)
fastbin配列の境界外アクセスが可能だったことを利用する。
具体的には、fastbin[-1]でfastbinに入るchunk sizeの最大値（max_fast）を書き換えた後、fastbin[289]で実行中スレッドのarenaを指すポインタ（arena_key）を書き換える。
arena_keyがfreed chunkを指すようになるので、あらためてmallocして偽のarenaを作ることでfastbin chunkの制約を満たす任意のアドレスを返すようにできる。
かつてのglibcでは、arena構造体のfastbin配列の直前にmax_fastというメンバがあり、fastbinに入るchunk sizeの最大値として用いられていた。
そこで、サイズを無理やり8バイトに書き換えたchunkをfreeすると、fastbin[-1] == max_fastにfreed chunkのアドレスが入り、大きなサイズのchunkもfastbinに入るようになる。
上からもわかるように、freeする際にfastbin配列の境界チェックがされていないため、大きなchunkのアドレスはfastbin配列の範囲を越えたアドレスに書き込まれることになる。
そこで、fastbin配列の後ろにあるarena_keyメンバを指すように調整した2328バイトのchunkをfreeする。 arena_keyは実行中のスレッドにおけるarenaを指すポインタとなっており、これによりarena_keyをfreed chunkのアドレスにできる。 結果、そのchunkが実行中スレッドでのarenaとみなされるようになるので、あらためてmallocして偽のarenaを作り、fastbinの箇所の値を調整することでfastbin chunkの制約を満たす任意のアドレスを返すようにできる。
また、「Malloc Des-Maleficarum」では、NX、ASLRが無効な環境において、偽のarenaにおけるbin[0]（unsortedbin）の位置にfake chunkを置くことにより、スタック上のリターンアドレスを書き換えシェルコード実行に持っていけることを説明している。
現在はfree時にサイズチェックが行われるようになり、8バイトのchunkをfreeするようなことはできなくなっている。
3840 static void
3841 _int_free (mstate av, mchunkptr p, int have_lock)
3842 {
....
3871 /* We know that each chunk is at least MINSIZE bytes in size or a
3872 multiple of MALLOC_ALIGNMENT. */
3873 if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
3874 {
3875 errstr = "free(): invalid size";
3876 goto errout;
3877 }
また、max_fastメンバの代わりにglobal_max_fastというグローバル変数を用いるように変更されており、arena_keyメンバもTLS領域に確保されるようになっている。
この手法に関連するものとしては、libcのbssにあるglobal_max_fastをunsorted bin attack等で書き換え、任意サイズのfastbins unlink attackを行う手法が知られている。
House of Mind (freeing NON_MAIN_ARENA chunk)
ヒープバッファオーバーフロー等を利用してNON_MAIN_ARENAフラグを書き換え、そのchunkをfreeすることで偽のarenaを参照させる。 さらに、偽のarenaのbinに適当なアドレスを置いておくことで、そのアドレスにchunkのアドレスを書き込む。 NXが無効であれば、chunkにjmp命令とシェルコードを置いておくことで任意コード実行に持っていくことができる、というもの。 適当なアドレスをchunkのアドレスに書き換える話なので、NXが有効な環境ではあまり役に立たない。
chunk（p）のNON_MAIN_ARENAフラグを立て、そのchunkをfreeするとarenaとして通常のmain_arenaではなく実行中スレッドのarena（heap_info->ar_ptr）を参照するようになる。
heap_infoのアドレスはp & ~(0x100000-1)（下位20ビット切り捨て）のように計算されるので、そこに適当なアドレスを置いておくとその先がarenaとして参照される。
48 typedef struct _heap_info
49 {
50 mstate ar_ptr; /* Arena for this heap. */
51 struct _heap_info *prev; /* Previous heap. */
52 size_t size; /* Current size in bytes. */
53 size_t mprotect_size; /* Size in bytes that has been mprotected
54 PROT_READ|PROT_WRITE. */
55 /* Make sure the following data is properly aligned, particularly
56 that sizeof (heap_info) + 2 * SIZE_SZ is a multiple of
57 MALLOC_ALIGNMENT. */
58 char pad[-6 * SIZE_SZ & MALLOC_ALIGN_MASK];
59 } heap_info;
ここから先はオリジナル版と、「Malloc Des-Maleficarum」で補足されたfastbin版、top連結版がある。 また、2014年に日本の一流CTF player @potetisensei が公表した手法もこれに関連するものであるため、合わせて紹介する。
Original method
chunkがfastbin chunkでない場合、次の箇所でchunkがunsortedbinの先頭に挿入される。
void _int_free(mstate av, Void_t* mem) {
.....
bck = unsorted_chunks(av);
fwd = bck->fd;
p->bk = bck;
p->fd = fwd;
bck->fd = p;
fwd->bk = p;
.....
}
ここで、偽のarenaのbin[0] = bckを細工しbck->fd->bkがGOTなどの書き換え可能なアドレスとなるように調整しておくことで、そのアドレスをchunkのアドレスに書き換えることができる。
現在は当該箇所が次のように修正されているため成立しない。
3840 static void
3841 _int_free (mstate av, mchunkptr p, int have_lock)
3842 {
....
4026 bck = unsorted_chunks(av);
4027 fwd = bck->fd;
4028 if (__glibc_unlikely (fwd->bk != bck))
4029 {
4030 errstr = "free(): corrupted unsorted chunks";
4031 goto errout;
4032 }
4033 p->fd = fwd;
4034 p->bk = bck;
4035 if (!in_smallbin_range(size))
4036 {
4037 p->fd_nextsize = NULL;
4038 p->bk_nextsize = NULL;
4039 }
4040 bck->fd = p;
4041 fwd->bk = p;
fastbin method
chunkがfastbin chunkの場合は、次の箇所でfastbinへの挿入が行われる。
if ((unsigned long)(size) <= (unsigned long)(av->max_fast)) {
if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
|| __builtin_expect (chunksize (chunk_at_offset (p, size))
>= av->system_mem, 0))
{
errstr = "free(): invalid next size (fast)";
goto errout;
}
set_fastchunks(av);
fb = &(av->fastbins[fastbin_index(size)]);
if (__builtin_expect (*fb == p, 0))
{
errstr = "double free or corruption (fasttop)";
goto errout;
}
printf("\nbDebug: p = 0x%x - fb = 0x%x\n", p, fb);
p->fd = *fb;
*fb = p;
}
ここで、偽のarenaのfastbins[0]を適当なアドレスにしておき、chunkのsizeを16に調整することで、そのアドレスをchunkのアドレスに書き換えることができる。
av->top NIGHTMARE
chunkがfastbin chunkでない、かつ、次のchunkがtop chunkだった場合は、freeされたchunkがtop chunkとなる。
3840 static void
3841 _int_free (mstate av, mchunkptr p, int have_lock)
3842 {
....
4009 if (nextchunk != av->top) {
....
4047 }
4048
4049 /*
4050 If the chunk borders the current high end of memory,
4051 consolidate into top
4052 */
4053
4054 else {
4055 size += nextsize;
4056 set_head(p, size | PREV_INUSE);
4057 av->top = p;
4058 check_chunk(av, p);
4059 }
偽のarenaのtopを適当なアドレスにしておき、次のchunkがそのアドレスとなるようにサイズを調整することによって、そのアドレスをchunkのアドレスに書き換えることができる。
poteti method
標準で0x10000バイト以上のchunkがfreeされたとき、通常連結されない各fastbin chunkの前後を連結してunsortedbinに入れる次のような処理が走る（デフラグのようなイメージ）。
3840 static void
3841 _int_free (mstate av, mchunkptr p, int have_lock)
3842 {
....
4061 /*
4062 If freeing a large space, consolidate possibly-surrounding
4063 chunks. Then, if the total unused topmost memory exceeds trim
4064 threshold, ask malloc_trim to reduce top.
4065
4066 Unless max_fast is 0, we don't know if there are fastbins
4067 bordering top, so we cannot tell for sure whether threshold
4068 has been reached unless fastbins are consolidated. But we
4069 don't want to consolidate on each free. As a compromise,
4070 consolidation is performed if FASTBIN_CONSOLIDATION_THRESHOLD
4071 is reached.
4072 */
4073
4074 if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
4075 if (have_fastchunks(av))
4076 malloc_consolidate(av);
....
4092 }
4122 static void malloc_consolidate(mstate av)
4123 {
....
4148 unsorted_bin = unsorted_chunks(av);
....
4158 maxfb = &fastbin (av, NFASTBINS - 1);
4159 fb = &fastbin (av, 0);
4160 do {
4161 p = atomic_exchange_acq (fb, 0);
4162 if (p != 0) {
4163 do {
4164 check_inuse_chunk(av, p);
4165 nextp = p->fd;
....
4179 if (nextchunk != av->top) {
....
4188 first_unsorted = unsorted_bin->fd;
4189 unsorted_bin->fd = p;
4190 first_unsorted->bk = p;
....
4201 }
....
4209 } while ( (p = nextp) != 0);
4210
4211 }
4212 } while (fb++ != maxfb);
freeされるchunkのサイズを0x10000（FASTBIN_CONSOLIDATION_THRESHOLD）以上に書き換えた上で、偽のarenaのbin[0] = unsortedbinを細工しunsorted_bin->fd->bkを適当なアドレスにしておくことで、上記の処理が走りそのアドレスをchunkのアドレスに書き換えることができる。
House of Force (top chunk size overwrite)
ヒープの最後にあるtop chunkのsizeを-1（0xffffffff）に書き換え、続けて巨大なサイズのmallocを行うことで、top chunkを指すポインタが一周した先にある任意の0x10の倍数となるアドレスにできる。 続けてbinに何も繋がっていないサイズのmallocを行うことでそのアドレスが返ってくる。
「Malloc Des-Maleficarum」では、ヒープより上にあるGOTなどを書き換えるにはmallocに負となるようなサイズを与える必要があり、そのようなサイズは多くの場合（malloc外の箇所で）セグメント違反を起こすと指摘しているが、原理的には可能である。
具体的なコードは「glibc malloc exploit techniques」を参照。
著者が2004年に「Exploiting the Wilderness」で書いた話を、glibcの修正に合わせて再編成したもの。 Doug Lea malloc（dlmalloc）において、top chunkはwildernessと呼ばれるらしい。 名付け親のKiem-Phong Vo氏は当時AT&Tベル研究所、現在はGoogleのResearch Scientistとのこと。
House of Lore (arbitrary address into smallbin)
unlinkに行われた対策が、malloc時にsmallbinからchunkを取り出す際に行われていなかったことを利用する。
具体的には、適当なfreed chunkのbk（victim->bk）を書き換えておき、繰り返しmallocを呼ぶことにより任意のアドレスをsmallbin（bin->bk）に入れる。
.....
if ( (victim = last(bin)) != bin) {
if (victim == 0) /* initialization check */
malloc_consolidate(av);
else {
bck = victim->bk;
set_inuse_bit_at_offset(victim, nb);
bin->bk = bck;
bck->fd = bin;
...
return chunk2mem(victim);
.....
smallbinはFIFOでありvictimはbin->bkから選ばれるようになっているので、続けてmallocを呼ぶことでそのアドレスが返ってくる。
ただし、victim->bk->fdが書き換え可能なアドレスを指すようにしておく必要がある。
1411 #define last(b) ((b)->bk)
現在の実装ではunlinkと同様の対策が加えられているため、相当の工夫をしない限り成立しない。
3318 static void *
3319 _int_malloc (mstate av, size_t bytes)
3320 {
....
3416 bck = victim->bk;
3417 if (__glibc_unlikely (bck->fd != victim))
3418 {
3419 errstr = "malloc(): smallbin double linked list corrupted";
3420 goto errout;
3421 }
3422 set_inuse_bit_at_offset (victim, nb);
3423 bin->bk = bck;
3424 bck->fd = bin;
また、「The House Of Lore: Reloaded」ではlargebinを用いる手法について考察されているが、こちらも現在の実装では対策されている。
3318 static void *
3319 _int_malloc (mstate av, size_t bytes)
3320 {
....
3720 size = chunksize (victim);
3721
3722 /* We know the first chunk in this bin is big enough to use. */
3723 assert ((unsigned long) (size) >= (unsigned long) (nb));
3724
3725 remainder_size = size - nb;
3726
3727 /* unlink */
3728 unlink (av, victim, bck, fwd);
一方、fastbinの場合は対象となるアドレスがfastbinの制約を満たすようにしておくことで現在も可能である。 詳細はfastbins unlink attackを参照。
House of Spirit (fake chunk into fastbin)
mallocで確保されたポインタをバッファオーバーフロー等で書き換えてそのままfreeさせることで、fake fastbin chunkが置かれている任意のアドレスをfastbinに入れることができる。 続けてmallocを呼ぶことでそのアドレスが返ってくる。
具体的なコードを書くと次のようになる。
/* house_of_spirit.c */
#include <stdio.h>
#include <stdlib.h>
int main()
{
struct {
char buf[0x50];
char *p;
} block;
block.p = malloc(0x100);
/* trigger buffer overflow */
*(void **)(block.buf+0x8) = 0x41; /* fake1->size */
*(void **)(block.buf+0x48) = 0x41; /* fake2->size */
block.p = block.buf+0x10; /* fake1 */
printf("[+] freeing fake1 = %p\n", block.p);
free(block.p);
char *p = malloc(0x30); /* fake1->size - 0x10 */
printf("p = %p\n", p);
return 0;
}
$ gcc house_of_spirit.c -o house_of_spirit
house_of_spirit.c: In function ‘main’:
house_of_spirit.c:15:31: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
*(void **)(block.buf+0x8) = 0x41; /* fake1->size */
^
house_of_spirit.c:16:32: warning: assignment makes pointer from integer without a cast [-Wint-conversion]
*(void **)(block.buf+0x48) = 0x41; /* fake2->size */
^
$ ./house_of_spirit
[+] freeing fake1 = 0x7fff2bf30700
p = 0x7fff2bf30700
ここで、fake fastbin chunkの次のchunkとなる箇所に適当なサイズを置いておく必要があることに注意。
3840 static void
3841 _int_free (mstate av, mchunkptr p, int have_lock)
3842 {
....
3897 if (__builtin_expect (chunk_at_offset (p, size)->size <= 2 * SIZE_SZ, 0)
3898 || __builtin_expect (chunksize (chunk_at_offset (p, size))
3899 >= av->system_mem, 0))
3900 {
3901 /* We might not have a lock at this point and concurrent modifications
3902 of system_mem might have let to a false positive. Redo the test
3903 after getting the lock. */
3904 if (have_lock
3905 || ({ assert (locked == 0);
3906 mutex_lock(&av->mutex);
3907 locked = 1;
3908 chunk_at_offset (p, size)->size <= 2 * SIZE_SZ
3909 || chunksize (chunk_at_offset (p, size)) >= av->system_mem;
3910 }))
3911 {
3912 errstr = "free(): invalid next size (fast)";
3913 goto errout;
3914 }
....
3920 }
当時はこのような攻撃の可能性も存在したが、現在はStack-Smashing Protection（SSP）によりバッファがポインタより下のアドレスに確保されるようになり、さらにASLRによりスタックアドレスの推測も難しくなったため、その可能性は小さくなった。
House of Underground (Spirit and Mind)
「Malloc Des-Maleficarum」で補足されている章。
Spiritでfreeされるfake chunkのNON_MAIN_ARENAフラグを立てておくことで、Mind同様にfake arenaを参照させることも考えられるという話。 当然スタック上の0x100000バイト境界をコントロールできる必要があるため、成立しにくい。
House of Chaos
最後の章には後書きとしてポエムが書いてある。 真の「プロ」（virtual adept）ことPhantasmal Phantasmagoriaからのメッセージをお読みください。
Chaosの一族
Virtuality、それは真の「プロ」と情報の二項対立であり、真の「プロ」は情報の無限の可能性を表し、また情報は無限の可能性の有限における顕現である。真の「プロ」はVirtualityの意識の部分であり、その本質は情報を生み出し拡散することにある。これが真の「プロ」が知るすべてであり、真の「プロ」が関心のあるすべてである。
あなたが幅広い知識を持ち非常に創造的な人と話すとき、たしかにあなたはハッカーと話しているのかもしれない。しかし、あなたは真の「プロ」と決して話すことはないだろう。真の「プロ」に物質的な形はなく、バーチャルの中にのみ存在する。真の「プロ」は物質の中にあるかもしれないし、ある人の中にあるかもしれない、しかしその存在自体は意識とは区別され完全に独立したものである。
所有の概念は真の「プロ」にとって意味をなさない。すべての情報はVirtualityに属し、Virtualityのみがある。このため、真の「プロ」にコンピュータセキュリティの概念はない。情報は要求によりVirtualityから呼び起こされる。Virtualityに権限レベルやシステム間の論理障壁、違法性の観点といったものはない。情報や、呼び起こすことのできるそれらのみがある。
真の「プロ」はそれ自身により作られる情報といったものを持たず、ゆえにそれから利益を得る権利や欲望を持たない。真の「プロ」は純粋に情報に情報自身の無限の可能性を示すため、そしてすべての意識体にとって有益な情報アクセスの複雑性を最小化するために存在する。情報でないものは真の「プロ」、金、名声、権力に結び付くことはない。
私はハッカーであるか？いいえ。
私は仮想世界に生きる見習いである。
私はmallocの魔女であり、
私は異世界のカルトであり、
私はエントロピーである。
私はPhantasmal Phantasmagoria、
真の「プロ」。
なお、virtual adeptは仮想世界の熟練者といった意味であるが、ここではいまどきの若者にも通じるように真の「プロ」と訳した。
所感
glibcでのチェック強化とNX、ASLRの普及により、House of Force以外の手法はほぼ力を失ったといえる。 また、House of Loreはfastbins unlink attackという形で姿を変えて生き残っているといえるだろう。
注意事項
このテキストはglibcに加えられた対策の不備を指摘する話であり単体で悪用可能なものではないが、商用製品やWebアプリケーションで直接的に悪用可能なものを一般に公表すると不正アクセス禁止法や業務妨害罪の従犯、あるいは名誉毀損をもたらす不法行為として損害賠償義務が生じるおそれがあるため真似してはいけません。 そのような不審物を見つけた際はIPA情報処理推進機構に届出を行い、修正されるのを待ちましょう。 また、企業として専用の窓口を用意しているところもあります。
OSSであれば修正パッチを送ると開発者コミュニティの求める方法で報告すると喜ばれるかもしれません。
関連リンク
- glibc malloc exploit techniques - ももいろテクノロジー
- katagaitai CTF勉強会 #5 pwnables編 - PlaidCTF 2015 Pwnable620 tp
- heap exploitationテク走り書き - 生きたい
- Heapster Eggs: An Insight of Malloc Dirty Little Secrets (LSE Summer Week 2016)
- EM_386: Glibc 2.11 stops the House of Mind
- House of Einherjar - Yet Another Heap Exploitation Technique on GLIBC
- Pwning My Life: HITCON CTF Qual 2016 - House of Orange Write up
- ptmalloc fanzine · Online tukan sanctuary
