hack.lu CTF 2016 Write-up (Crypto 200 「cornelius1」)

person 73spicafolder_openCTFaccess_time 2016-10-20

2016/10/19 19:00 ~ 10/20 19:00 に開催されたhack.lu CTF 2016というオンラインCTFに参加いたしました.

今回は比較的多くのチームメンバーと参加することができました(結果はあまり振るわなかったのですが…).

hack.lu CTF 2016

名前の通りのCTFです.ゲームボードはこんな感じで,凝ったフォントのページでした(見づらいのは確かですが私は好きですw).

hacklu_2016_gameboard

(関係は無いかもしれませんが,)時期的にハロウィンっぽくもあり,かわいいらしい感じです.

また,本CTFの特徴は,「問題を解くと規定の得点以外にボーナス点を得ることができ,解くのが遅いほど獲得できるボーナス点数が減るというところでした.他のチームが解いた問題はどんどん点数が下がってしまうんですね….途中参加して追い上げよう!ということが難しそうです.

単に解いた人数に応じて点数が変動する形式だった気がします。

手を付けた問題

  • CthCoin (Crypto/Web 150 pts)
  • redacted (Crypto 200 pts)
  • cornelius1(Crypto 200 pts)
  • cryptolocker (Crypto 200 pts)

解けた問題

  • cornelius1 (Crypto 200 pts)

redactedcryptolockerはチームの暗号班のリーダーが解いてくれました(リーダーのwrite-up).cornelius1は僕がフラグを取ることとなりました.

cornelius1 (Crypto 200 pts)

問題ウェブサイトへのリンクRubyのプログラムが渡されます.ウェブサイトではそのRubyのプログラムが動いているようです.サイトにアクセスするとこんな画面になります.

cornelius_server

Hello fnordとだけ表示されます.これでは何もわからないのでプログラムを見てみます.

Rubyのプログラムは以下になります.

どうやら,クエリに“?user=hoge”と投げることで,fnordの部分に表示される文字列をhogeにすることができるようです.

しかし今回はbodyに表示される部分はどうでも良く,Cookieやらget_auth関数やらencrypt関数に着目します.

Cookieにget_auth(user)の返り値をセット

htmlのbodyに,”hallo fnord”と表示している以外に,Cookieに値をセットするという処理をしています.どんな値をセットしているかというと,get_auth関数の返り値を渡しています.get_auth関数へ引数としてuserの値を渡していることもわかります.

では,get_authでは何をしているかと言いますと,フラグのキーファイルを読み込み,userの値と共にJSON形式に変換し,zipのdeflate圧縮にかけてencrypt関数に渡しています.つまり,下記のようなJSONをdeflate圧縮した後に暗号化をした値をCookieにセットしているわけです.

[“user:クエリのユーザ名”,”flag:フラグの値”]

では,暗号化を施しているencrypt関数を見てみます.

encrypt関数はAES-CTRモード

encrypt関数の処理はズバリAESのCTRモードです.

AESとは,Advanced Encryption Standardの略です.これ以前に使われていたDES (Data Encryption Standard)と呼ばれるブロック暗号に変わる暗号化方式で,アルゴリズムとしてRijndaelと呼ばれるブロック暗号が使われています.ブロック暗号にはモードという概念があり,モードによって暗号化の処理が変化します.今回はCTR (カウンターモード)と呼ばれるモードを使っているようです.

encrypt関数はめっちゃセキュア

まず最初に考えたことは,encrypt関数の脆弱性です.何か脆弱性が無いかと探していましたが,結論から申し上げますとどこからどう見てもセキュアでした.

というのも,そもそもブロック暗号におけるCTRモードは推奨されるセキュアな暗号方式なのです(電子政府における調達のために参照すべき暗号のリスト参照).

deflate圧縮に注目する

あと目につく特徴的な処理と言えば,get_authで行っているdeflate圧縮でしょうか.AES-CTRで暗号化する前に一度deflate圧縮をかけています.実は,知っている人であれば,とある攻撃手法を思い出すはずなのです.

CRIME : SSL暗号化を無効化する攻撃

CRIMEとはCompression Ratio Info-leak Made Easyの略です.例のごとくWikipedia先生を引用します.

