realloc-baseのmemory corruptionの古い小ネタと最近のtcache周りの小話

イントロ

最近、CTF を完全に辞めて、競プロをやることにしました。前から競プロできるひとかっこいいなぁと思っていたのですが、直接の動機はこの前の HITCON の問題でした。ここでダイクストラを使ったカーネルモジュールが出題されたのですが、アルゴリズム全然知らんマンなのでやる気がなくなってコードが読めませんでした。もともと数学は誇張抜きに小学 3 年生くらいしかできない(小学校は大部分行ってなかったので実質幼稚園並にしかできない)ので、それを克服するためにも頑張りたいです。 さてさて、ということで、今回はreallocを使った tcache double-free に関する小さいお話を少し。かなり古いネタですが備忘録的に書き残しておきます。 また、最近 glibc にちょっとしたパッチを送ったのを契機に glibc のメーリスを読むようになったので、そこで議論になっていた tcache の小ネタを書きます。 (今までブログは丹精込めて HTML をベタ書きしていたのですが、流石にめんどくさくなったので今回からブログの CSS 似合うような MD->HTML コンバータを作って MD で書いています。)

概要

小学校で既に教わっていると思いますが、glibc 2.29 以降では tcaceh に key というメンバが加わっています。 malloc() する際にはここに tcache(tcache_per_thread構造体の方) の値が書き込まれ、free() 時にこのアドレスに tcache のアドレスが入っていれば memory corruption としてエラーにするというやつですね。というわけで最近の glibc においては単純に二回続けて free() することで double-free を起こすということはできなくなっています。

但し、realloc() の場合には条件が揃うと簡単に tcache を用いて memory corruption を引き起こすことができます。具体的には、以下の 2 つのことができます。

1. 複数の chunk を異なるサイズの tcache に繋ぐことができる。(size-confusion)
2. 1 を用いて隣接する chunk を overwrite できる。 (memory corruption)

realloc 復習

そもそもにreallocがどういう挙動をするのか少し復習してみましょう。realloc の処理は、__libc_realloc() と _int_realloc() に大別されます。malloc/free と異なり、__libc_realloc() の方でも割とガッツリ処理が行われます。

__libc_realloc() においては、まず __realloc_hook を確認します。最初の段階ではここには realloc_hook_ini() のアドレスが入っており、内部で tcache の初期化及びフックの初期化を行います。(因みに、ここでは __realloc_hook だけでなく __malloc_hook もクリアされます)。

そのあとで、要求されたsizeが 0 である場合には __libc_free() を呼びます。普通に free()を呼んだ時と挙動の違いは全くありません。また、渡されたポインタが NULL であった場合には __libc_malloc() を呼びます。これも、通常通り malloc を呼ぶのと diff は全くありません。マルチスレッドである場合には、このあと同一関数内で全ての処理を行ってしまいます。シングルスレッドの場合には _int_realloc() に進みます。

_int_realloc() では要求されたサイズと現在の chunk のサイズに応じて処理が分岐します。 現在のサイズよりも要求サイズが大きい場合には、まず top から不足分を切り出そうと試みます。top に隣接している場合には top を下げるだけで終わりです。また、隣接 chunk と合併できるなら合併します。それもできない場合には、新たに _int_malloc() を読んで内容を memcpy() した後古い方の chunk を _int_free() します。合併を行った場合に要求サイズよりも大きくなってしまった場合は、残りの chunk にヘッダをつけて _int_free() を呼び出します。尚、残りの chunk のサイズが MINSIZE を下回る場合には新たな chunk にできないため諦めてヘッダだけつけて終わります。(つまり、どの bin にも繋がれず、top にも含まれていない完全に浮いた chunk ができあがります、合ってるよね??)。

要求サイズが以前の chunk よりも小さい(若しくは等しい)場合には、単純にヘッダを書き換えた後、残りの chunk を上と同様にして再利用を試みます。

細かい分岐はありますが、概ね realloc の処理はこんな感じです。

どうやるか

本題(といっても小さい話だけど)。

