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 标准库
博客索引