誕生日攻撃

誕生日攻撃（たんじょうびこうげき、英: birthday attack）は、暗号の理論で使われる、暗号システムに対する攻撃の考え方の1つで、数理的には確率における誕生日問題の応用である。関数 f があるとき、$f(x_{1})=f(x_{2})$ となるような2つの異なる入力 $x_{1},x_{2}$ を求めたい、という場合に関わる。この $x_{1},x_{2}$ のような組合せは衝突と呼ばれている。

暗号学において、このような衝突を求める攻撃には2種類がある。$x_{1}$と$x_{2}$の両方を攻撃者が任意に選ぶことができる場合と、片方は外部（たとえば送信者）によって固定されており、攻撃者はもう片方について探すことしかできない場合の2種類である。前者についての強度を強衝突耐性、後者についての強度を弱衝突耐性と呼ぶこともある。この項で対象としているのは前者であり、「衝突攻撃」とも呼ぶ。後者については「原像攻撃」を参照。

攻撃者が衝突するペアを見つける方法は、無作為にまたは作為的にあるいは擬似乱数的に生成した異なる複数の入力を関数 f に与えて評価し、複数回同じ値となるまで続けるだけである。この攻撃方法は、前述した誕生日問題から、想像よりも効率的である。特に関数 $f(x)$ が $H$ 個の異なる出力をそれぞれ同じ確率で生成し $H$ が非常に大きい場合、$f(x_{1})=f(x_{2})$ となるような異なる入力 $x_{1}$ と $x_{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 × 10¹⁹ 個の異なる出力がありうる。これらが全て同じ確率で発生する場合（最良ケース）、約 5.1 × 10⁹ 回の試行で衝突を発生させることができる。この値を birthday bound と呼び、n-ビットの符号についての birthday bound は $2^{n/2}$ となる。他の例は次のようになる。

ビット数	出力の個数 (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⁻¹⁸ から 10⁻¹⁵ は一般的なハードディスクで訂正できないビット誤りが発生する確率である。したがって、128ビットのMD5を文書のチェックサムとして使用する場合、8200億個の文書までならハードディスクでの誤り発生確率の範囲内に収まると言える（実際にはもっと多数のハッシュ値を生成できる）。

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

例

デジタル署名への攻撃

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

同様の手法でアリスはニセの契約書 $m'$ についても多数のバリエーションを作成する。次にアリスは、それらの正しい契約書とニセの契約書の全バリエーションについてハッシュ関数を適用し、同じハッシュ値 $f(m)=f(m')$ となるものを探す。そして、衝突した正しい方の契約書をボブに提示し署名を求める。ボブが署名したら、アリスはその署名を切り出し、ニセの（衝突した）契約書に添付する。この署名はボブがニセの契約書に署名したことを証明している。

なお，本来の誕生日問題とは若干異なり、正しい契約書間同士のペアやニセの契約書間同士のペアで衝突が見つかってもアリスには何の利益も生じない。アリスが詐欺を成功させるには、正しい契約書とニセの契約書の組み合わせのペアで衝突が発生する文面を見つける必要がある。つまり、上の説明での $n$ は正しい契約書とニセの契約書のペアの個数に相当するため、アリスは実際には $2n$ 回ハッシュ値生成を試行しなければならない。

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

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

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

BINDの実装上の問題などによる、誕生日攻撃を利用したDNSのDNSキャッシュポイズニングの可能性が議論されている。

参考文献

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

関連項目

• 中間一致攻撃

外部リンク

• "What is a digital signature and what is authentication?" RSAセキュリティの crypto FAQより
• "Parallel collision search with cryptanalytic applications, by Michael Wiener and Paul C. van Oorschot