md5 - MD5 は 1 億の文字列を一意に識別できますか

Question

平均長が数百の数億の一意の文字列が与えられた場合、md5 はそれらのそれぞれを一意に表すことができますか? 衝突することはできますか？セキュリティは問題ではありませんが、一意性は重要です。

Answer 1

MD5 が 2^128 空間に沿って結果を均等に分散する場合 (そうではありませんが、かなり近い値です)、サイズnのコレクション内の 2 つの値が衝突する可能性を計算できます。これはしばしば「誕生日問題」と呼ばれます。

この計算の一部はわかりにくいかもしれないので、できる限り詳しく説明します。

Mを MD5 の範囲のサイズとします (MD5 は 128 ビットのハッシュ関数であるため、2^128) 。

この範囲内のランダム値の数を nとします (100,000,000 と言いました)

少なくとも 1 回衝突する確率 p は、次の式で計算できます。

指定した値を使用して:

で出てくる上記の方程式 に対する答えを提供してくれたDukelingに感謝します。式の詳細については、こちらをご覧ください。1.46E-230.0000000000000000000000146

Answer 2

攻撃者が悪意を持って衝突する文字列を作成することが懸念される場合は、MD5 を使用できません。それが問題にならない場合、MD5 は、現実的なユース ケースでの一般的な失敗率が 100 万年に 1 回の偶発的な衝突のオーダーであるアプリケーションには十分である可能性が高いです。

ただし、心配する必要がないように、さらに信頼できるものを選択することをお勧めします。他に何もないとしても、「壊れていることがわかっている」ことを考えると、MD5 を使用するという決定を常に弁護する必要があります。

たとえば、MD160を使用して 160 ビット ハッシュを取得したり、SHA-1 を使用して 168 ビット ハッシュを取得したり、SHA-256 を使用して 256 ビット ハッシュを取得したりできます。これらのアルゴリズムはすべて、衝突を見つけようとする努力にもかかわらず、既知の衝突はありません。偶発的な衝突は、小惑星の衝突による失敗よりも数十億倍少ない可能性があります。

最適な選択は、優先順位によって異なります。衝突の結果は何ですか？悪意のある攻撃に抵抗する必要がありますか? パフォーマンスはどの程度重要ですか? ハッシュサイズはどのくらい重要ですか? 詳細をお知らせいただければ、より適切なアドバイスを差し上げることができます。

Answer 3

MD5 などのどのタイプのハッシュ関数でも、同じ値にハッシュされる 2 つの文字列が存在します。したがって、一意の文字列のセットが与えられた場合、それらを詳細に分析するか、すべてをハッシュしない限り、これらのうちの 2 つが同じ値にハッシュされないことを確認することはできません。