Google CTF 2017 Writeup

今回は一人で参加してました。
解いた問題

CRC

crc_82_darc(data) == int(data,2)

を満たすdataを作る問題。
crc_82_darcは入力データをビット列であらわしたものを\(b_{n-1} \dots b_{0}\)として（リトルエンディアン）
\( f(X) = \sum^{n-1}_{i=0} b_i X^i \)
を82次のある多項式P(X)で割った多項式の係数をハッシュ値とするハッシュ関数である。
今、入力のデータは'0'(=0x30)か'1'=(0x31)からなる文字列であるので、実際には\(c_i\)を入力の\(i\)文字目が'0'のとき0、'1'のとき1となるようにすると、
\( f(X) = \sum^{81}_{i=0} (c_i X^7 + X^3 + X^2) X^{8(81 - i)} \)
となる。
満たすべき値は
\( f(X) \mod P(X) = \sum_{i=0}^{81} c_{81-i} X^i \)
であり、各係数を比べるとc_iを変数とするGF(2)上の連立線形一次方程式となる。
なので解ける。

gpでの計算例
gist5b6f91c0783cbaf119d86b510fa01c22
フラグを保存するの忘れた。

Inst_prof

バイナリはNX, PIEだがPartial RELROなのでGOT overrideを目指す。
このプログラムは以下の処理を繰り返し行う。

  1. pageをmmapする(Read| Write)
  2. pageにテンプレートを書き込む
  3. 入力から4byte読んでpage + 0x5に書き込む
  4. pageをmprotectする(Read|Exec)
  5. r12にrdtscの結果を置く
  6. pageの先頭に関数呼び出しする。
  7. rdxにrdtscの結果を置く
  8. rdx - r12の値を出力する。
  9. pageをmunmapする。

任意の4byteを送るとその4byteをmmapしたページに配置して0x1000回実行してくれる。そのあとその実行にかかった時間を出力してる。
r12を0してみると現在のCPU時間の値がわかる。そのあとr12を適当な値にするとrdxの上位ビットはそれほど変わらないので、r12の上位ビットをleakできる。
レジスタの値をleakできたので次はlibcを特定するために__libc_start_main@got.pltとmunmap@got.pltを読みに行く。
今、rspの指すアドレスには関数呼び出しの戻り番地、すなわち.textセクションのアドレスが入っているので、そこからの相対値でmunmap@got.plt等にたどり着くようにする。
ただ、同じ命令を0x1000回繰り返すので例えばadd r12, 0x3などの命令は上手くいかない。
なのでrsp - 0x1000あたりのメモリを一時的なデータの退避場所として計算を進めた。

libcを特定したあとはGOT overrideでmunmapをsystemに書き換える。
そのままだとGOT overrideの直後にsystem(page)となって結局pageの先頭が不正な文字列となり何も起こらないが、プログラムはセグフォを起こさず次のループに進めるので次のような手順でshellを起動した。

  • r13 に*rsp + 0x1000を書き込む
  • r13 + 0x8に"sh\0"を書き込む
  • GOT overrideでmunmapをsystemに書き換える
  • mov rbx, r13 + 0x8

exploit
gist9ec3329544e2d45f02eb632b462ea44f

crypto_backdoor

本番中に解法はわかっていたが、寝落ちして解けなかった問題。
起きて作業したら十分くらいで終わって悔しかった。

DH法で秘密鍵を共有するプログラムがあたえられる。共有した秘密鍵を計算できればフラグが得られる。
ただし使用する群はよくわからない群でパッと見楕円曲線っぽくもあるが実は違った。
群の要素は\((Z_n/p)^2\)で\(p\)はそこそこ大きいが実は素因数分解できて素因数は\(10^9\)くらい。
群の演算は\((x_1, x_2)\)と\((y_1, y_2)\)に対して
\(x_3 = \frac{ x_1 x_2 - x_1 y_2 - x_2 y_1 + 2 y_1 y_2 }{ x_1 + x_2 - y_1 - y_2 - 1} \)
\(y_3 = \frac{ y_1 y_2 }{ x_1 + x_2 - y_1 - y_2 - 1 }\)
この式を変形すると
\( \frac{x_3}{y_3} - 1 = (\frac{x_1}{y_1} - 1) (\frac{x_2}{y_2} - 1) \)
となる。つまりこの群に対して離散対数問題、すなわち\(G = (x_g, y_g), X = (x,y)\)を入力として\(G^r = X\)となるrを求めるには
\((\frac{x_g}{y_g} - 1)^r = \frac{x}{y} - 1\)が成り立つので\(Z_n/p\)上の離散対数を計算してやればいいことになる。


gist836785ae9283d2abfa02fbe51a832c0e

$ gp -q doit.gp < /dev/null
6621005115841589341021728146593578127178145692816888878
3717310807101673722781843653766732925831732205102857032

gist34dd40234e8ae6fe263964a2f6c4f710

$ python crypto_backdoor.py 
length = 31, encrypted_message = 221625116140542176473033670030978737257674515917829815328018959235996341315
CTF{Anyone-can-make-bad-crypto}