Go 部落格

Go 1.22 中的安全隨機性

Russ Cox 和 Filippo Valsorda
2024 年 2 月 2 日

電腦並不是隨機的。恰恰相反，硬體設計師努力確保電腦每次都能以相同的方式執行每個程式。因此，當某個程式需要隨機數字時，就需要額外花費功夫。傳統上，電腦科學家和程式語言將兩種不同類型的隨機數字做了區分：統計隨機性與密碼隨機性。在 Go 中，它們分別由 math/rand 和 crypto/rand 提供。這篇文章探討 Go 1.22 如何讓兩者更接近，方法是在 math/rand 中使用密碼隨機數字來源（以及在我們的 先前文章 中提到的 math/rand/v2）。結果是改善隨機性，且當開發人員不小心使用 math/rand 代替 crypto/rand 時，損害將大幅減少。

在說明 Go 1.22 的作為之前，先來深入探討統計隨機性與密碼隨機性的差異。

統計隨機性

通過基本統計檢定的隨機數通常適用於模擬、抽樣、數值分析、非密碼學隨機演算法、隨機測試、洗牌輸入和隨機指數遞增後退等使用案例。非常基本、易於計算的數學公式已經足以用於這些使用案例。但是，由於這些方法非常簡單，所以觀察者在看到足夠值後通常可以根據知道使用的演算法來預測其餘序列。

基本上，所有程式設計環境都提供一種用於產生統計隨機數的機制，可追溯到 UNIX 第三版 (V3) 的 C 語言，其中新增了一對函數：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) 的總類，克努斯在《電腦程式設計藝術》第 2 冊 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 論文「隨機數生成器：好用的很難找」，短篇分析見克努斯第 2 冊第一章，長篇分析見同冊。）

即使有這些已知的問題，srand 和 rand 函式仍包含在第一個 C 標準中，而且從那時起，幾乎每種語言都包含等效的功能。LCG 曾經是主要的實作策略，儘管由於幾個重要的缺點，它們已變得不那麼普遍。其中一個重要的持續用途是 java.util.Random，驅動了 java.lang.Math.random。

從以上的實作還可以看出，rand 的結果完全公開了內部狀態。如果觀察者知道演算法並看到單一結果，就能輕鬆算出所有未來的結果。如果你正在執行一個伺服器，計算一些公開的隨機值和必須保密的隨機值，使用這種生成器將會造成災難：秘密將不再是秘密。

較新的隨機生成器雖不像原始的 Unix 生成器那麼糟，但仍然無法完全預測。為了證明這點，我們接下來將探討 Go 1 中原始的 math/rand 生成器和我們在 math/rand/v2 中新增的 PCG 生成器。

Go 1 生成器

Go 1 的 math/rand 中使用的產生器是一個稱為 線性回授移位暫存器 的實體。演算法基於喬治·馬薩利亞的構想，由唐·米契爾和吉姆·瑞德調整，然後由肯·湯普森進一步自訂為 Plan 9 而後是 Go。它沒有官方名稱，因此本篇文章稱其為 Go 1 產生器。

Go 1 產生器的內部狀態是一個包含 607 個 uint64 的片段 vec。在該片段中，有兩個特殊元素：vec[606]，最後一個元素，稱為「抽頭」，而 vec[334] 稱為「回饋」。為產生下一個隨機數字，產生器會將抽頭和回饋相加，以產生一個值 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，我們希望提供一個更現代化的統計隨機產生器，並採用了梅莉莎·歐尼爾於 2014 年在論文「PCG：一組用於隨機數產生之簡單、快速、省空間且統計良好的演算法」中發表的 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 位元乘法和加法。在回傳陳述式中，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 使用一個新的混淆函數，以乘法為基礎，更積極混合理位元

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 使用此 Scrambler 對 PCG 進行呼叫，將其命名為 PCG-DXSM，意為「雙異或位移乘法」。Numpy 也使用此類型的 PCG。

儘管 PCG 使用更多運算來產生每個值，但其使用的狀態顯著減少：兩個 uint64，而非 607。它也對此狀態的初始值較不敏感，而且 通過許多其他產生器無法通過的統計測試。在許多方面，這是一個理想的統計產生器。

儘管如此，PCG 仍非無法預測。儘管混合理位元以準備結果的方式不會像 LCG 和 Go 1 產生器那樣直接揭示狀態，PCG-XSL-RR 仍可被逆轉，PCG-DXSM 也不令人意外。對於密碼，我們需要一些不同的東西。

密碼隨機性

密碼隨機數字 在實務上必須完全無法預測，即使是知道生成方式及觀察過任何數量先前生成值的人員。密碼協定的安全性、密鑰、現代商業、線上隱私等等，都極度依賴對密碼隨機性的存取。

提供密碼隨機性最終是作業系統的任務，而作業系統可以從實體裝置收集真正的隨機性，例如滑鼠、鍵盤、磁碟和網路的計時，以及最近 CPU 本身直接測量的電氣雜訊。一旦作業系統收集到大量的隨機性，例如至少 256 位元，它就可以使用密碼雜湊或加密演算法將此種子延伸為任意長度的隨機數字序列。（在實務上，作業系統也會持續收集並將新的隨機性新增至序列中。）

