誕生日攻撃
次のような実験を考える。 H {\displaystyle H} 個の値の集合から n {\displaystyle n} 個の値を一様かつ無作為に選ぶ(重複もありうる)。この実験で少なくとも1つの値が2回以上選ばれる確率を p ( n ; H ) {\displaystyle p(n;H)} とする。この確率は次のように概算できる。
p ( n ; H ) ≈ 1 − e − n ( n − 1 ) / ( 2 H ) ≈ 1 − e − n 2 / ( 2 H ) {\displaystyle p(n;H)\approx 1-e^{-n(n-1)/(2H)}\approx 1-e^{-n^{2}/(2H)}}
衝突を発見する確率を p {\displaystyle p} 以上とするとき、行わなければならない試行回数の下限を n ( p ; H ) {\displaystyle n(p;H)} とする。すると、上の式から次のような近似が得られる。
n ( p ; H ) ≈ 2 H ln  1 1 − p {\displaystyle n(p;H)\approx {\sqrt {2H\ln {\frac {1}{1-p}}}}}
衝突発生確率を0.5とすると、次のようになる。
n ( 0.5 ; H ) ≈ 1.1774 H {\displaystyle n(0.5;H)\approx 1.1774{\sqrt {H}}}
誕生日攻撃(たんじょうびこうげき、英: birthday attack)は、暗号の理論で使われる、暗号システムに対する攻撃の考え方の1つで、数理的には確率における誕生日問題の応用である。関数 f があるとき、 f ( x 1 ) = f ( x 2 ) {\displaystyle f(x_{1})=f(x_{2})} となるような2つの異なる入力 x 1 , x 2 {\displaystyle x_{1},x_{2}} を求めたい、という場合に関わる。この x 1 , x 2 {\displaystyle x_{1},x_{2}} のような組合せは衝突と呼ばれている。
暗号学において、このような衝突を求める攻撃には2種類がある。 x 1 {\displaystyle x_{1}} と x 2 {\displaystyle x_{2}} の両方を攻撃者が任意に選ぶことができる場合と、片方は外部、たとえば送信者によって固定されており、攻撃者はもう片方について探すことしかできない場合、の2種類である。前者についての強度を強衝突耐性、後者についての強度を弱衝突耐性などと呼ぶこともある。ここで対象としているのは前者であり「衝突攻撃」とも呼ばれている。後者については「原像攻撃」を参照。
攻撃者が、衝突するペアを見つける方法は、無作為にまたは作為的にあるいは擬似乱数的に生成した異なる複数の入力を関数 f に与えて評価し、複数回同じ値となるまで続けるだけである。