Birthday Bound
誕生日限界とは、誕生日のパラドックスが定める攻撃計算量の下限であり、N 要素の集合で衝突を見つけるには約 sqrt(N) 個のサンプルで足りる。
目的
ハッシュ関数とブロック暗号モードの安全上限を定める。n ビットのハッシュは 2^(n/2) の衝突耐性しか持たず、n ビットブロックの CBC や CTR モードは 2^(n/2) ブロックで繰り返す。
メカニズム
誕生日のパラドックスにより、N 要素の集合からのランダムな抽出は約 sqrt(N) 回で高い確率で重複する。したがって n ビットハッシュの衝突には 2^(n/2) 回の操作が必要で、SHA-256 は 128 ビットの衝突耐性を持つ。
ユースケース
- ハッシュ関数のセキュリティ強度の評価
- ブロック暗号モードのブロック数上限
- 署名用ハッシュ長の選定