ハッシュテーブルに対する攻撃手法のはなし

ハッシュテーブル実装に対する攻撃とは

　昨年12月末にドイツで開催されたCCC（Chaos Communication Congress）において、"Effective Denial of Service attacks against web application platforms"（Webアプリケーションに対する効率的なDoS攻撃）と題した発表が行われました。タイトルに「Webアプリケーション」とついてはいますが、この問題はWebアプリケーションに限ったものではありません。以下の三つの条件が揃ったアプリケーションであれば例外なく、DoS攻撃の餌食となる危険があります。

• ハッシュテーブルというデータ構造を使っている
• ハッシュ値を計算するアルゴリズムが「脆弱」である
• ハッシュテーブルに登録するデータをプログラム外部から指定できる

ハッシュテーブルとその問題

　Wikipedia（日本語版）ではハッシュテーブルについて以下のように説明しています:

（「ハッシュテーブル」概要より引用）

ハッシュテーブルはキーをもとに生成されたハッシュ値を添え字とした配列である。 通常、配列の添え字には非負整数しか扱えない。そこで、キーを要約する値であるハッシュ値を添え字として値を管理することで、検索や追加を要素数によらず定数時間O(1)で実現する。しかしハッシュ関数の選び方（例えば、異なるキーから頻繁に同じハッシュ値が生成される場合）によっては、性能が劣化して最悪の場合O(n)となってしまう。

　ハッシュテーブルは、大量のデータを効率よく管理したい場合に使われます。Perlやawkなどの連想配列の実装にもハッシュテーブルは活用されています。

　また、Javaでハッシュテーブルといえば、標準APIとしてHashtableクラスやHashMapクラスなどが提供されています。

ハッシュテーブル

　Wikipediaの説明にもあるように、ハッシュテーブルは、入力データによっては処理の効率が悪くなる場合があることに注意が必要です。Wikipediaの説明では「異なるキーから頻繁に同じハッシュ値が生成される場合」と書かれています。異なるキーが同じハッシュ値を持つということは、異なるキーに対応する値を、ハッシュテーブルの「同じ」位置に置くことになります。

　このように複数のデータのハッシュ値が同じになった場合の対処方法はいくつかありますが、単純なやり方としては例えば、テーブルの各エントリを線形リストとして用意しておき、同じハッシュ値を持つデータは該当するエントリ位置の線形リストで管理します。JDKのHashtableクラスもそのような実装になっています。

　同一のハッシュ値を持つデータが多くなるほど線形リストを辿る場面が多くなり、登録や検索の効率は悪くなります。登録するデータのほぼ全てのハッシュ値が同一であった場合、処理のほとんどは線形リストの操作となり、効率の大幅な低下を招きます。攻撃者としては、そのようなデータを与えることができれば、DoS攻撃を行うことが可能になる、というわけです。

　この攻撃手法は2003年のUSENIX Security Symposiumで最初に発表されました。2011年末のCCCにおける発表は、この手法が、今現在広く使われているアプリケーションやフレームワークにも適用可能であることを示したものです。