自動化された整数ハッシュ関数探索技術
(github.com/skeeto)Hash Function Prospector
このツールは、整数ハッシュ関数を自動で探索するための小さなツールです。9種類の可逆演算の中からランダムに選択して、数十億個の整数ハッシュ関数を生成します。生成された関数はJITコンパイルされ、Avalancheの挙動が評価されます。現在、最良の関数がCの構文として出力されます。
- Avalancheスコア: 単一の入力ビットを反転したとき、平均して固定された状態で残る出力ビット数。スコアが低いほど良い。理想的にはスコアは0です。つまり、単一の入力ビットを反転すると、すべての出力ビットが50%の確率で反転します。
- Prospectorは32ビットと64ビットの整数ハッシュ関数の両方を生成できます。利用可能なオプションは使用方法（
-h）を参照してください。JITコンパイラのため、x86-64のみがサポートされますが、発見された関数自体はどこでも使用できます。
発見されたハッシュ関数
Prospectorとここにある他の補助ユーティリティにより発見された、2つの有用なクラスのハッシュ関数があります。どちらもxorshift-multiply-xorshift構造を使用しますが、ラウンド数が異なります。
2ラウンド関数
TheIronBornはこの構造の最良の既知パラメータを見つけるために、組み合わせ最適化を使用しました。
- この32ビット2ラウンド置換は特に低バイアスで、著名なMurmurHash3の32ビットfinalizerをわずかな差で上回ります。
- ハッシュ関数構造はProspectorで発見され、パラメータはヒルクライミングと遺伝的アルゴリズムを使って調整されています。
さらに低バイアスの2ラウンド定数があり、その中にはlowbias32よりも優れたものがあります。
3ラウンド関数
この構造にmultiply-xorshiftを1ラウンド追加すると、慎重に選択したパラメータで理論的なバイアスの下限に到達できます。例えば、このハッシュ関数は完全なPRFと区別がつきません。
triple32はhash(0) = 0の問題を解消するだけでなく、バイアスをさらに低減します。- さらに低バイアスの3ラウンド定数があります。
正確なバイアス測定
-Eモードは指定したハッシュ関数（-pまたは-l）のバイアスを評価します。標準では、Prospectorは関数のバイアスを高速に評価するために推定値を使用しますが、不確定であり、結果には多くのノイズがあります。正確なバイアスを網羅的に測定するには-eオプションを使用します。
-pとパターンを使うか、hash()を含む共有ライブラリと-lを使って評価対象となる関数を定義できます。- 64ビットハッシュ関数の正確かつ網羅的なテストは実行時間が長すぎるため存在しません。
可逆演算の選択
次の可逆演算を使用します。
x = ~x;x ^= constant;x *= constant | 1;（奇数定数のみ）x += constant;x ^= x >> constant;x ^= x << constant;x += x << constant;x -= x << constant;x <<<= constant;（左ローテーション）x = bswap(x)（上位バイトと下位バイトを交換）
技術的にはx = ~xはx ^= constantによってカバーできます。しかし~xは特有で、特に有用です。
16ビットハッシュ
16ビットハッシュには別の制約があるため、これらのハッシュを生成するための別ツールhp16があります。
- 32ビット/64ビット版Prospectorとは異なり、この実装は完全に移植可能で、ほぼすべてのシステムで実行できます。
- 128KiBのS-boxを生成および評価することも可能です。
- 16ビットハッシュは高速な乗算命令がないマシンでより必要となる可能性が高いため、探索時に特定の演算を省略できます（
-m,-r）。
いくつかの興味深い結果:
- 2ラウンドxorshift-multiplyハッシュ
- 3ラウンドxorshift-multiplyハッシュ
- 乗算を含まないハッシュ（xorshift-addのみ使用）
良好な3ラウンドxorshiftハッシュ（hp16 -Xn3の短い探索）は、優れたS-box（hp16 -S）に近いです。
16ビット演算を行う場合は、Cの整数昇格ルールに注意が必要です。このプログラムが出力するCプログラムでは、必要に応じて16ビット演算をunsigned intに昇格するよう配慮しています。
GN⁺の意見
-
ハッシュ関数の安全性は暗号学とコンピュータセキュリティで非常に重要な役割を担うため、このような探索ツールは研究に大きな役割を果たすと考えられます。特に、ランダム探索によってバイアスの低いハッシュ関数を見つけるのは興味深いことです。
-
ただし、統計的性質だけでハッシュ関数の安全性が保証されるわけではありません。暗号学的ハッシュ関数は、PreImage Resistance、Second PreImage Resistance、Collision Resistanceなど様々な攻撃に対して安全である必要があるため、これらの観点も含めた分析が必要だと思われます。
-
16ビットハッシュ関数は、IoTや組み込みシステムのような制約の厳しい環境で有用である可能性があります。乗算命令を持たないCPUでも使用できるように、ADD/XOR/SHIFTだけを使うハッシュ関数を作れる点が印象的です。
-
ハッシュ関数設計にヒルクライミングや遺伝的アルゴリズムのようなヒューリスティック探索手法を適用するのも新鮮なアイデアです。暗号アルゴリズム設計へのAI技術の導入が活発化する中、こうした最適化手法は将来さらに重要な役割を果たすと思われます。
-
ただし、Hash Functionには限界があるため、Avalanche特性がどれほど良くても、暗号学的に安全だと断言するのは難しく、これはこのプロジェクトの限界と考えられます。それでも、このツールを通して既存のハッシュ関数の問題点を分析し、改善するのに役立つ可能性があります。
1件のコメント
Hacker Newsコメント
multiply-shift-xor演算が長く支持され続けてきたことが興味深い