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

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

Perlの"randomized"ハッシュ関数

　2003年のUSENIX Security Symposiumの論文を受けて、Perlはバージョン5.8.1において、内部で使っているハッシュ関数に対策を行いました。PerlはC言語で実装されていますが、その方法自体はJavaアプリ開発者にとっても有用な情報だと思いますので、ここで紹介します。

　以下に、対策が行われる前（5.8.1より前）に使われていたハッシュ関数PERL_HASH()（のマクロ定義）を示します。引数として渡された文字列strに対し、文字列に含まれる各文字の文字コードを使ってハッシュ値を計算し、引数hashに代入します。引数lenは文字列strの長さです。

#define PERL_HASH(hash,str,len) \
  STMT_START		       { \
 register const char *s_PeRlHaSh = str; \
 register I32 i_PeRlHaSh = len; \
 register U32 hash_PeRlHaSh = 0; \
 while (i_PeRlHaSh--) \
     hash_PeRlHaSh = hash_PeRlHaSh * 33 + *s_PeRlHaSh++; \
 (hash) = hash_PeRlHaSh + (hash_PeRlHaSh>>5); \
} STMT_END

　JDKのStringクラスのhashCode()メソッドのところで説明したように、1つの文字列に対して計算されるハッシュ値はいつも同じ値であり、ハッシュ値の衝突を起こす文字列の集まりを一組用意すれば、どのサイトに対する攻撃にも使いまわすことができます。そこでPerl 5.8.1では、スクリプトの実行ごとにハッシュ関数が計算する結果を変化させることで、攻撃を受けにくくしました。

　以下が対策済みのコードです。

/* hash a key */
/* FYI: This is the "One-at-a-Time" algorithm by Bob Jenkins
 * from requirements by Colin Plumb.
 * (http://burtleburtle.net/bob/hash/doobs.html) */
 * ......
 * The "hash seed" feature was added in Perl 5.8.1 to perturb the results
 * to avoid "algorithmic complexity attacks". */
#define PERL_HASH(hash,str,len) \
     STMT_START		       { \
 register const char *s_PeRlHaSh_tmp = str; \
 register const unsigned char *s_PeRlHaSh = (const unsigned char *)s_PeRlHaSh_tmp; \
 register I32 i_PeRlHaSh = len; \
 register U32 hash_PeRlHaSh = PERL_HASH_SEED; \
 while (i_PeRlHaSh--) { \
         hash_PeRlHaSh += *s_PeRlHaSh++; \
     hash_PeRlHaSh += (hash_PeRlHaSh << 10); \
 hash_PeRlHaSh ^= (hash_PeRlHaSh >> 6); \
 } \
 hash_PeRlHaSh += (hash_PeRlHaSh << 3); \
 hash_PeRlHaSh ^= (hash_PeRlHaSh >> 11); \
 (hash) = (hash_PeRlHaSh + (hash_PeRlHaSh << 15)); \
 } STMT_END

　hash_PeRlHaShの初期値が単なる0ではなく、PERL_HASH_SEEDを使うようになっています。また、この初期値の変化が最終的な計算結果にも影響を与えるように、ハッシュ値の計算式自体も先ほどより複雑になっています。PERL_HASH_SEEDの値として乱数を使うことにより、計算されるハッシュ値はそれに応じて変化します。ある初期値ではハッシュ値が衝突するキーの組み合わせがあったとしても、異なる初期値ではハッシュ値が衝突しないようになります。攻撃者の観点では、DoS攻撃を行うための入力をあらかじめつくっておくことが難しくなる、というわけです。

　ちなみにRuby 1.8系では1.8.7-p357で対策が行われましたが、Perlと同様の対策を行ったそうです。

おわりに

　今回はハッシュテーブルの実装に対する攻撃手法とその対策について解説しました。ところでJDK/JREではなぜStringクラスのhashCode()実装をrandomized版にしないのでしょうか？ 正確なところはOracleからなにも表明されていないので分かりませんが、以下のような理由が推測できます。

• StringクラスのhashCode()のアルゴリズムはドキュメントに明記されている。そのアルゴリズムに依存するような実装を行なっているアプリケーションでは、いきなりhashCode()の中身を変更すると影響が大きい。
• ハッシュテーブルをシリアライズして別のプロセスに渡す場合、復元するプロセスでのハッシュ関数は違った計算結果を出すので、復元時にハッシュテーブルを構成しなおす処理が必要となる。そこまで含めての対応を考えると不可能ではないだろうが時間がかかる。

　なお、Javaセキュアコーディングスタンダードには今回の内容に対応するルールがありません。「リソース枯渇（攻撃）を防ぐ」という観点で類似のルールとしては、

• IDS04-J. ZipInputStreamに渡すファイルサイズは制限する
• MSC05-J. ヒープメモリを使い果たさない

などがあります。

　より直接的に今回のような問題を防ぐためのコーディングルールを新たに追加する必要がありそうです。

参考文献

• ハッシュテーブル
• JVNVU#903934: ハッシュ関数を使用しているウェブアプリケーションにサービス運用妨害 (DoS) の脆弱性
• 28C3: Effective Denial of Service attacks against web application platforms（28th Chaos Communication Congressでの講演）
• Cryptanalysis >> Effective DoS attacks against Web Application Plattforms
• 12th USENIX Security Symposium - Abstract Denial of Service via Algorithmic Complexity Attacks（元になった攻撃手法に関する2003年の論文）
• java.lang.String
• java.util.TreeMap
• [SECURITY] Apache Tomcat and the hashtable collision DoS vulnerability
• Denial of service attack was found for Ruby's Hash Algorithm (CVE-2011-4815)
• Perlのハッシュ関数を含むファイルの差分（OpenBSDのリポジトリに取り込まれているPerlのソース）
• perldoc.perl.org: perlsec Algorithmic Complexity Attacks

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

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