サイバーコロッセオ × SECCON 2016に参加しました

サイバーコロッセオと呼ばれるCTFのコンテストに，チーム“m1z0r3_NSL”として参加しました．Koth形式のCTFは初めてだったのでとても良い経験になりました．この記事では，サイバーコロッセオがどのような競技であるか，また私の着手した一部の問題について書きたいと思います．(問題の説明は中盤からです)

サイバーコロッセオとは

SECCON 2016の大会の一部とした開かれたCTFのコンテストなのですが，公式の内容には以下のようにあります．

2020年東京オリンピック・パラリンピック競技大会開催に向けた総務省のセキュリティ演習事業 「サイバーコロッセオ」とコラボしたSECCON大会です。

サイバーコロッセオというのは，総務省のセキュリティ演習事業のことです．それを今回はSECCON2016の競技として行っていただけるようです．本競技はKing of the hillという形式のCTFで，計24チームが参加しました．先に結果を申し上げますと，私の所属していたチーム”m1z0r3_NSL”は893点で8位でした．

 

King of the hillって何 ?

King of the hill というのは，CTFにおける競技形式の一つです．CTFというのはセキュリティの知識を競うコンテストのことで，そのコンテストには3つの形式があります．“Jeopardy”, “Attack and Defence”, “King of the hill”の3種類です．

Jeopardy

一言で言うと，クイズ形式の競技です．1964年からアメリカで放送されているクイズ番組の名前が由来です．この形式では，セキュリティの知識を生かして，出題されたクイズ (問題) を解きます．問題を解くことで答えとなる文字列 (フラグ)を手に入れることができ，それを解答ページで入力・送信し，正解であれば得点が得られます．例えば，ジャンル「暗号」の問題においては，「この暗号を解読しろ．」という問題文と共に暗号文が渡されます．その暗号文を解読すると，「答えはFlag{It’s the flag!!}」というような文が手に入り，答えとなる文字列はFlag{It’s the flag!!}となります．フラグは，それが答えだと分かりやすいように，大抵の場合「大会名{なんらかの文字列}」のように，なんらかの文字列が中括弧で囲まれ，先頭にその大会・コンテストの名前がくっついているような形をしています．これはJeopardyに限らず，他の形式の大会でも同じだと思います．例えば，今回のコンテスト，「サイバーコロッセオ×SECCON 2016」のフラグ形式は，「SECCON{なんらかの文字列}」でした．

Attack and Defence (A&D)

その名の通り攻防戦です．各チームが自分のサーバを持っていて，自チームのサーバを守りながら他チームのサーバを攻撃します．競技開始と同時にサーバの脆弱性を調査し，自チームのサーバの脆弱性を潰しながら他チームのサーバを攻撃するプログラムを書く，というようなことを行います．Jeopardyがフラグをサブミットすることでしか得点できないのに対し，A&Dは攻撃で得られるAttack Point (AP)と，防御で得られるDefence Point (DP)の二種類の加点要素が存在します．

King of the hill (Koth / KoH)

A&Dの特殊形式・派生形式などと言われています．私の個人の見解では，JeopardyとA&Dの中間という感じです．複数の問題を持つ大きなサーバがあり，各チームはそのサーバにアクセスして問題を解きます．A&Dとは違いチームごとにサーバを持っているわけではないので複雑な攻防は無いですが，小数チームが物理的に一つの場所に集まって行われる形式なので，Jeopardyには無い面白いルールが用意されていたりします(A&DのようなAPとDPなど)

サイバーコロッセオにおけるKoth

以上を踏まえた上で，今回行われたサイバーコロッセオにおけるKothについて説明します．

• 問題サーバは6つ(大問が6問)
• それぞれのサーバに問題が3~4つずつ(小問が3~4つ，問題サーバ1,6は例外)
• 各問題サーバの小問を解くとAttack Keyword (フラグ)が手に入り，サブミットするとAttack Pointが入る
• Attack Point獲得後に特定のファイルにDefence Keywordを書き込むことでDefence Pointが入る

問題サーバが6つあり，それぞれのサーバに複数の小問があります．小問一つに答えとして一つのAttack Keywordがあり，これをサブミットすればフラグが得られます．

