tkbctf4 [misc 400] amida

Cheer of CPUに続きましてmisc 400、amidaでございます。

この問題は私と@yuscarletによる作成です。

問題

203.178.132.117:42719

Ghost Leg - Wikipedia, the free encyclopedia

現在問題文中のサーバーは停止しています。こちらもソースコードはgithubで公開されていますので、試したい方はどうぞ。tkbctf4/misc400_amida at master · tkbctf/tkbctf4

なお実際の問題はfafrotskiesというCPUを100%持っていく素敵な自作サーバーと連携して動作していました。

問題中に英語版Wikipediaの"Ghost Leg"の記事にリンクが張ってありますが、「あみだくじ」って英語では"Ghost Leg"というそうです。

概要

所定のサーバーにアクセスすると無駄なようこそメッセージの後にBase64な文字列が降ってきます。これをデコードするとPNG画像が現れます。画像の内容はあみだくじの画像で、縦棒の各上端（始点）に番号が振られていて、縦棒のうち1つの下端（終点）に黒丸があります。黒丸に辿り着くような始点の番号をサーバーに送りつけて、正解なら次の問題が送られてきて、不正解ならその場で切断されます。こんな感じで1ステージ50問×20ステージ、計1000問解くとフラグが降ってきます。

とはいえまぁ単純なあみだくじを1000問も解かせるなんてことはないわけです。5ステージを1つのブロックとすると4つのブロックがあるわけですが、最初のブロックから次のような感じであみだくじが変化していきます。

  1. 普通のあみだくじ
  2. 横線が波線になる（横線の始点と終端のy座標は同じ）
  3. あみだくじが回転する（0°〜359°）
  4. 横線が波線になり、かつ回転する

で、各ブロックの最初のステージでは縦線が4本ですが、次のステージでは5本、その次では6本……となり、ブロックの5ステージ目では縦線が8本になります。次のブロックに進むと縦線の数は4本に戻り再び8本まで増えていきます。

この辺はリポジトリのcasegenを参照してください。casegenはステージ数を受け取ってそれを元にamida_evに渡す引数を変えるRubyスクリプトです。amida_evはgenerator.cppをコンパイルしたバイナリで、それに渡す引数で生成されるあみだくじが変わるようになっています。-rで回転、-wで波線、-nNで縦線がN本になります。

なお、さすがに全問解かないとフラグが来ないのでは時間的に誰も辿り着けない可能性があったので、問題投入後しばらくしてから各ブロックの終了時にチェックポイントを追加し、結果的に配点が変わりました。元々最終フラグのsubmitで300点でしたが、チェックポイント3つと最終フラグ1つの計4つのフラグにそれぞれ100点を割り振り合計400点の問題となりました。

結局競技時間内に最終フラグをsubmit出来たチームはありませんでしたが、非常に惜しいことになっていたチームがあったようで……

私「（最終）フラグはcheckpointじゃない」

プログラムについて

地味に面倒なことをしています。元々単純に縦線を描画して、y座標をランダムに生成してそこに横線を描く（なお横線が直線だとは言っていない）、という実装だったんですが、横線が連続してしまうケースとか、終端に横線がくっついてしまうケースとかがあって、その辺を調整した上で横線の座標を決定する辺りを@yuscarletに書いてもらいました。それ以外にはオプションのパースの実装も書いてもらっています。

なので私はあまりその辺のロジックはあまり苦労してなくて（逆に言うとロジックで面倒なところは全部やってもらった）、むしろ私を苦しめたのはcairoだったのでした……。何が一番つらかったかってPNG画像をファイルに吐くか、吐き出すデータ(unsigned char*)を受け取るコールバックを指定して吐き出すかのどちらかしか選択肢がなくて、「えっ適当なバッファに全部吐き出す関数とかそういうのないんですかファイルに出力する関数はあるのにえっ？」ってなってました。しかもコールバックに渡されるデータはどうやら「逐次」渡され、PNGファイル全体を出力するまでコールバックは複数回呼ばれるという仕様でいよいよ私の睡眠時間は0に近付いていきましたとさ。

そんな感じで、久々にグローバルにunsigned char *bufferとかいう変数を宣言しつつ、あとは適当にネットに転がっているbase64の実装を拾ってきてバッファ上のPNGファイルデータをエンコードして出力するようなプログラムを仕上げました。

