誕生日攻撃 誕生日攻撃の概要

ウィキペディア

誕生日攻撃

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/06/01 18:30 UTC 版)

暗号学において、このような衝突を求める攻撃には2種類がある。${\displaystyle x_{1}}$と${\displaystyle x_{2}}$の両方を攻撃者が任意に選ぶことができる場合と、片方は外部（たとえば送信者）によって固定されており、攻撃者はもう片方について探すことしかできない場合の2種類である。前者についての強度を強衝突耐性、後者についての強度を弱衝突耐性と呼ぶこともある。この項で対象としているのは前者であり、「衝突攻撃」とも呼ぶ。後者については「原像攻撃」を参照。

攻撃者が衝突するペアを見つける方法は、無作為にまたは作為的にあるいは擬似乱数的に生成した異なる複数の入力を関数 f に与えて評価し、複数回同じ値となるまで続けるだけである。この攻撃方法は、前述した誕生日問題から、想像よりも効率的である。特に関数 ${\displaystyle f(x)}$ が ${\displaystyle H}$ 個の異なる出力をそれぞれ同じ確率で生成し ${\displaystyle H}$ が非常に大きい場合、${\displaystyle f(x_{1})=f(x_{2})}$ となるような異なる入力 ${\displaystyle x_{1}}$ と ${\displaystyle x_{2}}$ を得るまでに f を評価する回数の平均は約 ${\displaystyle 1.25\cdot {\sqrt {H}}}$ 回である。

ある暗号システムに対し、誕生日攻撃が問題となるか否かは、その暗号システムの設計と目的次第である。例えば、他のシステムに含まれていない暗号学的ハッシュ関数それ自身の評価としては、誕生日攻撃が可能であることは当然であるため、誕生日攻撃よりも効率のよい攻撃方法が存在しないことが必要である。また誕生日攻撃に耐えなければならないシステムでは、十分に長いハッシュ値を採用するなどの対策をしなければならない。一方で、たとえば本来ならば攻撃者が片方のハッシュ値を自由に選ぶことができない（つまり、本来ならば誕生日攻撃が不可能である）はずのシステムに何らかの抜け穴があり、誕生日攻撃が可能になってしまっていた場合は問題となる。