The Go Blog

Go 1.22 における安全な乱数

Russ Cox と Filippo Valsorda
2024年5月2日

コンピューターはランダムではありません。それどころか、ハードウェア設計者は、コンピューターがあらゆるプログラムを常に同じ方法で実行することを確認するために、非常に熱心に作業しています。したがって、プログラムが乱数を必要とする場合、それは特別な努力を要します。伝統的に、コンピューター科学者とプログラミング言語は、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) に遡る統計的乱数生成メカニズムを提供しており、V3 は srand と rand のペア関数を追加しました。マニュアルページには次の注意書きが含まれていました。

警告   このルーチンの作者は長年乱数ジェネレーターを書いてきましたが、機能するものを作ったことが知られていません。

この注意書きは一部冗談でしたが、そのようなジェネレーターが 本質的にランダムではない ことの認識でもありました。

ジェネレーターのソースコードは、それがどれほど些細なものであるかを明確にしています。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) と呼ばれる一般的なクラスの ジェネレーター の一例であり、Knuth が『The Art of Computer Programming』第2巻3.2.1節で分析しています。LCG の主な利点は、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ビットシーケンスは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 第2巻の最初の章を参照してください。)

これらの既知の問題にもかかわらず、srand と rand 関数は最初の C 標準に含まれ、それ以来実質的にすべての言語に同等の機能が含まれていました。LCG はかつて主要な実装戦略でしたが、いくつかの重要な欠点のために人気が衰えました。残っている重要な用途の1つは、java.util.Random であり、これは java.lang.Math.random を動かしています。

上記の implemention からわかるもう1つのことは、内部状態が rand の結果によって完全に露出されていることです。アルゴリズムを知っていて、単一の結果を見た観察者は、将来のすべての結果を簡単に計算できます。公開されるいくつかの乱数値と秘密にしなければならないいくつかの乱数値を計算するサーバーを実行している場合、この種のジェネレーターを使用すると悲惨なことになります。秘密は秘密ではなくなります。

より現代的な乱数ジェネレーターは、オリジナルの 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 を生成し、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回のストアです。

残念ながら、ジェネレーターは内部状態ベクターからスライス要素を直接返すため、ジェネレーターから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ビットの乗算と加算です。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 を、"double xorshift multiply" の略で PCG-DXSM と呼んでいます。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 として計算を扱います。一般的な実装では、16個のベクトルレジスタにそれぞれ4個の uint32 を使用して、SIMD命令によって一度に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つの異なる場所で使用されています。

  1. math/rand/v2 パッケージの関数、例えば rand.Float64 や rand.N は、常に ChaCha8Rand を使用します。

  2. math/rand パッケージの関数、例えば rand.Float64 や rand.Intn は、rand.Seed が呼び出されていない場合、ChaCha8Rand を使用します。math/rand に ChaCha8Rand を適用することで、rand.Seed を呼び出していないプログラムであれば、math/rand/v2 に更新する前でもセキュリティが向上します。（rand.Seed が呼び出された場合、互換性のために Go 1 ジェネレーターにフォールバックする必要があります。）

  3. ランタイムは、以前使用していた安全性の低い wyrand ベースのジェネレーター の代わりに ChaCha8Rand を使用して、新しい各マップのハッシュシードを選択します。乱数シードは、攻撃者がマップの実装で使用される特定のハッシュ関数を知っている場合、マップを二次的な振る舞い（Crosby と Wallach の「アルゴリズム的複雑性攻撃によるサービス拒否」を参照）に導く入力を準備できるため、必要です。すべてのマップに単一のグローバルシードを使用する代わりに、マップごとにシードを使用することで、他の退化した振る舞い も回避されます。マップが暗号論的乱数シードを必要とするかどうかは厳密には不明ですが、必要としないとも言えません。慎重であると思われ、切り替えるのは些細なことでした。

独自の 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 を生成できます。衝突を心配する必要はありません。

もう1つの例として、受信したリクエストをバックエンドサーバーにランダムに割り当てるフロントエンドサーバーでの負荷分散を考えてみましょう。攻撃者が割り当てを観察し、それらを生成する予測可能なアルゴリズムを知っていれば、ほとんどが安価なリクエストのストリームを送信し、すべての高価なリクエストが単一のバックエンドサーバーに着地するように手配できます。これは、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 アルゴリズム を使用しています。64ビット除算の削除は、32ビット実行と Ampere ではアルゴリズム変更を支配します。

全体として、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 実装は、このアプローチが他のジェネレーターと競合できることを証明しています。

次の記事：Go 1.23 がリリースされました
前の記事：math/rand/v2 で Go 標準ライブラリを進化させる
ブログインデックス

go.dev は、サービスの品質を提供および向上させ、トラフィックを分析するために、Google の Cookie を使用しています。詳細はこちらをご覧ください。