セキュリティ用語集

誕生日パラドックス

用語の別名	Birthday-Attack、Birthday-Paradox、誕生日攻撃、誕生日問題
ジャンル	[攻撃][語彙]
内容	適当に人選したグループの中で、日付やメンバーを限定せず少なくとも2人の誕生日が一致する確率を算出してみると、想像以上に高い確率である、という事実を誕生日パラドックスと呼びます。そのグループの中で、自分と誕生日が一致するメンバーが存在する確率は単純に365分の1ですが、日付やメンバーを限定しなければ確率は格段に上がります。実際に計算すると、グループの人数が23人になると確率は2分の1を越え、100人を越える頃にはほぼ間違いなく1組のペアが存在する計算になります。この事実は、一方向ハッシュに対する総当たり攻撃の回数を大幅に削減するのに役立ちます。つまり、あるデータから算出されたハッシュ値に一致する別のデータを算出するにはハッシュ値の取り得る空間を総当たりしなければなりませんが、値は何でもいいからハッシュ値が一致する値のペアを発見できる確率は意外に高い、と言えます。事前にこのようなデータのペアを用意できれば、いつでも2つのデータは交換可能であり、通信の途中ですり換えてもハッシュ値による検証をクリアできるので改竄と同様の効果が得られます。このような攻撃を防ぐために、誕生日パラドックスを利用しても現実的に解が得られないような、充分に広い空間を持つハッシュ関数を選択する必要があります。

ネットワークセキュリティ関係者の部屋 > gLOSSARY > 誕生日パラドックス