誕生日攻撃とは

誕生日攻撃とは何かというと、いわゆるハッシュ関数の衝突を引き起こすための攻撃です。その方法はすごくシンプルで、ランダムな値を生成しまくってハッシュ関数にかけ続ける、というものになります。そんなの衝突を発生させるまでに一体何年かかるのか、という気もしますが、それが発生するのは直感に反し、意外な高確率になります。

例えば、 $n=30$ 人のクラスで誕生日が全く同じ人がいる確率は 70 % $\left(1-\frac{365!}{\left((365-n)!365^{n}\right)}\right)$ と意外な高さになります。この直感に反する確率の高さ (wikipedia:誕生日のパラドックスと言われます) こそが、誕生日攻撃の依拠するものです。

一体何回攻撃を繰り返したら衝突するのか。その期待値は。

Qiita にも書いたとおり、「UUID に少なくとも 1 回は衝突が発生する確率」が $p$ になるような UUID の生成回数は

$n\approx \sqrt{2^{123} \ln{\frac{1}{1-p}}}$

でした。これは、UUID version 4 においてランダムなビット数が 122 個あることに起因しています。もう少し一般化すると、これが $N$ bit なのであればその回数は $n\approx \sqrt{2\cdot2^{N} \ln{\frac{1}{1-p}}}$ になります。さらに一般化すると、値域が $2^{N}$ であり一様に分布するハッシュ関数があったとき、その衝突確率が $p$ になるために必要な試行回数も同じ式で表されるということです。

それではちょっと考え方を変えて、衝突を発生させるために必要な試行回数 $k$ の期待値 $E(W_{k})$ は何回くらいになるでしょうか？というのがこのエントリの主題です。

最初に結論を述べておくと、値域が $H$ の大きさである一様分布する関数があったとき、期待値 $E(W_{k})$ は

$-\frac{2}{5} \leq E(W_{k})-\sqrt{\frac{\pi H}{2} } \leq \frac{8}{5}$

の範囲で抑えられます。

$H$ は通常大きい値ですから、 $E(W_{k})$ の値は $\sqrt{\frac{\pi H}{2}}$ に収束することを意味します。値域が $n$ bit のハッシュ関数であれば、 $H=2^{n}$ ですから、その値は $\sqrt{\frac{\pi}{2}}2^{\frac{n}{2}}$ になります。

それでですね、なんでこの値になるのかっていうのを、丁寧に説明していこうと思っていたんです。ホントに。で、数式をスゲー書いていたんですが、途中でスゲー面倒くさくなりました。なんでオレはクリスマス近くになってこんなことを書いているんだろうみたいな。そもそもなんでこの値になるのか、っていうのは論文を読めば書いてあるし、ぼくがクリスマス近くになって、論文と同じ数式ばっかし書く意味なんてないし。

というわけですから、気になる人は以下の論文の証明あたりを読めば良いと思います。 Theorem 2. がターゲットだ。