こんにちは。今年のDEFCON Qualifierで出題された問題を紹介します。CTF初心者の方にも参考にしてもらえるよう、試行錯誤した過程も含めて記事にしてみました。といっても、今回は私が散々悩みながら手をこまねいているうちに、仲間がサラッと解いてしまった問題です。扱う題材に専門性があるため、初心者の方には難しい文章になってしまいましたが、量子ビットを使った面白そうな問題でした。
DEF CON開始後、いつものようにpwn(用語集①)問題は若者達に任せて、年配者(?)でも何か出来そうな問題がないか探していたところ、しばらくすると幾つかcrypt(用語集②)問題がオープンしました。(DEFCONはpwn多過ぎじゃないですかね?)
問題文には、サーバーアドレスの表記と、5つほどのpythonのソースコードファイルが添付されていました。サーバーアドレスにnc(用語集③)すると、こんなメッセージが。
zardus: Hey hacker! Shall we play a game against QOO? There are two competitors here and they each will bet on 0 or 1. Let’s put our numbers there so that the sum of ours is same as the multiplication of theirs
ゲームなら、ワンチャンラッキーパンチが当てられるかもと思ったので、今年はコレにしようと心に誓いました。
5つのファイルの解析
まずは、添付されているファイルを斜め読みします。サーバーアドレスに接続した時に始まるゲームのソースコードの一部のようでした。私がzardusとチームになって、相手プレイヤーチーム(com1、com2)が出す数を当てるようなゲームで、30ラウンドのそれぞれで私が0か1をbetし、勝率が85%を超えるとzardusがadamdというゲームに登場する人物とのチャット内容を(AES(用語集④)で暗号化されたフラグ?)暴露してくれるような流れのように読めました。さらに、QuNetSimという量子ネットワークをシミュレートするフレームワークを読み込んでいて、手札の決定や暗号に、量子力学で有名な「重ね合わせ」や「エンタングルメント(量子もつれ)」が使われている雰囲気が感じられて、早くも気後れし始めます。。。。
実際の5つのファイルのソースコードを掲載すると長くなるので、ここでは割愛します。
解き方の考察
まずはQuNetSimのことは忘れて、フラグの取得の道筋を考えてみました。素直にゲームに85%以上の勝率で勝ったうえで暗号を解くか、それとも、ソースコードからはサーバー上のflagファイルを読み込んでいることが分かっているので、直接サーバーのflagファイルを覗くのか。CTFでの、この手のゲームは、正面からぶつかっても無理ゲーなことが多いと予想して、後者を狙ってしばらく試みるも、何の取っ掛かりも掴めず。その頃、ちょうど同じ問題に取り組んでいた暗号専門家の仲間(A氏)がチームの連絡用チャットに下記メッセージをくれました。メッセージ中の用語であるアダマールゲート(Hゲート(用語集⑤))は脚注にて補足します。
- ゲームの登場人物は、Hacker(私)、Zardus、com1、com2の4人。
- com1のベット値をもとにHackerが0、1、qoinを選択できる。
- Zardusのベット値はcom2の値が0なら0。com2が1ならアダマールゲートを通過した重ね合わせ状態の測定で0か1の確率が50%。
- “Hacker XOR Zardus == competitor1 * competitor2”が成立すればWIN。
あれ?と、いうことは、com1とcom2の手はランダムなので、「私は常に0を出し続ければ勝率75%じゃないのか?」と思いました。com2が0なら、相手の乗算結果は常に0だから、私が0を出せば100%でWIN。com2が1の場合は不定ですが、その場合でも私が0を出して勝率50%と考えると、0を出し続ければ全体の勝率の期待値は75%じゃないのか、と考えたのです。が、実際にやってみると、そうならない。勝率50%前後になってしまいます。その後、A氏とチャットで何度かやり取りするも、com2が0の時も、Zardsuが1を出す時があるといった、必ずしも上記のメッセージ内容と一致しないパターンがあるようで、公開されていないソースコードの部分で、結果に何かしら影響を与えているのでは?と、A氏は予想しているようでした。
私が出す手には、0と1の他に”qoin”というものがあります。ソースコードを見てわかる事は、qoinを選ぶと、量子状態をRyゲートにかけて回転させることができるようで、qoinを選んだ後に回転なし、右回転、左回転を選択できます。正直に言って、さっぱりわかりません。時間を掛けて調べようかとも思いましたが、暗号の専門家であるA氏なら簡単に読み解くだろうと予想して、私の(唯一の)役割は、勝率が85%を超えるまで力業でゲームをし続けるスクリプトを書くことだと思い直しました。というのも、qoinを選んだ時には、理屈は分かりませんが、明らかに勝率が上がる傾向が見て取れていて、毎回適当に回転方向を選ぶだけで勝率7~8割という結果が出せていたからです。言い方を変えると、量子ゲートの仕組みが全く理解できないので、早くもラッキーパンチを当てる作戦(苦し紛れの作戦)の採用という感じですね。
スクリプトをコツコツ書いていると、A氏からチャットのコメントが。
回転なしでflipさせたら、7回目で成功しました。 (前略) Do you want to rotate your qoin before flipping? 0. No, do not rotate my qoin 1. Yes, rotate left 2. Yes, rotate right 0 [Round 29]: zardus’s competitor bets on 1, you bet on 0 Win! com1 : 010011010100100011010001010000 com2 : 000100001101101110010000111101 hac : 010101100110000101101011000000 zar : 010001100011101111111011010100 res : 000100000001001000000000000100 your winning rate: 0.8666666666666667 zardus: очень хороший! You are my true good friend. I am gonna share with you my chat with adamd. Shhhh, don’t let him know. zardus receives from adamd: 0:0 zardus receives from adamd: 1:0 zardus receives from adamd: 2:0 (中略) zardus receives from adamd: 28:1 zardus receives from adamd: 29:0 zardus receives from adamd: -1:894f32b88ddf01fe9b656168260403b0 zardus receives from adamd: -2:b87256b47293a7b85cd8567014681ed5b668cac5b38795f1bebf997fbeccf212d2ea8b898349be98741824291f1c569b9afa1e85c9
さすがA氏。もともとA氏は、試行回数がたった30回なので、ある程度勝率が見込めるところまで見極められれば、確率の偏りで85%をすぐに突破できると踏んでいたようで、サッとスクリプトを書いて試行を繰り返していたようでした。確かに、最初から勝率85%と中途半端に設定している、このゲームには違和感がありました。ソースコード上の脆弱性を突く攻撃で突破する問題なら、勝率100%で次に進めるようにすれば良いのですから。量子力学という、確率でしか現せない曖昧な世界でCTF問題を作ったがゆえかもしれませんね。
ちなみに、後日談ですが、大会終了後に運営が公開した”隠されていたソースコード部分”を見たA氏は、「HackerのネットワークはZardusのネットワークにエンタングルドさせている。やっぱりホスト間で量子ビットを括り付けている。これが不明だったので、いろいろモヤモヤした。」と言っていました。私がベット値を決定すると、エンタングルドされているZardusの値が決定するといった仕組みの部分が隠されていたから、私が常に0を出していたとしても、勝率が期待値(75%程度)にならなかったということか???量子力学と同様に、全く腑に落ちないので、一旦はそういう理解にしておくことにしました。qoinについても、公式の解説で原理が解説されています。ご参考まで。
話は大会中に戻って、A氏のコメントの後半部分が暴露されたZardusとadamdのチャット内容です。Zardusのチャット発言の最後の2行がAES暗号のnonceと暗号文であることは、公開されたソースコードから自明。また、秘密鍵(secret_key)は、値は不明だが、ソースコードの流れを見ると2進数で15桁であることは分析でき、生成処理は下記のとおり。
def key_array_to_key_string(self, key_list): key_string_binary = b''.join([bytes([x]) for x in key_list]) return hashlib.md5(key_string_binary).digest()
A氏は「15bitぐらいならブルートフォースすればいい」と、総当たりするコードを書いてあっさりフラグをゲットしてくれました。
$ ./chall.py OOO{qoo_is_a_good_competitor_and_zardus_is_a_leaker}
その後、A氏は涼しい顔をして、back-to-qoo(次の問題)に進んでいました。恐るべし。
量子暗号について
ここで話が終わると、読者の学びがあまりないと思いますので、解法と直接関係しませんが、少しだけ量子暗号について補足します。量子暗号というのは、ご存じのとおり次世代を担う暗号技術と目されていて、量子力学の特性を用いています。2021年現在は、”量子鍵配送”のことを指すことが一般的で、送るデータは従来の共通鍵で暗号化をして、鍵を相手に送る際に量子暗号の技術を用いる(だから量子鍵配送と呼ばれている)というものです。量子鍵配送の優れている点は、鍵の配送過程で、盗聴されたかどうかが、分かるというもので、それを検出する仕組みは、量子力学の量子状態は観測によって歪む性質を応用しているらしいです。この量子力学で起こる、我々の常識では捉えきれない現象を使って、我々の日常生活に深く関わる暗号の問題(ネットショッピングでの安全性を担保している部分とか)を解決しようとする発想が、とても面白いですよね。
実は量子暗号の技術は日本が世界的にリードしている分野らしく、実用化に向けて日々研究が進んでいるそうです。私は勝手に、遠い未来の技術だと思い込んでいましたが、今回のDEFCONに使われていた、Pythonで書けるQuNetSimを見ていると、(原理はチンプンカンプンですが)実用化はそんなに遠い未来じゃないのかも、と思うようになりました。
用語集
- pwn: CTF問題のジャンルのひとつで、主にメモリ領域にアクセスをしてサーバーを攻略する問題
- crypt: CTF問題のジャンルのひとつで、暗号分野に関する問題
- nc(netcat): クライアントプロセスやサーバープロセスを起動することができるコマンド
- AES: Advanced Encryption Standardの略で、共通鍵暗号アルゴリズムのひとつ
- Hゲート: 量子ビットの状態を移動することができる回転ゲートのひとつ


記事の著者
セキュリティ製品「秘文」Web機能のプログラム開発リーダ及び、セキュリティコンサルタント チームのリーダを経て、現在は同社ホワイトハッカーチームのマネージャ業に従事。 主な社外活動として、IPA 情報処理技術者試験・情報処理安全確保支援士試験 委員、 経済産業省 情報セキュリティ人材の育成指標等の策定事業 委員、産業構造審議会 オブザーバ、 早稲田大学 非常勤講師、情報セキュリティ大学院大学 アドバイザリーボードなどを歴任する。
関連記事
RELATED ARTICLE