開発チーム内での議論に決着をつけようとしています:
64 ビットの PHP ハッシュ関数を探しています。MurmurHash3 の PHP 実装が見つかりましたが、MurmurHash3 は 64 ビットではなく、32 ビットまたは 128 ビットです。
同僚 #1 は、MurmurHash3 から 64 ビット ハッシュを生成するには、128 ビット ハッシュの最初 (または最後、またはいずれか) の 64 ビットをスライスするだけで、ネイティブと同じくらい衝突防止になると考えています。 64 ビット ハッシュ関数。
同僚 #2 は、衝突を減らすためにネイティブの 64 ビット ハッシュ関数を見つける必要があり、128 ビット ハッシュの 64 ビット スライスはネイティブ 64 ビット ハッシュほどの衝突防止にはならないと考えています。
誰が正しいですか？
Murmur3 の代わりに SHA1 のような暗号化ハッシュの最初 (または最後、またはいずれか) の 64 ビットを取得すると、答えは変わりますか?
実際にランダムで一様に分散された値がある場合、「スライス」は、最初から小さい値で開始した場合とまったく同じ結果をもたらします。理由を理解するために、次の非常に単純な例を考えてみましょう: ランダム ジェネレーターが 3 つのランダム ビットを出力するとしますが、使用するランダム ビットは 1 つしか必要ありません。出力が
b1 b2 b3
可能な値は次のとおりです。
000, 001, 010, 011, 100, 101, 110, 111
すべてが 1/8 の確率で発生します。これらの 3 つのビットから、目的に合わせてスライスしたビット (1 番目、2 番目、3 番目) が何であれ、位置に関係なく、「1」になる確率は常に 1/2 になります。「0」についても同じことが言えます。 '。
この実験は、128 ビット中 64 ビットの場合に簡単にスケールできます。スライスするビットに関係なく、特定の位置で 1 または 0 になる確率は半分になります。これが意味することは、一様に分布した確率変数からサンプルを取得した場合、スライスによって衝突の可能性が高くなったり低くなったりすることはないということです。
ここで、衝突を防ぐためにランダム関数が本当に最善であるかどうかという問題があります。しかし、結局のところ、関数がランダムから逸脱するたびに、衝突を見つける確率が増加することを示すことができます。
実際の問題は、ハッシュ関数がまったくランダムではないことです。逆に、それらは退屈なほど決定論的です。しかし、暗号化ハッシュ関数の設計目標は次のとおりです。初期状態がわからない場合、その出力は実際のランダム関数と計算上区別できなくなります。つまり、ハッシュ出力の違いを計算上効率的に区別する方法はありません。および実際のランダム値。これが、半分よりも高い確率で実際のランダム値からハッシュを伝える方法である「識別器」を見つけることができれば、ハッシュはすでに一種の壊れていると見なす理由です。残念ながら、既存の暗号化ハッシュのこれらのプロパティを実際に証明することはできませんが、誰かがそれらを破らない限り、これらのプロパティがある程度の自信を持って保持されると想定できます.プロセスを説明する SHA-3 サブミッションの 1 つの識別子について。
要約すると、特定の暗号化ハッシュの識別子が見つからない限り、スライスはまったく問題なく、衝突の可能性は増加しません。
非暗号化ハッシュは、暗号化ハッシュと同じ一連の要件を満たす必要はありません。それらは通常、非常に高速であると定義され、「健全な/善意の条件下で」特定の特性を満たしますが、誰かが悪意を持って操作しようとすると、簡単に不十分になる可能性があります。これが実際に何を意味するかの良い例は、今年初めに発表されたハッシュテーブル実装に対する計算複雑性攻撃 ( hashDoS ) です。通常の状態では、非暗号化ハッシュは問題なく機能しますが、巧妙な入力によって衝突耐性が大幅に損なわれる可能性があります。これは、暗号化ハッシュ関数では起こり得ません。その定義そのものが、あらゆる種類の巧妙な入力の影響を受けないようにする必要があるためです。
非暗号化ハッシュの出力に対して上記のような識別器を見つけることは可能であり、場合によっては非常に簡単であるため、暗号化ハッシュ関数としての資格がないとすぐに言えます。違いを見分けることができるということは、出力のどこかにパターンまたはバイアスがあることを意味します。
そして、この事実だけでも、それらが多かれ少なかれランダム関数から逸脱していることを意味し、したがって (上で述べたように) 衝突はおそらくランダム関数の場合よりも発生する可能性が高くなります。最後に、完全な 128 ビットでは既に衝突がより高い確率で発生するため、これはより短い出力では改善されません。その場合、衝突はおそらくさらに発生する可能性が高くなります。
tl;dr切り捨てるときは、暗号化ハッシュ関数で安全です。ただし、出力が大きい非暗号化ハッシュを 64 ビットに切り詰めるよりも、「ネイティブ」な 64 ビット暗号化ハッシュ関数の方が適しています。
なだれ効果により、強力なハッシュとは、ソースの 1 ビットの変更により、平均してハッシュの半分のビットが反転するものです。適切なハッシュの場合、「ハッシュネス」は均等に分散されるため、各セクションまたはスライスは均等に分散された量のソース ビットの影響を受け、同じビット長の他のスライスと同じくらい強力です。なれ。
ハッシュが優れた特性を持ち、均等に分布している限り、私は同僚 1 に同意します。
この質問は、これが言及されていないと不完全なようです:
一部のハッシュは、特定のクラスの入力に対して完全なnハッシュであることが証明されています (たとえば、の妥当な値に対する長さの入力に対してn)。そのハッシュを切り捨てると、そのプロパティを破壊する可能性が高くなります。その場合、定義により、衝突の割合がゼロからゼロ以外に増加し、そのユース ケースでハッシュが弱体化します。
これは一般的なケースではありませんが、ハッシュを切り捨てるときの正当な懸念の例です。