「キャッシュで踊ろう-Microsoft IIS ハッシュテーブルへの攻撃」の解説 (1) - CODE BLUE 2022
2022.12.12 公開
はじめに
このエントリでは、DEVCORE に所属するオレンジ・ツァイ氏の CODE BLUE 2022 での講演「キャッシュで踊ろう-Microsoft IIS ハッシュテーブルへの攻撃」の中から、Microsoft Internet Information Services (Microsoft IIS) 製品の UriCache モジュールの処理にサービスを妨害される問題 (CVE-2022-22025 ) を取り上げて解説いたします。解説にあたり、同氏の CODE BLUE 2022 での講演だけでなく、同氏のブログ記事 や Black Hat USA 2022 で使用したとされる講演スライド も参考にしています。
以下は、継続的脆弱性管理ツール SIDfm VM での当該脆弱性情報の画面を表示したものです。
前提となる用語
まず初めに、混乱を避けるため、このエントリで用いる用語について簡単にまとめておきたいと思います。
ハッシュ関数について
ハッシュ関数とは、任意の長さの入力から固定長の値を出力する関数です。出力された値にはいくつかの呼び方がありますが、このエントリではハッシュ値と呼ぶことにします。
ハッシュテーブルについて
ハッシュテーブルとは、キーを使用して値へアクセスする辞書のようなデータ構造です。キーに対する値を格納する場所はバケットと呼ばれており、どのバケットにどの値を格納するかは、キーから計算したハッシュ値を元に決定します。このエントリ内では、キーと値のペアをレコードと呼ぶことにします。
ハッシュテーブルでは、バケットへのアクセスにキーから計算したハッシュ値を用いるため、レコードの検索・追加・削除の際の計算量は基本的に一定 (O(1)) で、キーの数に計算量が左右されることはありません。
衝突について
ハッシュ関数は、様々なデータから固定長の値を取得する都合上、異なる入力データから同じ値を出力する可能性があり、これを衝突と呼んでいます。ハッシュテーブルで衝突が発生した場合、2つ(または複数)のキーが同じバケットを示すことになってしまうため、データの格納を調整することになります。この調整方法には、別のバケットに値を格納するオープンアドレス法や、値を連結リストに格納するチェイン法などが知られています。どちらの方法を利用するにしても、ハッシュテーブルへアクセスするための計算量は確実に増大し、衝突が多数発生している場合は無視できない計算量になる可能性があります。
ハッシュフラッディング攻撃とは
ハッシュフラッディング攻撃とは、意図的に衝突を多発させることによってリソースを浪費させる攻撃です。衝突の解決にチェイン法を使用しているハッシュテーブルに対しては、異なるキーを持つ全てのレコードを同じバケットに追加する形で攻撃を仕掛けます。チェイン法は同じバケット内の連結リストに値を格納しているため、単一のレコードの検索・追加・削除に必要な計算量は最大で O(n) になります。
Microsoft IIS の UriCache モジュールの処理にサービスを妨害される問題 (CVE-2022-22025 )
さて、前提となるお話はここまでとして、ここからはツァイ氏の講演の内容にダイブしたいと思います。
Microsoft IIS では様々なコンポーネントでハッシュテーブルを使用していますが、ツァイ氏はその中のひとつである UriCache モジュールに着目しました。マイクロソフト社の説明 では、構成など URL 固有のサーバ状態の汎用キャッシュの実装、とされています。ツァイ氏は UriCache モジュールについて次のように述べています。
- デフォルトでリモートからアクセス可能
- アクセスごとにハッシュテーブルに対し検索・追加・削除が発生
- ハッシュテーブルには「TREE_HASH_TABLE」を使用
同氏によれば、TREE_HASH_TABLE は衝突の解決にチェイン法を使用するとされています。またハッシュ関数は DJBX33A の亜種であると述べられています。（補足：ハッシュ関数 DJBX33A は、容易に衝突を発生させることができることで知られています。衝突を発生させる方法については「ハッシュアルゴリズムと衝突 」の説明がわかりやすいです。さらに詳しい説明として「Efficient Denial of Service Attacks on Web Application Platforms 」などもありますので、興味のある方はご参照ください。）
ツァイ氏は講演の中で、TREE_HASH_TABLE で使用されているハッシュ関数に対して衝突を発生させる方法を説明しています。DJBX33A での衝突と同様に、まず同じハッシュ値を持つ異なる文字列のグループ（これを衝突グループと呼びます）を見つけ、衝突グループの文字列を連結することで同じハッシュ値を持つ新たな文字列を生成するというものです。方法の詳細についてはツァイ氏の Black Hat USA 2022 の講演スライド の p.57 〜 59 をご参照ください。
さて、衝突を発生させることはできましたが、実際にサービス妨害を成立させるためには膨大な数のリクエストが必要な上に、Cache Scavenger によって使用していないレコードは 30 秒ごとに削除されてしまうため、何か別の工夫が必要となります。
ツァイ氏は、TREE_HASH_TABLE のハッシュテーブルへレコードを追加する処理において、URL からハッシュテーブルのキーとなる部分を切り出すロジックに問題があるため、本来は 1 回のレコードの追加となるところを「スラッシュで区切られたサブディレクトリの数プラス 1 回」のレコード追加となる処理を発見しました。この挙動を利用することで、ひとつのリクエストから複数のレコードをハッシュテーブルへ追加することができます。またこの挙動により、衝突を発生させることがやや難しくなりましたが、ハッシュ値が 0 となるような文字列を各サブディレクトリ名として使用する工夫によって衝突を発生させるようにしています。（Black Hat USA 2022 講演スライド p.63 〜 69）
ツァイ氏によれば、1 秒あたり 30 回のリクエストを送信することによって 8 コア 32 GB RAM の Microsoft IIS サーバを応答不能にできたとのことです。 Windows Insider Preview Bounty Program の報奨金として同氏は $30,000 を獲得しています。この金額はサービス妨害のカテゴリでの最高額です。
対策
修正プログラム
Microsoft IIS の UriCache モジュールの処理にサービスを妨害される問題 (CVE-2022-22025 ) は、ツァイ氏によって発見された他の 2 件の脆弱性と共に、2022年7月のセキュリティ更新プログラムで修正されています。
更新履歴
-
2022年12月12日
- 新規公開
参照
- Orange Tsai, "Let's Dance in the Cache - Destabilizing Hash Table on Microsoft IIS!," Orange Blog, Aug 18, 2022.
- Orange Tsai, "Let's Dance in the Cache: Destabilizing Hash Table on Microsoft IIS," Black Hat, Aug, 2022.
- "Windows インターネット インフォメーション サービス Cachuri モジュールのサービス拒否の脆弱性 | CVE-2022-22025," Microsoft Security Update Guide, Sep 12, 2022.
