Go 部落格

Go 1.22 中的安全隨機性

Russ Cox 和 Filippo Valsorda
2024 年 5 月 2 日

計算機本身並不是隨機的。相反，硬體設計師努力確保計算機每次都以相同的方式執行每個程式。因此，當程式確實需要隨機數時，這需要額外的努力。傳統上，計算機科學家和程式語言區分兩種不同型別的隨機數：統計隨機性（statistical randomness）和加密隨機性（cryptographic randomness）。在 Go 中，它們分別由 math/rand 和 crypto/rand 提供。本文介紹 Go 1.22 如何透過在 math/rand（以及 math/rand/v2，正如我們在上一篇文章中提到的）中使用加密隨機數源，將這兩者拉得更近。結果是更好的隨機性，並且當開發者意外地使用 math/rand 而不是 crypto/rand 時，造成的損害大大減少。

在我們解釋 Go 1.22 的改進之前，讓我們先仔細看看統計隨機性和加密隨機性之間的區別。

統計隨機性

透過基本統計測試的隨機數通常適用於模擬、取樣、數值分析、非密碼學隨機演算法、隨機測試、打亂輸入以及隨機指數退避等用例。非常基礎、易於計算的數學公式已被證明對於這些用例足夠有效。然而，由於方法如此簡單，知道正在使用何種演算法的觀察者在看到足夠多的值後，通常可以預測出其餘的序列。

幾乎所有程式設計環境都提供了生成統計隨機數的機制，這些機制都可以追溯到透過 C 語言實現的 Research Unix 第三版 (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 返回生成器產生的下一個數。返回語句中的 AND 操作清除符號位，以確保結果是正數。

此函式是通用類別的例項線性同餘生成器 (LCG)，Knuth 在計算機程式設計藝術第二卷第 3.2.1 節中對其進行了分析。LCG 的主要優點在於可以選擇常數，使得在重複之前，它們會發出每個可能的輸出值一次，就像 Unix 實現對於 15 位輸出所做的那樣。然而，LCG 的一個嚴重問題是狀態的高位完全不影響低位，因此序列截斷到 k 位時必然以較小的週期重複。最低位必須交替出現：0, 1, 0, 1, 0, 1。最低兩位必須向上或向下計數：0, 1, 2, 3, 0, 1, 2, 3，或者 0, 3, 2, 1, 0, 3, 2, 1。有四種可能的三位序列；原始的 Unix 實現重複出現 0, 5, 6, 3, 4, 1, 2, 7。（這些問題可以透過對值取素數模來避免，但這在當時會非常昂貴。參見 S. K. Park 和 K. W. Miller 1988 年發表在 CACM 上的論文“隨機數生成器：好的很難找到”進行簡要分析，或參見 Knuth 第二卷第一章進行更詳細的分析。）

即使存在這些已知問題，srand 和 rand 函式仍被包含在第一個 C 標準中，此後幾乎所有語言都包含了等效功能。LCGs 曾是主要的實現策略，儘管由於一些重要的缺點，它們的受歡迎程度有所下降。一個重要的現有用途是 java.util.Random，它為 java.lang.Math.random 提供支援。

從上面的實現中還可以看到，內部狀態完全由 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。在該切片中，有兩個特殊的元素：vec[606]（最後一個元素）被稱為“抽頭”（tap），而 vec[334] 被稱為“反饋”（feed）。為了生成下一個隨機數，生成器將抽頭和反饋相加產生一個值 x，將 x 儲存回反饋位置，將整個切片向右移動一位（抽頭移到 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)
}

生成下一個數字非常廉價：兩次減法、兩次條件加法、兩次載入、一次加法、一次儲存。

不幸的是，由於該生成器直接從其內部狀態向量中返回一個切片元素，讀取生成器的 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 位狀態的兩半進行異或操作，然後根據狀態的高六位旋轉結果。這個版本被稱為 PCG-XSL-RR，意為“異或移位低位，右旋轉”。

根據 O’Neill 在提案討論中的建議，Go 的 PCG 使用了一種基於乘法的新混淆函式（scramble function），它可以更積極地混合位：

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 生成每個值需要更多的計算，但它使用的狀態顯著更少：只需要兩個 uint64，而不是 607 個。它對狀態的初始值也遠不那麼敏感，並且通過了許多其他生成器未能透過的統計測試。在很多方面，它是一個理想的統計生成器。

即便如此，PCG 仍然不是不可預測的。雖然用於準備結果的位混淆不像 LCG 和 Go 1 生成器那樣直接暴露狀態，但PCG-XSL-RR 仍然可以被逆轉，而且 PCG-DXSM 如果也可以被逆轉，也不會令人驚訝。對於秘密資料，我們需要不同的東西。

加密隨機性