問題を解き進めると，DPを得るための行動ができるようになります．そうしたら，指示通りに，予めチーム毎に通知されているDefence Keywordを特定のファイルに書き込みます．運営側が一定時間ごと(5分毎)にチェックをして，Defence Keywordの書き込みがあれば，そのチームへDPが入ります．DPは一つの問題につき20ポイントと決められていますが，これは複数のチームとの折半となります．例えば，1つのチームだけがそのサーバを攻略し，Defence Keywordの書き込みを行っていたら，そのチームには5分毎に20ポイントが入ります．その後他の3チームが攻略し，Defence Keywordを書き込めば，5分毎に割り振られるポイントは20 / (1+3) = 5となり，各チームに5ポイントのDPが入ります．ですから，先にDefence Keywordの書き込みに成功したチームは，他のチームがDefence Keywordを書き込めないように妨害してきます．このルールを見ると，問題を解く形式の点はJeopardyに似ており，AP,DPを奪い合う点はA&Dに似ているということで，私がJeopardyとA&Dの中間という理由が伝わると思います．．

ここまで本競技では各問題にAPとDPがあるという説明をしてきましたが，問題サーバ1と6は例外で，上述のような得点形式ではありませんでした．問題サーバ1については後程説明いたします．問題サーバ6は，DPが存在せず，APのみが存在しました ．

手を付けた問題

いつものCTFと違って，大問が6つしかないので一応全てのサーバを見ました．序盤でサーバ1の問題に着手していたら他のメンバーが他の問題を解いてくれていたので，サーバ1を定期的に見たりサーバ6のpcapを見たりしていました．今回はサーバ1について説明したいと思います．

(他の問題の説明については他のメンバーが書いてくれると信じてる)

サーバ1：セキュアでなるべく小さなModulusを作れ

(何となく問題のタイトルをつけてみましたが，最終的なアプローチは少し変わってきます．)

サーバ1では，各チームは30分に一度，二つの素数をアップロードすることができます．「二つの素数(p,qとする)なんかをアップロードして何をするの?」というと，以下のようなルールに従い任意のp,qをアップロードする必要があります．

• 各チームが二つの素数p,qをアップロードし合う
• 素数p,qと，その積p*q (RSAで言うModulus) がランキングに表示され，そのランキングを競う
• 小さいModulus程ランキング上位に入る
• ランキングに表示される各Modulusに対し，ブレイクという行動が可能
• そのModulusを構成するp,qを特定してサブミットすることで，そのModulusをランキングから除外することができる
• ランキング1位を維持すると一定時間ごとにDPが入る

つまるところサーバ1は，他のチームがアップロードするModulusよりも小さくてかつブレイクされにくいModulusを構成できるp,qを見つけてアップロードする問題です．ここで重要なのが，「ランキング1位を維持すると一定時間ごとにDPが入る」という部分です．ここでいう一定時間というのは，他の問題でDefence Keywordを書き込んでいる時に運営がチェックをする5分毎という時間のことです．（私は一定時間とあるので必ずしも他と同じ5分とは限らないと思っていたのですが，確認したところ運営の方が他のDPのルールと同様5分毎に確認をしていると言っていました．）つまり，チェックをするのは5分毎なので，ずっと1位を維持していなくても，チェックの直前に1位になってチェックを受けられれば得点は貰えるということになります．だったらその時を狙って超小さいp,qをアップロードすれば良いじゃん，という話になるのですが，もう一つ重要なルールが「各チームは30分に1度しかp,qをアップロードできない」という部分です．つまりあまりにも弱い素数をアップロードしてしまうと (運が良ければ) 一度はDPを取れますが，それを過ぎると再アップロードのできない30分の間は絶対にDPを獲ることができなくなります．

つまり，この問題で素数をアップロードするアプローチは以下の二つに絞られます(たぶん)．

• 相手よりも小さいけども簡単にはブレイクされないModulusを作れるp,qを見つけて30分毎にアップロードする
• 安全性は度外視して，とにかく小さい素数を確実に1回DPを獲れるタイミング (30分毎) でアップロードする

私は，序盤は以下のようなコードを書いて，現在1位の人よりは小さいけど簡単にはブレイクされない素数を生成していました．

p,qのおおよそのbit数とか決める処理が適当なので，もっと頭良くできると思いますね．最後の方はなるべく大きめにしても仕方なかったので一個見つけたらbreakしてました．

最初のうちはこの選びかたで結構1位を維持できたのですが，途中からタイミングゲーになってきました(もとからそういうゲームだと言われればその通りなのですが)．30分のサイクルでたまたま競合の少ない5分毎のタイミングでアップロードできることが重要になってきまして，終盤はこのスクリプトの方法で選ぶよりも狙いすまして短い素数を挙げることに努めました．

