Birthday Attack

目的

衝突探索が現実的でなくなるよう、ハッシュ出力長の下限を定める。

メカニズム

誕生日のパラドックスでは、23 人の中で 2 人が同じ誕生日になる確率が 50% になる。n ビット出力のハッシュでは、約 1.177×√(2^n) = 1.177×2^(n/2) 個のランダムな入力で 50% の衝突確率に達する。したがって 128 ビットハッシュは 2^64 回の試行で破られるため安全ではない。

ユースケース

• ハッシュ出力長の選定
• 電子署名のセキュリティ強度
• 証明書ライフタイムの評価
• 暗号学の教育コンテンツ

例

• 入力

  128-bit hash

  Output

  Collision found in 2^64 trials

  Insecure

よくあるエラー

Assuming an n-bit hash needs 2^n trials to collide

Collisions take only 2^(n/2); use outputs of at least 256 bits