#seccon 2015 online ctf で自分が一番ハマったのは Unknown 300 の QR puzzle (Nonogram) の問題。 Web上でノノグラムが出題されて、それを解くとQRコードになっていて、その中身を投稿すると次の問題に進むというのを30問ほど行うもの。 ノノグラムをSATにエンコードして解いたのだが、解が一意でなく、かつ解の中にはQRコードとして妥当でないものがあるために、色々と混乱したりハマったりした。
最終的にやった方法は以下の通り:
まずSATで解を列挙して、得られた解をstrong-qr-decoder https://github.com/waidotto/strong-qr-decoder/ にかける。 解の中にはこの段階でエラーになるものや、デコード結果に制御文字が入っているものもあり、それらは除外する。 これでも複数の解が残っていることがあるが、異なる解であってもQRコードとしてのデコード結果が等しいものもあるので、デコード結果の中から最も多かったものを手で選んで送信。 これでも間違えになってしまうことがあって、2回目の挑戦で30問正解できた。
ノノグラムのソルバには最初はCoprisのもの http://bach.istc.kobe-u.ac.jp/copris/puzzles/nonogram/index.html を使っていたのだけど、解を列挙する機能がなく、ちょっと書き換えれば良いだけなんだけど、Scalaコンパイラの使い方調べるのが面倒だったので、Haskellで自前で書いてしまった。
それから、QRコードのノウハウがなかったので、最初は解から(chunky_pngで)画像を生成して、スマホのアプリで読み取ってとやっていたのだけれど、アプリの調子が悪かったのか自分が何かをミスっていたのか、列挙した解の中にQRコードとして妥当なものが見つからなかったりして、この辺りはだいぶ混乱してしまった。 これは、最終的にstrong-qr-decoderを見つけて、画像を介さずにテキストで自動処理できるようになって、なんとか助かった。
それから、通信周りはRubyで書いていたのだけど、net/httpでクッキーを扱うにはどうするのかとか、そういうしょうもないレベルでも色々ハマってしまった。