2014-07-19 09:00 - 21:00に行われたSECCON 2014 オンライン予選のWrite-upです。今回は「あみだくじ」。
問題概要
問題は64bit ELF形式の実行ファイルamida。これを実行すると「No.i」(i = 1, 2, …)と書かれた行に続けて1から順に番号が振られたあみだくじが表示され、いずれかの終端の1箇所に*印がついている。……が、後になると
- 番号の振り方が逆 (左から1, 2, …ではなく8, 7, …になっている)
- そもそもくじの上下が逆
- 各行の先頭にnull文字が突っ込まれている （追記: これは出題者の意図していない、問題プログラムのバグだった模様）
- くじの縦線の間が広がる
- くじが横向きになる
……といった面白形式で表示されるようになります。具体例は最後に書いてあるのでそちらを。
解法
問題を確認せずに1から順に解答してみる。
やることとしては、次の手順をフラグが得られるまで繰り返します。
amidaは問題を出力した後?という文字を出力して入力待ちに入るのでそれが見つかるまで読み捨てる- 次の解答を試す
- 正解ならその番号を記録して、試行する番号を1にリセット。次の問題へ。
- 不正解なら
amidaはWrongを出力して終了するので、amidaを再び立ち上げて、これまでの正解番号を次々に入力して、失敗したところまで進める。
なお、実際には問題の記録のために問題は読み捨てるのではなく、読んだものをファイルに保存しました。
この方針の提案と、この後に行うソルバの実装は@yuscarletがC++で、amidaとソルバの間を適当に受け持つ部分をRubyで私が実装しました。最終的に使用した総当たり方式はRubyのみで実装しました。
ところでamidaの実行ファイルなんですが、異様に問題出力が遅いんですね。私と@yuscarletが順当（？）にプログラム書いてる一方で@6f70がamidaのプログラムを解析していて、それによって「問題数は1000問であること」、「問題を出力する際にsleepが噛まされている」ということがわかりました。そこで彼が問題を出力するときに挟まっているsleepを潰したバイナリを用意して、それを用いて総当たり法を実行。結果としてプログラムを動かしてから5分かそこらくらいでフラグを得ました。
ans: c4693af1761200417d5645bd084e28f0f2b426bf
その他諸々
一旦この総当たり方式で実装してみたんですが、どうにも上手く行かなかった（問題の終了判定が上下が逆転しているケースに対応していなかったり諸々）のとさすがにあまりにも遅かったので（この原因は上述のsleep）ソルバで真っ正面から解いてみようということになりました。
（※最初は1行ずつ読んで判定していたので上手く行きませんでした。ソルバによる解答を諦めた後に1文字ずつ読めばいいことに気がついて上述の解答となりました）
番号やらくじの向きやら幅やらが変わっていることに気がつく度にソルバやらRubyのプログラムやらを修正していたんですが、51番目でくじが横向きになっているのがわかると「こんな調子でいろんなパターン対応してたらキリがない」として、ソルバによる解答を放棄して、最初の総当たり方式に戻しました（ちなみに他の方のwrite-upを読むとどうやら100問目までで全パターンが出ていた模様）。
あと番号が逆とかくじの上下が逆とかはともかくとして、null文字突っ込まれてるのは最高にタチが悪いと思いました（小並感）。これ、ソルバによる解答をしているときに遭遇してめちゃくちゃ悩んでて、最終的に問題をファイルに保存してvimで眺めるまでわかりませんでした。
それと1000問あるらしいということとsleepが入っていることがわかったのは結構大きかったですね。前者がわかっていたことでソルバによる対応を諦める判断をすぐに下せましたし、後者が判明していたこと、かつそれを潰せたことで、解答にかかる時間をかなり短縮出来ました。