SECCON 2015 Online CTF Writeup(WebQR)
TMCTFに引き続き、ガッツリCTF参加しました。
あまりWriteupが見当たらないWebQRだけWriteup書きます。
(と言っても、ただ「やる」だけの問題なのですが、、)
概要
問題内容は、QRコードを4x4に分割したスライドパズルを50問も解けというもの。
最初の数問は、手動でも解けますが、
だんだん混ぜ方が複雑になってきて、回答が遅いと「遅すぎだよ!」って怒られます。
これ以外にもQR問題が何問かありましたが、時間制限付きはこの問題だけだったと思います。
なので、手動では得点を取らせてくれません。
自動で解くなり補助してくれるようなソフトを作る必要があります。
方針
どうやって自動で解かせるかについて考え、以下の内容で方針をたてました。
- スライドパズルを解かなくても、4x4に分割されてる各パーツがどの部分に配置されるかを考えれば、答えは作れる
- 真ん中の4パーツは別として、他のパーツは特徴があるので位置の判定が行い易い。
- VB.NETでWebBrowser上にロードし、各画像を取得して再構成、真ん中の4パーツは24通りなので総当りで解いていくのはどうだろうか。
- QR自体は適当なソルバーに投げる。
- ただしこの方法は、5x5や3x3など縦横が変則的なスライドパズルが出てきたら死滅する。
最後の懸念で結構ドキドキでしたが、結局以下のとおり問題ありませんでした。
- 1問目〜10問目 Easy:右下だけが欠ける
- 11問目〜20問目 Medium:辺のいずれかが欠ける
- 21問目〜30問目 MediumHard:中央4マスのいずれかが欠ける
- 31問目〜40問目 Hard:右下以外の隅のいずれかが欠ける
- 41問目〜50問目 Random:上記4種のいずれかのパターン
実装
VB.NETをまともに触るのは相当久しぶりでしたが、実装はそれほど困ることなく進みました。
まず、WebBrowserコントロールにページをnavigateして、
document.body.getElementsByTagNameで画像URLを取得・ダウンロードし、
それぞれをBitmapオブジェクトにして、GetPixelで色判定していきました。
角の判定
隅は、以下の条件で判別しました。
- 左上角のQRマーカーの真ん中の黒い■が全部黒で1ピクセル目が白なら左上確定
- 右上角のQRマーカーの真ん中の黒い■が全部黒で1ピクセル目が白なら右上確定
- 左下角のQRマーカーの真ん中の黒い■が全部黒で1ピクセル目が白なら左下確定
1ピクセル白判定は、スライドの空きマス(全部真っ黒)を判定から除外するためです。
辺の判定
辺部分の判定ですが、上下左右辺のどれであるかは、それぞれの辺側の白いスペースを判定に使うことで簡単に分かります。
ただし、辺は2パーツで構成されているため、どちらが上下左右に来るのかを判別しないといけません。
この判別については、手動で解いていた時に、左上のマーカーに隣接する場合は、隣接辺が白一色になっていることに気づき、同じような特徴をもう一方の隅に隣接する辺も持っていたため、これを利用しました。
ちょっと分かりづらいですが、図の青枠のところが白くなります。
中央4パーツの判定
ここまでで、方針で考えていた内容の実装は終わりなんですが、
実装しながら「中央4パーツも位置判別できるのでは」って思い、目を凝らしました。
総当りで試すより、簡単に判別できるなら判別してやっちゃった方が楽だと思ったからです。
中央4パーツは、それぞれ以下のような4条件を作ることで絞れました。
- 「上の1行目と2行目が一致しないなら上側ではない」
- 「右の1列目と2列目が一致するなら左側ではない」
- 「上の1行目と3行目が一致しないなら下側ではない」
- 「右の最後の列と2つ手前の列が一致しないなら右側ではない」
復号
位置判別後は、正しい位置に描画してあげるだけです。
QRの判別は、Q太郎というWindowsのQR復号ソフトと、iPhoneのアプリ(QuickMark)で行いました。
QR複合後に画面へ描画+クリップボードへ復号した画像をコピーする機能と、
文字列がコピーされたらTrimして回答を送信する機能だけつけました。
難易度Hardで問題発生
この方法で、30問目までは難なくクリアできました。
ときどきQ太郎で読めないQRがでた時は、iPhoneのQuickMarkで読み込ませて、
LINEの一人グループに貼り付けてと、コピペリレーしました。
31問目からは、いずれかの角のマーカーが欠けます。
そのため、そのままではQRを認識してくれません。
なので、適当に1問目から角のマーカー画像をとってきて保存しておき、
角だけは、描画時に保存してあるマーカー画像を上書き描画するようにしました。
これで31問目〜40問目も問題なく通りました。
41問目〜50問目は、これまでのパターンがランダムに発生するだけだったので、問題ありませんでした。
作業風景
左側に問題のWebサイト、右側に解答が表示されます。
解答生成時に解答画像がクリップボードへコピーされるので、
Q太郎では貼り付けボタンを押すだけで勝手に新しいQRを認識します。
Q太郎でフラッグをコピーすると、これも勝手に認識して、Trimしてから解答欄へ入力し、送信ボタンをinvoke("click")して次の問題に進みます。
辺が欠ける問題でたまーにQ太郎が認識しないことがあったので、その時はiPhoneのQuickMarkで代用しました。
50問目を解くと、フラッグが表示されます。
フラッグ
SECCON{U_R_4_6R347_PR06R4MM3R!}
ぐれーとぷろぐらまあ らしいです。やった!