誕生日攻撃

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

誕生日攻撃(たんじょうびこうげき、: birthday attack)は、暗号理論における暗号攻撃方法の1つ。確率論における誕生日問題の背後にある数学的理論を利用することからこの名称になっている。関数 f があるとき、この攻撃の目的は f(x_1)=f(x_2) となるような2つの異なる入力 x_1,x_2 を求めることである。この x_1,x_2 のような組合せを衝突と呼ぶため、衝突攻撃ともいう。

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

数学的解説[編集]

次のような実験を考える。H 個の値の集合から n 個の値を一様かつ無作為に選ぶ(重複もありうる)。この実験で少なくとも1つの値が2回以上選ばれる確率を p(n;H) とする。この確率は次のように概算できる。

 p(n;H) \approx 1 - e^{-n(n-1)/(2H)} \approx 1-e^{-n^2/(2H)}

衝突を発見する確率を p 以上とするとき、行わなければならない試行回数の下限を n(p;H) とする。すると、上の式から次のような近似が得られる。

n(p;H)\approx \sqrt{2H\ln\frac{1}{1-p}}

衝突発生確率を0.5とすると、次のようになる。

n(0.5;H) \approx 1.1774 \sqrt H

最初の衝突が発生するまでに行わなければならない試行回数を Q(H) とする。この近似は次のようになる。

Q(H)\approx \sqrt{\frac{\pi}{2}H}

例えば、64ビットの暗号学的ハッシュ関数を使っている場合、約 1.8 × 1019 個の異なる出力がありうる。これらが全て同じ確率で発生する場合(最良ケース)、約 5.1 × 109 回の試行で衝突を発生させることができる。この値を birthday bound と呼び、n-ビットの符号についての birthday bound は 2^{n/2} となる[1]。他の例は次のようになる。

ビット数 出力の個数
(H)
衝突発生確率 (p)
10−18 10−15 10−12 10−9 10−6 0.1% 1% 25% 50% 75%
32 4.3 × 109 2 2 2 2.9 93 2.9 × 103 9.3 × 103 5.0 × 104 7.7 × 104 1.1 × 105
64 1.8 × 1019 6.1 1.9 × 102 6.1 × 103 1.9 × 105 6.1 × 106 1.9 × 108 6.1 × 108 3.3 × 109 5.1 × 109 7.2 × 109
128 3.4 × 1038 2.6 × 1010 8.2 × 1011 2.6 × 1013 8.2 × 1014 2.6 × 1016 8.3 × 1017 2.6 × 1018 1.4 × 1019 2.2 × 1019 3.1 × 1019
256 1.2 × 1077 4.8 × 1029 1.5 × 1031 4.8 × 1032 1.5 × 1034 4.8 × 1035 1.5 × 1037 4.8 × 1037 2.6 × 1038 4.0 × 1038 5.7 × 1038
384 3.9 × 10115 8.9 × 1048 2.8 × 1050 8.9 × 1051 2.8 × 1053 8.9 × 1054 2.8 × 1056 8.9 × 1056 4.8 × 1057 7.4 × 1057 1.0 × 1058
512 1.3 × 10154 1.6 × 1068 5.2 × 1069 1.6 × 1071 5.2 × 1072 1.6 × 1074 5.2 × 1075 1.6 × 1076 8.8 × 1076 1.4 × 1077 1.9 × 1077
この表は、指定した確率で衝突を発生させるのに必要な試行回数を示している(各ハッシュ値の発生確率は等しいと仮定)。ちなみに 10−18 から 10−15 は一般的なハードディスクで訂正できないビット誤りが発生する確率である[2]。したがって、128ビットのMD5を文書のチェックサムとして使用する場合、8200億個の文書までならハードディスクでの誤り発生確率の範囲内に収まると言える(実際にはもっと多数のハッシュ値を生成できる)。

関数の出力が一様に分布しない場合、衝突をもっと早く見つけられることは容易に想像がつく。ハッシュ関数の「バランス」の観念は、誕生日攻撃への関数の耐性を定量化し、MDやSHAなどのよく知られたハッシュの脆弱性を見積もることを可能にする[3]

デジタル署名の脆弱性[編集]

デジタル署名は誕生日攻撃に弱い場合もある。メッセージ m暗号学的ハッシュ関数 f と秘密鍵を適用して署名 f(m) を得る。ここでアリスがボブを騙し、ニセの契約書に署名させる場合を考える。アリスはまず正しい契約書 m とニセの契約書 m' を用意する。次に m の意味を変えずに字面を変えた書面をコンマを挿入したり、空行を挿入したり、文の後の空白を増やしたり、同義語で置換したりしていくつも作成する。このようにすることで、正しい契約書 m の膨大なバリエーションを作成できる。

同様の手法でアリスはニセの契約書 m' についても多数のバリエーションを作成する。次にアリスは、それらの正しい契約書とニセの契約書の全バリエーションについてハッシュ関数を適用し、同じハッシュ値 f(m) = f(m') となるものを探す。そして、衝突した正しい方の契約書をボブに提示し署名を求める。ボブが署名したら、アリスはその署名を切り出し、ニセの(衝突した)契約書に添付する。この署名はボブがニセの契約書に署名したことを証明している。これは本来の誕生日問題とは若干異なり、正しい契約書間同士のペアやニセの契約書間同士のペアで衝突が見つかってもアリスには何の利益も生じない。アリスが詐欺を成功させるには、正しい契約書とニセの契約書の組み合わせのペアで衝突が発生する文面を見つける必要がある。つまり、上の説明での n は正しい契約書とニセの契約書のペアの個数に相当するため、アリスは実際には 2n 回ハッシュ値生成を試行しなければならない。

このような攻撃を防ぐため、署名で使用するハッシュ関数の出力長は誕生日攻撃が事実上不可能な程度にまで十分長くなければならない。つまり、通常の総当り攻撃を防ぐのに必要なビット数の2倍を必要とする。

ポラード・ロー素因数分解法の離散対数への応用(en)は、離散対数の計算に誕生日攻撃を応用した例である。

実環境[編集]

インターネットのDNSシステムには誕生日攻撃への脆弱性があるのではないかという議論がある[4]

脚注・出典[編集]

参考文献[編集]

  • Mihir Bellare, Tadayoshi Kohno: Hash Function Balance and Its Impact on Birthday Attacks. EUROCRYPT 2004: pp401–418
  • Applied Cryptography, 2nd ed. by Bruce Schneier

関連項目[編集]

外部リンク[編集]