2日前、マイク・マローンがMediumで、V8におけるMath.random()の実装と、そこで使われているPRNGの品質がいかに脆弱であるかについての興味深い記事を公開した。http://bit.ly/1SPDraN。

その記事は今日、Hacker Newsでトップニュースの一つになっていた。Math.random()がどのように壊れていて、どう修正すべきかという観点からは非常に分かりやすく有益な内容なので、この件自体について私から付け加えることは何もない。ただ、著者が巨大で衝突する可能性が低いIDを生成するという文脈でPRNGの脆弱性を発見したので、私が過去に何度も使ってきた、高速で極めて信頼性の高い代替手法を皆さんに共有したい。

ユニークIDの問題

理論上、ユニークなIDを生成したいのであれば、IDが二度と重複しないことを保証するための何らかの状態を保存する必要がある。最も単純なケースでは、単なるカウンターを使えばよい。しかし、前回生成したIDは一貫性のある方法で保存されなければならない。システムが再起動した際に、保存されたカウンターが正しくディスクに永続化されていなかったせいで、同じIDが再び生成されてしまうようなことがあってはならないのだ。

複数のプロセスでユニークIDを生成したい場合、各プロセスは、他のプロセスのプレフィックスと絶対に衝突しない、プロセス固有のプレフィックスをIDの先頭に付けることを保証しなければならない。これも管理が複雑になりうる。1秒あたり大量のIDを生成したい場合に、過去のIDを信頼できる方法で保存しなければならないという単純な事実が、非常に時間のかかる処理になってしまうのだ。

幸い、シンプルな解決策がある。0からNまでの範囲で乱数を生成するのだ。ただしNは、衝突の確率があらゆる実用的な用途において無視できるほど小さくなるくらい十分に大きな値にする。これは、生成される数が0からNの間で一様に分布している場合にのみ機能する。この前提が成り立つなら、誕生日のパラドックスを利用して衝突の確率を計算できる。

十分なビット数を使えば、たとえ毎秒何百万ものIDを何百年も生成し続けたとしても、衝突の確率を、地球に小惑星が直撃する確率よりも数十億倍も低くすることは造作もない。もしこれでもまだ余裕が足りないと思うなら、単にビット数を増やせばよい。宇宙に存在する原子の数よりも大きなID空間を簡単に実現できるのだ。

この生成方法には大きな利点がある。完全にステートレスだということだ。複数のノードがメッセージを交換することなく同時にIDを生成できる。さらに、ディスクに保存すべきものが何もないため、CPUが処理できる限りの速度で生成できる。計算は簡単にCPUキャッシュに収まる。だから、恐ろしく高速で便利なのだ。

マイク・マローンはこの考え方を使い、PRNGを用いて、それぞれが64種類の文字のいずれかである文字の集合からなるIDを作成していた。各文字を作り出すために脆弱なV8のPRNGが使われた結果、衝突が発生したのだ。そもそもの前提は、新しいIDがそれぞれ0からNまでの空間の中で一様に選択されなければならないということだったことを思い出してほしい。

より強力なPRNGを使えばこの問題は解決できるが、そのためにはPRNGの解析が必要になる。もう一つの問題はシードだ。再起動後に同じPRNGの初期状態を再び選んでしまわないように、どのようにしてプロセスを再開するのか。そうしなければ、実際のID空間は出力空間自体ではなく、PRNGのシードによって制限されてしまう。

以上のような理由から、これらの問題のほとんどを回避できる、ごく単純な手法を紹介したい。

暗号学的ハッシュ関数を使ってユニークIDを生成する

暗号学的ハッシュ関数は、ビット列を固定長のビット列に変換する、逆算不可能な関数だ。さまざまな攻撃に対する耐性を持つように設計されているが、この用途で依拠するのは、その関数が持つある一つの特性、すなわち出力の均一性だけである。ハッシュ関数の入力の1ビットを変えると、出力の各ビットが50%の確率で変化するのだ。

信頼できるシードを得るために、OSの力を借り、/dev/urandomに問い合わせる。ジェネレータにシードを与える瞬間こそ、本当に外部からのエントロピーが必要な場面だ。そうしなければ、同じシーケンスを再び生成してしまうという大きなミスを本当に犯しかねない。

暗号学的ハッシュ関数の例として、よく知られたSHA1を使う。これは160ビットの出力を持つ。なお、この用途であればMD5 sumを使っても構わない。MD5が抱える脆弱性は、ここでの使い方には何の影響も与えない。

まず、/dev/urandomから160ビットを読み取ってシードを作成する。擬似コードでは次のようになる。

seed = devurandom.read(160/8)

カウンターも初期化する。

counter = 0

そして、これが新しいIDを生成するたびに呼び出す関数だ。

function get_new_id()
    myid = SHA1(string(counter) + seed)
    counter = counter + 1
    return myid
end

基本的に、シードである固定の文字列があり、それを増加していくカウンターとともにハッシュする。たとえばシードが「foo」であれば、新しいIDは次のように出力される。

SHA1(“0foo”)
SHA1(“1foo”)
SHA1(“2foo”)

これだけでも我々のユースケースには十分だ。しかし、IDが予測されにくいことも必要になる場合がある。IDを予測困難にしたいのであれば、get_new_id()関数でSHA1の代わりにSHA1_HMAC()を使えばよい。シードを秘密鍵、カウンターをメッセージとしてHMACを計算するのだ。

この手法は高速で、優れた分布が保証されているため、衝突の起こりにくさは誕生日のパラドックスが予測する通りになる。PRNGについての解析も不要で、完全にステートレスだ。

私はこの手法を、分散システム内の複数のノード間でメッセージIDを生成するために、自身のDisqueプロジェクトで使っている。

Hacker Newsのスレッドはこちら: https://news.ycombinator.com/item?id=10606910