Go1.22からの疑似乱数生成器について/go-122-pseudo-random-generator

2024/03/18(月) Go 1.22 リリースパーティ にて発表した内容です
https://gocon.connpass.com/event/310606/

Transcript

1. Go 1.22 からの疑似乱数生成器について 2024/03/18(月) Go 1.22 リリースパーティ
2. 自己紹介 @convto 株式会社LayerX所属 レイヤ低めの技術などに興味がありま す (読みはこんぶとです)
3. contents - リリースノートななめ読み - ChaCha8 概要 - ChaCha8 が runtime に実装された - ChaCha8 が math/rand 規定アルゴリズ ムに - PCG-DXSM が実装された - おまけ: 規定アルゴリズムが ChaCha8 に決まった議論おさらい - まとめ: これからの math/rand の使い方
4. リリースノートななめ読み
5. math/rand/v2 がでて、変更てんこ盛り https://tip.golang.org/doc/go1.22#math_rand_v2
6. math/rand/v2 がでて、変更てんこ盛り https://tip.golang.org/doc/go1.22#math_rand_v2 今日お話するのはこのへんです
7. 新しい疑似乱数生成器が入った - ChaCha8 と PCG というやつが入った - ChaCha8 は暗号学的な強度を持っていて、PCGと実行コストが同程度 - ChaCha8 が math/rand/v2 トップレベルや runtime, math/rand の seed なしの トップレベルで採用
8. 新しい疑似乱数生成器が入った - ChaCha8 と PCG というやつが入った - ChaCha8 は暗号学的な強度を持っていて、PCGと実行コストが同程度 - ChaCha8 が math/rand/v2 トップレベルや runtime, math/rand の seed なしの トップレベルで採用
9. 新しい疑似乱数生成器が入った - ChaCha8 と PCG というやつが入った - ChaCha8 は暗号学的な強度を持っていて、PCGと実行コストが同程度 - ChaCha8 が math/rand/v2 トップレベルや runtime, math/rand の seed なしの トップレベルで採用 ChaCha8, PCG について概要などを触 れつつ、どのように導入されたか整理し ていきます
10. ChaCha8 概要
11. ChaCha8 って？ - ストリーム暗号の一種 - 暗号学的な強度があるとされている - 実行コストが軽く、ハードウェアサポートがなくても結構はやい - めちゃめちゃ簡素な説明をすると、入力や定数から内部状態をつくり、それをラウン ド関数でかき回して疑似乱数を作り、XORとることで暗号化/復号をする - 内部でかき回すラウンド関数の数によって ChaCha N みたいな表現をする - 詳細に立ち入りすぎると時間が足りなくなるので触りだけ紹介
12. ChaCha 概要 - 入力や定数からなる 4byte * 16 の内 部状態を持つ - これをめっちゃかき回す - 4byte * 4 の単位でかき回す関数 Quarter Round が定義されてるの で、それをぶん回しまくる - 内部カウンタがあるので、カウントアッ プしながら疑似乱数列 stream を吐く
13. ChaCha しくみ概要 - 入力や定数からなる 4byte * 16 の内 部状態を持つ - これをめっちゃかき回す - 4byte * 4 の単位でかき回す関数 Quarter Round が定義されてるの で、それをぶん回しまくる - 内部カウンタがあるので、カウントアッ プしながら疑似乱数列 stream を吐く Go 1.22 ではこの部分を 疑似乱数生成器として採用
14. ChaCha かき回し方 - Quarter Round という関数を内部状 態にかけて回る - column 方向に4回(1ラウンド)、 diagonal 方向に4回(1ラウンド)、計2 ラウンドで1セット - ChaCha8 はこれらを4回繰り返す(計 8ラウンド) colmun diagonal
15. ChaCha Quarter Round 関数 - Quarter Round という名前の関数が 定義されてる - ようは 4byte * 4 の入力を受け取っ て、bit演算とかシフトを使って値をめ ちゃめちゃかき回す処理 - 良さげな図を見つけたのでペタリ https://en.wikipedia.org/wiki/Salsa20#ChaCha _variant
16. ChaCha8 が runtime に実装された
17. internal/chacha8rand 実装 - ChaCha8 自体の実装は internal/chacha8rand にある - 各アーキテクチャ向けに最適化し てる部分もあるが、先ほど話した基 本的な操作をしていることは確認で きる - 参考程度に操作がわかりやすい実 装を貼った。column round & diagonal round をこなして状態を 混ぜてるのがわかる https://cs.opensource.google/go/go/+/refs/tags/go1.22 .1:src/internal/chacha8rand/chacha8_generic.go;l=17 4-185
18. runtime 実装 - runtime rand としてよしなに使わ れている - スレッドごとに `chacha8.State` が 初期化されてるので、そこから値を 読み出している - 排他制御もしてる https://cs.opensource.google/go/go/+/refs/tags/go1.22 .1:src/runtime/rand.go;l=125-147
19. ChaCha8 が math/rand 規定アルゴリズムに
20. math/rand/v2 - linkname ディレクティブでさっき紹 介した runtime.rand が使われてる - math/rand/v2 では Source interface に破壊的変更が入ってい て `Uint64()` だけでよくなってる - runtime.rand は排他制御してるの で気にせず使ってOK https://cs.opensource.google/go/go/+/refs/tags/go1.22 .1:src/math/rand/v2/rand.go;l=247-263
21. math/rand/v2 注意 - 普通に NewChaCha8() すると internal 実装が使われるんです が、Uint64() とかを見たけど排他 制御とか特にしてなさそうに見える ので注意。自分でやる必要がある - とくに理由がなければトップレベル のものを使いまわせばよさそう https://cs.opensource.google/go/go/+/refs/tags/go1.22 .1:src/math/rand/v2/chacha8.go;l=7-20
22. math/rand - 基本的には似ていて、 runtime.randを被せている - runtime.rand は Seed() に類する 実装がないのでその考慮が必要 - 詳細は割愛するが `randautoseed=0` とするか `math.Seed()` が呼び出されると runtime ChaCha8 ではない別の randSource に差し替えるような実 装が入っている https://cs.opensource.google/go/go/+/refs/tags/go1.22 .1:src/math/rand/rand.go;l=349-369
23. PCG-DXSM が実装された
24. PCG概要 - LCG(線形合同生成器) という疑似乱数生成器と置換関数を組み合わせることで、 統計学的な性質を改善したもの - たとえば、LCGは内部で mod を取るが入力として渡す法が2べきだと下位bitの周 期が短くなる既知の性質があったが、そのあたりも改善している - 内部状態や置換処理によっていくつかのファミリが定義されている
25. PCG-DXSM 概要 - PCGファミリの一つ - 2019年生まれなのでかなり若い - `double xorshift multiply` の略らしい - 厳密な spec 定義が見当たらなかった？ので知ってる方いたら教えてください。今 回はcppの実装とかGoの実装とかを見てきました
26. PCG 導入 proposal で論文著者の O'Neill 氏もコメントしてい る https://github.com/golang/go/issues/21835#issuecomment-739065688
27. Go の PCG-DXSM 実装 - 基本的にはLCGを進めたあといろ いろかき回してるよう(LCGも定数 カウンタを使っていたりして多少毛 色が違う感じがある) - 以下の操作をしてる - hi 下位半分でXOR - 定数で mul - hi 上位1/4でXOR - hi と下位1bitをたてた lo で mul https://cs.opensource.google/go/go/+/refs/tags/go1.22 .1:src/math/rand/v2/pcg.go;l=100-121;bpv=0;bpt=0
28. おまけ: 規定アルゴリズムが ChaCha8 に 決まった議論おさらい
29. proposal での議論で言及されていた https://github.com/golang/go/issues/61716#issuecomment-1668850572
30. ChaCha8 にした背景 - もともと使ってた lockedSource は PCG, ChaCha8 と比較して相対的に堅牢性が 低い - 実装した PCG と ChaCha8 の実行コストはだいたい同じ(とプロポーザルで言及さ れていた) - だったらChaCha8のほうが暗号学的強度が見込まれるのでより望ましいだろう！ - (余談だけど、このスレをおうと rsc が「crypto/rand との誤用を避けるために math/rand/v2 で Reader けしたけど、今後も ChaCha8 みたいな暗号学的強度が あるものを top level で採用し続けるならそのうち復活させてもいいかもなぁ」みた いなこともぼやいていて面白い)
31. まとめ: これからの math/rand の使い方
32. これからの math/rand ってどう使えばいい？ - math/rand/v2 利用を推奨。Source interface が整理されたり、危険な利用をされう る実装が消えたりいろいろ良い変更が入っている - Read が消えたりとか - top level の処理では ChaCha8 使ってたり排他制御も考慮されている。特別な ユースケースでなければ top level のものを単に利用するだけでよい - math/rand では top level `Seed()` を呼ぶと randSource が切り替わる。理由がな ければ top level `Seed()` は使わないようにしよう
33. これからの math/rand ってどう使えばいい？ - v2 で seed を固定化したいときは top level じゃなくて自前で `NewChaCha8()` や `NewPCG()` したものを使えばいい！ - ↑するときは排他制御を自前で作る必要がある(はず)なので注意
34. ご清聴ありがとうございました