加密隨機數實際上需要完全不可預測，即使觀察者知道它們是如何生成的，並且已經觀察到任意數量的先前生成的值。加密協議、金鑰、現代商業、線上隱私等方面的安全性都關鍵地依賴於對加密隨機性的訪問。

提供加密隨機性最終是作業系統的職責，作業系統可以從物理裝置收集真正的隨機性——滑鼠、鍵盤、磁碟和網路的時序，以及最近的由 CPU 本身直接測量的電噪聲。一旦作業系統收集到足夠量的隨機性——例如至少 256 位——它就可以使用加密雜湊或加密演算法將該種子拉伸成任意長的隨機數序列。（實際上，作業系統也一直在不斷收集新的隨機性並將其新增到序列中。）

確切的作業系統介面隨時間推移而演變。十年前，大多數系統提供一個名為 /dev/random 或類似的裝置檔案。今天，認識到隨機性的基礎地位，作業系統轉而提供直接的系統呼叫。（這使得程式即使與檔案系統隔離，也能讀取隨機性。）在 Go 中，crypto/rand 包抽象了這些細節，在所有作業系統上提供相同的介面：rand.Read。

每次需要一個 uint64 時都讓 math/rand 向作業系統請求隨機性是不實際的。但我們可以使用密碼學技術來定義一個程序內隨機生成器，該生成器在 LCGs、Go 1 生成器乃至 PCG 的基礎上有所改進。

ChaCha8Rand 生成器

我們的新生成器，為了規範目的我們沒有創意地命名為 ChaCha8Rand，並在 math/rand/v2 中實現為 rand.ChaCha8，是 Daniel J. Bernstein 的ChaCha 流密碼的輕微修改版本。ChaCha 的 20 輪形式 ChaCha20 被廣泛使用，包括在 TLS 和 SSH 中。Jean-Philippe Aumasson 的論文“加密過多”有力地論證了 8 輪形式的 ChaCha8 也是安全的（並且速度大約快 2.5 倍）。我們使用 ChaCha8 作為 ChaCha8Rand 的核心。

大多數流密碼，包括 ChaCha8，透過定義一個函式來工作，該函式給定一個金鑰和一個塊號，生成固定大小的看似隨機的資料塊。這些密碼旨在達到的（並且通常能夠達到）的密碼學標準是，在不存在某種指數級昂貴的暴力搜尋的情況下，其輸出與實際隨機資料是不可區分的。加密或解密訊息是透過將連續的輸入資料塊與連續生成的隨機資料塊進行異或來實現的。要將 ChaCha8 用作 rand.Source，我們直接使用生成的塊，而不是將它們與輸入資料進行異或（這相當於對全零進行加密或解密）。

我們修改了一些細節，使 ChaCha8Rand 更適合生成隨機數。簡而言之：

ChaCha8Rand 接受一個 32 位元組的種子，用作 ChaCha8 的金鑰。
ChaCha8 生成 64 位元組的塊，計算時將一個塊視為 16 個 uint32。一種常見的實現方式是使用 16 個包含四個 uint32 的向量暫存器，透過SIMD 指令一次計算四個塊。這會生成四個交錯塊，需要進行解交錯才能與輸入資料進行異或。ChaCha8Rand 定義交錯塊就是隨機資料流，從而去除了分解交錯的成本。（出於安全目的，這可以視為標準 ChaCha8 後接一次重新排序。）
ChaCha8 透過將某些值新增到塊中的每個 uint32 來完成一個塊。其中一半是金鑰材料，另一半是已知常量。ChaCha8Rand 定義不再重新新增這些已知常量，從而去除了最終加法的一半。（出於安全目的，這可以視為標準 ChaCha8 後接減去已知常量。）
每生成第 16 個塊，ChaCha8Rand 會將其最後 32 位元組用作下一組 16 個塊的金鑰。這提供了一種前向保密性：如果系統因攻擊而洩露了生成器的整個記憶體狀態，則只能恢復自上次重新金鑰化以來生成的值。過去的資料是不可訪問的。迄今為止定義的 ChaCha8Rand 必須一次生成 4 個塊，但我們選擇每 16 個塊進行一次金鑰輪換，以便為使用 256 位或 512 位向量的更快實現留下可能性，這些實現一次可以生成 8 個或 16 個塊。

我們編寫併發布了 ChaCha8Rand 的C2SP 規範以及測試用例。這將使其他實現能夠在給定種子的情況下與 Go 實現共享可重複性。

