2017-04-09

ASIS CTF Quals 2017 writeup

CTF crypto

m1z0r3で参加、1006ptで51位でした。cryptoを3問解いて523ptを入れました。

なお、終了後すぐDLPも解けたので一応載せておく。

A fine OTP server (crypto 79pt)

RSA暗号の暗号文が与えられるが、e=3であり平文も比較的短いので3乗根をとるだけ。後のSecured OTP serverで言及するのでここではソルバは省略。（3乗根で解けることに最初は気づかず、Secured OTP serverと同じソルバで解いた）

ASIS{0f4ae19fefbb44b37f9012b561698d19}

F-4 Phantom (crypto 176pt)

適当な素数pを元に、ランダムな2bitを反転させたもののnext_primeをqとしたRSA暗号。またeは65537ではなく大き目な値。

(なお、最初はwiener's attackを試したりもしたがダメだった)

反転させるランダムな2bitに注目すると、pとqが比較的近い値になる場合があることがわかる。この場合フェルマー法により素因数分解できるので、このようなnを引けるまでガチャる。

都合の良いnを素因数分解すると、φ(n)とeが互いに素ではないため秘密鍵dが計算できないことがわかる。計算してみると、素数pに対してeはp-1の素因数となっている。

なので、ひとまず素数qを用いて $d_q \equiv e^{-1} \pmod{q-1}$ を計算し、 $m_q \equiv c^{d_q} \pmod{q}$ を導く。

同様に、素因数分解可能なnをもう１つ入手して $m_q$ を計算する。

あとは、これらの $m_q$ をCRTにより持ち上げるとmが求まる。いわゆるRSA-CRTの計算である。

ASIS{Still____We_Can_Solve_Bad_F4!}

Secured OTP server (crypto 268pt)

ある平文の末尾に、ランダムな18文字を連結したものを平文としたRSA暗号の暗号文を2つ与えられる。なお、2つの平文の差は、 $n^{\frac{1}{9}}$ より小さい。

わざわざこの条件が与えられていることから、Short Pad AttackやFranklin-Reiter Related Message Attackをすると考えられる。が、手持ちのソルバを用いてもShort Pad Attackで解が得られなかった。

そこで、平文の上位bitがわかっていることから、シンプルにCoppersmith's theoremから解いた。

ASIS{gj____Finally_y0u_have_found_This_is_Franklin-Reiter's_attack_CongratZ_ZZzZ!_!!!}

おまけ。DLP

開催中には解けなかったやつ。

暗号文として、 $(n+1)^{msg} \pmod{n^{s+1}}$ とnが得られる。

$n^{s+1}$ 以上の項はすべて消える。つまり、s=11としたとき、 $a_0*n^{11} + a_1*n^{10}+ ... + msg*n + 1$ となる。なので、 $n^2$ でmodをとれば $msg*n+1$ のみ残るので、あとは計算して終わり。

ASIS{Congratz_You_are_Discrete_Logarithm_Problem_Solver!!!}

まとめ

都合上日曜日しか参戦できなかったとはいえ、DLPとunsecure ASIS sub-dは解けるべきだと思った。start_hardも少し手をつけたので気になるところ。

2017-03-31

House of Force をやってみる

CTF pwn

過去の問題を元にHouse of Forceの練習をしてみたので、そのwriteupのような覚書です。

how2heapにも載っている、Boston Key Party 2016 の cookbook という問題を解いてみました。

House of Forceとは

以下のような状況を想定。

main_arena.top のアドレスがわかる
main_arena.top を書き換え可能
任意サイズでmallocすることができる

このとき、main_arena.topを0xffffffffなどの大きな値で書き換える。その後適当な大きさでmallocをすることで、次回のmallocで任意のアドレスを返すことができるというもの。

ここで適当な大きさとは、(確保したいアドレス-8)-現在のtop-8となる。

前者のマイナス8は、malloc_chunk構造体によるもの（prev_size, sizeを考慮）である。

後者のマイナス8は、topからchunkを切り出すか判断する際のmallocの仕様によるものであり、細かくは気にしなくてよい（と思われる）。

通常はmallocで確保した領域に対して書き込みが可能なアプリケーションがほとんであるため、任意のアドレスを確保できるようになることはすなわち、任意のアドレスを上書き可能となったに等しい。

cookbook writeup

名前の通り料理系のアプリ。素材の登録・削除、レシピの登録・削除、cookbook名の登録・削除ができる。

それぞれのデータはヒープで管理されている。

gdb-peda$ checksec
CANARY    : ENABLED
FORTIFY   : disabled
NX        : ENABLED
PIE       : disabled
RELRO     : Partial

解析パートは省くが、様々な脆弱性がある（heap oveflow, double free, use-after-free）

このうち、use-after-freeとheap oveflowを使って解く。

main_arena.top 、ヒープのアドレスリーク

まずは、House of Forceの条件の1つ目である、現在のmain_arena.topのアドレスリークを行う。これは、レシピ登録にあるuse-after-freeを用いる。具体的には、一旦レシピに適当な素材を適当数登録した後discardすると、素材の個数へのポインタが入っていたアドレスにbkメンバが入る。discard後もprint current recipeすることができ、素材の個数の欄にbkの情報が漏洩する。

特にfree listがない状態でこれを行うと、bkはmain_arena.topを指すため、main_arena.topのアドレスをリークすることができる。

また、main_arena.topのアドレスを元にヒープのベースアドレスも計算することができる。

main_arena.top overwrite

次に、2つ目の条件であるmain_arena.topの書き換えを行う。これは、レシピ登録にあるheap oveflowを用いる。具体的には、レシピ名でoverflowが可能なので、main_arena.topのある位置まで書き込み、0xffffffffで上書きをする。

任意サイズでのmalloc

これは脆弱性を使うことなく、cookbook名の登録機能で実現できる。16進数で入力した値をそのまま引数にmallocしてくれるため、任意のサイズ（負数も可）でmallocを呼べる。

さて、以上よりHouse of Forceの条件がすべて整った。

あとは書き換えたいアドレスから確保すべきサイズを計算し実際に確保するだけである。

この問題はFULL RELROではないので、GOT overwriteをしてsystem(/bin/sh)を呼ぶのがおそらく一番簡単である。入力をそのまま引数にとるatoiがあるので、これのGOTを書き換える。が、systemのアドレスを求めるためにlibcのベースアドレスを漏洩させる必要がある。したがって、atoiのgotを一旦printf@pltに書き換えることでFSBを発生させてlibcのアドレスを計算する。ちなみにatoiはadd ingredientのpriceやcal設定で呼ばれる。

なお、ユーザの入力をそのまま引数にとるという点ではmallocもそうだが、このプログラムはいたる所でmalloc/freeを呼ぶため、libc計算のためにmallocを壊すとうまく動かなくなるためatoiを使った。

以上のことをすべてまとめると以下の手順になる。

create_recipeのuse-after-freeによりmain_arena.topのアドレスをleak
create_recipeのoveflowによりmain_arena.topを0xffffffffでoverwrite
House of ForceによりmallocでatoiのGOT付近を返す
GOT overwriteによりatoiをprintfにする
FSBによりlibcのアドレスをleak
再びHouse of ForceによりatoiのGOTをsystemにoverwrite

以下ソルバ

工夫点（苦戦点）

一番はじめにingredient用chunkを確保

House of Force後にやると変なところに確保されるのでは？という気がしたため。ただしこの後の工夫によって杞憂となったと思う。

1回目のGOT overwriteをしつつtopをheap領域に戻すようなsizeを指定

GOTの破壊が進行してしまうのを防ぐため。ここに適当なsizeを指定していたときは、GOT内のアドレスをfreeに渡してエラー終了していたが、工夫することで正常に動くようになった。

GOT overwriteの際、4バイト手前から書き込んでいる点

これは、mallocの8バイトアラインメントによりピッタリのアドレスを返せないことが原因だと思われる。はじめは丁度のアドレスを返そうと試していたが、入力sizeを4バイトずらすと確保される領域は8バイトずれてしまう。

まとめ

というわけでHouse of Forceをやってみました。m1z0r3内の勉強会でcookbookをやっていたときはヒープがよくわからないのでスルーしていたものの、unlink attackで解いてたような気がするので時間があったらそっちもやってみます。

次はHouse of Einherjarをやってみたいです。

おわり。

参考

House of Forceの概要と実践(題材：BCTF2016 bcloud) - Pwn De Ring

glibc malloc exploit techniques - ももいろテクノロジー

2017-03-29

0CTF 2017 writeup その3

CTF pwn

その他writeup

0CTF 2017 writeup その2 - きゅうり。 (char)

0CTF 2017 writeup - きゅうり。 (integrity, oneTimePad)

残り解く予定（oneTimePad2、BabyHeap2017、diethard）

今回は、EasiestPrintfのwriteupです。と言っても、自力では解けないので他の人のwriteupを参考に勉強した記録です。

tl;dr

今回得られた知見

printf内でのmalloc/free呼び出し
hook関数
one-gadget RCE

writeup

動作としては、任意のアドレスを1つだけ教えてくれた後、FSBのあるleave関数が呼び出されて即exitという流れ。

NX、Full RELROで制約は厳しい。

まず、任意のアドレスをリークできる部分で適当にlibcのアドレスを特定。

本来ならばここからデストラクタを書き換えたりGOT overwriteしたりしたいところだが、Full RELROなので思いつくことが諸々できない。

現状ではEIPを奪えていないので、まずはEIPを奪うことを考える。

結論から述べると、printf内で呼ばれるmalloc/freeを利用する。printfを追って行くとvfprintf.cなるものが呼ばれることがわかるが、ソースコードを読んでみると、widthという値がWORK_BUFFER_SIZE-32以上のときmallocが呼ばれる様子がわかる。（1475行目前後）

要するに、printfで表示する文字列がある程度長いときには一旦mallocで確保した領域に文字列を置き、表示後にfreeしているものと考えられる。

ではこのmalloc/freeをどう利用するかだが、各種hook関数（__malloc_hook, __free_hook）に注目する。hook関数を用いるとmallocなどの関数を独自関数に置き換えることができ、通常はデバッグ用などに使われる。ユーザが定義するので当然と言えば当然だが、この各種hook関数はlibcのうちwritableな領域にある。（画像一番下）

f:id:Kyuri:20170329175011j:plain

未定義の時は該当するアドレスには0が入っているため、おそらく最初にhook関数のアドレスが0かどうかを確認し、0でない時はそのアドレス先が呼ばれると思われる。

なので、FSBで__free_hookをoverwriteしつつ、一定量表示させるようにすることでEIPを奪うことができる。

最後にどうやってシェルを取るかだが、one-gadget RCEを用いた。いわゆる一発でシェルをとれるgadgetである。なおこのようなgadgetがlibcのどこにあるかは外部によくまとまっているブログがあったのでそこを参考にした。どうやら本番環境のlibcにも同様のgadgetはあるようなので問題ない、と思う。

EIPを奪えているので、スタックのアドレスをリークしつつmainに再び飛ばしても解けるとは思うが、せっかくなので新たなものを使ってみた。

2017-03-29

0CTF 2017 writeup その2

CTF pwn

その他writeup

0CTF 2017 writeup その3 - きゅうり。 (EasiestPrintf)

0CTF 2017 writeup - きゅうり。 (integrity, oneTimePad)

今更ですが、本番中には解けず、後から解いたもののwriteupシリーズです。

char

自明なbuffer over readがあり、offset=32で簡単にEIPが奪える。ただし入力はprintableなもの（asciiで0x20〜0x7e）しか受け付けないので、その範囲内でROPを組む必要がある。

libcが固定アドレスでprintableなアドレスに読み込まれるので、その中の使えるgadgetを組み合わせて頑張る。rp++の結果からprintableなものだけ抽出するスクリプトを適当に書いて、あとは泥臭く組み立てていっただけなので特に説明はないです。

ecxは{"/bin/sh",NULL}ってずっと思ってたものの、特になにもしなくてもシェルとれた。知見。

flag{Asc11_ea3y_d0_1t???}

2017-03-28

Volga CTF 2017 Quals writeup

CTF crypto

m1z0r3として参加して、450ptsで188位でした。

予定があってあまり時間がとれませんでしたが、cryptoを2問解いて250pts入れたのでそのwriteupを書きます。（今回はスクリプトは無し）

VC (crypto 50pts)

png画像が2枚渡される問題。B.pngはA.pngになんらかの情報が追加されてるように見えるので、2枚の差分をとるとフラグ。

f:id:Kyuri:20170328130048p:plain

Curved (crypto 200pts)

楕円曲線DSA（ECDSA）を用いた署名を使ってコマンド実行を行うサーバが動いており、そのスクリプトとexit、leaveコマンドの署名が渡される。

lsやcatなどを実行するには、正しい署名を生成する必要があるが、署名をするには秘密鍵が必要となる。

一般にECDSAでは署名を施す際にランダムな値kを用いる必要があり、これが固定値だと秘密鍵が逆算可能となってしまう。（詳しくは楕円曲線DSA - Wikipedia）

今回渡されたexitとleaveの署名を見ると、rの値が等しいことからkが同一であったことがわかる。したがって秘密鍵が逆算でき、得られた秘密鍵からcat flagを実行すればフラグが得られる。

実はこの問題、過去にチーム内CTFで出題したものとまったく同じコンセプトだったのでECDSAの処理を見た瞬間に見当がついたりもした。

所感

Oracleはやればできそうだったり、Casinoは面白そうな問題だなぁと思った。が、cryptoはどれもPoWがめんどくさすぎて途中で投げ出した。（予定があったのもあるけど）

ちゃんとPoW用のライブラリは用意しておくべきですね...

2017-03-20

0CTF 2017 writeup

CTF crypto

0CTF 2017にm1z0r3として参加しました。

266ptで111位でした。WelcomeとServeyを除いた222ptのうち189ptを入れました。

cryptoのintegrityとoneTimePadを解いたのでそのwriteupです。

その他writeup

0CTF 2017 writeup その3 - きゅうり。 (EasiestPrintf)

0CTF 2017 writeup その2 - きゅうり。 (char)

integrity (crypto 75pt)

・register

こちらからnameを送信すると、

md5(pad(name))+pad(name)

をAES-CBCで暗号化して、IVと暗号文が送られてくる。

ただしpad(name) == pad("admin")は弾かれる。

・login

こちらからIVと暗号文を送信すると、それを復号してmd5チェックをした後unpadして出てきたnameとしてログインする。

nameがadminならフラグ。

解法

name = md5(pad("admin")) + pad("admin")としてregisterして、返ってきた暗号文からIVを除いてそのままloginに送信すればフラグ。

flag{Easy_br0ken_scheme_cann0t_keep_y0ur_integrity}

oneTimePad (crypto 114pt)

keygenという自作PRNGから乱数を生成しOTPにより暗号化したもの。keygenでは乱数をseedとしてprocess関数から乱数を生成しているので、process関数が鍵になってくる。

process関数は $GF(2^{256})$ の元で $tmp^2$ を返しているだけ。なお生成多項式はP。また、すべての演算は $GF(2)$ 上で行われるのでxorと+は等価。

これを数式で表すと、

$process(m,k) = p(m) + p(k) = m^2 + k^2$

ただし $p(x) = process(x,0)$ とする。

これを利用して与えられた暗号文を変形していく。ただし、fake_secretからkey2,3は既に計算済みとする。

$ctxt1 = true\_secret + key1$

$key2 = process(key1,seed) = key1^2 + seed^2$

$key3 = process(key2,seed) = key2^2 + seed^2$

$p(key2) + key3 = key2^2 + key2^2 + seed^2 = seed^2$

$key2 + seed^2 = key1^2 + seed^2 + seed^2 = key1^2$

$p(ctxt1) + key1^2 = true\_secret^2 + key1^2 + key1^2 = true\_secret1^2$

したがって、あとは $true\_secret1^2$ の平方根をとればよい。

一般に $GF(2^n)$ の元で平方根をとるには、n-1回平方をとればよい。

flag{t0_B3_r4ndoM_en0Ugh_1s_nec3s5arY}

所感

oneTimePadは最初見たときに数学系の問題かな〜と思いつつxorこねくり回したり1bitずつ求めようとしたりして時間を浪費したのがもったいなかった。さらに、平方根とるだけって気づいてからn-1回平方すればいいことを知るまでに無駄に時間を使った。

ので、この2問は瞬殺できるぐらいにはなりたい。ただ無駄に苦戦したおかげでoneTimePad解けたときはうれしかった（こなみ）。

oneTimePad2も解きたかったけど式がより複雑になってて断念しました。

今回はほぼソロ参加みたいな状況でpwnが手付かずで残ってたのに1問も解けてないので精進💪

2017-03-12

ED CTF my_sandbox writeup

CTF pwn

解いたのでwriteupです。

プログラムとlibcが渡されてます。

事前確認

$ ./my_sandbox
Your name please: hoge

Welcome to my echo program!


This program has an bug.
I couldn't fix this bug... :(

But, I developed sandbox for this bug.
Hackers will never be able to get shell, haha! :)

Enter your message: 1
Entered: 1

(snip)

Enter your message: 10
Entered: 10


It seems cracker couldn't crack my program, I'm winner!
See you.

入力をそのまま返すのを10回繰り返すようなプログラム。バグがあるけどsandbox化してやったからシェルとれないやろ？？？みたいなやつ。

バグがあると言っている通り、FSBがあります。

続いてchecksec

CANARY    : disabled
FORTIFY   : disabled
NX        : disabled
PIE       : disabled
RELRO     : FULL

方針

FSBがあるので、まずは素直にlibcのアドレスをリークします。この時点で最後はret2libcに帰着しそうなことがなんとなくわかります。

あとはreturnアドレスを書き換えるためにスタックのアドレスをリークする必要があります。しかし、sandbox化（？）により、FSBは通常のスタックではなくmallocによって確保された領域（擬似スタックと呼称）で発生します。なので、都合よくリークできそうなアドレスが積まれていません。

ここで擬似スタックがlibcの直前にあることに注目すると、libcのベースアドレスから、入力した値が積まれる擬似スタックのアドレスが計算できます。そして計算したアドレスからsnprintfの第一引数にあたるアドレスを計算しリークさせることでスタックのアドレスがリークできます。

これを図解すると、snprintf(buf,size,user_input);が呼ばれる際の擬似スタックは、

addr_buf
size
addr_user_input
xxx
xxx
xxx
xxx
xxx
user_input

となっており、libcのベースアドレスからuser_inputのアドレスが計算できます。これが計算できるということは通常のスタックにあるbufのアドレス、つまりaddr_bufが計算できるためスタックのアドレスもリークできます。

ここまでできたら後はリークしたスタックのアドレスからreturnアドレスの場所を計算して書き換えてsystemを呼んで終了。