MD5の衝突の可能性

Question

最悪の場合、私はキャッシュに1億8千万の値を持っています（失効する前の15分間のウィンドウ）、MD5には2^128の値があります。私の衝突確率は？それとももっと良いのですか？その質問に答えるどこかのWebページがあるのでしょうか？それは私のチャンスを知っているので、揺れ動くだろう。

Answer 1

確率が1-M！/（mⁿ（M-N）！）であるM =2¹²⁸とN =1.8億。

オンラインのWolframで実行すると、計算時間が超過します。

あなたがローカルにインストールスモールトークを持っている場合は、この実行することができます：

|m n p| 

m := 2 raisedTo:128. 
n := 180000000. 
p := (1-(m factorial/((m raisedTo:n)*(m-n)factorial)))asFloat. 

Transcript show:p printString;cr. 

を誕生日のパラドックスのための検索は、彼らは128ビット2.6×1010ハッシュ、確率のために示した表を提供Wikipedia pageが表示されます衝突の数は1017で1であり、これはあなたが検討している数よりもハッシュ数が140倍多いためです。だからあなたはあなたのオッズがこれよりも「悪い」ことを知っています。

良い近似N«Mあなたはメートルとnは上記に差し込む場合、あなたは4.76×を得る1-E ^{-n /2メートル}、ある場合10⁻²³衝突の可能性として2.10×1022の1である。

衝突の可能性は非常に低くても、FOOBARのケースでは賢明です。問題があり、少なくともハッシュが15分以上溜まっている場合は、少なくとも衝突。