CSPRNGs：如何正确生成随机数

并不是所有程序中的随机数都需要高度安全。例如，在决定晚餐吃什么时，编程语言提供的基本随机模块通常就足够了。然而，在生成敏感数据（如随机数和私钥）的情况下，随机性应该是不可预测的。可预测随机数据的出现绝不能发生，但不幸的是，偶尔还是会发生。

在2023年8月，与比特币开发工具包 Libbitcoin Explorer↗ 相关的随机性弱点被 Milk Sad↗ 披露，导致估计损失超过90万美元的加密资产。这引出了本文的基本问题：我们如何正确生成随机数？

软件中的随机数生成器

为了回答基本问题，我们首先需要理解不同类型的数字生成器。

就像抛Coin或掷骰子一样，计算机也可以使用各种来源（包括设备驱动程序和诸如网络数据包和鼠标移动等外部源）生成随机数。这些外部来源的多样性足以使预测随机数被认为是无法实现的，这种随机性被称为 真正的 随机性。

然而，计算机不能仅仅依赖外部来源来获取随机性。当在短时间内需要大量随机性时，来自外部来源的值可能变化不足以提供足够的熵。此外，从外部来源读取值可能会更慢。因此，当需要大量随机数时，一个常用的方法是从真正的随机性源获取一个短长度的种子，并使用该种子作为输入生成随机数。这被称为 伪随机数生成器 (PRNG)。

PRNG 和 真正随机数生成器 (TRNG) 的主要区别在于可重现性。使用 PRNG 时，序列是确定性的，这意味着如果种子相同，将重现相同的序列。相比之下，使用 TRNG 时，序列完全随机，无法重现。

然而，并非所有 PRNG 都是安全的。（虽然“安全”的含义可以接受为“不可预测”，我们将在 CSPRNG 部分讨论安全的正式含义。）

我们首先考虑一个简单的 32 位 PRNG，表示为 PRNG(s)=x0,x1,…，其中 x0=s 并且 xi=(axi−1+b)mod2^32，对于 i>0。

其中 s 表示种子，a 和 b 是固定常量。这个 PRNG 被称为 线性同余生成器 ↗（LCG），用于高效生成随机数。然而，一旦观察到 xi，序列中的所有其他元素 x{i+1}, x{i+2}, … 都可以被导出。此外，其周期最多仅限于 2^32，这是不足够的。减轻这些问题的一种方法是截断某些位。例如，Java 的随机数采用 48 位状态，而生成的每个数字是32个最高有效位。然而，这种截断仅微乎其微地改善其统计特性和安全性。给定多个捕获的元素，仍然很容易推导种子，并且序列可以被向前和向后任意长地预测。这个 Github 存储库↗ 是破解 Java 随机数的一个例子。

另一种 PRNG 被称为 梅森旋转器 ↗，在 Python 和 C++ 等语言中使用。梅森旋转器仍然依赖于相对简单的计算，但具有 2^19937 − 1 的长周期。尽管梅森旋转器相对于 LCG 提供了更好的安全性，但它仍然是可预测的。一旦给出 624 个连续的 32 位随机数，则可以重构内部状态，使得序列变得可预测。你可以参考这个 GitHub 存储库↗。

大多数编程语言提供的默认随机数生成函数优先考虑性能而非安全性。如果强大的安全性是一个优先事项，则必须使用密码安全的伪随机数生成器（CSPRNG）。

CSPRNG

CSPRNG 是一种 PRNG，因为其输出是与 TRNG 一样不可预测和没有偏见。因此，它以不可区分性来定义：如果 PRNG G 与 TRNG 无法区分，则称 G 是 CSPRNG。

为了理解其数学属性，让我们看看 Alice 和 Bob 之间进行的一场例子游戏。

1. Alice 生成一个序列，可能是生成自 TRNG 或由 PRNG G 生成，每种情况的概率均为 1/2。
2. Alice 将生成的序列提供给 Bob。
3. Bob 的目标是猜测该序列是来自 TRNG 还是 PRNG。如果 Bob 的猜测正确，他获胜；反之，则 Alice 获胜。

如果 Bob 随机猜测，那么他的胜率正好是 1/2。这个 1/2 的值可以视为基准。然而，如果 PRNG G 显示异常特性，那么 Bob 的优势可能会高于 1/2。例如，如果第一个元素总是被固定为一个奇数，那么 Bob 的策略就是，如果序列以奇数开始则回答 PRNG，否则回答 TRNG。当序列由 PRNG 生成时，Bob 的猜测总是正确的。但是，如果序列由 TRNG 生成时，Bob 的猜测正确的概率为 1/2。在这种情况下，Bob 的胜率为 (1/2)×1+(1/2)×(1/2)=3/4，较基准高出 1/4。换句话说，Bob 有 1/4 的优势。如果 G 是 CSPRNG，则该优势应被认为是微不足道的。当这个优势小于 2^{-128} 时，我们说 CSPRNG 实现了 128 位的安全性。

