概要
ここでは、 正しくない実装をされた UUID を使うことによる安全性の検討をします。
特に言及のない場合は UUIDv4 の話となります。（乱数による生成）
実装がメインの話となります。
以下の用途での検討を行います。
- UUIDv4 である
正しい UUID
正しい UUID は、耐衝突性に優れます。
詳細は下記記事に詳しいですが、「鳩の巣原理」「誕生日攻撃」の2つは乱数の耐衝突性を考えるうえで重要です。
UUID(v4) がぶつかる可能性を考えなくていい理由
鳩の巣原理
誕生日攻撃
上記の記事内にありますが、衝突までの期待値は $N$ をビット数とした $ f(N) = 2^{N/2} $ となります。
UUIDは $ N = 122 $ から$ f(122) \simeq 2.3 * 10^{18} $となります。
正しくない UUID
ここでは、 正しくない 実装をされた 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を利用する必要があります。