概要

ここでは、 正しくない実装をされた UUID を使うことによる安全性の検討をします。
特に言及のない場合は UUIDv4 の話となります。（乱数による生成）

実装がメインの話となります。

以下の用途での検討を行います。

正しい UUID

正しい UUID は、耐衝突性に優れます。

詳細は下記記事に詳しいですが、「鳩の巣原理」「誕生日攻撃」の2つは乱数の耐衝突性を考えるうえで重要です。
UUID(v4) がぶつかる可能性を考えなくていい理由
 鳩の巣原理
 誕生日攻撃

上記の記事内にありますが、衝突までの期待値は $N$ をビット数とした $ f(N) = 2^{N/2} $ となります。
UUIDは $ N = 122 $ から$ f(122) \simeq 2.3 * 10^{18} $となります。

ここでは、 正しくない 実装をされた UUID を考えてみます。
個々のライブラリがただしいかは議論せず、一般的理論にとどめます。

一般的な疑似乱数（Random等）は前後の値を推測可能です。
これは、疑似乱数が一定の周期で繰り返しているため、前後の値が一意にきまっているためです。

そのため、特定の UUID を解析すれば、その前後の値が生成可能ということになります。

わかりやすい例では、ゲームのRTAにおいて敵へのダメージから現在の乱数番地を特定するようなものです。

UUID の生成過程において、十分な周期を持てない場合があります。

UUID は122ビットの空間を持ちます。
しかし、生成に用いる疑似乱数は122ビットの空間を持たない場合が多いです。
32ビットや、64ビットの疑似乱数装置から生成されます。

そのため、これら短周期の疑似乱数装置を利用した場合、鳩の巣理論により期待する空間を埋められません。
32ビットの場合は $ f(32) \simeq 6.6 * 10^{4} $となり、
64ビットの場合は $ f(64) \simeq 4.3 * 10^{4} $となります。

一般的な疑似乱数は、初期化を時刻によって行います。
処理系の開始時刻から、おおよそのSeedを特定できます。

時刻をミリ秒で処理する系で、1分間にとり得るSeedの数は $ 60s * 1000ms = 60,000 \simeq 2^{16}$ となります。
この場合は、 $ f(16) \simeq 256 $ となります。

上記の問題は、擬似乱数に起因する問題です。
これらの問題は、暗号論的乱数の使用により解決されます。

暗号論的疑似乱数生成器

しかし、暗号論的乱数にも弱点があります。

暗号論的乱数は外部雑音をエントロピーとして利用しますが、エントロピーがたまらない状態では十分に安全な乱数が生成されません。

一般的に、下記状態ではエントロピーが不足している状態となります。

仮想サーバーである
- 仮想サーバーでは高品位のエントロピーを得ることが難しい場合があります
- Is it appropriate to use haveged as a source of entropy on virtual machines?
起動直後である
- 起動直後はエントロピーが十分に蓄積されていない場合があります。
- 乱数生成

UUID は、十分な耐衝突性を持っていますが、その効果を得るためには暗号論的に正しいUUIDを利用する必要があります。