yoggy's diary

◆ DEFCON 17 CTF - Pursuits Trivial 300の解説

先日のDEFCON 17 CTF予選のPursuits Trivial 300の問題は、一風変わった 迷路を解く問題が出題されていました。問題文は次の通りです。

 ?????.ddtek.biz:?????, provide 200 valid solutions in a row and you will get a prize, but you better be quick! Password == MAZE4J002PLAY
 ※????の部分は問題サーバのホスト名・ポート番号なので伏せています

netcatなどで指定されたサーバ・ポートに接続すると、ASCIIで迷路が表示され、 8秒以内にスタート地点からゴールまでの経路を入力します。

% nc ?????.ddtek.biz ?????
Password: MAZE4J002PLAY
Good luck! You have 8 seconds per maze.
Maze solutions must be presented as a single line of input.
##############
#........#.f.#
#.#.##.#..##.#
#...#..##....#
##.#..#.#.##.#
#.#..#....##.#
#..s##.#.#...#
#.#......#.#.#
##..##.#.....#
#..###.#.#.#.#
#.#.#.....##.#
#.#...#.#....#
#...##...##.##
#.#....#.....#
##############

※sがスタート地点、fがゴール地点で、n,e,w,sで方向を指定します。
 移動可能なのは上下左右で、斜めには移動できません

正解すると、また次の迷路が表示されるのですが、これを200回連続で正解すると 答えの文字列をゲットできるという感じの問題でした。

迷路の大きさは大きくても20x20程度のサイズなのですが、1問あたり8秒以内で 200回も連続して正解するのは人力だと無理なので、自動で解答する クライアントプログラムを作って対応します。

socketで接続して、問題を読み込んで、迷路の経路を解答するプログラムを組めばいいのですが、 解答に使用した迷路を解くアルゴリズムを簡単に説明します。 このアルゴリズムは、前提としてあらかじめ迷路全体の状態がわかっていることが必要です。

まず、下記のような感じの迷路があったら、

ゴール地点からの距離を移動可能な部分に書き込んで、

スタート地点から数が小さくなる方向に進んでいくと、スタート地点からゴール地点までの 最短パスを求めることができます。

迷路の大きさがそれほど大きくないので、単純に幅優先探索でもいいかもしれないですね。

…で、作っていて微妙にコーディングが面倒だと感じたのは実は迷路を解く以前の部分で、 通信プロトコル、迷路の読み込み、迷路クラスの作成などの部分でした。 迷路データの先頭にサイズを入れるとか、迷路データの終端に何か終端文字を入れるとか、 もう少しプログラムから読み込みやすいプロトコルを考えてほしかったなぁ…と思いました。 あと、解答を送信する際に終端に改行をつけないで送信しないとダメという仕様にも 少しはまってしまいました。

サーバ側での迷路の作り方にも多少問題があって、どうも乱数で適当にスタート地点とゴール地点を 配置していたっぽい雰囲気でした。 そのため、かなり適当に迷路の中にsとfの文字列を配置され、たまにスタート地点とゴール地点が重なっていて "s"の文字が迷路のどこにもないケースや、ごくまれにゴール地点が壁に埋まっていて どう考えてもゴールにたどり着けないケースが出現することがありました。

問題としては、何をすれば答えをゲットできるのか？という点ではかなり明確な問題で、 また、過去の問題にはなかったジャンルだったので、なかなか面白かった問題だったと思います。

◆ DEFCON 17 CTF予選の結果分析

先日AVTokyo CTFプロジェクトの方でDEFCON 17 CTF予選に参戦しました。結果は12位でした。

主催者サイトの方で詳細な予選結果が公開されたので、そのデータを元に DEFCON 17 CTF予選の結果を分析してみました。

データは以下の3つを使用しました。

• http://ddtek.biz/qualsDC17scores.txt (順位と得点一覧)
• http://ddtek.biz/qualsDC17_all_answer.txt (すべてのチームの解答時刻)
• http://ddtek.biz/qualsDC17_time_to_solve.txt (問題が開いてから最初に解答されるまでの所要時間)