当 PRNG 的内部状态能够被重构或其下一个数字可以被预测时，就可能将 PRNG 的输出与 TRNG 区分开。这在 CSPRNG 中不会发生，因为它们的输出与 TRNG 是不可区分的（除非其种子以某种方式被揭示或泄露）。换句话说，CSPRNG 必须抵御任何形式的“种子恢复”攻击。

有关更多详细信息，推荐参考普林斯顿大学的这些 讲义笔记↗。

来自弱随机的漏洞

CSPRNG 在正确生成随机数方面真的那么重要吗？是的。当使用弱 PRNG 生成敏感数据时，可能会导致重大的安全问题。常见漏洞枚举 (CWE) 还包括与随机性漏洞相关的条目，例如 “CWE-334：随机值的微小空间 ↗、” “CWE-335：PRNG 中种子的错误使用 ↗、” 和 “CWE-338：使用密码不安全的 PRNG ↗。这些类型的漏洞已经知道了很长时间，但仍继续出现。以下是几个因弱随机性造成的真实案例。

Milk Sad (CVE-2023-39910)

Milk Sad↗ 指的是在 Libbitcoin Explorer↗ 加密钱包工具中的一个漏洞。该漏洞是在对丢失资金的调查中发现的。

主要问题在于 bx seed ↗（https://github.com/libbitcoin/libbitcoin-explorer/wiki/bx-seed）命令中使用的 PRNG。该命令生成一个伪随机种子，如以下示例所示：

bx seed -b 192
d915107990a42dfb2ea5762729002d47a4748e0f24aceb61

乍一看，这似乎是随机的。然而，这个命令中使用的 PRNG 有两个关键缺陷：

1. PRNG 基于梅森旋转器，这不是 CSPRNG。
2. PRNG 的种子是根据当前时间选择的，仅提供 32 位的熵。

尽管梅森旋转器如果输出短且种子有足够熵时可能难以预测，但在这个案例中，种子选择不当，使得攻击者可以暴力破解由 bx seed 命令生成的私钥。尽管在 bx seed 维基页面↗ 上有警告声明，但它们可能没有对用户强调足够。甚至有些开发者可能也忽视了这个问题，因为 维基首页↗ 中包括了使用 bx seed 命令创建新钱包地址的示例，而没有任何警告。

最初，Libbitcoin 团队回应说 bx seed 命令从来不打算是密码安全的，而且他们没有计划去解决这个问题。然而，他们后来发布了一个修补程序，移除了该命令。

除了 Milk Sad，Cake Wallet↗、Profanity 以太坊地址工具 (CVE-2022-40769) ↗ 和 Trust Wallet (CVE-2023-31290) ↗ 是其他种子生成不当而导致的漏洞示例。

ECDSA 随机数使用错误

数字签名方案 是一种加密方案，拥有私钥的签名者可以为消息 m 生成签名 σ，并且知道相应公钥的验证者可以验证签名 σ 的有效性。

椭圆曲线数字签名算法 (ECDSA) 是一种基于椭圆曲线的数字签名方案。在加密货币中，ECDSA 允许确保交易是由合法的钱包拥有者进行的。然而，ECDSA 在滥用时 存在一个与非随机数 k 相关的重大安全漏洞。非随机数是签名生成过程中使用的随机生成值。

虽然 ECDSA 在正确使用时是安全的，但非随机数 k 的引入潜在地造成安全弱点，尤其是在非随机数重用的情况下。若非随机数在同一个私钥下重用，则此漏洞允许攻击者从签名中恢复出密钥。如果非随机数是以高熵选择的，则不会发生碰撞。然而，如果非随机数是以低熵生成的，则可能会发生碰撞。在 2013年，Android 中使用的 PRNG 的弱点导致了非随机数重用，造成大量比特币被盗（见 此处↗）。

此外，以不安全的方式选择非随机数（例如将一半的交易哈希与一半的私钥连接）也可能导致私钥的泄露（见 此处↗）。给定足够的消息，甚至每个非随机数泄露不到一个比特的情况也可能被 利用↗。由于有偏的非随机数生成可能导致完全的泄露，因此确保安全的非随机数生成是极其重要的。

总之，在 ECDSA 中安全且随机无偏地生成非随机数 k 是至关重要的。为了解决这个问题，RFC 6979↗ 建议使用私钥和消息哈希值作为种子的 HMAC-DRBG 运行结果来生成非随机数 k。这种方法有助于减轻与 ECDSA 中非随机数滥用相关的风险。

