セキュアなランダム性 in Go 1.22
コンピュータはランダムではありません。むしろ、ハードウェア設計者は、コンピュータが毎回同じ方法でプログラムを実行するように非常に努力しています。そのため、プログラムがランダムな数値を必要とする場合、それには追加の努力が必要です。伝統的に、コンピュータ科学者やプログラミング言語は、統計的ランダム性と暗号的ランダム性という2つの異なる種類のランダム数を区別してきました。Goでは、それらはそれぞれ math/rand と crypto/rand によって提供されています。この投稿では、Go 1.22がこれら2つをどのように近づけたかについて説明します。具体的には、math/rand（および前回の投稿で言及した math/rand/v2）で暗号的ランダム数のソースを使用することにより、より良いランダム性を実現し、開発者が誤って math/rand を使用した場合の被害を大幅に減らすことができました。
Go 1.22が何をしたのかを説明する前に、統計的ランダム性と暗号的ランダム性の違いを詳しく見てみましょう。
統計的ランダム性
基本的な統計テストに合格するランダム数は、シミュレーション、サンプリング、数値解析、非暗号的なランダム化アルゴリズム、ランダムテスト、入力のシャッフル、ランダムな指数バックオフなどのユースケースに適しています。これらのユースケースには、非常に基本的で計算が容易な数学的な公式が十分に機能します。しかし、これらの方法が非常に単純であるため、使用されているアルゴリズムを知っている観察者は、十分な値を見た後に残りのシーケンスを予測することができます。
ほとんどのプログラミング環境は、Cを通じてResearch Unix Third Edition (V3) に遡る統計的ランダム数を生成するメカニズムを提供しています。V3には srand と rand という2つの関数が追加されました。マニュアルページには次のような注意書きがありました
WARNING このルーチンの著者は何年もランダム数ジェネレーターを書いてきましたが、うまく動作するものを書いたことはありません。
この注意書きは一部ジョークですが、これらのジェネレーターが本質的にランダムではないことを認めています。
ジェネレーターのソースコードは、その単純さを明らかにしています。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は「The Art of Computer Programming, Volume 2, section 3.2.1」でこれを分析しています。LCGの主な利点は、定数を選択することで、すべての可能な出力値を一度ずつ出力し、繰り返すことができることです。しかし、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ビットのシーケンスは4つしかありません。元の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 Volume 2の最初の章を参照してください。）
これらの既知の問題があっても、srand と rand 関数は最初のC標準に含まれ、同等の機能はそれ以降のほとんどの言語に含まれました。LCGはかつて支配的な実装戦略でしたが、いくつかの重要な欠点のために人気が落ちました。現在も使用されている重要な例の一つは、java.util.Random であり、java.lang.Math.random を動かしています。
上記の実装からもわかるように、内部状態は rand の結果によって完全に露出されています。アルゴリズムを知っている観察者が1つの結果を見ると、将来のすべての結果を簡単に計算できます。公開されるランダム値と秘密にしておくべきランダム値を計算するサーバーを実行している場合、この種のジェネレーターを使用することは災害的です。秘密は秘密ではなくなります。
より現代的なランダムジェネレーターは、元のUnixのものほどひどくはありませんが、それでも完全に予測不可能ではありません。この点を明確にするために、次にGo 1の math/randジェネレーターと math/rand/v2 に追加されたPCGジェネレーターを見てみましょう。
The Go 1 Generator
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 を返します。ジェネレーターは「線形フィードバック」と呼ばれますが、タップがフィードに加算されるためです。全体の状態は「シフトレジスタ」です。
もちろん、スライスの各エントリを前方に移動するのは非常に高価なので、実装ではスライスデータをそのままにして、各ステップでタップとフィードの位置を後方に移動させます。コードは次のようになります
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のPCGアルゴリズムを採用しました。これは2014年に彼女の論文「PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation」で発表されました。この論文の徹底的な分析により、最初は気づきにくいかもしれませんが、ジェネレーターは非常に単純です：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)
}
全体の状態は単一の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ビットに従って回転させます。このバージョンはPCG-XSL-RR（「xor shift low, right rotate」）と呼ばれます。
提案の議論中にO’Neillからの提案に基づいて、GoのPCGは乗算に基づく新しい scramble 関数を使用し、ビットをより積極的に混ぜます
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をPCG-DXSM（「double xorshift multiply」）と呼びます。Numpyもこの形式のPCGを使用しています。
PCGは各値を生成するためにより多くの計算を使用しますが、使用する状態は大幅に少なくなります：2つの uint64 です。初期値にもあまり敏感ではなく、他のジェネレーターが通過しない多くの統計テストに合格します。多くの点で、理想的な統計ジェネレーターです。
それでも、PCGは予測不可能ではありません。結果を準備するためのビットのスクランブリングは、LCGやGo 1ジェネレーター器のように状態を直接露出しませんが、PCG-XSL-RRは逆転可能であり、PCG-DXSMも逆転可能である可能性があります。秘密のためには、別のものが必要です。
暗号的ランダム性
暗号的ランダム数は、生成方法を知っている観察者が以前に生成された値をいくら見ても、実際には全く予測不可能である必要があります。暗号プロトコル、秘密鍵、現代の商取引、オンラインプライバシーなどの安全性はすべて、暗号的ランダム性へのアクセスに依存しています。
暗号的ランダム性を提供するのは最終的にはオペレーティングシステムの仕事であり、物理デバイスからの真のランダム性を収集できます。例えば、マウス、キーボード、ディスク、ネットワークのタイミング、最近ではCPU自体によって直接測定される電気ノイズなどです。オペレーティングシステムが意味のある量のランダム性（例えば、少なくとも256ビット）を収集すると、暗号的ハッシュや暗号化アルゴリズムを使用して、そのシードを任意の長さのランダム数列に伸ばすことができます。（実際には、オペレーティングシステムは常に新しいランダム性をシーケンスに追加しています。）
正確なオペレーティングシステムインターフェースは時間とともに進化してきました。10年前、ほとんどのシステムは /dev/random というデバイスファイルを提供していました。今日では、ランダム性がどれほど基本的なものになったかを認識して、オペレーティングシステムは直接のシステムコールを提供しています。（これにより、ファイルシステムから切り離されていてもプログラムがランダム性を読み取ることができます。）Goでは、crypto/rand パッケージがこれらの詳細を抽象化し、すべてのオペレーティングシステムで同じインターフェースを提供します：rand.Read。
math/rand が uint64 を必要とするたびにオペレーティングシステムにランダム性を求めるのは現実的ではありません。しかし、暗号的技術を使用して、LCG、Go 1ジェネレーター、さらにはPCGよりも優れたインプロセスランダムジェネレーターを定義することができます。
ChaCha8Rand ジェネレーター
私たちの新しいジェネレーターは、仕様上の目的で ChaCha8Rand と名付けられ、math/rand/v2 の rand.ChaCha8 として実装されました。これは、Daniel J. BernsteinのChaChaストリーム暗号の軽く修正されたバージョンです。ChaChaは、TLSやSSHを含む20ラウンド形式のChaCha20で広く使用されています。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として扱います。一般的な実装では、SIMD命令を使用して16個のベクトルレジスタに4つのuint32を持つ4つのブロックを一度に計算します。これにより、入力データとXORするためにアンシャッフルする必要がある4つのインターリーブされたブロックが生成されます。ChaCha8Randは、インターリーブされたブロックがランダムデータストリームであると定義し、アンシャッフルのコストを削減します。（セキュリティ目的では、これは標準のChaCha8の後にリシャッフルが行われると見なすことができます。）
ChaCha8はブロックを終了する際に、ブロック内の各uint32に特定の値を追加します。半分の値はキー素材であり、残りの半分は既知の定数です。ChaCha8Randは、既知の定数が再追加されないと定義し、最終的な加算の半分を削減します。（セキュリティ目的では、これは標準のChaCha8の後に既知の定数を引くと見なすことができます。）
16番目の生成ブロックごとに、ChaCha8Randはブロックの最後の32バイトを次の16ブロックのキーとして使用します。これにより、ある種の前方秘匿性が提供されます。ジェネレーターのメモリ状態が攻撃によって完全に回復された場合でも、最後の再キーイング以降に生成された値のみが回復されます。過去の値はアクセスできません。ChaCha8Randはこれまでのところ4ブロックを一度に生成する必要がありますが、256ビットまたは512ビットのベクトルを使用して8または16ブロックを一度に生成する可能性を残すために、キー回転を16ブロックごとに行うことを選びました。
ChaCha8RandのC2SP仕様とテストケースを作成し公開しました。これにより、他の実装がGoの実装と同じシードで再現性を共有できるようになります。
Goランタイムは現在、OSが提供する暗号的ランダム性でシードされたコアごとのChaCha8Rand状態（300バイト）を維持しており、ロック競合なしにランダム数を迅速に生成できます。コアごとに300バイトを割り当てるのは高価に思えるかもしれませんが、16コアシステムでは、単一の共有Go 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を適用することで、rand.Seed を呼び出していない限り、プログラムが math/rand/v2 に更新される前でもセキュリティが向上します。（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 を使用する方が依然として良いですが、オペレーティングシステムカーネルはランダム値をさまざまな種類の覗き見からよりよく守ることができ、カーネルは常に新しいエントロピーをジェネレーターに追加しており、カーネルはより多くの精査を受けています。しかし、誤って math/rand を使用することはもはやセキュリティの大惨事ではありません。
「暗号」ではないように見えるが、それでも予測不可能なランダム性を必要とするさまざまなユースケースもあります。これらのケースは、Go 1ジェネレーターの代わりにChaCha8Randを使用することで、より堅牢になります。
例えば、ランダムなUUIDを生成する場合、UUIDは秘密ではないため、math/rand を使用するのは問題ないように思えます。しかし、math/rand が現在の時間でシードされている場合、異なるコンピュータで同時に実行されると同じ値が生成され、「ユニバーサルに一意」ではなくなります。これは、現在の時間がミリ秒単位でしか利用できないシステムで特に起こりやすいです。Go 1.20で導入されたOS提供のエントロピーを使用した自動シードでも、Go 1ジェネレーターのシードは63ビットの整数に過ぎないため、起動時にUUIDを生成するプログラムは2⁶³の可能なUUIDしか生成できず、2³¹程度のUUIDを生成した後に衝突が発生する可能性があります。Go 1.22を使用すると、新しいChaCha8Randジェネレーターは256ビットのエントロピーからシードされ、2²⁵⁶の可能な最初のUUIDを生成できます。衝突を心配する必要はありません。
別の例として、フロントエンドサーバーでランダムにバックエンドサーバーにリクエストを割り当てるロードバランシングを考えてみましょう。攻撃者が割り当てを観察し、予測可能なアルゴリズムを知っている場合、安価なリクエストのストリームを送信し、すべての高価なリクエストを単一のバックエンドサーバーに割り当てることができます。これはGo 1ジェネレーターを使用する場合に起こりうる問題ですが、Go 1.22を使用する場合、全く問題ありません。
これらの例のすべてにおいて、Go 1.22はセキュリティ問題を排除または大幅に軽減しました。
パフォーマンス
ChaCha8Randのセキュリティ上の利点には小さなコストがありますが、ChaCha8RandはGo 1ジェネレーターやPCGと同じ範囲内にあります。以下のグラフは、さまざまなハードウェアでの3つのジェネレーターのパフォーマンスを比較し、2つの操作を実行しています：次の uint64 をランダムストリームで返すプリミティブ操作「Uint64」と、範囲[0, 1000)のランダム値を返す高レベル操作「N(1000)」です。
「32ビットコードの実行」グラフは、GOARCH=386でビルドされたコードを実行している現代の64ビットx86チップを示しています。つまり、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 のアルゴリズムを使用しており、そのアルゴリズムが2つの64ビット整数除算操作を行うためです。対照的に、「PCG: N(1000)」および「ChaCha8: N(1000)」は、ほとんどの場合除算を回避する高速な math/rand/v2 アルゴリズムを使用しています。32ビット実行およびAmpere上での64ビット除算の削除がアルゴリズムの変更を支配しています。
全体として、ChaCha8RandはGo 1ジェネレーターよりも遅いですが、2倍以上遅くなることはなく、典型的なサーバーではその差は3nsを超えることはありません。非常に少数のプログラムがこの差によってボトルネックになるでしょうし、多くのプログラムはセキュリティの向上を享受するでしょう。
結論
Go 1.22は、コードの変更なしにプログラムをよりセキュアにします。これは、math/rand の代わりに crypto/rand を誤って使用するという一般的なミスを特定し、math/rand を強化することで実現しました。これは、プログラムをデフォルトで安全に保つためのGoの継続的な取り組みの一環です。
この種のミスはGoに特有のものではありません。例えば、npmの keypair パッケージはWeb Crypto APIを使用してRSAキーのペアを生成しようとしますが、利用できない場合はJavaScriptの Math.random にフォールバックします。これは決して孤立したケースではなく、システムのセキュリティは開発者がミスをしないことに依存することはできません。代わりに、最終的にはすべてのプログラミング言語が「数学的」ランダム性のためにも暗号的に強力な疑似乱数ジェネレーターに移行し、この種のミスを排除するか、少なくともその影響範囲を大幅に減らすことを望んでいます。Go 1.22のChaCha8Rand実装は、このアプローチが他のジェネレーターと競争力があることを証明しています。