https://qiita.com/howmuch515/items/b86f7341c574edcbc717#war
こちらに上級者によるWriteupがあるので私が書くまでもないのですが…picoCTFのこの問題で手こずる初心者(=私)にはわかりにくいところがあるので説明をメモします
調査
まず問題文に”Connect on shell2017.picoctf.com:15646.”とありますがpicoCTFのサイトで用意されているシェルではtelnetコマンドが使えないのでncコマンドを使います。ncコマンドは多分どこでも使えるので、ncコマンドを使うのが普通みたいです
で、ちょっとプレイすると勝てないらしいことがわかります。
ソースコードを見ると、プレイヤーが勝った場合に表示する文に「あれ?勝った?おかしいな…」旨の文章が書いてあり、勝てないように作ってあることがわかります。
ゲーム自体は、26枚のカードデッキが2人のプレイヤー(コンピュータと人間)に作られ、それのマーク(suit)と数字を比較し、強い方が勝ち…で、26枚全て使い切ると終わりということになっています。使い切ったらカードスイッチング(?)をする予定だが未実装、という表示が出ます。
26枚のデッキ2組は、毎回固定値で生成され、乱数でシャッフルするのですが、コンピュータ側のデッキはどのカードも人間プレイヤーのカードより強くなるように生成されているので絶対に勝てません。
構造体の中身
ここで、gamestate構造体の中身は、「人間プレイヤーのカード配列、char型name配列、deckSize変数、コンピュータプレイヤーのカード配列」の順に並んでいます。
name配列に値を受け取るときに使われるreadInput関数は、末尾のインデックス+1に’ x00′ (=null)を格納してしまうというバグ持ちです。本来は末尾のインデックス+0に’ x00’を格納すべきです。
よって、name配列の長さ32文字を入力すると、name配列の範囲+1バイト、つまりとなりのdeckSize変数に1バイトぶん’ x00’を書き込んでしまうことになります。
(しかし、deckSize変数はsize_t型であり、32bit環境では4バイト、64bit環境では8バイトにだいたいなるはずです。なぜ1バイトぶん、deckSize変数に0を書き込むとdeckSizeが0になってしまうかというと、メモリ上のバイト列の並び方がリトルエンディアンだからです。要は下位1バイトを全部0にしているというわけです。deckSize変数に入れられた値が26でなく下位1バイトで表現しきれないほどもっともっと大きかった場合、下位1バイトを0にしただけじゃdeckSizeは0になってくれません。)
勝負がついたかどうかの判定
そして、残りデッキ枚数判定は、deckSizeをデクリメントして更新したあとに行われ、deckSizeが0と等しいかどうかで判定しています。deckSizeの初期値(正規には26)を不正に0にした場合、デクリメントにより負の値となってしまうのでこの判定をすり抜けてしまい、カードが無いのに勝負が続きます。
勝負がカードの枚数より多く繰り返された場合
一つのdeck構造体につきカード配列はなぜか52枚用意されます。
なので52回より多く勝負をすると、
人間プレイヤーの場合は、人間プレイヤーのカードの配列の次に並んでいる、name配列を読み込んでしまいます。コンピュータプレイヤーなら…0を読んでいます。(初期値なしグローバル変数として宣言されているからBSSセクションに配置されるから?そんでそのBSSセクションのあとはヒープ領域まで何もないっぽくて(参考:http://th0x4c.github.io/blog/2012/10/10/os-virtual-memory-map/)ずっと0が並んでるっぽいからみたい?メモリマップは以下のようにして確認できます。)
$ cat /proc/3812/maps 00400000-00402000 r-xp 00000000 fc:00 320292 /home/user1/デスクトップ/a.out 00601000-00602000 r--p 00001000 fc:00 320292 /home/user1/デスクトップ/a.out 00602000-00603000 rw-p 00002000 fc:00 320292 /home/user1/デスクトップ/a.out 01e80000-01ea1000 rw-p 00000000 00:00 0 [heap] 7fbb358c5000-7fbb35a85000 r-xp 00000000 fc:00 523255 /lib/x86_64-linux-gnu/libc-2.23.so 7fbb35a85000-7fbb35c85000 ---p 001c0000 fc:00 523255 /lib/x86_64-linux-gnu/libc-2.23.so 7fbb35c85000-7fbb35c89000 r--p 001c0000 fc:00 523255 /lib/x86_64-linux-gnu/libc-2.23.so 7fbb35c89000-7fbb35c8b000 rw-p 001c4000 fc:00 523255 /lib/x86_64-linux-gnu/libc-2.23.so 7fbb35c8b000-7fbb35c8f000 rw-p 00000000 00:00 0 7fbb35c8f000-7fbb35cb5000 r-xp 00000000 fc:00 523253 /lib/x86_64-linux-gnu/ld-2.23.so 7fbb35e93000-7fbb35e96000 rw-p 00000000 00:00 0 7fbb35eb4000-7fbb35eb5000 r--p 00025000 fc:00 523253 /lib/x86_64-linux-gnu/ld-2.23.so 7fbb35eb5000-7fbb35eb6000 rw-p 00026000 fc:00 523253 /lib/x86_64-linux-gnu/ld-2.23.so 7fbb35eb6000-7fbb35eb7000 rw-p 00000000 00:00 0 7ffdf2771000-7ffdf2792000 rw-p 00000000 00:00 0 [stack] 7ffdf2793000-7ffdf2795000 r--p 00000000 00:00 0 [vvar] 7ffdf2795000-7ffdf2797000 r-xp 00000000 00:00 0 [vdso] ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0 [vsyscall]
と
$ size --format=SysV -x a.out a.out : section size addr .interp 0x1c 0x400238 .note.ABI-tag 0x20 0x400254 .note.gnu.build-id 0x24 0x400274 .gnu.hash 0x24 0x400298 .dynsym 0x198 0x4002c0 .dynstr 0x8c 0x400458 .gnu.version 0x22 0x4004e4 .gnu.version_r 0x20 0x400508 .rela.dyn 0x30 0x400528 .rela.plt 0x150 0x400558 .init 0x1a 0x4006a8 .plt 0xf0 0x4006d0 .plt.got 0x8 0x4007c0 .text 0x7d2 0x4007d0 .fini 0x9 0x400fa4 .rodata 0x32c 0x400fb0 .eh_frame_hdr 0x54 0x4012dc .eh_frame 0x174 0x401330 .init_array 0x8 0x601e10 .fini_array 0x8 0x601e18 .jcr 0x8 0x601e20 .dynamic 0x1d0 0x601e28 .got 0x8 0x601ff8 .got.plt 0x88 0x602000 .data 0x10 0x602088 .bss 0x150 0x6020a0 .comment 0x34 0x0 Total 0x1657
実際にメモリのダンプをして見ると
$ gdb a.out (gdb) run ...(省略)... (gdb) x/200xb 0x6020a0 0x6020a0 <stdout@@GLIBC_2.2.5>: 0x20 0x26 0xdd 0xf7 0xff 0x7f 0x00 0x00 0x6020a8 <completed.7585>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x6020b0: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x6020b8: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x6020c0 <gameData>: 0x64 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x6020c8 <gameData+8>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x6020d0 <gameData+16>: 0x1a 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x6020d8 <gameData+24>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x6020e0 <gameData+32>: 0x00 0x06 0x01 0x03 0x00 0x05 0x03 0x03 0x6020e8 <gameData+40>: 0x01 0x08 0x02 0x02 0x01 0x05 0x00 0x04 0x6020f0 <gameData+48>: 0x02 0x05 0x00 0x07 0x01 0x06 0x02 0x07 0x6020f8 <gameData+56>: 0x02 0x03 0x01 0x07 0x03 0x07 0x02 0x04 0x602100 <gameData+64>: 0x01 0x04 0x00 0x03 0x00 0x08 0x00 0x02 0x602108 <gameData+72>: 0x01 0x02 0x03 0x02 0x03 0x06 0x03 0x04 0x602110 <gameData+80>: 0x02 0x06 0x03 0x05 0x00 0x00 0x00 0x00 0x602118 <gameData+88>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x602120 <gameData+96>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x602128 <gameData+104>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x602130 <gameData+112>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x602138 <gameData+120>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x602140 <gameData+128>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x602148 <gameData+136>: 0x7a 0x7a 0x7a 0x7a 0x7a 0x7a 0x7a 0x7a 0x602150 <gameData+144>: 0x7a 0x7a 0x7a 0x7a 0x7a 0x7a 0x7a 0x7a 0x602158 <gameData+152>: 0x7a 0x7a 0x7a 0x7a 0x7a 0x7a 0x7a 0x7a 0x602160 <gameData+160>: 0x7a 0x7a 0x7a 0x7a 0x7a 0x7a 0x7a 0x00 (gdb) 0x602168 <gameData+168>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x602170 <gameData+176>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x602178 <gameData+184>: 0x1a 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x602180 <gameData+192>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x602188 <gameData+200>: 0x03 0x09 0x03 0x0b 0x02 0x09 0x01 0x0a 0x602190 <gameData+208>: 0x01 0x0e 0x03 0x0c 0x02 0x0c 0x03 0x08 0x602198 <gameData+216>: 0x01 0x0b 0x01 0x0d 0x01 0x09 0x00 0x0c 0x6021a0 <gameData+224>: 0x02 0x0b 0x02 0x0a 0x00 0x0a 0x00 0x0d 0x6021a8 <gameData+232>: 0x02 0x0e 0x00 0x0b 0x03 0x0e 0x03 0x0d 0x6021b0 <gameData+240>: 0x01 0x0c 0x00 0x0e 0x03 0x0a 0x02 0x08 0x6021b8 <gameData+248>: 0x02 0x0d 0x00 0x09 0x00 0x00 0x00 0x00 0x6021c0 <gameData+256>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x6021c8 <gameData+264>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x6021d0 <gameData+272>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x6021d8 <gameData+280>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x6021e0 <gameData+288>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x6021e8 <gameData+296>: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x6021f0: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x6021f8: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x602200: 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0x00
こんな感じになってます。name配列へはzzzzz…を入力してあり、0x7a(=z)が並んでいるところがname配列です。他ずっと0が並んでいるのがわかるかと思います。
なお、checkInvalidCard関数でカードの値(suit<=4, value<=14でないと不正)がチェックされるので、それに違反しないようにしなくてはなりません。
解法
よって、まずname配列への名前の入力時に32文字、checkInvalidCard関数に引っかからない4以下の値を入れることで、readInput関数のバグを利用しdeckSize変数の下位1バイトに0を入れます。26回の勝負を行わせ正規のカードを使い切らせ、確保されているカード配列は全部で52なので、追加で(52-26=)26回の勝負を行います。そうすると人間プレイヤーはカードとして(カード配列の次に配置されている)name配列の領域を、コンピュータプレイヤーはカードとして(カード配列の次に配置されている)0が並んでいる領域を読むため、その後の勝負で勝利することができます。
よって、name配列への入力として0x04を32個、そのあとカードを使い切るために適当に少ないベットで勝負を繰り返すため、適当に1を52回送信し、そのあとはこちらが勝つのでたくさんのコインをベットしていきます。
冒頭に挙げたwriteupでそのスクリプトが公開されています。
picoCTFのサイト上のシェルからでなくローカルのシェルからエクスプロイトコードを実行して得たflagは、なぜか受け付けてもらえなかったので、picoCTFのサイト上のシェルでやらざるを得ませんでした。
ctrl+V, ctrl+Cで0x03が入力できます。連打でがんばれ!
p.p1 {margin: 0.0px 0.0px 0.0px 0.0px; font: 15.0px Menlo; color: #000000; background-color: #ffffff}
コメント