先日開催したライブCTFの工夫点など (付記 CodeBlue CTF 2018 Finals Fuzzy Fault Writeup)
※この記事は CTF Advent Calendar 2018 13日目の記事です。
12日はxrekkusuさんの WebAssembly解いてみる - バランスを取りたい、14日はkotarou777775さんの CTF Reversing Challenges List Baby writeupまとめ - kriwの日記 でした。
博多市が所属しているサークルTSGでは、最近 TSG LIVE! と称してライブプログラミングの生放送配信を行っている。
その中の企画の1つとして「ライブCTF」という枠を用意しており、名前の通り生放送の時間中にCTFを行う様子を配信する⋯⋯ということをやっている。
前回11月の駒場祭で行った配信の様子は以下にアーカイブされているので是非見て頂きたい。
part1 (web day)
part2 (binary day)
放送時間は1枠90分、そのうち競技時間は75分であり、通常のCTFの競技時間を考えるとどう考えても短すぎるのだが、短すぎるなりに面白く見せるための工夫をいくつか行っている。そもそもライブCTFという企画自体が世界的に見て珍しい取り組みだと思うので、そういった点も含めていくつか開催する上での知見を共有しておく。
近年の動画コンテンツの躍進もあるので、個人的にはプログラミング界においてもこういった生放送企画や動画などが積極的に流行してほしいと願っている。
計画
webとbinaryで放送を分ける
まず今回のライブCTFを計画する上で一番大きかったのは、出題する問題のジャンルによって「web day」「binary day」という大きな区分を設けたことである。CTFというのはけったいな代物で、ジャンルによって要求される知識分野が全く異なるため、どうしても人によって得意不得意なジャンルが出てきてしまう。時間制限内で最大限のパフォーマンスを見せるためには、やはり自分の得意なジャンルの問題が出題される方がいいに決まっているので、今回webが得意なプレイヤーにweb問を、バイナリが得意なプレイヤーにはバイナリ問をという配役を行った。これは見る側の都合として自分の興味のあるほうの配信を見ればよいという利点もあるため、かなり良い決断だったと思う。
外部への問題公開
また今回は、プレイヤー用に用意した問題を外部にも公開し、プレイヤーと同時に自由に解いてもらえるようにした。これは前回開催時の外部からの要望を踏まえてのことだったのだが、作問をする上でのモチベーションに繋がったし、本番では予想を遥かに超えて様々なひとに参加してもらえた。準備段階では「参加するとしてもせいぜい数チームやろ」などと話し合っていたのが嘘のようで、本当にありがたい話である。
作問
今回、web day の作問は@kcz146に、binary day の作問は@satos___jpに、それぞれお願いした。同じサークル内から強いプレイヤーとそれ以上に強い作問者を拠出しないといけないのはかなり大変である。
今回、駒場祭への出展が決定したのが直前だったこともあって、準備期間がとてつもなく短く、作問は本当に修羅場だった。短い期間内でハイクオリティな問題を仕上げてくれた両名には改めて感謝を捧げたい。
テストプレイ
ライブCTFの作問は、「ちゃんと時間内に解ける問題を作る」という点で、通常のCTFにましてテストプレイが大事である。前回配信ではそのあたりを怠り、2日間全チームを通して解けた問題が1問だけという結果に終わったため、今回の作問では「絶対に解ける問題」という枠を用意し、少なくとも焼き鳥では終わらないように工夫した*1。テストプレイの際には必ず最初に問題を見てから解ききるまでの時間を計測してもらい、実際に放送時間で解ける問題かどうかをよく検討した。
プレイヤーと視聴者の問題サーバーの分離
また、問題を外部公開する上で一番気を使ったのがサーバーの耐性である。実況解説を行うという都合上、プレイヤーには可能な限り快適な環境で問題をプレイしてもらわないといけない。外部からのアクセスが殺到してサーバーが重くなったり、悪意ある攻撃でサーバーが落とされたりしたら配信に大きな支障が出る。
このようなことを踏まえ、作成した問題はプレイヤー向けと視聴者向けとでまるっきり同じ2つの環境を用意し、プレイヤー向けの環境では東大の外からのアクセスを遮断するようにした。本番では内部向け環境にトラブルがあったりしたが、外部向け環境で競技を続行することができたので、多重化が意図せずよく機能したとおもう。
本番
インフラ
今回、スコアサーバーおよび問題サーバーはGCPに置き、スコアサーバーはオープンソースのCTFdを使用した。このあたりの環境は全部インフラ担当の@kcz146が管理・構築してくれた。本当に感謝。
また、@kcz146は先に述べたとおり作問にも参加していたため、ライブCTF本番ではプレイヤー・実況解説も担当している。トラブルがあった時の対応のためにできればインフラ担当と分けておきたかったが、どうしても人員が足りなかったので妥協した*2。配信ではインフラには大きなトラブルがなくて本当に良かった。
おまけ: CodeBlue CTF 2018 Finals Fuzzy Fault Writeup
おまけとして、本来 CTF Advent Calendar の内容として書く予定だったがあまりに内容が無いので没にしたCBCTFのWriteupを置いておく。
CodeBlue CTF は、セキュリティカンファレンスであるCodeBlueの併設CTFであり、日本一の強豪CTFチームであるBinjaとTokyoWesternsが主催している。我らがチームTSGはなんと予選で世界4位、日本1位という好成績を収め、厚かましくもHarekazeやNaruseJunを蹴落とし、日本唯一の本戦出場チームとして東京の会場でDragonSectorやCyKORとお目見えすることとなった。
予選の様子はこちら↓
で、その11月1日から2日にかけて行われた本戦だが、事前に予告されていなかったバイナリ問題が中心だったこともあってTSGは英気揮わず、正式なスコアボードはまだ公開されていないものの少なくとも下から数えたほうが早い状況となり、まさに世界との格の違いを見せつけられる結果となった。しかしこうして本格的なオンサイトのCTFに参加したのは初めて*3の経験で、非常にわくわくしたし、寿司はおいしかったし、いろんな知見を得ることができた。
TSGとしてはとにかくボコボコにされた大会だったが、唯一の矜持としてjeopardyのcrypto問の “Fuzzy Fault" を解いたので、ここにそのWriteupを記しておく。
問題
問題文: CBCTF Fuzzy Fault · GitHub
AESに関する問題。FLAGから生成されたAESのRoundKeyを用いてランダムなデータを暗号化した結果が与えられる。これと同時に、同じ暗号化の8～10ラウンド目において1回ずつランダムな位置のバイトがランダムな値に書き換わった結果が与えられる。このようなデータペアが5セット与えられるため、ここからFLAGを推測せよ、という内容。
正気か?
解法
@yamayu832, @lmt_swallow, @taiyoslime などのメンバーとともに取りかかった。
博多市はまずAESという単語が暗号化に関する何かであることしか知らなかったので、問題の趣旨を理解するのにとても時間がかかった。他のメンバーは問題を見て即AES問だと気づき、さらにこれを100%自力で解くのは不可能と悟ったらしく、関連する論文をひたすら漁る作業をしていた。
一般にこのような、暗号化の過程にエラーを加えて正しい暗号化結果と比較することによる攻撃手法は Differential fault analysis と呼ばれる。特にAESに関してはよく研究されている攻撃手法の一種らしく、調べていくうちに@taiyoslimeが以下の論文を発見した。
Low voltage fault attacks to AES - IEEE Conference Publication
この論文に書いてある手法を用いることにより、最後のRoundKeyに関しては2**32通りを全探索する必要があるものの、正常なデータと不正なデータを比較してそのRoundKeyの正しさを検証することができる。
上の論文に記載してあるのはfaultが1度のみの場合なので少しシチュエーションが違うのだが、今回のように複数回faultが注入される場合も、データの汚染区域を追っていくことで似たように考えることができる。
AES問の解法メモです #cbctf pic.twitter.com/Ckvrje4vHw
— 博多市 (@hakatashi) November 2, 2018
上の図は例えばMatrixの左から2番目、上から2番目のバイトが汚染された場合の汚染区域の変遷を追ったものである。網掛けが一重の部分は汚染が一度混ざったデータ、二重の部分は汚染が二度混ざったデータである。
汚染が二度以上混ざったデータに関しては対応するRoundKeyを推測することが不可能だが、一度までなら上の論文と同じ手法で正しい値と比較することによりRoundKeyの値を探索することができる。上の図では、最後のInjectFaultが終了した時点で、2列ぶんのバイト列が一度のみの汚染で残っているため、これらの列に関してRoundKeyの値の探索が可能である。このように、(どこが汚染されるかによるものの) 多くの場合一部の列は一度のみの汚染で済むため、マトリックス上のこのような列を特定することにより論文の手法に帰着することができる。
実際にはどの列が無事かは単一のデータペアから推測することはできないが、複数のデータペアが与えられることによって推測することができるようになる。まずそれぞれのデータペアのそれぞれの列に対してRoundKeyが求まるものと仮定してRoundKeyの候補を一覧する。その後それぞれの列に対して、2つ以上のデータペアにわたって共通するRoundKeyの候補を見つけることによって、汚染されてないデータのペアと正しいRoundKeyを導くことができる。
スクリプトを走らせて調査すると、実際にそれぞれの列に関してそのような候補が1つ存在することが分かる。
$ ruby set.rb
Row 0:
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
#<Set: {"", "472737445"}>
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
Row 1:
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
#<Set: {"", "4068182999"}>
#<Set: {"", "4068182999"}>
#<Set: {""}>
#<Set: {"", "4068182999"}>
#<Set: {""}>
#<Set: {""}>
Row 2:
#<Set: {""}>
#<Set: {""}>
#<Set: {"", "2922383666"}>
#<Set: {"", "2922383666"}>
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
#<Set: {"", "2922383666"}>
Row 3:
#<Set: {""}>
#<Set: {"", "940379498"}>
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
#<Set: {""}>
で、これで求まるのは暗号化の最後のラウンドのRoundKeyである。FLAGにたどり着くにはここから最初のラウンドのRoundKeyを求める必要があるのだが、博多市には当初この手法が皆目検討つかなかった⋯⋯が、どうやらKeyExpansionを逆算して最初のRoundKeyを求める方法はよく知られていくらしく、@kcz146がすぐに以下のスクリプトを見つけてくれた。
ctf/inverse_aes.py at master · ResultsMayVary/ctf · GitHub
このスクリプトに先程求まった最後のRoundKeyを入力すると、最初のRoundKey, 即ちフラグが求まる。
Cipher key: 596f755f4172655f5468655f42657374 As string: ‘You_Are_The_Best’
フラグはCBCTF{596f755f4172655f5468655f42657374}である。
ソルバは以下の通り。一人で書いたのになぜかRustとNode.jsとRubyのハイブリッドである。なんでや。
cbctf2018-final/fuzzy-fault at master · tsg-ut/cbctf2018-final · GitHub
感想
非常に解き応えがあって面白い問題だった。これが正しい解法なのか知らないが、部分的に論文ゲーになったのは微妙かもしれない。いや、AESについてもっと詳しくなっておけというのはそのとおりなのだが⋯⋯。
