Go 博客

Go 1.22 中的安全随机数

Russ Cox 和 Filippo Valsorda
2024 年 5 月 2 日

计算机不是随机的。相反，硬件设计师非常努力地确保计算机每次以相同的方式运行每个程序。因此，当程序确实需要随机数时，这需要额外的努力。传统上，计算机科学家和编程语言将两种不同的随机数区分开来：统计随机数和加密随机数。在 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 在计算机程序设计艺术，第 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 论文“随机数生成器：好的很难找”以获得简短的分析和 Knuth 第 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 中使用的生成器是所谓 线性反馈移位寄存器 的一个实例。该算法基于 George Marsaglia 的一个想法，由 Don Mitchell 和 Jim Reeds 进行了调整，并由 Ken Thompson 为 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，我们希望提供一个更现代的统计随机生成器，并选择了 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 位乘法和加法。在返回语句中，scramble 函数将 128 位状态缩减为 64 位状态。原始的 PCG 使用（同样使用假设的 uint128 类型）

func scramble(x uint128) uint64 {
    return bits.RotateLeft(uint64(x>>64) ^ uint64(x), -int(x>>122))
}

这段代码将 128 位状态的两个部分进行异或运算，然后根据状态的前 6 位旋转结果。此版本称为 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 称为 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 被广泛用于 20 轮形式的 ChaCha20，包括 TLS 和 SSH。Jean-Philippe Aumasson 的论文“Too Much Crypto” 有力地论证了 8 轮形式的 ChaCha8 也是安全的（并且速度大约快 2.5 倍）。我们使用 ChaCha8 作为 ChaCha8Rand 的核心。

大多数流密码，包括 ChaCha8，的工作原理是定义一个函数，该函数接受一个密钥和一个块号，并生成固定大小的明显随机数据块。它们的目标（通常也能实现）的密码学标准是，在没有某种指数级代价的暴力搜索的情况下，此输出与实际随机数据无法区分。消息通过将输入数据的连续块与连续生成的随机块进行异或运算来进行加密或解密。为了将 ChaCha8 用作 rand.Source，我们直接使用生成的块，而不是将它们与输入数据进行异或运算（这相当于对所有零进行加密或解密）。

我们修改了一些细节，使 ChaCha8Rand 更适合生成随机数。简要地说

• ChaCha8Rand 接受一个 32 字节的种子，用作 ChaCha8 密钥。
• ChaCha8 生成 64 字节的块，计算将一个块视为 16 个 uint32。常见的实现是使用 SIMD 指令 在 16 个向量寄存器（每个寄存器包含 4 个 uint32）上一次计算 4 个块。这将产生 4 个交错块，必须对其进行重新排序才能与输入数据进行异或运算。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 标准库中的三个不同位置使用。

1. math/rand/v2 包中的函数，比如 rand.Float64 和 rand.N，始终使用 ChaCha8Rand。

2. math/rand 包中的函数，比如 rand.Float64 和 rand.Intn，在 rand.Seed 未被调用时使用 ChaCha8Rand。在 math/rand 中应用 ChaCha8Rand 提高了程序的安全，即使在它们更新到 math/rand/v2 之前也是如此，前提是它们没有调用 rand.Seed。（如果调用了 rand.Seed，则实现需要回退到 Go 1 生成器以确保兼容性。）

3. 运行时使用 ChaCha8Rand 为每个新映射选择散列种子，而不是它之前使用的安全性较低的 基于 wyrand 的生成器。需要随机种子，因为如果攻击者知道映射实现使用的特定散列函数，他们就可以准备输入，将映射驱动到二次行为（参见 Crosby 和 Wallach 的“Denial of Service via Algorithmic Complexity Attacks”）。使用每个映射的种子，而不是为所有映射使用一个全局种子，还可以避免 其他退化行为。目前还不完全清楚映射是否需要密码学随机种子，但也不清楚它们是否不需要。这似乎是谨慎的做法，并且切换起来很容易。

需要自己的 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 位模式下运行。在这种情况下，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 生成器速度更慢，但永远不会慢两倍以上，在典型的服务器上，差异永远不会超过 3ns。很少有程序会受到这种差异的瓶颈影响，而许多程序将享受改进的安全性。

结论

Go 1.22 提高了程序的安全性，无需任何代码更改。我们通过识别意外使用 `math/rand` 而不是 `crypto/rand` 的常见错误，然后加强了 `math/rand` 来实现这一点。这是 Go 在持续的旅程中迈出的一小步，旨在默认情况下保持程序安全。

这类错误并不局限于 Go。例如，npm 的 `keypair` 包试图使用 Web Crypto API 生成 RSA 密钥对，但如果不可用，它会回退到 JavaScript 的 `Math.random`。这绝非个例，我们系统的安全性不能依赖于开发人员不犯错误。相反，我们希望最终所有编程语言都将转向密码学强度高的伪随机生成器，即使是用于“数学”随机性，从而消除这种错误，或者至少大大减少其影响范围。Go 1.22 的 ChaCha8Rand 实现证明这种方法与其他生成器具有竞争力。