誕生日攻撃 数理的解説

ウィキペディア

誕生日攻撃

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/06/01 18:30 UTC 版)

数理的解説

次のような実験を考える。$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などのよく知られたハッシュの脆弱性を見積もることを可能にする。