高速ハッシュアルゴリズム

この記事は特に高速なハッシュアルゴリズムをまとめた資料です。

暗号的な強度が重要でない場合に使用できるアルゴリズムと暗号強度が考慮されたアルゴリズムがありハッシュ関数の利用環境あわせて検討すべきである。また、実行速度は実行環境に依存するので実際の実行環境で実測して判断するべきである。

MurmurHash

2008年に”Austin Appleby”が考案した非暗号ハッシュアルゴリムです。このアルゴリズムは暗号化処理などに向いていない。MurmurHash3は現在のバージョンで、32ビットまたは128ビットのハッシュを生成する。MurmurHash2は古いバージョンで、32ビットまたは64ビットのハッシュを生成する。64ビットのハッシュ値生成するソースには2つの変種がある。64ビットプロセッサ用に最適化された用のMurmurHash64Aと32ビットプロセッサ用に最適化されたMurmurHash64Bである。MurmurHash1は廃止されたバージョンです。

CityHash

MurmurHashアルゴリズムに触発されて、2010年にGoogleの”Geoff Pike”と”Jyrki Alakuijala”によって考案された特に文字列に有効な非暗号ハッシュアルゴリムです。このアルゴリズムは暗号化処理などに向いていない。文字列から32bit、64bit、128bit、256bitのハッシュを生成する。

CityHash128は128bitのハッシュを生成する。少なくとも数百バイトの列のために調整されている。コンパイラとハードウェアによっては十分に長いストリングでは CityHash64()より速くなる場合があるが短いストリングでは遅い。衝突を最小にしたい場合にCityHash128()の変種を使う。

CityHashCrc128とCityHashCrc256はSSE4.2のCRC32インストラクションを使用することで高速化した変種です。

FarmHash

2004年にGoogleの”Geoff Pike”と”Jyrki Alakuijala”によってCityHashの後継として考案された非暗号ハッシュアルゴリムです。このアルゴリズムは暗号化処理などに向いていない。文字列から32bit、64bit、128bitのハッシュを生成する。

xxHash

“Yann Collet”が考案した非暗号ハッシュアルゴリムです。このアルゴリズムは暗号化処理などに向いていない。32ビットまたは64ビットのハッシュを生成する。高速性を重視した圧縮アルゴリズムであるLZ4で使用されている。

SipHash

2012年に”Jean Philippe Aumasson”と”DJB”が考案した暗号ハッシュアルゴリムです。このアルゴリズムは一方向性を持つ暗号学的なハッシュ関数である。文字列から64bit、128bitのハッシュを生成する。128bitの生成の変種は実験バージョンである。SipHashでは、一方向性を持つ暗号学的なハッシュ関数であるMD5やSHA-Xの2つの欠点を改善している。

  • 小さい入力に対して遅い
  • mod を取った値が衝突しやすい

ハッシュの一方向性が弱い場合、タイミング攻撃でコリジョンが発生するペアが幾つか分かると鍵を推測してコリジョンを起こす他のメッセージを大量生成する事が可能となる。寿命の長いデーモンで鍵が更新されるまでにタイミング攻撃が出来るとハッシュ関数で鍵を使っていてもHashDoSに対して脆弱となる。暗号論的な一方向性があれば、メッセージがコリジョンしたかどうかという情報から鍵を推測することは出来ないので攻撃者は衝突する異なるメッセージを作成することはできない。

参考