[レポート]キャッシュで踊ろう-Microsoft IIS ハッシュテーブルへの攻撃 – CODE BLUE 2022 #codeblue_jp

こんにちは、臼田です。

今回はCODE BLUE 2022で行われた以下のセッションのレポートです。

ハッシュテーブルは、コンピューターサイエンスにおける最も基本的なデータ構造であり、データを連想的に格納するためのソフトウェアアーキテクチャとして広く応用されている。しかし、その構造上、コリジョン攻撃を受ける可能性が高い。この問題に対処するため、25年前にMicrosoftは独自のDynamic Hashingアルゴリズムを設計し、MicrosoftのWebサーバーであるIISのあらゆる場所に適用して、HTTP Stackからさまざまなデータを提供するようにした。ハッシュテーブルがいたる所にあるように、Microsoftの設計は精査する価値があるのではないか？

われわれは、数カ月にわたるリバース・エンジニアリングを通じてIISの内部に潜入し、Hash Tableの実装とHash Tableアルゴリズムの使用の両方を検証してきた。 本研究では、いくつかのタイプの攻撃を提案し、発見した。 ① Microsoftの自己実装アルゴリズムに対して特別に設計されたゼロハッシュ・フラッディング攻撃 ② Hash-Key間の不整合に基づくキャッシュ・ポイズニング攻撃 ③ ハッシュの衝突に基づく異常な認証バイパス攻撃

この講演を理解することで、なぜハッシュテーブルを簡単に不安定にすることができるのか、驚かれることはないだろう。また、IISの内部をどのように調査し、その結果に驚いているのかを知ることができる。これらの結果は、デフォルトでインストールされているIISサーバーを100%のCPUでハングアップさせるだけでなく、細工したHTTPリクエストを通じて任意のHTTPレスポンスを変更することができた。さらに、IDキャッシュを衝突させることで、単一の細工したパスワードで認証要件を回避する方法を紹介する。

Presented by : オレンジ・ツァイ - Orange Tsai

レポート

• 前回日本に来てからしばらくぶり
• コロナ前は年に5-6回日本に来ていた
• 話す前にちょっとした事例
  • スーパーセキュアなログインでは、長いパスワードが必要
  • IISでは画面上の8桁の沢山のパスワードすべてが有効である
• 自己紹介
  • Webとアプリの脆弱性リサーチャー
  • 様々な肩書がある
• 概要
  • 重要なコンセプト
    • キャッシュについて理解する
  • リサーチ
  • 脆弱性
    • バイパスを説明
  • レコメンド

イントロ

• ハッシュテーブル
  • データサイエンスの基本的な構造
  • 簡単なものはキーバリュー
  • 幅広く使われている
  • OS / DB / Web Serverなど
  • プログラミング言語でも使っている
  • よりハイレベルな構造でラップする
    • 配列など
• Hash-Flooding Attack
  • Hashテーブルを悪用する
  • 同じバケットにすべてを入れる
  • 攻撃者が予測して悪用する
  • 攻撃者が悪意ある記録をいくつか作る
  • 最初のレコードは04に書き込める
  • 他のものも同じ場所に書き込める
  • そうするとテーブルが単一のリストになる
  • O(n2)となる
  • パフォーマンスがひどい
• IISはハッシュテーブルが大好き
  • 幅広く使っている
  • HTTPヘッダ、サーバー変数、キャッシュなどを保存する
  • 幅広く使われている
  • TREE_HASH_TABLE
    • 最もよくある共通のハッシュテーブル
    • Linked-Listにする
    • このハッシュ関数の使い方はあとから
  • LKRHash Table
    • 拡張可能
    • 同時並行のものを導入する
    • LKRは作成者の頭文字
    • Linear Hashingを活用
    • 作成者の一部はIISのチームにも所属している

リサーチ

• バグを見つけるだけでなく仕様に注目している
• キャッシュのメカニズムがメインターゲット
• 自身をOSSを使って設計していない
• メモリの破損やロジックバグを探していく
• CVE-2006-3017にフォーカス
  • PHPのインプリ
  • 攻撃者は恣意的なものでunset()できる
• Hash-Floodingも見ている
• ほとんどは解決済み
• インプリに注目していく
• LKRHashは持ち運びしやすい
• 自身のテーブル関連の機能を初期化できる
• バグを見つける機会を広げる
• どのようにコリジョンが起きたときに選べるのか
• 関係性を考える
  • リクエストを受けたときにHTTP.SYSがあつかい、ディスパッチする
  • アクティブなものがなければWASが新しいプロセスを起動する
  • Workerが動く
  • WorkerからIIS Modulesを読み込む
• IISはデフォルトで様々なモジュールを読み込む
  • グローバルキャッシュプロバイダーでいくつか管理される
    • 静的ファイル
    • ログオントークン
    • など
  • すべてロードされるとライフサイクルを入力
• リクエストライフサイクル
  • キャッシュクリーンなどにサブスクライブする
  • リクエストライフサイクルだけでなくグローバルキャッシュプロバイダーもターゲット

