Go 1.22における安全な乱数生成
Secure Randomness in Go 1.22 by Russ Cox and Filippo Valsorda
コンピュータはランダムではありません。それどころか、ハードウェアの設計者たちは、コンピュータがどんなプログラムでも
毎回同じように実行することを保証するために大変な努力をしています。そのため、プログラムが本当に乱数を必要とする場合には、
余分な工夫が必要になります。従来、計算機科学者やプログラミング言語は乱数を2種類に区別してきました。統計的乱数と
暗号学的乱数です。Goでは、それぞれ math/rand と
crypto/rand によって提供されています。この記事では、Go 1.22がこの2つを
どのように近づけたかを説明します。具体的には、math/rand(そして前回の記事で
触れた math/rand/v2 も含めて)で暗号学的な乱数源を使うようにしたのです。その結果、乱数の質が向上し、開発者が
誤って crypto/rand の代わりに math/rand を使ってしまった場合の被害もはるかに小さくなりました。
Go 1.22が何をしたのかを説明する前に、統計的乱数を暗号学的乱数と比較しながらもう少し詳しく見ていきましょう。
統計的乱数
基本的な統計的検定に通る程度の乱数は、シミュレーション、サンプリング、数値解析、非暗号学的なランダムアルゴリズム、 ランダムテスト、 入力のシャッフル、 ランダムな指数バックオフ といった用途には十分なことがほとんどです。非常に単純で計算も容易な数式で、こうした用途には十分な結果が得られます。 ただし手法があまりに単純なため、使われているアルゴリズムを知っている観察者は、十分な数の値を見れば、 たいてい残りの数列を予測できてしまいます。
統計的な乱数を生成する仕組みは、ほぼすべてのプログラミング環境に用意されていますが、その系譜をたどると、
Cを経由してResearch Unix Third Edition(V3)にたどり着きます。V3では srand と rand という一対の関数が
追加されました。マニュアルページには次のような注意書きがありました。
WARNING The author of this routine has been writing random-number generators for many years and has never been known to write one that worked.
(警告:このルーチンの作者は長年にわたって乱数生成器を書き続けてきたが、まともに動くものを書けたためしがない。)
この注意書きは半ば冗談でしたが、同時にこの種の生成器が 本質的にランダムではない ことを認めるものでもありました。
この生成器のソースコードを見れば、それがいかに単純なものかがよくわかります。PDP-11のアセンブリから 現代のCに書き直すと、次のようになります。
uint16 ranx;
void
srand(uint16 seed)
{
ranx = seed;
}
int16
rand(void)
{
ranx = 13077*ranx + 6925;
return ranx & ~0x8000;
}
srand を呼び出すと、単一の整数値のシードで生成器を初期化し、rand は生成器から次の数を返します。
戻り値の中のANDは符号ビットをクリアして、結果が正の値になるようにするためのものです。
この関数は 線形合同法(LCG) と呼ばれる生成器の一般的なクラスの一例で、KnuthはLCGを『The Art of Computer Programming』第2巻の 3.2.1節で分析しています。LCGの主な利点は、定数をうまく選べば、周期が来るまでにすべての出力値を 1度ずつ出力させられる点にあります。実際、Unixの実装でも15ビットの出力についてはそうなっていました。 しかしLCGには重大な問題があります。状態の上位ビットが下位ビットにまったく影響を与えないため、 数列を下位 k ビットに切り詰めると、必ずより短い周期で繰り返してしまうのです。最下位ビットは 0, 1, 0, 1, 0, 1 と交互に切り替わるしかありません。下位2ビットは 0, 1, 2, 3, 0, 1, 2, 3 のように 数え上げるか、あるいは 0, 3, 2, 1, 0, 3, 2, 1 のように数え下げるしかありません。3ビットの数列としては 8通りが考えられますが、オリジナルのUnixの実装では 0, 5, 6, 3, 4, 1, 2, 7 という並びを繰り返します。 (こうした問題は、値を素数で割った余りを使うことで回避できますが、当時としてはかなり高くつく計算でした。 簡潔な分析についてはS. K. ParkとK. W. Millerによる1988年のCACM論文 “Random number generators: good ones are hard to find”を、 より詳しい分析についてはKnuthの第2巻の第1章を参照してください。)
こうした問題が知られていたにもかかわらず、srand と rand の両関数は最初のC標準に取り込まれ、
その後もほぼすべての言語で同等の機能が用意されました。LCGはかつて実装戦略として主流の座を占めていましたが、
いくつかの重大な欠点のために、その人気は下火になっています。今もLCGが広く使われている代表例として
java.util.Random
があり、これは
java.lang.Math.random
を支えています。
先ほどの実装を見ればもう一つわかることがあります。内部状態が rand の戻り値によって完全に露呈してしまうのです。
アルゴリズムを知っていて1つの結果を見た観察者は、そこから将来のすべての結果を簡単に計算できてしまいます。
公開してよい乱数値と秘密にしておくべき乱数値の両方を計算するサーバーを運用しているなら、この種の生成器を
使うのは致命的です。秘密が秘密でなくなってしまいます。
より現代的な乱数生成器はオリジナルのUnixのものほどひどくはありませんが、それでも完全に予測不可能というわけには
いきません。それを示すために、次はGo 1で使われているオリジナルの math/rand の生成器と、
math/rand/v2 に追加したPCG生成器を見ていきます。
Go 1の生成器
Go 1の math/rand で使われている生成器は、
線形フィードバックシフトレジスタ
と呼ばれる仕組みの一種です。このアルゴリズムはGeorge Marsagliaのアイデアをもとに、Don MitchellとJim Reedsが
手を加え、さらにKen ThompsonがPlan 9向けに、続いてGo向けに独自にカスタマイズしたものです。正式な名前が
ないため、この記事ではこれを「Go 1生成器」と呼びます。
Go 1生成器の内部状態は、607個の uint64 からなるスライス vec です。このスライスの中には
特別な意味を持つ要素が2つあります。最後の要素である vec[606] は「タップ」と呼ばれ、vec[334] は
「フィード」と呼ばれます。次の乱数を生成するには、タップとフィードを足して値 x を求め、それをフィードに
書き戻したうえで、スライス全体を1つ後ろにシフトし(タップは vec[0] に移動し、vec[i] は vec[i+1] に
移動します)、x を返します。タップをフィードに 加算する ことから「線形フィードバック」と呼ばれ、
各ステップでスライスの要素をシフトすることから、状態全体は「シフトレジスタ」と呼ばれます。
もちろん、実際にスライスの要素を1つずつ前に動かすのは現実的でないほどコストがかかるため、実装ではスライスのデータは そのままにしておき、代わりにタップとフィードの位置を各ステップで後ろにずらしています。コードは次のように なります。
func (r *rngSource) Uint64() uint64 {
r.tap--
if r.tap < 0 {
r.tap += len(r.vec)
}
r.feed--
if r.feed < 0 {
r.feed += len(r.vec)
}
x := r.vec[r.feed] + r.vec[r.tap]
r.vec[r.feed] = x
return uint64(x)
}
次の数を生成する処理はとても安く済みます。減算2回、条件付き加算2回、ロード2回、加算1回、ストア1回だけです。
残念ながら、この生成器は内部の状態ベクトルの要素を1つそのまま返すため、生成器から607個の値を読み取ると、
その内部状態はすべて露呈してしまいます。その値さえあれば、自分で vec を組み立ててアルゴリズムを実行することで、
将来の値をすべて予測できます。また、アルゴリズムを逆向きに実行する(タップからフィードを引いて、
スライスを左にシフトする)ことで、過去の値もすべて復元できます。
これを実際に示すデモとして、脆弱なプログラムを用意しました。これは
疑似乱数の認証トークンを生成するプログラムと、それ以前のトークンの並びから次のトークンを予測するコードの
両方を含んでいます。ご覧のとおり、Go 1生成器はまったくセキュリティを提供しません(もっとも、
そもそもそのために作られたものではありません)。また、生成される乱数の質は vec の初期状態にも左右されます。
PCG生成器
math/rand/v2 では、より現代的な統計的乱数生成器を提供したいと考え、Melissa O’Neillが2014年の論文
“PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation”
で発表したPCGアルゴリズムを採用することにしました。この論文の分析はあまりに網羅的であるため、この生成器が
実はきわめて単純であることが一見わかりにくいのですが、要するにPCGとは、後処理を加えた128ビットのLCGです。
もし状態 p.x が(仮に)uint128 だとしたら、次の値を計算するコードは次のようになります。
const (
pcgM = 0x2360ed051fc65da44385df649fccf645
pcgA = 0x5851f42d4c957f2d14057b7ef767814f
)
type PCG struct {
x uint128
}
func (p *PCG) Uint64() uint64 {
p.x = p.x * pcgM + pcgA
return scramble(p.x)
}
状態全体はたった1つの128ビットの数で、更新処理も128ビットの乗算と加算だけです。戻り値の計算では、
scramble 関数が128ビットの状態を64ビットの状態にまで縮約します。オリジナルのPCGでは(ここでも
仮の uint128 型を使うと)次のようになっていました。
func scramble(x uint128) uint64 {
return bits.RotateLeft(uint64(x>>64) ^ uint64(x), -int(x>>122))
}
このコードは128ビットの状態を上位と下位の2つに分けてXORを取り、その結果を状態の上位6ビットに従って 回転させています。このバージョンは「xor shift low, right rotate」を略してPCG-XSL-RRと呼ばれています。
Goのプロポーザルの議論の中でO’Neillが提案した内容を もとに、GoのPCGはビットをより激しく混ぜ合わせる、乗算をベースにした新しいスクランブル関数を使っています。
func scramble(x uint128) uint64 {
hi, lo := uint64(x>>64), uint64(x)
hi ^= hi >> 32
hi *= 0xda942042e4dd58b5
hi ^= hi >> 48
hi *= lo | 1
}
O’Neillはこのスクランブラを使ったPCGを、「double xorshift multiply」の略でPCG-DXSMと呼んでいます。 Numpyもこの形のPCGを採用しています。
PCGは1つの値を生成するのにより多くの計算を必要とするものの、状態として持つ量はずっと少なく、607個ではなく
uint64 を2個保持するだけで済みます。また状態の初期値に対する感度もずっと低く、
他の生成器が通らないような統計的検定の多くに通ることも
わかっています。多くの点で、これは理想的な統計的生成器だと言えます。
とはいえ、PCGも予測不可能というわけではありません。結果を作るためのビットのスクランブル処理は、LCGや Go 1の生成器のように状態を直接露呈させるわけではありませんが、それでも PCG-XSL-RRは逆算できることが 知られていますし、PCG-DXSMについても同様のことができたとしても驚きではありません。秘密の情報を扱うには、 何か別のものが必要です。
暗号学的乱数
暗号学的乱数は、生成方法を知っていて、これまでに生成された値をいくつ観察していたとしても、実用上まったく 予測できないものでなければなりません。暗号プロトコルの安全性、秘密鍵、現代の商取引、オンラインでのプライバシーなど 数多くのものが、暗号学的乱数を利用できるかどうかに死活的にかかっています。
暗号学的乱数を提供するのは、突き詰めればオペレーティングシステムの役目です。OSはマウス、キーボード、 ディスク、ネットワークなどの物理デバイスのタイミング、そして最近では CPU自身が直接計測する電気的なノイズ から、真の乱雑さをかき集めることができます。OSが意味のある量、たとえば256ビット以上の乱雑さを収集したら、 暗号学的なハッシュ関数や暗号化アルゴリズムを使って、そのシードを任意の長さの乱数列に引き伸ばすことができます。 (実際にはOSはその後も継続的に新しい乱雑さを収集し、数列に加え続けています。)
こうしたオペレーティングシステムのインターフェースは、時代とともに変化してきました。10年ほど前までは、
ほとんどのシステムが /dev/random あるいはそれに類するデバイスファイルを用意していました。今日では、
乱数がいかに基盤的なものであるかが認識されるようになり、OSは代わりに専用のシステムコールを提供しています。
(これにより、ファイルシステムから切り離された状態でもプログラムが乱数を読み取れるようになります。)
Goでは、crypto/rand パッケージがこうした詳細を抽象化し、
rand.Read という、どのOSでも同じインターフェースを提供しています。
math/rand が uint64 を1つ必要とするたびにOSへ乱数を要求するのは、実用的ではありません。しかし
暗号学的な手法を使えば、LCGやGo 1の生成器、さらにはPCGよりも優れた、プロセス内で完結する乱数生成器を
定義できます。
ChaCha8Rand生成器
私たちが新たに作った生成器は、仕様上の名前として深く考えずにChaCha8Randと名付けましたが、
math/rand/v2 の rand.ChaCha8 として実装されており、
Daniel J. BernsteinのChaChaストリーム暗号に軽い変更を加えたものです。
ChaChaは20ラウンド版のChaCha20という形で、TLSやSSHをはじめ広く使われています。Jean-Philippe Aumassonの
論文“Too Much Crypto”は、8ラウンド版のChaCha8も安全であると
説得力を持って論じています(しかもおよそ2.5倍高速です)。私たちはこのChaCha8をChaCha8Randの核として
採用しました。
ChaCha8を含む多くのストリーム暗号は、キーとブロック番号を受け取り、一見ランダムに見えるデータの
固定サイズのブロックを生成する関数として定義されています。こうした暗号が目指す(そしてたいてい達成する)
標準的な基準は、指数関数的なコストのかかる総当たり攻撃でもしない限り、出力が実際のランダムなデータと
区別できないというものです。メッセージの暗号化や復号は、入力データの連続するブロックと、生成された
ランダムな値の連続するブロックをXORすることで行われます。ChaCha8を rand.Source として使うにあたっては、
生成したブロックを入力データとXORするのではなく、そのまま直接使います(これは、すべてゼロのデータを
暗号化あるいは復号しているのと等価です)。
私たちはChaCha8Randを乱数生成により適したものにするため、いくつかの点に手を加えました。要点をまとめると 次のとおりです。
- ChaCha8Randは32バイトのシードを受け取り、これをChaCha8のキーとして使います。
- ChaCha8は64バイトのブロックを生成し、計算上はブロックを16個の
uint32として扱います。よくある実装では、 それぞれ4個のuint32からなる16本のベクトルレジスタを使い、 SIMD命令によって一度に4ブロックを 計算します。これによりインターリーブされた4ブロックが得られ、入力データとXORするにはこれをアンシャッフル する必要があります。ChaCha8Randでは、このインターリーブされたブロックをそのまま乱数の出力ストリームと 定義することで、アンシャッフルのコストを取り除いています。(セキュリティの観点からは、これは標準の ChaCha8に続けて再シャッフルを行っているものと見なせます。) - ChaCha8はブロックの最後に、ブロック内の各
uint32にある値を加算して仕上げます。この値の半分は キー由来のもので、残り半分は既知の定数です。ChaCha8Randでは、この既知の定数の加算をやり直さないと 定義することで、最後の加算処理の半分を取り除いています。(セキュリティの観点からは、これは標準の ChaCha8に続けてこの既知の定数を引き算しているものと見なせます。) - ChaCha8Randは16ブロック生成するごとに、そのブロックの最後の32バイトを自分自身のために取り出し、 それを次の16ブロック分のキーとします。これはある種の 前方秘匿性(forward secrecy)をもたらします。もし 何らかの攻撃によってシステムが侵害され、生成器のメモリ状態がすべて奪われたとしても、直前の鍵の 更新以降に生成された値しか復元できません。それより過去の値には手が届きません。ここまでの定義では ChaCha8Randは常に4ブロックずつ生成する必要がありますが、鍵の更新を16ブロックごとに行うことにしたのは、 256ビットや512ビットのベクトルを使ってより高速な実装を行い、一度に8ブロックや16ブロックを生成できる 余地を残しておくためです。
私たちはChaCha8RandのC2SP仕様をテストケースとともに公開しました。 これにより、他の実装が、与えられたシードに対してGoの実装と同じ乱数列を再現できるようになります。
Goのランタイムは現在、コアごとにChaCha8Randの状態(300バイト)を保持しており、それぞれOSが提供する 暗号学的な乱雑さでシードされています。これにより、ロックの競合なしに高速に乱数を生成できます。 コアごとに300バイトを確保するのは高くつくように思えるかもしれませんが、16コアのシステムであれば、 これは共有のGo 1生成器の状態を1つ保持する場合(4,872バイト)とほぼ同じ量です。この速度には十分な 価値があります。このコアごとのChaCha8Rand生成器は、現在Goの標準ライブラリの3つの箇所で使われています。
math/rand/v2パッケージのrand.Float64やrand.Nといった関数は、常にChaCha8Randを使用します。math/randパッケージのrand.Float64やrand.Intnといった関数は、rand.Seedが呼ばれていない場合にChaCha8Randを使用します。math/randにChaCha8Randを適用したことで、まだmath/rand/v2に移行していないプログラムであっても、rand.Seedさえ呼んでいなければ、その安全性が向上します。(rand.Seedが呼ばれた場合、実装は 互換性のためにGo 1の生成器にフォールバックする必要があります。)ランタイムは各マップのハッシュシードを選ぶ際に、これまで使っていた安全性の低い wyrandベースの生成器の代わりにChaCha8Randを使うように なりました。マップの実装が使う具体的なハッシュ関数を攻撃者が知っていると、マップを二次関数的な 振る舞いに追い込むような入力を用意できてしまうため、ランダムなシードが必要になります(Crosbyと Wallachによる “Denial of Service via Algorithmic Complexity Attacks”を参照してください)。 すべてのマップで共通の1つのグローバルなシードを使うのではなく、マップごとに異なるシードを使うことで、 他の種類の縮退した挙動も 避けられます。マップに暗号学的に安全な乱数のシードが本当に必要かどうかは厳密にはわかりませんが、 必要でないとも言い切れません。慎重を期すのが賢明に思えましたし、切り替えるのも簡単でした。
自分自身のChaCha8Randのインスタンスが必要なコードは、rand.ChaCha8を
直接作成できます。
セキュリティ上の誤りを修正する
Goは、開発者が既定で安全なコードを書けるように手助けすることを目指しています。セキュリティ上の影響がある
よくある間違いを見つけたときには、その間違いのリスクを減らす、あるいは完全になくす方法を探します。今回の
ケースでは、math/rand のグローバルな生成器があまりに予測しやすく、さまざまな場面で深刻な問題を
引き起こしていました。
たとえば、Go 1.20でmath/rand の Readが非推奨になったとき、
非推奨機能の利用を指摘するツールのおかげで、鍵材料の生成のような、本来
crypto/rand の Readを使うべき場所で
それを使っていたことに気づいた、という声が開発者から寄せられました。Go 1.20を使っている場合、この間違いは
深刻なセキュリティ上の問題であり、被害の実態を把握するには詳細な調査が必要になります。鍵はどこで使われたのか。
鍵はどのように漏洩したのか。攻撃者が鍵を導き出せてしまうような他の乱数の出力が露呈していなかったか。
といった具合です。Go 1.22であれば、この間違いはただの間違いで済みます。それでも crypto/rand を
使うほうが良いことに変わりはありません。OSのカーネルのほうが、さまざまな種類の詮索の目から乱数値を
秘密に保つ点で優れた仕事をしてくれますし、カーネルは自身の生成器に絶えず新しいエントロピーを加え続けていますし、
カーネルはより多くの検証を経てきているからです。しかし、誤って math/rand を使ってしまったとしても、
もはやセキュリティ上の大惨事にはなりません。
一見「暗号」には見えないものの、予測不可能な乱数を必要とするユースケースも数多くあります。こうしたケースは、 Go 1の生成器の代わりにChaCha8Randを使うことで、より頑健になります。
たとえば、ランダムなUUIDの
生成を考えてみましょう。UUIDは秘密の情報ではないため、math/rand を使っても問題なさそうに見えます。
しかし、もし math/rand が現在時刻でシードされていた場合、複数のコンピュータでまったく同じ瞬間に実行すると、
同じ値が生成されてしまい、「universally unique(世界中で一意)」ではなくなってしまいます。現在時刻が
ミリ秒単位でしか取得できないシステムでは、これは特に起こりやすい問題です。Go 1.20で導入された、OS提供の
エントロピーによる自動シードを使っていたとしても、Go 1の生成器のシードはたかだか63ビットの整数でしかない
ため、起動時にUUIDを生成するプログラムは最大で2⁶³通りのUUIDしか生成できず、およそ2³¹個ほど
UUIDを生成した時点で衝突が起きやすくなります。Go 1.22であれば、新しいChaCha8Rand生成器は256ビットの
エントロピーでシードされ、最初のUUIDとして2²⁵⁶通りの候補を生成できます。衝突を心配する必要はもう
ありません。
もう一つの例として、受信したリクエストをランダムにバックエンドサーバーへ振り分けるフロントエンドサーバーの 負荷分散を考えてみましょう。もし攻撃者が振り分け結果を観察でき、それを生成している予測可能な アルゴリズムを知っていたなら、攻撃者は安価なリクエストばかりの流れを送りつけつつ、高価なリクエストだけを すべて1台のバックエンドサーバーに集中させるように仕組むことができてしまいます。これはGo 1の生成器を 使っている場合には、起こりそうにはないものの十分に起こりうる問題です。Go 1.22であれば、これはまったく 問題になりません。
これらの例のいずれにおいても、Go 1.22はセキュリティ上の問題を取り除くか、あるいは大幅に軽減しています。
パフォーマンス
ChaCha8Randによるセキュリティ上の利点には、わずかなコストが伴います。とはいえ、ChaCha8RandはGo 1の
生成器やPCGと十分に張り合えるレベルにとどまっています。次のグラフは、さまざまなハードウェア上で、
2種類の操作を実行した際の3つの生成器のパフォーマンスを比較したものです。1つは乱数列の次の uint64 を
返す基本操作である「Uint64」、もう1つは [0, 1000) の範囲のランダムな値を返す、より高レベルな操作である
「N(1000)」です。
「running 32-bit code(32ビットコードでの実行)」のグラフは、現代の64ビットx86チップ上で
GOARCH=386 を指定してビルドしたコード、つまり32ビットモードで実行した場合の結果を示しています。
この場合、PCGは128ビットの乗算を必要とするため、32ビットのSIMD演算しか使わないChaCha8Randよりも
遅くなります。実際の32ビットシステムの重要性は年々薄れていますが、そうしたシステムでもChaCha8Randの
ほうがPCGより高速だというのは興味深い点です。
システムによっては、「Go 1: Uint64」は「PCG: Uint64」よりも高速なのに、「Go 1: N(1000)」は
「PCG: N(1000)」よりも遅い、ということが起こります。これは「Go 1: N(1000)」が、ランダムな int64 を
[0, 1000) の範囲の値に落とし込むために math/rand のアルゴリズムを使っており、そのアルゴリズムが
64ビット整数の除算を2回行っているために起こります。それに対して「PCG: N(1000)」と「ChaCha8: N(1000)」は、
より高速な math/rand/v2 のアルゴリズムを使っており、
これはほとんどの場合で除算を回避します。32ビット実行時とAmpere上では、この64ビットの除算を取り除いた
ことによる影響が、アルゴリズムの変更による効果の中でも支配的になっています。
全体として、ChaCha8RandはGo 1の生成器よりも遅いものの、最大でも2倍を超えることはなく、一般的なサーバーでは その差は3ナノ秒を超えることはありません。この差がボトルネックになるプログラムはごくわずかであり、 多くのプログラムはセキュリティの向上という恩恵を受けられるはずです。
まとめ
Go 1.22は、コードを一切変更することなく、プログラムをより安全にします。私たちは、crypto/rand の
代わりに誤って math/rand を使ってしまうというよくある間違いを特定し、math/rand そのものを強化する
ことでこれを実現しました。これは、Goがプログラムを既定で安全に保ち続けるという、これまでの歩みの中の
小さな一歩にすぎません。
こうした種類の間違いは、Goに限った話ではありません。たとえばnpmの keypair パッケージは、Web Crypto
APIを使ってRSA鍵ペアを生成しようとしますが、それが使えない場合にはJavaScriptの Math.random に
フォールバックしてしまいます。これは決して孤立した事例ではなく、私たちのシステムの安全性を開発者が
間違いを犯さないことに依存させ続けるわけにはいきません。むしろ私たちは、いずれすべてのプログラミング言語が、
「数学的な」乱数であっても暗号学的に強い疑似乱数生成器へと移行し、この種の間違いをなくす、あるいは
少なくともその被害範囲を大幅に小さくすることを願っています。Go 1.22の
ChaCha8Randの実装は、このアプローチが他の生成器と十分に張り合えることを
証明しています。
By Russ Cox and Filippo Valsorda