また，素数のアップロード以外に，弱いModulusをブレイクするという処理も必要なのですが，これに関してはどのような手法が良いのかよくわかりませんでした．私はsageとyafuと自作のfermat法solverを回して，短いのは即ブレイク，長いのはワンチャンにかける，ということをしていました．ですが，やはり大きなModulusは全然sage等でもブレイクできなかったです．でも他のチームには大きめのModulusでもブレイクできてた方々がいました．是非ともやり方をご教授いただきたいです…．

 良かったこと・悪かったこと

良かったこととしては，チームで分担ができていたことだと思います．というのも，チームメンバーの得意ジャンルのバランスが良く，普段バイナリ担当なのが2人，Web担当なのが1人，暗号担当なのが1人の計4人でした．分担ができたといいつつバイナリ担当の二人に重荷を背負わせてしまいましたが，彼らは優秀だったのでどんどんAPを稼いでくれました．僕も他のサーバ攻略しなきゃとは思っていたのですが，序盤はサーバ1で結構調子が良かったのでそちらに注力していました．（とはいえサーバ1は30分に一度しかチャンスが巡ってこないので，さっさと自動化して，もっと早くwebnetwork担当のもう一人のサーバ6攻略を手伝うべきだったと感じます．）

あと，初めてのKothを楽しめたのは良かったと思います．

悪かったこととしては個人としてもチームとしてもめちゃくちゃあると思っています．自分の整理のためにも書くと，

• 準備不足 ( CTFを解く環境という意味で )
• 情報共有不足
• サーバ1の攻め方
• 冷静さ
• スキル不足

まずは準備不足です．本競技では問題サーバに繋ぐために無線ネットワークが用意されていました．持ち物に優先ケーブルが無いことや無線が使えるPCを指定されていたことから無線を使うことは分かっていたのですが，その影響で無線のアダプタを使ってしまうのでテザリング等で外のネットワークに繋ぐことができませんでした．つまるところ手軽にググったりslackとかで情報共有ができなかったんですね．我ながらアホだなと感じました．僕はiPhoneでケーブルを繋いでやってたのですが上手いことネットワークの設定ができず，両方繋ぐとiPhoneの方に引っ張られてしまって問題サーバに繋げなくなってしまったので，結局ほぼググったりせずに競技を進めて，どうしても必要な時だけ繋げ変えたりしていました．ググるのはともかくとして，slack等による情報共有ができなかったことで，一人がゲットしたAttack Keywordに記載されたヒントをスルーしてしまって次の答えがすぐに分からないという状況に陥ったりしたので，これは事前に考えておくべき事案だったと思います．

サーバ1の攻め方も他にも色々あったなぁと思っています．まず，素数の選び方ですが，

• 他の素数と被らないようにする
• next_primeなどの関数ですぐ見つからないようにする

などのチェックも入れても良かったかなと思います．普通はこんなんで重複することないと思うのですが，「前の人の素数よりは少ないけどなるべくセキュアなやつ」とかやっているともしかしたら作り方が他のチームと似ていて近い素数を選んでしまうなどが考えられるのかなぁとか思いました．また，ブレイクの方法については，

• 素数の使いまわしもチェックする

という手法もあったなぁと思いました．自分や他チームにブレイクされたModulusについてはブレイク履歴としてp,qが見れるようになる仕組みでしたので，その素数群を取ってきておいて使いまわしをチェックする，という手法もあったかなと思いました．

また，わたくし，少し浮足立っていました…．「何か会場かっけぇ」「強い人めっちゃおる！」こんな感じでなんかふわふわしていて，自動化スクリプト書くときも何かすごく効率の悪い書き方をしたりしていました．スキル不足で手を出せなかった問題もあるのでそこは精進が必要ですが，次は場慣れして冷静に問題を解きたいです．

感想

初めてのKing of the hill形式のCTFはとても良い経験になりました．オンラインCTFと違い対戦相手が近くにいるという環境，Jeopardyとは違うAP,DPという加点要素などから，普段とは違う楽しさを感じることができました．

もっと勉強して次はトラブルシューティングコンテストなどに参加してみたいです．大事なのはコンテストのための勉強にならないことだと思います．コンテストをモチベーションにすることは良いことだと思いますが，普段の勉強の成果を確認する場としてコンテストを活用するのが理想の形だと考えます．今後もセキュリティやインフラに関する知識を磨いていきたいこうと思います．

参考

• CTFとは