Go 執行時現在維護一個每核心的 ChaCha8Rand 狀態（300 位元組），該狀態使用作業系統提供的加密隨機性進行初始化，以便可以快速生成隨機數而無需鎖競爭。為每個核心分配 300 位元組聽起來可能很昂貴，但在一個 16 核系統上，它與儲存單個共享的 Go 1 生成器狀態（4,872 位元組）大約相同。速度值得記憶體的開銷。這個每核心的 ChaCha8Rand 生成器現在在 Go 標準庫的三個不同地方使用：

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 生成器。）
執行時現在使用 ChaCha8Rand 為每個新對映選擇雜湊種子，而不是之前使用的安全性較低的基於 wyrand 的生成器。需要隨機種子是因為如果攻擊者知道對映實現使用的具體雜湊函式，他們可以準備輸入，導致映射出現二次行為（參見 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 不再是安全災難。

還有各種看似與“加密”無關，但仍然需要不可預測的隨機性的用例。透過使用 ChaCha8Rand 而非 Go 1 生成器，這些用例變得更加健壯。

例如，考慮生成一個隨機 UUID。由於 UUID 不是秘密的，使用 math/rand 似乎可以。但是，如果 math/rand 使用當前時間作為種子，那麼在不同計算機上同時執行它會生成相同的值，這使得它們不再是“全域性唯一”的。在只能以毫秒精度獲取當前時間的系統上，這種情況尤其可能發生。即使使用 Go 1.20 中引入的基於作業系統提供的熵的自動 seeding，Go 1 生成器的種子也僅是一個 63 位整數，因此一個在啟動時生成 UUID 的程式只能生成 2⁶³ 種可能的 UUID，並且在大約 2³¹ 個 UUID 後很可能發生衝突。使用 Go 1.22，新的 ChaCha8Rand 生成器使用 256 位熵作為種子，可以生成 2²⁵⁶ 種可能的首個 UUID。無需擔心衝突。

再舉一個例子，考慮前端伺服器中的負載均衡，它將接收到的請求隨機分配給後端伺服器。如果攻擊者能夠觀察到分配情況，並知道生成這些分配的可預測演算法，那麼攻擊者就可以傳送大量廉價請求，但安排所有昂貴的請求都落在同一個後端伺服器上。使用 Go 1 生成器，這是一個不太可能但合理的潛在問題。使用 Go 1.22，這完全不是問題。

在所有這些例子中，Go 1.22 已經消除或大大減少了安全問題。

效能

ChaCha8Rand 的安全性優勢確實帶來了一些小小的開銷，但其效能仍與 Go 1 生成器和 PCG 大致相當。以下圖表比較了這三種生成器在各種硬體上執行兩個操作的效能：“Uint64”基本操作返回隨機流中的下一個 uint64，而“N(1000)”高階操作返回範圍 [0, 1000) 內的隨機值。

“執行 32 位程式碼”圖表顯示了現代 64 位 x86 晶片執行使用 GOARCH=386 構建的程式碼，這意味著它們執行在 32 位模式下。在這種情況下，PCG 需要進行 128 位乘法，這使得它比 ChaCha8Rand 慢，而 ChaCha8Rand 只使用 32 位 SIMD 算術。實際的 32 位系統每年都變得越來越不重要，但 ChaCha8Rand 在這些系統上比 PCG 更快仍然很有趣。

在某些系統上，“Go 1: Uint64”比“PCG: Uint64”快，但“Go 1: N(1000)”比“PCG: N(1000)”慢。這是因為“Go 1: N(1000)”使用了 math/rand 的演算法將隨機 int64 縮減到 [0, 1000) 範圍內的值，該演算法進行了兩次 64 位整數除法運算。相比之下，“PCG: N(1000)”和“ChaCha8: N(1000)”使用了更快的 math/rand/v2 演算法，該演算法幾乎總是避免除法。消除 64 位除法對於 32 位執行和 Ampere 系統上的演算法改進起主導作用。

總的來說，ChaCha8Rand 比 Go 1 生成器慢，但最慢也只慢一倍以內，在典型的伺服器上，差異從未超過 3 納秒。很少有程式會因此而成為效能瓶頸，並且許多程式將受益於改進的安全性。

結論

Go 1.22 無需任何程式碼更改即可使您的程式更加安全。我們透過識別出開發者意外使用 math/rand 而非 crypto/rand 這一常見錯誤，然後增強了 math/rand 的能力。這是 Go 在持續努力使程式預設安全程序中的一小步。

這類錯誤並非 Go 所獨有。例如，npm 包 keypair 嘗試使用 Web Crypto API 生成 RSA 金鑰對，但如果這些 API 不可用，它會回退到 JavaScript 的 Math.random。這絕非孤立案例，我們系統的安全性不能依賴於開發者不犯錯誤。相反，我們希望最終所有程式語言都能轉向使用加密強度高的偽隨機生成器，即使是用於“數學”隨機性，從而消除這類錯誤，或者至少大大減小其影響範圍。Go 1.22 的ChaCha8Rand 實現證明了這種方法與其他生成器相比具有競爭力。

下一篇文章：Go 1.23 釋出了
上一篇文章：使用 math/rand/v2 演進 Go 標準庫
部落格索引