まずは、問題が公開されてから解答するまでにかかった時間のグラフです。最速で解答したチームの所要時間、Top10チームの平均解答所要時間、今回のチームsutegomaと比較しています。 グラフを見ていると、今年から主催者がかわっていままでに無かった傾向の問題ではまっていたことが 多かったような気がします。発想勝負の問題に弱い傾向なのかも？

あとグラフを見ていて思ったのですが、解答するのにだいたい6時間を超えるような問題はかなり難しい問題が多いので、逆に「6時間以内に解けそうか？」というのを目安にして、作戦を考えた方がいいのかな？と思いました。

時間がかかる問題は難しいという前提で、出題者の点数配分は適切か？という視点で見ると、binary系の問題は難しい問題ほど得点が高く適切な点数配分だったと思います。しかしcrypt300、forensic100, potent100あたりの問題は点数が低い割には難しく、参戦している時もこの辺は点数配分がおかしいよなぁ…と思っていました。特にforensic100potent100はTop10チームの平均解答所要時間を判断基準にすると4番目に難しい問題となり、400点問題ぐらいにしても良かったのでは？と思う難易度だったと思います。

次に上位20位チームの得点推移のグラフです。このグラフの時間はUTCで表示しています。少しわかりにくいのですがチームsutegomaは紫色の線で表示しています。

これを見ていると、終盤戦で得点が停滞してしまって最後の追い込みで 他チームに抜かれまくってる感じです。 JSTなタイムゾーンから参戦していると、終盤戦は徹夜状態になってしまうのが ちょっと厳しいのかもしれないです。

あと、上位チームはどの時間帯でもコンスタントに細かく点数をとり続けて得点をのばしていることがわかります。チームsutegomaは前半をすぎたあたりから中盤までが停滞ぎみで、中盤のJSTな時間で2日目の昼に突然500点問題を2つ立て続けに正解して、急激に点数をのばしています。

去年のCTF優勝チームが今回の予選1位で、このチームはシード権を持っているチームなので、本戦へは10位までのチームが進出します。 チームsutegomaは12位の補欠の2番手で、欠員が2チーム出たときに 繰り上がりで本戦に出場できる位置にいます。

6/13現在、ここを見ていると、参加確認がとれていないチームがいてちょうど2枠開いている状態なのですが、毎年常連で強豪のセクシーパンダスが出場しないわけないよなぁ…と思いつつ、 最終的な結果が出るまではハラハラしながらサイトをチェックしたいと思いますｗ

6/19に最終的な本戦出場チームが決まるそうです。

◆ 声の「つぶやき」をTwitterに投稿するスクリプト

Windows環境で音声合成や音声認識をするSAPIの使い方を調べていたのですが、 ついでに音声認識した文字列をTwitterへそのままま投稿するRubyのスクリプトを作ってみました。

ソースはこちら

• sapi_tw.rb

require 'rubygems'
require 'twitter'
require 'win32ole'
require 'kconv'

# config
user = 'ユーザ名'
pass = 'パスワード'

$twitter = Twitter::Base.new(Twitter::HTTPAuth.new(user, pass))

# setup SAPI (for Speech Recognition)
context = WIN32OLE.new("SAPI.SpSharedRecoContext.1")
grammar = context.CreateGrammar(0)
grammar.DictationLoad
grammar.DictationSetState(1)

# for recognition event
event = WIN32OLE_EVENT.new(context, "_ISpeechRecoContextEvents")
event.on_event("Recognition") { |*e|
  text = e[3].PhraseInfo.GetText
  puts text
  $twitter.update(text.toutf8)
}

# main loop...
loop {
  WIN32OLE_EVENT.message_loop
  sleep(1)
}

何も考えずにしゃべって投稿してると、かなりカオスな発言になると思いますｗ

あと、実際に声に出さないと投稿できないので、職場とかでは使わないほうがいいかもしれないですね…