Goブログ
Go 1.22における安全な乱数生成
コンピュータはランダムではありません。むしろ、ハードウェア設計者は、コンピュータが毎回同じ方法でプログラムを実行するように非常に努力しています。そのため、プログラムが乱数を必要とする場合は、特別な努力が必要です。従来、コンピュータ科学者やプログラミング言語は、統計的乱数と暗号学的乱数の2種類の乱数を区別してきました。Goでは、これらはそれぞれmath/randとcrypto/randによって提供されます。 この記事では、Go 1.22がmath/rand（および、以前の記事で述べたようにmath/rand/v2）で暗号学的乱数ソースを使用することで、この2つをどのように近づけたかについて説明します。その結果、乱数の品質が向上し、開発者が誤ってcrypto/randの代わりにmath/randを使用した場合の被害が大幅に減少します。
Go 1.22で行われたことを説明する前に、統計的乱数と暗号学的乱数を詳しく見てみましょう。
統計的乱数
基本的な統計テストに合格する乱数は、通常、シミュレーション、サンプリング、数値解析、非暗号学的ランダムアルゴリズム、ランダムテスト、入力のシャッフル、ランダムな指数バックオフなどのユースケースに適しています。非常に基本的で計算しやすい数式は、これらのユースケースには十分に機能することがわかっています。しかし、これらの方法は非常に単純であるため、使用されているアルゴリズムを知っている観測者は、通常、十分な値を見た後にシーケンスの残りを予測できます。
基本的にすべてのプログラミング環境は、Cを介してResearch Unix Third Edition (V3)まで遡る統計的乱数を生成するメカニズムを提供しています。これは、srandとrandという2つの関数を追加しました。マニュアルページには、次のような注記が含まれていました。
警告：このルーチンの作者は、長年乱数ジェネレータを書いてきましたが、動作するものを書いたことが知られていません。
この注記は partly ジョークでしたが、このようなジェネレータが本質的にランダムではないことを認めたものでもありました。
ジェネレータのソースコードは、それがどれほど些細なものであるかを明確に示しています。PDP-11アセンブリから最新のCに変換すると、次のようになります。
uint16 ranx;
void
srand(uint16 seed)
{
ranx = seed;
}
int16
rand(void)
{
ranx = 13077*ranx + 6925;
return ranx & ~0x8000;
}
srandを呼び出すと、ジェネレータに単一の整数シードがシードされ、randはジェネレータから次の数を返します。return文のANDは、結果が正になるように符号ビットをクリアします。
この関数は、線形合同法ジェネレータ（LCG）と呼ばれる一般的なクラスのインスタンスです。これは、クヌースが「The Art of Computer Programming」第2巻3.2.1項で分析しています。LCGの主な利点は、Unixの実装が15ビット出力に対して行ったように、繰り返される前にすべての可能な出力値を1回出力するように定数を選択できることです。しかし、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論文「乱数ジェネレータ：良いものは見つかりにくい」を、より長い分析については、クヌース第2巻の第1章を参照してください。）
これらの既知の問題があっても、srand関数とrand関数は最初のC標準に含まれており、それ以降、基本的にすべての言語に同等の機能が含まれています。LCGはかつて支配的な実装戦略でしたが、いくつかの重要な欠点により人気が低下しています。残っている重要な用途の1つは、java.util.Randomで、java.lang.Math.randomを支えています。
上記の実装からわかるもう1つのことは、内部状態がrandの結果によって完全に公開されていることです。アルゴリズムを知っていて、1つの結果を見ている観測者は、将来のすべての結果を簡単に計算できます。独自のvecに入力してからアルゴリズムを実行することで、すべての将来の値を予測できます。また、アルゴリズムを逆方向に実行する（タップをフィードから減算し、スライスを左にシフトする）ことで、以前のすべての値を復元することもできます。
完全なデモンストレーションとして、擬似乱数認証トークンを生成する安全でないプログラムと、以前のトークンシーケンスから次のトークンを予測するコードを示します。ご覧のとおり、Go 1ジェネレータはセキュリティをまったく提供していません（意図もされていません）。生成される数値の品質は、vecの初期設定にも依存します。
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を生成し、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：乱数生成のためのシンプルで高速、省スペースで統計的に優れたアルゴリズムファミリ」で発表されました。論文の徹底的な分析により、ジェネレータがどれほど些細なものであるかを一見して見落とす可能性があります。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ビットの乗算と加算です。return文では、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と呼ばれます。
提案の議論中に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-DXSM（「double xorshift multiply」の略）を使用したPCGを呼び出します。Numpyもこの形式のPCGを使用しています。
PCGは各値の生成により多くの計算を使用しますが、使用する状態は大幅に少なくなります。607ではなく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など、ChaCha20と呼ばれる20ラウンド形式で広く使用されています。Jean-Philippe Aumassonの論文「Too Much Crypto」は、8ラウンド形式のChaCha8も安全であると説得力を持って主張しています（そして、約2.5倍高速です）。ChaCha8RandのコアとしてChaCha8を使用しました。
ChaCha8を含むほとんどのストリーム暗号は、鍵とブロック番号が与えられ、固定サイズのブロックの見かけの乱数データを生成する関数を定義することによって機能します。これらの目標とする暗号標準（通常は満たされます）は、この出力が、指数関数的にコストのかかるブルートフォース検索がない場合、実際の乱数データと区別できないようにすることです。メッセージは、入力データの連続するブロックを連続してランダムに生成されたブロックとXORすることによって暗号化または復号化されます。ChaCha8をrand.Sourceとして使用するために、生成されたブロックを直接使用し、入力データとXORしません（これは、すべてのゼロを暗号化または復号化することと同じです）。
ChaCha8Randを乱数生成に適したものにするために、いくつかの詳細を変更しました。簡単に説明すると
- ChaCha8Randは、ChaCha8キーとして使用される32バイトのシードを受け取ります。
- ChaCha8は64バイトのブロックを生成し、計算ではブロックを16個の
uint32として扱います。一般的な実装では、SIMD命令を使用して、それぞれ4つのuint32の16個のベクトルレジスタで4つのブロックを一度に計算します。これにより、入力データとXORするためにシャッフル解除する必要がある4つのインターリーブされたブロックが生成されます。ChaCha8Randは、インターリーブされたブロックがランダムデータストリームであると定義し、シャッフル解除のコストを削減します。（セキュリティの観点からは、これは標準のChaCha8に続いて再シャッフルと見なすことができます。） - ChaCha8は、ブロック内の各
uint32に特定の値を追加することによってブロックを終了します。値の半分はキーマテリアルであり、残りの半分は既知の定数です。ChaCha8Randは、既知の定数が再度追加されないことを定義し、最終的な追加の半分を削除します。（セキュリティの観点からは、これは標準のChaCha8に続いて既知の定数を減算することと見なすことができます。） - 生成された16ブロックごとに、ChaCha8Randはブロックの最後の32バイトを自身のために取得し、それらを次の16ブロックのキーにします。これは一種の前方秘匿性を提供します。ジェネレーターのメモリ状態全体を回復する攻撃によってシステムが侵害された場合、最後のキーの再生成以降に生成された値のみを回復できます。過去はアクセスできません。これまでに定義されたChaCha8Randは一度に4つのブロックを生成する必要がありますが、256ビットまたは512ビットのベクトルを使用してより高速な実装の可能性を開いたままにするために、このキーローテーションを16ブロックごとに行うことを選択しました。これにより、一度に8または16ブロックを生成できます。
私たちは、ChaCha8RandのC2SP仕様とテストケースを作成して公開しました。これにより、他の実装は、特定のシードに対してGo実装との再現性を共有できます。
Goランタイムは現在、コアごとにChaCha8Rand状態（300バイト）を維持し、オペレーティングシステムが提供する暗号論的乱数でシードされるため、ロックの競合なしに乱数をすばやく生成できます。コアごとに300バイトを専用にするのは高価に聞こえるかもしれませんが、16コアシステムでは、単一の共有Go 1ジェネレーター状態（4,872バイト）を格納するのと同じです。速度はメモリに見合う価値があります。このコアごとのChaCha8Randジェネレーターは、Go標準ライブラリの3つの異なる場所で現在使用されています
-
rand.Float64やrand.Nなどのmath/rand/v2パッケージ関数は、常にChaCha8Randを使用します。 -
rand.Float64やrand.Intnなどのmath/randパッケージ関数は、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の両方と同じ程度の範囲にあります。次のグラフは、さまざまなハードウェアで、2つの操作を実行する3つのジェネレーターのパフォーマンスを比較しています。ランダムストリームの次の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)」がmath/randのアルゴリズムを使用して、ランダムなint64を[0, 1000)の範囲の値に縮小しており、そのアルゴリズムが2つの64ビット整数除算演算を実行するためです。対照的に、「PCG: N(1000)」と「ChaCha8: N(1000)」は、より高速なmath/rand/v2アルゴリズムを使用しており、ほとんどの場合、除算を回避します。64ビット除算の削除は、32ビット実行とAmpereでは、アルゴリズムの変更よりも支配的です。
全体として、ChaCha8RandはGo 1ジェネレーターよりも低速ですが、2倍以上低速になることはなく、一般的なサーバーでは、その差は3nsを超えることはありません。この違いによってボトルネックとなるプログラムはほとんどなく、多くのプログラムはセキュリティの向上を享受できます。
結論
Go 1.22は、コードを変更することなく、プログラムのセキュリティを向上させます。これは、crypto/randの代わりにmath/randを誤って使用するというよくある間違いを特定し、math/randを強化することで実現しました。これは、デフォルトでプログラムを安全に保つためのGoの継続的な取り組みにおける小さな一歩です。
この種の間違いはGo特有のものではありません。たとえば、npmのkeypairパッケージは、Web Crypto APIを使用してRSAキーペアを生成しようとしますが、使用できない場合は、JavaScriptのMath.randomにフォールバックします。これは、決して孤立したケースではなく、システムのセキュリティは、開発者が間違いを犯さないことに依存することはできません。代わりに、最終的にはすべてのプログラミング言語が、「数学的」なランダム性のために、暗号的に強力な擬似乱数ジェネレーターに移行し、この種の間違いをなくすか、少なくともその爆発半径を大幅に縮小することを願っています。Go 1.22のChaCha8Rand実装は、このアプローチが他のジェネレーターと競合することを証明しています。