hash - ハッシュ関数の選択

Question

私は疑問に思っていました:ハッシュ関数の予想される衝突数を維持しながら、安全にハッシュできる最大バイト数はいくつですか?

md5 の場合は、sha-*、おそらく crc32 または adler32 です。

Answer 1

あなたの質問は明確ではありません。「最大バイト数」とは、「最大アイテム数」を意味しますか? ハッシュされるファイルのサイズは、衝突の数とは関係ありません (もちろん、すべてのファイルが異なると仮定します)。

そして、「予想される衝突回数を維持する」とはどういう意味ですか? 文字通り、答えは「無限」ですが、予想通り、特定の数を超えると衝突が発生します。

「x% 未満の衝突の確率を維持しながら、いくつのアイテムをハッシュできるか?」という質問に対する答えについては、次の表をご覧ください。

http://en.wikipedia.org/wiki/Birthday_problem#Probability_table

リンクから：

比較のために、10^-18 から 10^-15 は、一般的なハードディスクの訂正不可能なビット エラー率です [2]。理論的には、128 ビットの MD5 は、出力可能なドキュメント数がさらに多くなるとしても、約 8,200 億ドキュメントまではその範囲内にとどまるはずです。

これは、一様分布を出力するハッシュ関数を想定しています。ハッシュ化するのに十分なアイテムと、暗号化ハッシュ関数 (md5 や sha など) または適切なハッシュ (Murmur3、Jenkins、City、Spooky Hash など) があれば、それを想定することができます。

また、衝突を積極的にでっち上げている悪意のある敵がいないことも前提としています。次に、SHA-2 のような安全な暗号化ハッシュ関数が本当に必要になります。

注意: CRC と Adler はチェックサムであり、予想される衝突を最小限に抑えるのではなく、データの破損を検出するように設計されています。それらには、「最大 Z キロバイトまでの入力に対して、サイズ < X または > Y のすべてのビットゼロ化を検出する」などのプロパティがありますが、統計的なプロパティとしては適切ではありません。

編集：これはすべて確率に関するものであることを忘れないでください。0.5kb より小さい 2 つのファイルのみをハッシュして同じ SHA-512 を取得することは完全に可能ですが、その可能性は非常に低いです (たとえば、この日まで SHA ハッシュの衝突は見つかっていません)。

Answer 2

あなたは基本的に誕生日のパラドックスを見ていますが、本当に大きな数字だけを見ています。データの正規分布を考えると、問題が発生する前に、可能性の量の約5〜10％に達する可能性があると思いますが、何も保証されていません。

問題が発生しないように、十分な長さのハッシュを使用してください;）