誕生日攻撃
最初の衝突が発生するまでに行わなければならない試行回数を Q ( H ) {\displaystyle Q(H)} とする。この近似は次のようになる。
Q ( H ) ≈ π 2 H {\displaystyle Q(H)\approx {\sqrt {{\frac {\pi }{2}}H}}}
例えば、64ビットの暗号学的ハッシュ関数を使っている場合、約 1.8 × 10 個の異なる出力がありうる。これらが全て同じ確率で発生する場合(最良ケース)、約 5.1 × 10 回の試行で衝突を発生させることができる。この値を birthday bound と呼び、n-ビットの符号についての birthday bound は 2 n / 2 {\displaystyle 2^{n/2}} となる。他の例は次のようになる。
この表は、指定した確率で衝突を発生させるのに必要な試行回数を示している(各ハッシュ値の発生確率は等しいと仮定)。ちなみに 10 から 10 は一般的なハードディスクで訂正できないビット誤りが発生する確率である。したがって、128ビットのMD5を文書のチェックサムとして使用する場合、8200億個の文書までならハードディスクでの誤り発生確率の範囲内に収まると言える(実際にはもっと多数のハッシュ値を生成できる)。
関数の出力が一様に分布しない場合、衝突をもっと早く見つけられることは容易に想像がつく。ハッシュ関数の「バランス」の観念は、誕生日攻撃への関数の耐性を定量化し、MDやSHAなどのよく知られたハッシュの脆弱性を見積もることを可能にする。