水無月ばけらのえび日記

HashTableのアルゴリズムを突いたDoS攻撃

更新: 2012年1月20日1時0分頃

これは興味深いですね……「Webアプリケーションに対する広範なDoS攻撃手法(hashdos)の影響と対策 (blog.tokumaru.org)」。

ハッシュテーブルの実装では、まず配列を用意しておき、格納したいキーのハッシュ値を取って、値に対応するインデクスに値を格納する処理をします。こうすることで、キーを検索することなく、ハッシュ値を求めるだけですぐに値を取ってくる事ができるようになっています。

しかしながら、複数のキーのハッシュ値が衝突するようなケースもあり得ます。そのような場合は、仕方ないので同じインデクスに複数のキーをぶら下げておき、その中からキーを検索して値を取り出すことになります。つまり、キーのハッシュ値が衝突するとハッシュテーブルは遅くなりますし、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でハッシュテーブルの実装が変わって追加順序を保持するようになったという話を発見したので、その際に内部実装が変わって影響を受けなくなったのか……と一瞬思いました。

しかし、ハズレでした。なかださんが教えてくださったところによると、

……ということだそうで、意図的に対策しているとのことです (ありがとうございます)。

• 「HashTableのアルゴリズムを突いたDoS攻撃」にコメントを書く

関連する話題: Web / セキュリティ / Ruby