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

Javaセキュアコーディング入門（4）

Java実行環境やJava/Androidアプリへの影響

　Java言語仕様では、クラス階層の最上位に位置するObjectクラスがhashCode()メソッドを持つように規定されています。JDKにおける実装では、文字列を表すStringクラスのhashCode()メソッドは、以下のようにオーバライドされています。

JDK7付属のsrc.zipから引用

public int hashCode() {
    int h = hash;
    if (h == 0 && count > 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

　すなわち、文字列を構成する各文字の文字コードを使って以下のようにハッシュ値を計算しています。

n 文字からなる文字列 s[0] s[1] ... s[n-1] に対し
ハッシュ値 = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

　同じ文字列をキーとするデータを大量に登録させる、あるいは、ハッシュ値が衝突するような文字列を複数あらかじめ探しておき、それらを大量に登録させることができれば、ハッシュテーブルへの登録処理の効率を悪くすることが可能です。与えられた文字列から計算されるハッシュ値はいつでも一通りに決まっているために、ハッシュ値が衝突するような文字列をあらかじめ調べておくことができるのです。

　そのため、StringクラスのオブジェクトをキーとしたHashtableなどのクラスを使っているアプリケーションでは、登録するデータをプログラムの外部から受け付けている場合、DoS攻撃を受ける危険があると考えなければなりません。

　この問題に対する対策としては「randomizedハッシュ関数」を使うとよい、とされています。これはハッシュ関数の計算内容をプロセスごとに変化させるもので、ハッシュ値が衝突する文字列の組み合わせをあらかじめ用意することを困難にして、攻撃される危険を低減しようというものです。具体的なコードは（JavaではなくCですが）、次のセクションで Perlの対策例として紹介します。

　CCCの発表資料によると、OracleはJDK/JREにおけるハッシュ関数の実装をPerlのようなrandomizedハッシュ関数に変更するつもりはないようです。そのため、JDK/JREを更新することで対策を行うことは期待できません。Javaアプリケーション側で何らかの対策を行う必要があります。

　Javaアプリケーション側で行う対策としては、PerlやRuby 1.8で行われたようなrandomizedハッシュ関数を自分で実装して使うか、あるいは、最悪時の計算量がハッシュテーブルほど悪化しないjava.util.TreeMap<K,V>のようなデータ構造を使うように変更することが考えられます。

　そのような大きな変更が難しい場合には、回避策として、問題となる入力を受け付けないようにする必要があります。

　Apache Tomcatでは、HTTPリクエストの内容をハッシュテーブルに格納してWebアプリケーションに渡しています。そのため、攻撃者は細工したHTTPリクエストを送りつけることでDoS攻撃が可能です。Tomcatでは、以前から実装されているmaxPostSizeによってPOSTリクエスト全体の大きさを制限するか、新たに追加されたmaxParameterCountという設定項目によって、DoS攻撃に使われるような大量のパラメタを含むリクエストを拒否できるようにしています。

　このような回避方法では、アプリケーションの実装や実行環境、さらに稼働状況によって、制限すべき値（あるいは許容できる値の範囲）は変わってきます。サイト固有の状況を考慮して最適な値を検討する必要があるでしょう。

短期集中セミナーのお知らせ

　JPCERTコーディネーションセンターの講師陣による「Androidセキュアコーディングセミナー」を2012年3月14日に開催します（主催：翔泳社／CodeZine）。詳しくは特設ページまで！