確切的操作系統介面隨著時間演變。十年前，大多數系統提供名為 /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 廣泛運用於一種稱為 ChaCha20 的 20 輪形式中，包含在 TLS 和 SSH 中。Jean-Philippe Aumasson 的論文「太多密碼」具說服力地主張 8 輪形式的 ChaCha8 也具有安全性（並且快了大約 2.5 倍）。我們將 ChaCha8 用作 ChaCha8Rand 的核心。

包含 ChaCha8 在內的大多數雜湊資訊，運作方式為定義一個函數，提供一個金鑰和一個區塊號碼，並產生一塊看來隨機且大小固定的資料。這些函數所追求（且通常達到的）密碼標準是，在沒有任何類型指數成本的暴力搜尋情況下，此輸出應該與實際的隨機資料無從區分。訊息的加密或解密方式為，將連續輸入資料區塊與連續產生隨機區塊進行 XOR 運算。若要使用 ChaCha8 作為 rand.Source，我們直接使用產生的區塊，而不是將它們與輸入資料進行 XOR 運算（這等同於對所有零進行加密或解密）。

我們更改了幾個細節，讓 ChaCha8Rand 更適合用於產生隨機數。簡單來說

• ChaCha8Rand 會取一個 32 位元組的種子，用作 ChaCha8 金鑰。
• ChaCha8 會產生 64 位元組的區塊，計算時將區塊視為 16 個 uint32。普遍的實作方式是在 16 個向量暫存器（每個暫存器有 4 個 uint32）上使用 SIMD 指令 一次運算四個區塊。這會產生四個交錯區塊，必須解開交錯後才能與輸入資料進行 XOR。ChaCha8Rand 定義交錯區塊為隨機資料串流，移除了解開交錯的成本。（出於安全性考量，這可以視為標準 ChaCha8，然後重新排列。）
• ChaCha8 會為區塊加上特定值以完成區塊，而區塊內的每個 uint32 都會加上這些值。一半的值是金鑰素材，而另一半是已知的常數。ChaCha8Rand 定義已知的常數不會重新加總，這樣移除了一半的最後加總。（出於安全性考量，這可以視為標準 ChaCha8，然後減掉已知的常數。）
• ChaCha8Rand 每產生 16 個區塊，就會取用區塊的最後 32 個位元組，用於當作後續 16 個區塊的金鑰。這提供了一種 前進憑證：如果系統遭攻擊而讓產生器的全部記憶體狀態外洩，只有從最後一次重新設定金鑰後產生的值會外洩。先前的資料不會外洩。到目前為止，定義的 ChaCha8Rand 一次必須產生 4 個區塊，但我們選擇每 16 個區塊執行一次金鑰輪換，以保留使用 256 位元或 512 位元向量更快實作的可能性（一次可以產生 8 或 16 個區塊）。

針對特定種子，我們撰寫並發布了 ChaCha8Rand 的 C2SP 規範 和測試案例。這將讓其他實作可以和 Go 實作重複使用。

Go 執行時期現在維護每個核心的 ChaCha8Rand 狀態（300 個位元組），種子使用作業系統提供的密碼學隨機數，這樣產生亂數時可以更快速且不產生鎖定爭用。每一個核心專門使用 300 個位元組聽起來感覺很昂貴，但在 16 核心的系統上，這大約等於儲存單一共享 Go 1 產生器狀態（4,872 個位元組）。速度彌補了記憶體的不足。目前，這個每個核心的 ChaCha8Rand 產生器用於 Go 標準函式庫的以下三個位置

1. math/rand/v2 套件函式，例如 rand.Float64 和 rand.N，永遠使用 ChaCha8Rand。

2. math/rand 套件函式，例如 rand.Float64 和 rand.Intn，在 rand.Seed 尚未呼叫時使用 ChaCha8Rand。即便沒有呼叫 rand.Seed，在 math/rand 中套用 ChaCha8Rand 也可以提升程式的安全性。只要確定沒有呼叫 rand.Seed 即可（如果呼叫 rand.Seed，實作必須回退到 Go 1 產生器以維持相容性）。

3. 執行期會在每個新的映射中使用 ChaCha8Rand 選擇雜湊種子，取代之前在安全層面較低 基於 wyrand 的產生器 所使用的安全層面較低 wyrand-based generator。需要隨機種子是因為如果攻擊者知道映射實作所使用的特定雜湊函式，他們可以準備輸入資料，讓映射產生二次行為（請參閱 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 中引進了使用作業系統提供的熵值自動建立種子，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 位於相近的範圍內。下列圖表比較了三個產生器在各種硬體上執行的效能，運行兩個操作：基本操作「 Uint64 」會傳回亂數串流中的下一個 uint64，而較高層級的操作「 N(1000) 」則會傳回範圍為 [0, 1000) 中的亂數值。

「執行 32 位元程式碼」圖表顯示現代 64 位元 x86 晶片執行以 GOARCH=386 撰寫的程式碼，表示它們在 32 位元模式下執行。在這種情況下，ChaCha8Rand 僅使用 32 位元 SIMD 運算，而 PCG 需要 128 位元乘法，讓它比 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) 範圍內的數值，而該演算法進行兩次 64 位元整數除法運算。相比之下，「PCG：N(1000)」和「ChaCha8：N(1000)」使用 更快的 math/rand/v2 演算法，幾乎總是避免除法運算。移除 64 位元除法運算主導了 32 位元執行和 Ampere 的演算法變更。

總括來說，ChaCha8Rand 比 Go 1 產生器慢，但從未慢過兩倍，且在典型伺服器上，差異從未超過 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 實作證明這種作法與其他產生器具有競爭力。