誕生日攻撃【birthday attack】バースデーアタック

概要

誕生日攻撃（birthday attack）とは、ハッシュ値、ハッシュ関数に対する総当たり攻撃の一種で、同じハッシュ値が得られる2つの値の組を見つけたい時、両者とも任意の値を選択できるなら少ない試行回数で発見できるというもの。

ハッシュ関数は任意の長さのデータから固定長のデータを得る関数で、中でも暗号システムなどに用いられる暗号学的ハッシュ関数は「元の値とハッシュ値の関係に規則性がない」「元の値を効率的に推測することはできない」「同じハッシュ値となる元の値の組を効率的に見つけることはできない」という性質を満たしている。

最後の性質は、「ある元の値が与えられたとき、同じハッシュ値となる別の元の値を見つけるのは困難」（片方の値は固定）と「元の値の候補の中から、同じハッシュ値となる組を探すのは困難」（両方の値が任意）という性質に分けられ、前者を「弱衝突耐性」、後者を「強衝突耐性」という。

誕生日攻撃は片っ端から候補値を計算してみる総当たり攻撃によって強衝突耐性を突破する攻撃である。あるハッシュ関数がH個の値を出力し得る場合、平均で約1.25√H回の試行で同じハッシュ値を取る2つの値の組を発見できることが知られている。Hを増大させていっても試行回数（強度）はHの2乗根に比例してしか増やすことができない。

誕生日攻撃という名称は、いわゆる「誕生日のパラドックス」（誕生日問題）と同じ構造の問題となっていることに由来する。誕生日は365日（閏年を考慮するなら366日）の候補があるが、「誕生日が同じ人が2人以上になる確率が50%を超えるのは何人以上の集団か」を計算すると「23人」となる。日付のバリエーションの多さに比べ意外なほど少ないため、確率論のパラドックスの有名な例として広く知られている。

(2022.12.13更新)