hash - md5ハッシュの衝突。

Question

1からXまで数える場合、Xは前の番号とmd5の衝突が発生した最初の番号ですが、Xは何番ですか？

シリアル番号にmd5を使用しているかどうか、衝突する前に列挙できると予想できるユニット数を知りたいです。

Answer 1

^{理論的には、Xの衝突は約264}であると予想できます。nビットの出力を持つハッシュ関数の場合、約2 ^{n / 2}の出力を累積すると最初の衝突が発生します（入力の選択方法は関係ありません。連続する整数値はその点で特別なことではありません）。

もちろん、MD5は優れたハッシュ関数ではないことが示されています。また、2 ^n/2は平均にすぎません。じゃあ、やってみませんか？MD5実装を取得し、シリアル番号をハッシュして、衝突が発生するかどうかを確認します。基本的なMD5実装では、1秒あたり数百万の値をハッシュできる必要があります。適切なハードディスクを使用すると、数十億の出力を蓄積して並べ替え、衝突があるかどうかを確認できます。

Answer 2

私はあなたの質問に答えることはできませんが、あなたが探しているのはuuidです。UUIDシリアル番号は何百万もの製品で一意である可能性がありますが、衝突のわずかな可能性を軽減するためにデータベースをチェックする必要がある場合があります。

Answer 3

私は誰もこれについていくつかのテストを行っていないと信じています

単純な増分数がある場合は、ハッシュする必要がないことを考慮してください

Answer 4

私の知る限り、md5には2 ^ 32（整数のサイズ）の既知の衝突はありません。

Answer 5

それは本当にあなたの入力のサイズに依存します。完全なハッシュ関数には、（input_length / hash_length）ハッシュごとに衝突があります。入力が小さい場合、衝突はほとんど発生しません。これまでのところ、1ブロックの衝突は1回しかありません。

Answer 6

これは古い質問だと思いますが、私はそれに遭遇し、はるかに優れたアプローチを見つけ、それを共有したいと思いました。

序数Nには上限があるので、それを利用しましょう。^{N< 232≈4.3} *1010^としましょう。これで、新しい識別子が必要になるたびに、ランダムな32ビットの数値Rを選択し、それをR xor N（連結前のゼロパッド）と連結します。これにより、ランダムに見える一意の64ビット識別子が生成されます。これは16進数で16桁で表すことができます。

同じランダム成分を持つ2つの識別子は必然的に別個の排他的論理和成分を持つため、このアプローチは衝突を完全に防ぎます。

ボーナス機能：このような64ビット識別子を2つの32ビット数値に分割し、それらを相互に排他的論理和して、元の序数を復元できます。