誕生日攻撃

誕生日攻撃とは

誕生日攻撃とは、暗号理論における攻撃手法の一つで、数学的な確率の問題である「誕生日問題」を応用したものです。この攻撃は、ある関数fにおいて、異なる2つの入力x₁とx₂に対して、f(x₁) = f(x₂)となるような衝突（同じ出力値）を見つけ出すことを目的とします。暗号学においては、このような衝突を悪用することで、システムのセキュリティを脅かす可能性があります。

衝突の種類

衝突を求める攻撃には大きく分けて2種類あります。

1. 強衝突耐性：攻撃者がx₁とx₂の両方を自由に選択できる場合。
2. 弱衝突耐性：攻撃者が片方の入力（例えばx₁）は固定されており、もう片方（x₂）を探す場合。これは「原像攻撃」とも呼ばれます。

この項目では、主に前者である「強衝突耐性」について解説します。これは、単に「衝突攻撃」とも呼ばれます。

攻撃の仕組み

攻撃者が衝突するペアを見つける方法は比較的シンプルです。関数fに、ランダムに生成した複数の異なる入力を与え、同じ出力が得られるまで繰り返します。一見非効率に見えるこの方法ですが、誕生日問題の性質から、意外なほど少ない試行回数で衝突を発見できることが知られています。

特に、関数fがH個の異なる出力をそれぞれ同じ確率で生成する場合、異なる入力x₁とx₂でf(x₁) = f(x₂)となるペアを見つけるために必要な試行回数の平均は、およそ1.25√H回程度となります。この特性が、誕生日攻撃を強力な攻撃手法としている理由です。

誕生日攻撃の対策

誕生日攻撃が問題となるかどうかは、暗号システムの設計と目的に依存します。例えば、ハッシュ関数自体の評価においては、誕生日攻撃が可能であることは当然の前提であり、より効率的な攻撃手法がないことが求められます。一方で、誕生日攻撃に耐えられないシステムでは、十分に長いハッシュ値を使用するなどの対策が必要になります。

また、本来誕生日攻撃ができないはずのシステムに脆弱性があり、攻撃が可能になっている場合は、深刻な問題となります。

数理的な解説

衝突確率の計算

H個の値の集合からn個の値を無作為に選ぶとき、少なくとも1つの値が2回以上選ばれる確率p(n;H)は、以下の式で近似できます。


p(n;H) ≈ 1 - e^(-n(n-1)/(2H)) ≈ 1 - e^(-n²/(2H))


衝突を発見する確率をp以上とするために必要な試行回数の下限n(p;H)は、以下の式で近似できます。


n(p;H) ≈ √(2H ln(1/(1-p)))


特に、衝突確率を0.5とする場合、必要な試行回数は以下のようになります。


n(0.5;H) ≈ 1.1774√H

試行回数の近似

最初の衝突が発生するまでに行うべき試行回数Q(H)は、以下の式で近似できます。


Q(H) ≈ √(π/2 H)

具体的な例

例えば、64ビットのハッシュ関数を使用する場合、約1.8 × 10¹⁹個の異なる出力が存在する可能性があります。すべてが同じ確率で発生する場合、約5.1 × 10⁹回の試行で衝突を見つけることができます。この値を「誕生日限界」と呼び、nビットの符号では2^(n/2)となります。

以下の表は、特定の確率で衝突を発生させるために必要な試行回数の概算を示しています。

誕生日攻撃の例

デジタル署名への攻撃

デジタル署名は、誕生日攻撃の影響を受けることがあります。攻撃者が、同じハッシュ値を持つ異なるメッセージ（契約書など）を作成し、署名を悪用する可能性があります。

例えば、アリスがボブを騙して偽の契約書に署名させようとする場合を考えてみましょう。アリスは、まず正当な契約書mと偽の契約書m'を用意します。次に、それぞれの内容を少しずつ変更したバリエーションを作成し、それぞれハッシュ関数を適用します。アリスは、同じハッシュ値を持つ正当な契約書と偽の契約書の組み合わせを探し出し、正当な契約書に署名させた後、署名を偽の契約書に転用します。

このような攻撃を防ぐためには、署名に使用するハッシュ関数の出力長を、誕生日攻撃が事実上不可能になる程度まで長くする必要があります。

DNSキャッシュポイズニング

DNSキャッシュポイズニングにも、誕生日攻撃が利用される可能性があります。特にBINDの実装上の問題により、攻撃者がDNSキャッシュに偽の情報を注入するリスクが指摘されています。

その他の応用例

誕生日攻撃は、ポラード・ロー素因数分解法などの他のアルゴリズムにも応用されています。

まとめ

誕生日攻撃は、暗号システムの脆弱性を突く強力な攻撃手法です。この攻撃に耐えるためには、ハッシュ値の長さを適切に設定し、システムの設計段階から十分な考慮を行う必要があります。

もう一度検索