有关更多细节，推荐参考这篇来自 Trail of Bits 的 博客文章↗。

CSPRNG 构造

那么，我们如何构造 CSPRNG 呢？

在2006年，美国国家标准与技术研究院 (NIST) 发布了一份技术出版物，标题为 《使用确定性随机位生成器的随机数生成推荐》↗。在这份文件中，建议了四种 CSPRNG：

1. Hash-DRBG
2. HMAC-DRBG
3. CTR-DRBG
4. Dual_EC_DRBG

（备注：DRBG 表示确定性随机位生成器，这与 CSPRNG 意思相同。）

在这四种中，Dual_EC_DRBG 于2014年撤回，因为发现了其后门。其背景故事很有趣，但话题有些偏离。如果你感兴趣，可以在 这里↗ 获取更多信息。

在我们对 PRNG 的讨论中，我们侧重于基本形式，其中 PRNG 初始化时使用种子，然后生成伪随机数。在这种基本形式下，无法向 PRNG 提供额外的熵。然而，允许在操作期间注入额外熵可以增强安全性。没有这一能力，如果 PRNG 的状态或熵源在一段时间内受到影响，可能会完全受到破坏。另一方面，如果可以提供额外的熵，PRNG 可以在提供足够熵后恢复到安全状态。重要的是每次提供新熵时，其内部状态必须发生变化。

这就是 PRNG 的三个关键组件：

1. Setup(s)：PRNG 使用种子 s 初始化。
2. Refresh(I)：PRNG 接受新的熵 I。
3. Next(n)：PRNG 基于当前状态生成 n 位输出。

现在让我们看看如何生成加密安全的 PRNG。除了 Dual_EC_DRBG，其他三种 CSPRNG 基于对称原语，如哈希函数和块密码。选择这一点是合理的，因为哈希函数和块密码存在标准化的算法，并且其安全属性被广泛接受。即便针对某一特定对称原语发现了漏洞，这不是一个灾难性的场景，因为过渡到更安全的算法在相对容易方面比构造新的 DRBG 更易于实现。

由于其简单性，Hash-DRBG 是最佳示例，用于演示 CSPRNG 的工作原理。

Hash-DRBG

Hash-DRBG 是一个基于加密哈希函数 H 的 DRBG。为了便于理解，我们将介绍一个简化版本。在这个版本中，我们将状态表示为 S。

1. Setup(s)：将状态初始化为 S=H(s)。
2. Refresh(I)：将状态更新为 S=H(S∥I)。
3. Next(n):
   • 生成一个序列 R=H(S)∥H(S+1)∥…∥H(S+k)，其中 k 是满足 ∥R∥≥n 的最小数。
   • 将状态更新为 S=H(S∥H(S))。
   • 返回 R 的最左边 n 位。

这三个 DRBG（Hash-DRBG、HMAC-DRBG 和 CTR-DRBG）都是使用对称原语构建的，其安全性可以基于这些对称原语的安全属性进行证明，利用不可区分性的概念。

请注意，在这些 DRBG 的声称安全性与其理论分析之间可能存在轻微的差距，因为在证明中做出了强假设。然而，这些 DRBG 通常被认为足够安全，适用于现实世界，并且它们的安全性已成为近来的持续研究主题，如在 EUROCRYPT 2019 中提出的论文（例如 《NIST SP800-90A标准的分析》↗）。

如何正确生成随机数

要正确生成随机数，我们只需记住两件事。首先，种子应该从足够的熵中生成，其次，应使用 CSPRNG 而不是弱 PRNG，例如每种语言中的默认随机模块。（更多信息，请参见 这篇文章↗，列举了在各种编程语言中生成安全随机数的方法。）

结论

在这篇文章中，我们讨论了 CSPRNG 的数学定义，并研究了实际中的漏洞。虽然这些漏洞相对容易检测和防御，但其发生可能导致敏感信息暴露和重大损失。

由于 PRNG 是几乎每个软件程序中的基本组件，开发者始终有可能错误地为敏感数据生成随机数。因此，开发者确保以安全的方式生成随机数，并让审计员跟踪代码中 PRNG 的逻辑是至关重要的。

关于我们

Zellic 专门在新兴技术上提供安全保障。我们的安全研究人员在从财富500强到 DeFi 巨头的最有价值目标上发现了漏洞。

开发者、创始人和投资者信任我们的安全评估，使他们能够快速、自信地交付，而没有关键的漏洞。借助我们在现实中进攻性安全研究的背景，我们发现其他人遗漏的东西。

‍ 联系我们↗，进行比其他审计更好的审计。真实审计，而非官方盖章。

• 原文链接： zellic.io/blog/csprngs-h...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～