ネットワークセキュリティにおける誕生日攻撃とは？仕組み・計算方法・対策を徹底解説

誕生日攻撃（Birthday Attack）とは、確率論で有名な「誕生日のパラドックス」を利用した暗号解読攻撃の一種です。ハッシュ関数の弱点を突き、デジタル署名など現代のセキュリティシステムにも脅威となり得ます。本記事では、誕生日攻撃の基本概念から具体的な計算方法、脆弱なアルゴリズム、そして有効な対策までをわかりやすく解説します。

誕生日攻撃とは何か？

誕生日攻撃とは、確率論における「誕生日のパラドックス（誕生日問題）」を悪用した暗号攻撃のことです。誕生日のパラドックスとは、「ランダムに選んだn人の中に、同じ誕生日の2人が存在する確率」に関する現象で、直感に反して少数の集団でも一致する確率が非常に高くなることを指します。

この確率的な性質を暗号技術に応用したものが誕生日攻撃であり、攻撃者はこれを利用して、通信を行う2者以上の間で不正を働こうとします。

誕生日のパラドックスの具体例

例えば、部屋にいる人たちと順番に誕生日を比べていく状況を想像してみてください。1人あたりの一致確率は最大でも365分の1程度しかなく、特定の誰かと誕生日が被ることは稀に感じられます。

しかし、人数が増えるほど比較対象となる「ペア」の数が爆発的に増加するため、全体として誰か同士の誕生日が一致する確率は急激に高まります。実際には、わずか23人で約50%、30人で約70%に達するのです。この直感とのギャップこそが「パラドックス」と呼ばれる理由です。

誕生日攻撃はブルートフォース攻撃の一種？

誕生日攻撃は、ブルートフォース攻撃（総当たり攻撃）の一種に分類される暗号攻撃です。ただし、すべての鍵や入力を機械的に順番に試す従来型の総当たりとは異なり、誕生日のパラドックスに基づく一定量の順列（組み合わせ）を活用することで、はるかに少ない試行回数で目的を達成できる点が大きな特徴です。

誕生日攻撃の確率はどう計算される？

集団の人数nに対して、少なくとも1組の誕生日が一致するペアが存在する確率p(n)は、以下のように変化します。

• n＝23：約50.7%
• n＝60：約99.4%
• n＝70：約99.9%
• n＝75：約99.97%
• n＝100：約99.99997%

このように、人数が増えるにつれて一致確率は急速に100%へ近づいていきます。

ハッシュ関数への攻撃はどのように行われる？

誕生日攻撃の主な標的となるのがハッシュ関数です。値域がrであるハッシュ関数hに対する誕生日攻撃の目標は、およそrの平方根（r^1/2）回の試行（ハッシュ計算）で「衝突（コリジョン）」を見つけることです。

ここで衝突とは、異なる2つの入力xiとxj（i≠j）が、同じハッシュ値yi＝yjを返す現象を指します。つまり、別々のデータなのに同一のハッシュ値が得られるペアが存在すれば、攻撃は成功したことになります。試行回数qが増えるほど、このようなペアが見つかる確率は誕生日のパラドックスと同じ理屈で急速に高まります。

誕生日攻撃の影響を受けやすいものは？

誕生日攻撃の潜在的な脅威となりやすいのがデジタル署名です。一般的にデジタル署名では、まずメッセージmに対して暗号学的ハッシュ関数Hを適用してハッシュ値H(m)を求め、その値を秘密鍵で署名します。

例えば、攻撃者のAliceがBobに偽の契約書へ署名させようとするケースを考えてみましょう。Aliceは「正規の契約書」と「悪意のある契約書」の両方について、ハッシュ値が一致する多数のバリエーションを事前に生成しておきます。Bobが正規の契約書に署名した時点で、その署名は同じハッシュ値を持つ偽の契約書にも転用できてしまうのです。

脆弱なアルゴリズムの例：MD5

誕生日攻撃に対して脆弱なアルゴリズムの代表例がMD5です。MD5は128ビットという短いハッシュ値を出力するため、衝突を見つける難易度が低く、実際に衝突の生成に成功した事例も報告されています。そのため現在では安全性が失われたハッシュ関数とみなされており、新規システムでの使用は避けるべきとされています。

自分と同じ誕生日の人に出会う確率は？

特定の誰か1人と自分の誕生日が一致する確率は、うるう年を考慮しなければ1/365です。偶然出会った2人の誕生日が一致する可能性は決して高くないでしょう。しかし、集団の中で「誰か同士」の誕生日が一致する確率は話が別で、人数が増えるほど急速に上昇します。この直感とのギャップこそが、誕生日攻撃の根拠となる「誕生日のパラドックス」なのです。

まとめ：誕生日攻撃への対策

誕生日攻撃は、確率論の性質を利用してハッシュ関数の衝突を効率的に探し出す巧妙な攻撃手法です。対策としては、以下のポイントが重要です。

• SHA-256やSHA-3など、256ビット以上の長いハッシュ値を持つ暗号学的ハッシュ関数を使用する
• MD5やSHA-1など、脆弱性が確認されている旧式のアルゴリズムを使わない
• デジタル署名の運用においても、安全なハッシュ関数と十分な鍵長を維持する

ハッシュ値のビット長が倍になれば、誕生日攻撃による衝突探索のコストは指数関数的に増大します。現代的な暗号技術の選択と適切な運用によって、誕生日攻撃のリスクは効果的に低減できます。