本記事は 暗号学一人アドベントカレンダー 第5日目(相当)の記事です。
誕生日問題とは
「誕生日のパラドックス」の計算を使って、どれくらいの確率でハッシュが衝突するか、どれくらいの回数ハッシュ計算を行えば衝突を発生させられるか、という問題です。これの計算結果により、暗号学的ハッシュ関数は最大でもハッシュの長さの半分のビット数ぶんの安全性しか得ることができない、という性質を得ることができます。
衝突を得る確率
ハッシュの空間サイズ（ハッシュ長が64ビットならば\(2^{64}\)）をHとし、ここで扱うハッシュは完全にランダムにハッシュ空間に値をマッピングするものとすると、n個の異なる値をハッシュして衝突が発生しない確率、つまりn回すべて異なる値になる確率は
$$\overline{P} = 1 (1 - \frac{1}{H})(1 - \frac{2}{H})...(1 - \frac{n-1}{H})$$
になります*1。
ここで、x << 1での \(e^x\) の1次のテイラー展開 \(e^x \approx 1 + x\) を使って、
$$\overline{P} \approx e^{-\frac{1 + 2 + ... + n-1}{H}} = e^{-\frac{n(n-1)}{2H}}$$
を得ます。ということは、この余事象を使って、衝突を得る確率は
$$P = 1 - e^{-\frac{n(n-1)}{2H}}$$
になります。
確率を指定したときに必要な試行回数
上の式を変形して、
$$1-P = e^{-\frac{n(n-1)}{2H}}$$
$$\ln(1-P) = - \frac{n(n-1)}{2H}$$
$$n(n-1) = 2H \ln (\frac{1}{1-P})$$
nが十分に大きいとき、n(n-1) = n2と見立てて、
$$n \approx \sqrt{2H \ln (\frac{1}{1-P})}$$
ここでP = 1/2として数値計算すると \(n \approx 1.1774\sqrt{H}\)くらいになります。
初めて衝突を得るために必要な回数の期待値
ここからは正直追いきれなかったので現時点では最終結果は英語版Wikipediaの誕生日問題のページに頼ると、初めて衝突を得るために必要な回数の期待値は
$$N \approx \sqrt{\frac{\pi}{2}H}$$
と近似できます。おそらく円周率に平方根がかかってるあたりとか上のPを得る途中で階乗が出てくる関係からスターリングの公式とかで導出できそうだけど手に負えませんでした。
結果としてだいたいHの平方根くらい、つまりハッシュ長がhビットならば\(2^{\frac{h}{2}}\)回ハッシュ計算をしたら衝突が得られる、ということになり、どんなに理想的な暗号学的ハッシュでもその出力の長さによって衝突耐性を破るのに必要な計算回数が決まってしまう、ということがわかります。
次回は「誕生日攻撃でない方法で」いかにしてSHA-1が破られたか、という話（つまりSHAttered攻撃の紹介）の予定です。
*1:overlineにしているのは衝突の確率のほうが求めたい値だから
