誕生日攻撃
誕生日攻撃（たんじょうびこうげき、）は、暗号の理論で使われる、暗号システムに対する攻撃の考え方の1つで、数理的には確率における誕生日問題の応用である。関数 "f" があるとき、formula_1 となるような2つの異なる入力 formula_2 を求めたい、という場合に関わる。この formula_2 のような組合せは衝突と呼ばれている。
暗号学において、このような衝突を求める攻撃には2種類がある。formula_4とformula_5の両方を攻撃者が任意に選ぶことができる場合と、片方は外部、たとえば送信者によって固定されており、攻撃者はもう片方について探すことしかできない場合、の2種類である。前者についての強度を強衝突耐性、後者についての強度を弱衝突耐性などと呼ぶこともある。ここで対象としているのは前者であり「衝突攻撃」とも呼ばれている。後者については「原像攻撃」を参照。
攻撃者が、衝突するペアを見つける方法は、無作為にまたは作為的にあるいは擬似乱数的に生成した異なる複数の入力を関数 "f" に与えて評価し、複数回同じ値となるまで続けるだけである。前述した誕生日問題から、この方法は思ったよりは効率的である。特に関数 formula_6 が formula_7 個の異なる出力をそれぞれ同じ確率で生成し formula_7 が非常に大きい場合、formula_1 となるような異なる入力 formula_4 と formula_5 を得るまでに "f" を評価する回数の平均は約 formula_12 回である。
何らかの暗号システムに対し、誕生日攻撃が問題であるか否かは、その暗号システムの設計と目的次第である。例えば、他のシステムに含まれているのではない暗号学的ハッシュ関数それ自身の評価としては、誕生日攻撃が可能なことは当然であって、誕生日攻撃よりも効率よく攻撃可能な手法が存在しないことが要件となる。また誕生日攻撃に耐えなければならないシステムでは、それを考慮に含めて十分に長いハッシュ値を採用するなどしなければならない。一方で、たとえば本来ならば攻撃者が片方のハッシュ値を自由に選ぶことができない（つまり、誕生日攻撃による攻撃が不可能でなければならない）はずのシステムに何らかの抜け穴があり、誕生日攻撃が可能になっていた、というような場合は欠陥として問題となる。