この記事は特に高速なハッシュアルゴリズムをまとめた資料です。
暗号的な強度が重要でない場合に使用できるアルゴリズムと暗号強度が考慮されたアルゴリズムがありハッシュ関数の利用環境あわせて検討すべきである。また、実行速度は実行環境に依存するので実際の実行環境で実測して判断するべきである。
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 の２つの欠点を改善している。
- 小さい入力に対して遅い
- mod を取った値が衝突しやすい
ハッシュの一方向性が弱い場合、タイミング攻撃でコリジョンが発生するペアが幾つか分かると鍵を推測してコリジョンを起こす他のメッセージを大量生成する事が可能となる。寿命の長いデーモンで鍵が更新されるまでにタイミング攻撃が出来るとハッシュ関数で鍵を使っていても HashDoS に対して脆弱となる。暗号論的な一方向性があれば、メッセージがコリジョンしたかどうかという情報から鍵を推測することは出来ないので攻撃者は衝突する異なるメッセージを作成することはできない。