理系学生日記

おまえはいつまで学生気分なのか

忍者TOOLS

誕生日攻撃が成功する回数の期待値は?

このあいだ、Advent Calendar に UUID の衝突確率の話を書きました。

もちろんこれは、昔に書いた以下のエントリをちょっとだけ修正しただけで、早速バレたりしていた。

とはいえ、UUID の衝突には続く話がありまして、それが誕生日攻撃というものです。

誕生日攻撃とは

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

例えば、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. がターゲットだ。

以下は途中まで書いた証明ですが、詳しくは論文を読んでくれ。

期待値の定義から

まず、ここで求める期待値を E(V) とします。V は確率変数で、ここでは試行回数を表現します。 期待値の定義から E(V)=\sum_{k=1}^{\infty}kP(V=k) なわけですが、これをもう少し進めると、以下のような引き算で表されます。

  • E(V)= \sum_{k=1}^{\infty}kP(V>k-1) - \sum_{k=1}^{\infty} kP(V>k)

ここで第一項について k=1 のときを考えると

  •  \sum_{k=1}^{\infty}kP(V>k-1) = \sum_{k=0}^{\infty}(k+1)P(V>k)

ですし、第二項については k=0 のとき 0 なので、

  • \sum_{k=1}^{\infty} kP(V>k)=\sum_{k=0}^{\infty} kP(V>k)

となります。これらを代入すると、

  • E(V) = \sum_{k=0}^{\infty}(k+1)P(V>k) - \sum_{k=0}^{\infty} kP(V>k) = \sum_{k=0}^{\infty} P(V>k)

となります。

k 回の試行でも衝突が発生しない確率の上界

いま、k 回の試行でも衝突が発生しない確率を P(W>k) と定義すると、Qiita に書いた議論から

  • P(W > k) = \prod_{j=1}^{k-1}\left(1-\frac{j}{n}\right)

となることが分かります。ここで両辺の対数を取ると

  • \ln\left(P(W > k)\right) = \sum_{j=1}^{k-1}\ln\left(1-\frac{j}{n}\right)

となります。さらに、\ln (1-x)のテイラー展開は-\sum_{i=1}^{\infty}\frac{x^{i}}{i} になるので、これを代入すると、

  • -\ln\left(P(W > k)\right) = \sum_{j=1}^{k-1}\sum_{i=1}^{\infty}\frac{x^{i}}{i}

右辺を展開すると、\sum_{j=1}^{k-1}\left( \frac{j}{n} + \frac{j^{2}}{2n^{2}} \right) = \frac{k(k-1)}{2n} + \frac{k(k-1)(2k-1)}{12n^{2}} + \cdots となるので、

-\ln\left(P(W > k)\right) \geq \frac{k(k-1)}{2n}、つまり P(W > k)P(W > k) \leq \exp\left( -\frac{k(k-1)}{2n} \right) という上界で抑えられることが分かります。

期待値の上界

これまでの議論から、

E(W)=\sum_{k=0}^{\infty}P(W > k)=1+\sum_{k=1}^{\infty}P(W > k) \leq 1+\sum_{k=1}^{\infty}\exp\left( -\frac{k(k-1)}{2n} \right)

となります。このあたりでもう疲れた。気になる人は論文読もう。

というわけで

みなさんメリークリスマス!!!!!!!!!!