HashTableのアルゴリズムを突いたDoS攻撃
2012年1月5日(木曜日)
HashTableのアルゴリズムを突いたDoS攻撃
更新: 2012年1月20日1時0分頃
これは興味深いですね……「Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 (blog.tokumaru.org)」。
PHPなど多くの言語では、文字列をキーとする配列（連想配列、ハッシュ）が用意されており、HTTPリクエストのパラメータも連想配列の形で提供されます。PHPの場合、$_GET、$_POSTなどです。
連想配列の実装には、高速な検索が要求されるためハッシュテーブルが用いられます。ハッシュテーブルは、文字列を整数値（ハッシュ値）に変換するハッシュ関数を用いて、平均的には一定時間に検索・挿入・削除が行えるデータ構造です。しかし、ハッシュ値が一致する（衝突する）キー文字列については、通常ハッシュテーブルは順次的な探索となり、検索・挿入などが遅くなります。
ハッシュテーブルの実装では、まず配列を用意しておき、格納したいキーのハッシュ値を取って、値に対応するインデクスに値を格納する処理をします。こうすることで、キーを検索することなく、ハッシュ値を求めるだけですぐに値を取ってくる事ができるようになっています。
しかしながら、複数のキーのハッシュ値が衝突するようなケースもあり得ます。そのような場合は、仕方ないので同じインデクスに複数のキーをぶら下げておき、その中からキーを検索して値を取り出すことになります。つまり、キーのハッシュ値が衝突するとハッシュテーブルは遅くなりますし、CPUを使うことになります。
この攻撃のポイントの一つは、データを格納する時点で問題が起きるということです。通常、ハッシュテーブルでは同一のキーを複数持つことができず、既に存在するキーの値を追加しようとすると、既存の値を上書きするようになっています。そのため、データを挿入する際、そのキーが既に存在するかどうかをチェックすることになります。
ハッシュ値が衝突するキーがたくさんあればあるほど、検索は遅くなります。追加しようとするたびに検索が走り、その検索の負荷は追加されたキー数に比例しますので、負荷は衝突するキー数に比例するのではなく、衝突するキー数の二乗に比例します。衝突するキーを増やすと、とても効率の良いDoSができるというわけです。
これは言語のハッシュテーブルの実装の問題ですので、影響範囲はWebアプリケーションに限定されません。にもかかわらずWebについて言われているのは、値が自動的にハッシュテーブルに格納されるためです。
Webアクセス時、ほとんどの環境では、HTTP要求ヘッダの内容がハッシュテーブルに格納されます。衝突するような名前のフィールドを大量に入れておくと、その値をキーとしたハッシュテーブルが自動的に作られて攻撃が成立します。先に述べたように、ハッシュテーブルにデータを格納する時点で問題が発生しますので、アプリケーションで値を使っていなくても影響を受けてしまいます。
※2012-01-19 追記: HTTP応答ヘッダと書いていましたが、HTTP要求ヘッダの誤りでした。
※2012-01-20 追記: HTTP要求ヘッダの列挙だけではApacheの通常の制限で100件程度しか送れないため、POSTデータやクエリ文字列を使う、Cookieを利用するなどが必要になるようです (参考: Cookieによるhashdos攻撃と対策 (blog.tokumaru.org))。
根本的な対策としては、ハッシュテーブルにデータを格納する際のハッシュ値を予測困難にすることが考えられます。たとえば、キーの値をそのままハッシュアルゴリズムに通すのではなく、ランダムな値を連結してからハッシュ値を取るようにします。こうすると、ランダムな値が知られない限り、攻撃者は衝突するキーの組み合わせを用意することができません。
言語側でパッチが続々と出ていますので、適用すれば解決します。パッチが適用できない場合は、徳丸さんも書かれているように、リクエストを制限することで問題を緩和することができます。
ところで余談ですが、今回の問題、古いRuby1.8は影響を受けるがRuby1.9はそもそも影響を受けない、という話を耳にしました。少し調べたところ、Ruby1.9でハッシュテーブルの実装が変わって追加順序を保持するようになったという話を発見したので、その際に内部実装が変わって影響を受けなくなったのか……と一瞬思いました。
しかし、ハズレでした。なかださんが教えてくださったところによると、
その二つは無関係。順序はforeachの高速化のためにdouble linked listにした副作用。衝突耐性は今回の1.8.7同様random seedの追加によるもの(と多分MurMur hash化による逆演算の困難化も少々)。
以上、https://twitter.com/#!/n0kada/status/154775878142935040 より
……ということだそうで、意図的に対策しているとのことです (ありがとうございます)。
- 「HashTableのアルゴリズムを突いたDoS攻撃」にコメントを書く
- 前(古い): FF13-2 モンスター育成その3: 銀チョコボ
- 次(新しい): マリオカート7 三つ星達成