脆弱性

• 今回は2つ紹介
• FloodingとBypass
• どのように最大化するか
• Hash Flooding Attack
  • すべてのハッシュが影響をうける
  • 脆弱であるから侵入できるわけではない
  • いくつか乗り越えないといけない
• UriCacheModule
  • 良いターゲットに見えた
  • TREE_HASH_TABLEを使っていた
  • アクセス可能なTREE_HASH_TABLEは聞こえは良い
  • ランダム挿入とコリジョンがある挿入に違いがある
  • 35kと75kのジッターがおかしい
  • 通常は線形であるはず
  • なぜなのか
• 答えはリハッシュ
  • Insertのコードを見る
  • 重複がないことを確認する
  • RehashTableIfNeededという関数が実行される
  • しきい値はPrimeから選ばれる
  • 関数は表を拡大し再マッピングする
  • なのでなめらかに増加しない
• 高価なRehashを使う前に質問がある
  • いくつコントロールできるか
  • コリジョンはどうやるか
  • 制御できるのはURLのみ
  • すべてを大文字にしてハッシュ計算する
  • CalcHash関数
  • 101でかけて足す
  • ハッシュ関数はこれでいいのか？
  • No
  • DJBハッシュを変形したもの
  • 衝突可能であることが証明されている
  • Equivalent Substrings
  • 2つを組み合わせて違う値で同じハッシュを作れる
  • STRINGを繰り返せるので簡単に実現できる
  • しかしまだ弱い
  • 1つのリクエストで1つのレコードしか加えられない
  • 35k送らないといけないので遅い
  • しかもCache Scavengerがいる
  • 利用していない記録を30秒ごとに消去される
• これを乗り越えるためにimplementationに移る
  • この攻撃を助けられる挙動
  • キーを再帰的にスキャンする
  • 各サブディレクトリは新しい記録として扱われるので複数Insertで扱う
  • どうやってハッシュをサブディレクトリすべて衝突させるか
  • 0にすれば簡単
  • 0 Hashのセットを作って10倍の攻撃が可能になる
• 結果
  • サーバーを止めるのに30リクエスト/secで実現
  • デフォルトで影響したのでバウンティを獲得
  • youtubeにデモがある
• 認証バイパス
  • なぜ沢山のパスワードでバイパスできるのか
  • Logonはコストの掛かるオペレーション
  • パフォーマンスを落とさないようにすべてをキャッシュしている
  • LKRHashをつかう
  • 15分毎消去している
• LKRHash Table
  • 様々な関数がある
  • fnCalcKeyHash
  • fnEqualKeys
    • どれが正しいのかを確認する
    • 両方のメソッドとユーザーネームを2回チェック
    • なぜ2回？
    • 当初はパスワードをチェックするところで間違えて実装したのでは
    • コードをコピペしたので
  • これで問題が生まれる
  • Usernameだけでチェックするようになる
• 別のユーザーのログイントークンをランダムパスワードで再利用できる
  • 前提条件がいくつかある
    • 1/2^32の確率
    • 攻撃が成功する前にログインが成功して15分以内であること
  • これでこのバグは価値がなくなる
• このバグをより深刻なものにするために3つの方法を考えた
  • 衝突の可能性を増やす
  • ユーザーインタラクションなしで利用する
    • あまりかっこうよくないから
  • 15分の制限時間を突破する
• 衝突
  • 40億分の1はとんでもない
  • LCGで小さくできる
  • 辞書を事前に計算してキャッシュに入っていないパスワードを減らす
  • KeySpaceを減らして成功率を13%増やす
• Connect As
  • 通常はVirtual Hostingで使っている
  • これを再利用する
  • Windows Serverを1,800のログインを秒間で処理できる
  • ガチャでSSRを出すより確率を高くできた
  • 5日続ければ20%
  • 24日で100%に到達する
  • パスワードを5日で得ることができた
• 時間
  • 考えはシンプル
  • バックグラウンドデーモンを見ることが一般的
  • クレデンシャルがCRONにアタッチされている
  • 15分以内にアクセスしていればなくならない
  • ある
  • Exchangeサーバーの話
  • Active Monitoring Service
    • デフォルトで有効化
    • すべてのサービスを確認
    • 10分毎
  • クレデンシャルが永遠にキャッシュされる
  • 試したいだけ試すことができる
  • OWAのログインに利用することができる
  • メールボックスを持っている

レコメンド

• Hash Tableのデザイン
  • SipHash / HighwayHash
  • より攻撃者にコストを使わせられる
• Cacheデザイン
  • 不一致であることが根本
• 歴史から学ぶ
  • サイズ制限
  • シードを導入してハッシュをランダム化する

感想

相変わらず非常に面白い話でした。

近年オレンジ氏はMicrosoft製品について挑戦されている機会が多いですが、内容はすべてのアプリケーションに共通して大事な知見になりますね。