ちなみに私が元々「サンプル実装」として書いたコードが出発点なせいで相当なクソコードになってたのでtkbctf4前半（1日目）終了後に書き直した上でbase64エンコードとかその辺追加してました。時間がないときに限って書き直したくなる法則が発動しました。おかげで寝られませんでした。

感想とか諸々

元ネタ

名前が名前だけに気付いている人もいましたが、この問題の元ネタは夏に行われたSECCON 2014オンライン予選で出題された「あみだくじ」です（リポジトリのREADMEにも記述しています）。

「あみだくじ」でやることとしてはこの問題と同じで所定の終端に辿り着く始点の番号をひたすら答えるとフラグがもらえる、という問題でした。この問題と異なる点はこんな感じ。

  • あみだくじが画像じゃない（アスキーアート）
  • あみだくじがbase64じゃない
  • あみだくじが任意の角度に回転しない（アスキーアートだし）
  • あみだくじが上下反転する（180°の回転ではなくて上下のフリップという感じ）
  • 実行バイナリが配布される形式であり、ローカルで試行出来る
  • 何度実行しても出題される内容や順序は全く同じ
  • 出題の度にsleepが挟まれている

元ネタになった問題を解いたのも私と@yuscarletでして、まぁなんというか地味に苦しめられたというかなんというか。「任意の」角度には回転しないもののあみだくじが横向きになるとかはあって、形式が変わったためにプログラムが例外吐いて死ぬ度に私たちも悲鳴を上げながらプログラムを修正していく作業をひたすらしてました（最終的には総当たりしたんですけど）。それはともかく、その記憶がまだ鮮明に残っている中で私と@yuscarletで酒を飲んでるときに「なんかもっと嫌らしい『あみだくじ』作れねえかな」みたいな話になって、まずは画像化しようって話になって、「画像化してもなんか世の中には線認識ライブラリくらい転がってるから大丈夫じゃろｗ」とか言いながら適当にサンプル的な出題プログラムの実装書いてたらマジでそのまま問題になっちゃったって感じです。この段階ではもっと強烈な加工をかけることも考えてましたが自分たちで解法が実装どころか思いつきすらしなかったのでやめました。

まぁそういうわけで、つまるところ酔った勢いみたいなところは大いにあるわけで、

決して恨んでるわけではないです……はい……。（むしろ前述のfafrotskiesがCPUを100%持っていくので私が鯖管に恨まれている可能性の方が高い）

あとは元ネタの方のwrite-upを書いてあるのでそちらで。 SECCON 2014 オンライン予選 【あみだくじ】

難易度、解法とか

元ネタとの相違で挙げた最後の2点だけでもぼちぼち難易度違ったんじゃないかなぁと思っています。というのも、ローカルで試行出来て何度やっても同じということはトライアンドエラーがいくらでも効くということで、実際私たちはこの問題を総当たりで解いています（sleepはopに潰してもらいましたが）。“amida"では問題生成はサーバー側で、しかも毎回ランダムに問題が生成されるのでそういうわけにはいかず、まともにあみだくじのソルバを書く必要があります。といっても、あみだくじの構造さえわかってしまえばソルバの実装自体は大して難しくはなくて、事実上「いかに回転する画像と戦いながら画像を認識するか」という問題だったと思います（横線が波線になるのは回転に比べれば大した問題ではないです）。

ちなみに初期の段階での想定解実装はOpenCVを使っていて、波線にした瞬間爆死したので真面目に線の認識をすると逆に死ぬんじゃないかと思います。その辺上手く手抜き（？）して直接ピクセルデータ見に行って云々ってやった方が確実ですし、そもそもOpenCVとか入れなくていいんで幸せになれたのではないでしょうか。

チェックポイント追加後のフラグ送信スピードとか見てるとやっぱ回転する辺りが大きな関門になってたのかなぁという印象です。黒丸のy座標を使うとか色々方法はあったようですが、ぶっちゃけこちらの想定解よりよほど頭のいい解法を皆さん考えられててすごいなぁと思って見てました（小並感）。

最後に

酔った勢いでも問題のアイディアは出てくるので、作問で詰まったら酒を飲もう！！！！（確か日本酒飲んでた気がする）