2 つのメッセージが同じ MD5 ダイジェストと同じ SHA1 ダイジェストを持つ可能性はどれくらいですか?

StackOverflow https://stackoverflow.com/questions/1323013

質問

2 つの異なるメッセージ A と B (サイズが重要な場合は、おそらく 20 ～ 80 文字のテキスト) がある場合、A の MD5 ダイジェストが B の MD5 ダイジェストと同じである確率はどれくらいですか? そして A の SHA1 ダイジェストは B の SHA1 ダイジェストと同じですか?あれは：

(MD5(A) == MD5(B)) && (SHA1(A) == SHA1(B))

悪意はないと仮定します。つまり、メッセージは衝突を見つける目的で選択されたものではないと仮定します。これが自然に起こる確率を知りたいだけです。

その可能性は「天文学的に低い」と考えていますが、これを確認する方法がわかりません。

詳しくは：考えられるメッセージのプールのサイズは制限されていますが、大きい (数億) です。誕生日のパラドックス状況はまさに私が心配していることです。

役に立ちましたか？

解決

ランダムな文字列の MD5 および SHA-1 ハッシュの範囲内で一様な広がりがあると仮定し (実際にはそうではありません)、文字列のプールについてではなく 2 つの文字列についてのみ話していると仮定します (誕生日のパラドックスを回避します)。 -タイプの複雑さ):

MD5 ハッシュの幅は 128 ビットで、SHA-1 のハッシュ幅は 160 です。上記の仮定により、2 つの文字列 A と B は、両方のハッシュが衝突する場合、P と衝突する確率があります。それで 

P(both collide) = P(MD5 collides) * P(SHA-1 collides)

そして 

P(MD5 collides) = 1/(2^128)
P(SHA-1 collides) = 1/(2^160)

それで

P(both) = 2^-128 * 2^-160 = 2^-288 ~= 2.01 x 10^-87

繰り返しますが、文字列のプールがあり、そのプールとの衝突の確率を判定しようとしている場合、あなたは次の領域に入ります。 誕生日のパラドックス ここで計算したこの確率は当てはまりません。それとハッシュは本来あるべきほど均一ではありません。実際には、衝突率ははるかに高くなりますが、それでも小さいです。

編集

誕生日のパラドックス状況に対処しているため、誕生日のパラドックスに対する解決策と同じロジックを適用します。1 つのハッシュ関数だけの観点から見てみましょう。

N := the number of hashes in your pool (several hundred million)
S := the size of your hash space (2^288)
Therefore,
P(There are no collisions) = (S!)/(S^N * (S - N)!)

2^29 (約 5 億 3,000 万) のような偶数のハッシュがあると仮定しましょう。

P = (2^288!)/(2^288^(2^29) * (2^288 - 2^29)!)

要するに、この数字を計算することさえ考えたくありません。どうやって見積もればよいのかさえわかりません。少なくとも、膨大な階乗を死なずに処理できる任意精度の計算機が必要です。

次の場合、確率はほぼ 0 から始まる曲線に従うことに注意してください。 N = 1 or 2, 、次のときに 1 に達します。 N >= 2^288, 、Wikipedia の誕生日のパラドックスのページにあるものと形が似ています。

誕生日のパラドックスが届く P = .5 いつ N = 23. 。つまり、N が S の 6% の場合、衝突の確率は 50% になります。これがスケールする場合 (スケールするかどうかはわかりませんが)、2^288 ハッシュが 6% ある場合、衝突の可能性が 50% になることを意味します。2^288 の 6% は約 2^284 です。あなたの N の価値 (数億) は、それには遠く及びません。Sに比べれば微々たるものですので、心配する必要はないと思います。衝突の可能性はあまり高くありません。

他のヒント

メッセージのサイズが制限されていない場合は可能なメッセージの無限の数と可能なハッシュの有限数がありますように、

、チャンスは、漸近的に100％に近づいています。

（注：質問への編集は、今、この関連性の低いなります）の

一つはランダムにN個の要素を選ぶ場合

一般に、衝突の確率よりも衝突数の期待値を計算することが容易です。衝突数の期待値は、それが頻繁に適切な上限として使用することができる。

衝突の確率よりも小さくすることができないため

と仮定する P の二つのランダム要素が衝突採取確率です。我々はNランダム要素を選ぶ場合、N *（N-1）/ 2の要素の対ひいては衝突数の期待値である

あります
  

P * N *（N-1）/ 2

例えば、我々はMD5やSHA1の両方のための衝突の確率は、p = 2 -288 次にされた後であっても、ランダムに2 100 要素を選ぶと仮定すると、我々まだのみ約2 -89 衝突を期待しています。

別の例：私たちは2 30 ランダム要素を選択し、唯一のMD5を計算します。 2 MD5の間に衝突がハッシュと仮定すると、これは衝突の数の2の予想される数 -59 を与え、P = 2 -128 です。 MD5ハッシュは、2つの入力のために衝突し、従っても確率が既に非常に小さい。

それは間違っている確率を使用しているため、選択した答えは間違っています。私は（あなたはみかんその答えにコメントで私の思考プロセスを見ることができる）、および実際の答えは、次の（あなたが話しているものよりもわずかに大きいメッセージの誕生日のための攻撃）であると信じて、これを研究し、今日の良い部分を費やし：

2 ^ -61 の* <のhref = "HTTPS：//eprint.iacr .ORG / 2013 / 170.pdf」のrel = "nofollowを"> 2 ^ -18 に=衝突で一回79 ^ 2でます。

そして、それはちょうど（私はそれがわからないよ）。

これらの確率を乗算してOKだ場合、それはです

このは（数ヶ月未満と毎年ドロップ）今日のスーパーコンピュータでなんとかです。

（誕生日のパラドックスを有意義にするために）これはメッセージの十分な大きさのプールに基づいていることに注意してください。また、これは、あなたが心配したシナリオです。

次に、異なる状況が特定ののメッセージのハッシュの対（SHA1およびMD5）のための衝突を見つけることです。これはBDAYパラドックスの領土のあなたをとり、桁違いがより困難です。私はそれが2であるかどうかわからないんだけど^（ - 61 * 2）* 2 ^（ - 18 * 2）、または何か他のもの。 の誰もがそれが何であるかを知っていれば、（スーパーいただければ幸いです！）この回答へのコメントを投稿してください。のの

今、あなたは尋ねます：

  

二つの異なるメッセージを考えると、AとB（テキストの多分20〜80文字、すべてのサイズの問題であれば）

はい、サイズは問題ありません。 2 ^ -18図へのリンクをクリックすると、その値は、2つの入力ブロックのためにある表示されます。 MD5において、入力ブロックは512バイトです。テキストの20~80文字そのためには小さすぎる、そして単一ブロックの値が2 ^ 41である。

このように、データの量のために、あなたが得る2 ^ -61（と思う）* 2 ^ -41 = 2 ^ -102ます。

そのサイズのためだから<のhref = "http://www.wolframalpha.com/input/?i=%282%5E102+%2F+%282%2a46626.93+%2a+10%5E12%29% +年間で29 +秒+」のrelは= "nofollowを">安全のようだ（リンクはSHA256の二倍現在のビットコインのhashrateの姿含まれています：46626.93 TH /秒）。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top