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:実は未確定の文字を'?'として処理していたのだが、実際にフラグに'?'の文字が入っていたのでちょっと苦労した。