ここでは、任意サイズの chunk を realloc() できるような状況を考えてみましょう。加えて free() もできるがフリーの後は保持しているポインタがクリアされて参照できなくなってしまうとします。(edit 機能はなくてもいいです。あったら楽になります。というか、この方法をわざわざ使うまでもなく tcache-poisoning して終わりです。) このような状況のときには、realloc(ptr, 0) とすることでポインタをクリアすることなく free() ができるというのはすぐに思いつくと思います。UAF ができあがるため、double-free もできますが、した瞬間に最初に述べた key による検知で死んでしまいます。

さて、最初に「free() 時に key に tcache のアドレスが入っていると死ぬ」と言いましたがあれは嘘です。実際には key に tcache のアドレスが入っていることを検知すると tcache の linked-list の全探索が始まります。この中に現在 free しようとしている chunk が既に入っていた場合に限って abort されることになります。重要なこととして、この key によるdouble-free 検知の全探索は同一サイズの chunk にしか行われません。そのため、一度 free した chunk を別のサイズとして free した場合には全探索の結果として正常と判断されエラーが発生しません。

実際の操作の例としては、最初に 0x80 の chunk を realloc() した後 realloc(0) をすることでポインタを保持したまま free をします(UAF)。これによって chunk は 0x90 の tcache に繋がれます。このあと、同一 chunk に対して realloc(0x20) をします。すると、上述した処理によって chunk は 0x30 サイズのものと 0x60 サイズのものに分割されます。この際、保持しているポインタが指す chunk の方のヘッダは 0x90 から 0x30 に書き換えられます。この後で realloc(0) 若しくは free() を行うと、保持していた chunk が 0x30 の tcache に繋がれます。このときには key の値に 0x90 として free した時に書き込まれた値が残っているため tcache の全探索が始まりますが、この chunk は 0x90 の tcache には繋がれているものの 0x30 には繋がれていないためエラーは発生しません。これで、同一の chunk が 0x90 と 0x30 の両方の tcache に繋がれたことになります。

しかも、実際のメモリのレイアウト的にはこの chunk は 0x30 の chunk です。このあとで 0x90 サイズの chunk をとると、0x30 サイズの chunk を 0x90 として取ったことになり、alloc 時の書き込み機能が有るならばコレによって隣接する chunk に対して 0x60 分だけ overwrite することができるようになります。

以上!!!

tcache の free 時の infinite-loop

小話。せっかく tcache の free における全探索の話が出たので。

もともと tcache はユーザランドにおける小さなメモリ領域の利用を高速化するために glibc2.27 で実装されたもので、速さのためにセキュリティチェックを甘くしてあります。これによって一昔前の CTF では tcache に UAF さえあればもう終わりみたいな強力なものになっていました。最近では、上述した double-free チェックや、glibc2.32 から実装される linked-list encryption(safe unlinking)によりちょっとずつ exploit の難易度が増してきています。

上の全探索はその経緯で実装されたものであり、一見すると同一サイズのリストだけでなく全サイズを探索してしまえば良いように思えますが、tcache が実装された目的である速度のオーバーヘッドのために同一サイズだけをチェックしているという経緯があります。

さて、この全探索ですが、探索の終わりの基準が「次の chunk へのポインタ(fd)が NULL である」ということしかありません。

これが何を意味するかと言うと、仮にtcache の linked-list 内に circular linked-list が出来上がっていた場合、探索が終わることがなく infinite-loop に陥ってしまいます。 このような endless-loop を引き起こすような PoC は以下のとおりです。(ver 2.32 用にポインタを encrypt しています.)

 1#include<stdio.h>
 2#include<stdlib.h>
 3
 4unsigned long protect_ptr(unsigned long pos, unsigned long ptr){
 5  return (pos>>12) ^ (ptr);
 6}
 7
 8int main(void)
 9{
10  char *a,*b,*c;
11  a = malloc(0x50);
12  b = malloc(0x50);
13  c = malloc(0x50);
14  free(a);
15  free(b);
16
17  *(unsigned long*)(b) = (unsigned long*)protect_ptr(b, b);
18  ((unsigned long*)c)[1] = ((unsigned long*)a)[1];
19  free(c);
20
21  return 0;
22}