2012年にBEAST攻撃の報告者によって、TLSにおいてデータ圧縮が有効な場合において、本来第三者に対して秘密であるべきCookieの内容が回復可能となるCRIMECompression Ratio Info-leak Made Easy, 英語版)が報告された,

少しだけ補足をします.

まずCRIMEは,SSLやSPDY(あるいはHTTPボディ部のgzip圧縮)で使われる圧縮アルゴリズムを逆手に取って行われる攻撃です.この圧縮アルゴリズムがdeflate圧縮です.

deflate圧縮はLZ77と呼ばれる処理とハフマン符号化と呼ばれる処理を組み合わせた圧縮処理です.

LZ77は繰り返し出てくる文字列を省略するという処理です.ハフマン符号化は頻出文字を短いビットに割り当てて符号化(0,1に直す)することで文字列を短くします.要するに,繰り返しの文字列が多く含まれるほど圧縮後の文字列は短くなるのです.

今回の問題に適用する

問題を解きつつ,CRIMEの攻撃手法について説明をしていきます.今回deflateで圧縮されているのは,userとflagの値をJSON形式に変換したものです.例えば,userを73spicaにする(url?user=73spicaとしてアクセスする)ことで生成されるJSONは以下のようになります.

[“user:73spica”,”flag:フラグの値”]

説明しやすいように,フラグの値を以下のように変えてみましょう.

[“user:73spica”,”flag:nanami_chiaki_is_very_cute”]

これがdeflate圧縮されるわけですが,この文字列をdeflate圧縮してもあまり文字数が短くなりそうにありません.なぜならdeflate圧縮は,繰り返し文字列が多く表れるほど高率良く圧縮されるからです.

そこで,userを別の文字列に変えてみましょう.例えば”na”とします.

[“user:na“,”flag:nanami_chiaki_is_very_cute”]

“na”という文字列は3回も出てきています.こういう場合,deflate圧縮は効率よく圧縮を施し,文字列を短いものにします.

では,フラグを知らないとして,こんな文字列をuserにしてみます.

[“user:flag:“,”flag:nanami_chiaki_is_very_cute”]

こうすると,”flag:”という文字列が2回出てきているので,効率よく圧縮されそうですね,では,以下の二つはどちらの方が効率よく圧縮されそうでしょうか.

[“user:flag:a“,”flag:nanami_chiaki_is_very_cute”]

[“user:flag:n”,”flag:nanami_chiaki_is_very_cute”]

二つ目の方が一致部分が多いので,二つ目の方が効率よく圧縮されそうですね.実際に二つ目の方が圧縮後の文字列は短くなります.

つまり,仮にフラグの1文字目が”n”だと知らなくても,“flag:a” , “flag:b”, …と順番に試していけば,“flag:n”の時だけ圧縮後の文字列が短くなります.今回圧縮後の文字列はbase64エンコードされてCookieに入りますので,Cookieの値をbase64デコードして長さを見れば,どの文字の時だけ圧縮後の文字列が短くなったかわかりそうです.

Solverを書く

つまり今回実装する処理はこうです.

  1. クエリを”?flag:a”としてアクセス
  2. cookieの値を取得してbase64デコードしたものの文字列の長さを保持する
  3. クエリを”?flag:b”としてアクセス
  4. cookieの値を取得しtbase64デコードしたものの文字列の長さを保持する
  5. 1~4のように,flag:に続くと思われる1文字を全て試し,一つだけ短くなったものを正解とする
  6. 1~5をJSONの要素の終了である”(ダブルクォート)まで繰り返す

前の文字よりも短くなった時点でそれを正解とし,正解がなかったら1文字目が正解としています(明らかに一つ短いと分かったら終了とする処理を書いた方が高速かもしれません).

flag

この問題はフラグ形式がflag{}ではないとのことですので,

The flag is “Mu7aichede” .

まとめ

本問題のアプローチのまとめは以下になります.

  • Cookie, deflate, AES-CTRという情報から,CRIMEを使った攻撃ができることに気づく
  • 実装

知っていればやるだけ,というシンプルな問題でした.実際プロの方もやるだけとおっしゃっていました(誰とは申し上げませんが).

余談

CthCoinが中々簡単な解法だったようで…(sig.upper()的な…).ジャンルCryptoではないような気がします.

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">