κeenです。こちらのスライドが話題になっているようです。
10秒で衝突するUUIDの作り方 - Speaker Deck
笑い話としても乱数の難しさの側面としても面白いのですが、これを見た人たちの反応がちょっと勘違いしてそうだったので補足します。
別に私は暗号とか乱数とかの専門家ではないです。
発表者の方のコードは読みましたか？
少し速度が必要になるのでRustに移植します。
[package]
name = "genuuidv4"
version = "0.1.0"
edition = "2018"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
rand = "0.7.2"
sfmt = "0.6.0"
sfmtはメルセンヌツイスタのRNG(乱数生成器)ライブラリです。
use rand::{Rng, SeedableRng};
use sfmt::SFMT;
use std::io::{self, BufWriter, Write};
struct GenUuidV4(SFMT);
impl GenUuidV4 {
const VERSION: u8 = 4;
const VARIANT: u8 = 2;
pub fn generate(&mut self) -> String {
let bytes = self.random_16bytes();
Self::from_16bytes(bytes)
}
pub fn random_16bytes(&mut self) -> [u8; 16] {
self.0.gen()
}
pub fn from_16bytes(b: [u8; 16]) -> String {
format!("{:x}{:x}{:x}{:x}-{:x}{:x}-{:x}{:x}-{:x}{:x}-{:x}{:x}{:x}{:x}{:x}{:x}",
b[0], b[1], b[2], b[3],
b[4], b[5],
(Self::VERSION << 4 | 0b00001111u8 & b[6]), b[7],
(Self::VARIANT << 6 | 0b00001111u8 & b[8]), b[9],
b[10], b[11], b[12], b[13], b[14], b[15],
)
}
}
fn main() -> io::Result<()>{
use std::env;
let n = env::args().nth(1).expect("missing arg N").parse::<u32>().expect("arg N isn't a number");
// IOがそこそこ重いので高速化しておく
let out = io::stdout();
let mut out = BufWriter::new(out.lock());
for _ in 0..n {
let mut uuid = GenUuidV4(SFMT::from_entropy());
out.write(&uuid.generate().into_bytes())?;
writeln!(out, "")?;
};
out.flush()?;
Ok(())
}
これを実行すると衝突するので正しく移植できているようです。
$ cargo run --release 65536 | LANG=C sort | uniq -d
Finished release [optimized] target(s) in 0.01s
Running `target/release/genuuidv4 65536`
2669ea66-d52f-4179-8758-462ccfa05
このコード、問題なのはループ内だけです。
for _ in 0..n {
let mut uuid = GenUuidV4(SFMT::from_entropy());
out.write(&uuid.generate().into_bytes())?;
writeln!(out, "")?;
};
ループ内でシードを初期化しているのが問題です。from_entropy で内部の初期化に使われているのは追っていくとシステムコールのgetrandomです。getrandomソースは urandom ですがこれはマニュアルによると暗号用途にも使えるらしいので乱数の質としては問題ないでしょう。
問題になっているのはこの SFMT のシードに使われるベクトルが 32bitしかない点です。
シードが同じなら同じ乱数列が生成されるのでUUIDも同じものになってしまうのはスライドで紹介されている通りです。メルセンヌツイスタのアルゴリズムではなく、シードの空間の問題です。
シードの空間が32bitであるということは 誕生日のパラドックス の考え方でいくとおおむね32bitの1/2乗くらいのオーダーで衝突するので、 平均して 2^16 = 65536 個のUUIDを生成すると衝突する組が得られる訳です。
メルセンヌツイスタ自体は2^19937-1の周期を持っているのでそう簡単には衝突しません。
初期化を一度だけして、メルセンヌツイスタの内部状態をずっと使い回すようにしてみましょう。
let mut uuid = GenUuidV4(SFMT::from_entropy());
for _ in 0..n {
out.write(&uuid.generate().into_bytes())?;
writeln!(out, "")?;
};
これなら16,777,216個くらい生成しても衝突しません。
$ cargo run --release 16777216 | LANG=C sort | uniq -d
Compiling genuuidv4 v0.1.0 (/home/shun/Rust/genuuidv4)
Finished release [optimized] target(s) in 0.34s
Running `target/release/genuuidv4 16777216`
$
原理的には少なくとも (2^19937)^(1/2) 個のUUIDを生成すれば乱数が1周しますが、その前にUUID v4の空間が122bitしかないことから2^61個生成すれば衝突するはずなのであんまり周期は関係なさそうですね。
該当のスライドを見て「メルセンヌツイスタは暗号論的疑似乱数生成器でないから衝突する」なんて言ってる人もいましたが暗号論的に次の値が予測できないことと122bit生成して衝突しないことはあんまり関係なさそうに見えます。暗号論詳しくないので詳しい方いましたら教えて下さい。
ということでUUIDが衝突する原理はメルセンヌツイスタのアルゴリズムではなく、32bitしかないシードを毎回与えていたのが原因であることを紹介しました。詳しくないことを正しく怖がるのはいいんですが半知半解のまま適当に怖がり回すのはやめましょうね。