これを実行すると最後の free において tcache の全探索が走り、永遠に同じ chunk を回り続けるためプログラムがハングします。

tcache は管理構造体(tcache_per_thread)において現在保持している tcache の個数をカウントしていますが、これは tcache から chunk を取れるかどうかと、tcache に chunk を put できるかどうかという判定にしか使われていないため、chunk の最大保持数(7)を超えてもループは回り続けます。

考えてみれば当たり前のことではあります。しかし、僕がある日競プロの問題を解いていて後少しでシェルが取れるという時にこのハングが起こりました。すぐにはこのループが原因であることが思いつかずに、他の原因を探して 30 分ほど無駄にしてしまいました。これはあってはならないことです。

というわけで、全探索のループに上限を定めるように glibc にパッチを送りました。そもそもにこのようなことが起きるのは既に memory corruption が発生した後であり、影響としてもプログラムが止まるだけなので大した影響はありません。しかし、30 分を浪費したことが許せなかったため、DoS attack に繋がり得るという理由をでっちあげて Bugzilla にファイリングし、ML という面倒くさい手続きを踏んで修正しました。(たかだか数行のパッチになんでこんなにめんどいねん)

というわけで、修正後の現在の master においては上のプログラムを実行すると以下のようになります。

なんと分かりやすいエラーメッセージ!!! これで次から競プロ中に思わぬ memory corruption でループが発生して時間を費やす時間がなくなったね！

tcache の更なる強化

そんなこんなで glibc の ML に目を通すことが日課になったのですが、そのなかで以下のような tcache の強化がリクエストされていました。

• https://sourceware.org/pipermail/libc-alpha/2020-December/120653.html

以下引用です。

Hmm… OK, I think I get it. It’s not the ’e’ we know, its the ’e’ from the previous call to tcache_get(). So basically, when we remove a chunk from the tcache, we want to validate the pointer we’re leaving behind?

 1 static __always_inline void *
 2 tcache_get (size_t tc_idx)
 3 {
 4   tcache_entry *e = tcache->entries[tc_idx];
 5   if (__glibc_unlikely (!aligned_OK (e)))
 6     malloc_printerr ("malloc(): unaligned tcache chunk detected");
 7   tcache->entries[tc_idx] = REVEAL_PTR (e->next);
 8+  /* Validate the pointer we're leaving behind, while we still know
 9+     where it came from, in case a use-after-free corrupted it.  */
10+  if (tcache->entries[tc_idx])
11+    * (volatile char **) tcache->entries[tc_idx];
12   --(tcache->counts[tc_idx]);
13   e->key = NULL;
14   return (void *) e;
15 }

代入するわけでもなく、変更するわけでもなく、ただ tcache にアクセスするだけの行が tcache_get() に追加されています。端的に言うと、このパッチが当てられると tcache から chunk を取る時に、取る対象の tcache だけでなく、その次の tcache のアドレスも関なものでなくてはならないようになります。

これが迷惑になる例としては、例えばleak-lessな状況でtcache-poisoningによって stdout を書き換えたいというようなときに、stdout 直上に chunk を取った後の linked-list には stodut.flag の値が入ります。この時使った chunk と同じサイズの chunk をどうしても使いたいという場合には同一サイズの chunk を free して繋いだ後もう一回 alloc することに鳴ると思いますが、このとき取得する chunk の次の chunk(つまり取得する chunk の fd)は stdout->flag の値(0xFBAD2084とか)であり大抵のプロセスの場合不正なアドレスであるため、死ぬことになってしまいます。

まぁ、これ自体は大した変更ではないし害になるようなものではないですね。けど、tcache が速さ目的で実装されたもののはずなのに、どんどんセキュリティ機構をもりもりにしていっています。だったら tcache 辞めちゃえばいいのにね。嘘です。ごめんね。

アウトロ

というわけで、realloc-base の size-confusion の話と、tcache 周りの小話でした。 tcache に限らず、どんどん heap 周りの exploit は難しくなっています。

だから僕は、pwn を、辞めた。 (ヨルシカ風)

参考

• ニルギリ: https://www.youtube.com/watch?v=yvUvamhYPHw
• ほのぼの: https://blog.hideo54.com/archives/1020