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によりglibcsafe 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であれば修正パッチを送ると開発者コミュニティの求める方法で報告すると喜ばれるかもしれません。

関連リンク