現代のソフトウェア開発を支える大きな技術のひとつにハッシュ関数がある。ハッシュ関数とひとえに言っても用途に応じて必要となる特性にも違いがあり一概にこうだとは言い難い。ハッシュ関数の用途としては次の３つがある。
- ハッシュテーブルのキー位置導出
- 改ざん検知
- パスワードの安全な保管・比較
ハッシュ関数でまず連想されるのは最初に挙げたハッシュテーブルだろうか。プログラミング言語によって Map と言ったり連想配列と言ったりするが、文字列などのキー値からそれに紐づく値を取得するデータ構造の代表例だ。このようなデータ構造の実現に必ずしもハッシュ関数が必要なわけではないが、O(1)相当の処理となり高速なためデフォルトの実装にはおおむねハッシュテーブルが使われる。*1
２番目の改ざん検知では、暗号学的ハッシュ関数と呼ばれるものが使われる。ハッシュ関数の結果（ハッシュ値）から元の値が推測できないなどの工夫がされている。この用途では永らくMD5が使われてきたが、衝突耐性の問題から SHA-1やSHA-2(SHA-256 など)が使われるようになってきている。最近ではより高速で安全性の高い BLAKE3という手法も発表されている。
３つ目のパスワードの安全な保管・比較もメジャーな用途ではある。パスワードそのものを補完すると流出や不正利用の危険性があるため、元のパスワード自体を保管するのではなくハッシュ化した値のみを保管する。
この用途では、BCYPT が永らく使われてきたが、コンピュータの高速化に伴い総当たり攻撃を受ける可能性が出てきたことから、最近はより総当たりコストの高い ARGON2 (argon2id) や SCRYPT を使うことが推奨されている。
実はここからが本題。
2、3番目の方法が数学に立脚したしっかりとした基盤の上に作られているのに対し、最初の用途のハッシュ関数は意外と探索的である。この理由としては、用途的に (1) ハッシュ関数の呼び出し回数が多くなりがちでパフォーマンスが極めて重要こと、(2) 分散の均一性は重要だがある程度均一性があれば十分なことが挙げられる。
究極的には n の入力に対し 0～n-1が割り当てられるようなハッシュ関数ができればデータ構造としては単なる配列で良くなり、速度的にも空間効率も優れたハッシュテーブルを作ることができる。もちろん、そのような手法は考えられていて、最小完全ハッシュ関数と呼ばれる。
じゃあ、それ使えばいいじゃん、と思うのだが、ところがぎっちょん*2、多くの制約があり意外に使いどころが難しい。
- キーの種類が事前に決まっている必要がある（＝キーが変われば作り直し）
- 最小完全ハッシュ関数を探すのに時間がかかる（＝構築に時間がかかる）
- 最小完全ハッシュ関数自体は速いとは限らない（＝ルックアップにも時間がかかる）
- キーに存在しない値に対するハッシュ値の範囲はキーのハッシュ値範囲とかぶるので、キーを保存しておきルックアップ後に再度比較が必要となる
この制約のため、最小完全ハッシュ関数を使っても効率が良いかは条件次第となる。
最小完全ハッシュ関数を探し出し生成するライブラリは昔からあり、有名なのは gperf である。gperf も決して効率が悪いわけではないが、大規模データセットには向かないようで、その場合には RecSplit アルゴリズムをサポートした cmph や PtHash を使ったほうがよいようだ。*3
調べ始めたきっかけは Set （値が True/False の2値からなる Map）を効率的に構築するするようなハッシュ関数を求める方法を知りたかったのだが、どうやらそんなものは存在しないようでまったく見つからない（もし知っていたら教えてください）。
通常は、事前にキーは決められないし構築にもそこまで時間はかけられないので、このような最小完全ハッシュ関数を使うことはできない。
この用途でのハッシュ関数の例として良く知られているのは Effective Java で紹介され有名になった要素に 31 をかけて足すという手法だろう。単純な方法ではあるが、うまく分散され衝突が少なくなることが知られている。
名前の付いた非暗号学的軽量ハッシュ関数の中で最も有名なのは MurmurHash だろう。2008年に発表されたこの関数は単純かつ高速なため、Ruby など多くのプログラミング言語の Map 実装に採用された（最新は MurmurHash3）。その後、これを契機に CityHash、FarmHash、MetroHash、xxHash など様々な高速ハッシュ関数が提案された。*4
しかしながら、意図的にハッシュ値の衝突を起こすことで分散を悪化させ、負荷をかける攻撃が可能なことが分かって以来、パフォーマンスも高く衝突耐性も高い暗号学的ハッシュ関数の SipHash が使われるようになってきている。*5
もちろんMapのキーを外部から指定できない用途であれば、MurmurHash など非暗号学的ハッシュ関数を使うことに問題はない。その方が制約が少ない分、よりパフォーマンスが良い方法を選択できる。*6
用途を特化し性能を高速化した例として Firefox や Rust コンパイラで使われている FxHash という手法がある。FxHash を使うと 64bit 環境で 8バイト分をまとめて計算できるため、うまく使えば高速化ができる。
*1:その他の方法として、B-Tree などの木構造アルゴリズムやBitSetを使う方法がある
*2:久々に使った
*3:各アルゴリズムの比較はこちらの資料がわかりやすい。PtHash はルックアップは速いが空間効率が悪い、RecSplitは空間効率が良いがルックアップは遅い、というトレードオフの関係がある。
*4:それ以前にも FNVHash という手法が存在している。
*5:Map は HTTP の GET パラメータの格納などにも使われる。キー値も攻撃者が自由に指定できるため、そのプログラミング言語を使っているアプリケーションサーバすべてに脆弱性が存在することとなるため、対応せざるを得ない状況があった。
*6:ハッシュ関数とは直接関係ないが、用途を特化することで手法の選択肢は増える。例えばURLのような超大規模なキーに対しては、ハッシュ関数の前処理として Bloom Filter を使い検索範囲を分割する方法や、ハッシュ関数を工夫するのではなく Cuckoo Hashing を使い探索回数を減らす方法も考案されている。mkhashtable というツールでは整数キーに対する Map の構築に Cuckoo Hashing が使われている。
