测试与验证 RNG 实现

随机数生成器测试面临一个根本性挑战：真正的随机序列与优秀 PRNG 生成的伪随机序列，在统计测试看来完全相同。任何有限长度的测试都无法证明一个序列是随机的——统计方法只能以一定置信度检测非随机性。测试可以验证 RNG 没有明显偏差或模式，但无法证明其密码学安全性。密码学 RNG 测试有两个不同目标：(1) 统计质量——验证输出分布看起来均匀且相互独立；(2) 密码学强度——验证 DRBG 算法实现正确，并且其安全性声明成立。这两个目标需要采用不同的测试方法。

NIST SP 800-22 提供了 15 项用于评估比特序列的统计测试。这些测试包括：频率（单比特）测试——1 的比例应接近 0.5；块频率测试——统计每个 m 位块中 1 的频率；游程测试——统计相同比特连续不间断游程的数量；最长游程测试——统计 1 的最长游程长度；二进制矩阵秩测试——计算由序列构成的二进制矩阵的秩；谱测试（DFT）——检测周期性模式；重叠模板匹配——统计特定模式的出现次数；Maurer 通用统计测试——压缩序列，并测量压缩后缩短了多少。每项测试都会生成一个 p 值；p < 0.01 表明可能存在非随机性。测试使用 100 万至 10 亿个位运行。

TestU01（勒库耶与西马尔，2007 年）是 RNG 社群广泛使用的综合统计测试套件。SmallCrush：10 项测试，约 35 秒，适合快速检查。Crush：144 项测试，约 2 小时。BigCrush：160 项测试，约 24 小时。BigCrush 测试能够发现 NIST SP 800-22 遗漏的细微相关性。设计良好的密码学 DRBG（HMAC_DRBG、CTR_DRBG）可以轻松通过 BigCrush——对于多项式时间算法而言，它们的输出在计算上与随机序列不可区分。非密码学 PRNG（梅森旋转算法、线性同余生成器）会在某些 BigCrush 测试中失败。BigCrush 测试失败是一个强烈信号，表明不应将该 RNG 用于密码学用途。

SP 800-90B 和 90A 规定，DRBG 必须在运行期间持续执行健康测试。连续 RNG 测试（CRNGT）：将每个生成的块与前一个块进行比较——如果两者相同（RNG 卡死），DRBG 必须进入错误状态并停止生成。重复计数测试：如果连续样本中的相同值重复次数超过根据熵估计值在统计上预期的次数，则测试失败。自适应比例测试：如果某个窗口中出现频率最高的值超过阈值次数，则测试失败。这些健康测试能够在熵源故障（传感器卡死、HWRNG 硬件故障）悄然危及密码学密钥生成之前将其检测出来。

PractRand 是一种现代 RNG 测试工具，专为在线（流式）评估而设计。它会在序列生成的同时进行分析，而不要求预先确定序列长度。它会采用间隔测试、位分布测试和谱测试等测试，并使用自适应精度。PractRand 特别擅长检测这样一种 RNG：生成较短序列时表现良好，但在数十亿个位之后显露出模式。无论长度如何，密码学 DRBG 产生的输出都能让 PractRand 无法将其与随机序列区分开来——这就是计算不可区分性的操作性定义。PractRand 还用于评估熵源（测试 /dev/urandom 输出和 RDRAND 输出），以检测硬件故障或系统性偏差。

密码算法验证计划（CAVP）为 SP 800-90A DRBG 提供官方测试向量。CAVP 测试要求将实现提交至 NIST 的自动化测试系统，并使用已知答案测试（KAT）向量：给定特定的熵输入、随机数、个性化字符串和 additional_input，实现必须生成完全匹配的预期输出位。CAVP 不测试统计属性，而是测试算法正确性。FIPS 140-3 认证要求模块边界内使用的所有密码学算法都通过 CAVP 验证。CAVP 测试向量可从 NIST 的 ACVP（自动密码验证协议）服务器公开获取，并已集成到 OpenSSL、mbedTLS 和 BoringSSL 的测试套件中。

在安全初始化 DRBG 之前，必须先验证其熵源。SP 800-90B 规定了以下内容：(1) 熵估计——使用统计测试测量每个位的实际熵（最小熵估计）。(2) 启动测试——在首次使用之前验证熵源能够产生有效输出。(3) 按需测试——由应用程序触发的可选测试。(4) 噪声源健康测试——检测硬件退化。常见熵源及其估计的每位熵如下：CPU RDRAND/RDSEED（约 1 位/位，经过硬件认证）；/dev/urandom（混合多个来源，熵估计较为保守）；环形振荡器 TRNG（每位 0.5–0.9 位，取决于设计）；ADC 噪声（每位 0.1–0.5 位）。SP 800-90B 验证要求使用专用设备进行实验室测试。

虚拟环境带来了特定的 RNG 测试挑战。VM 可能在启动时（没有硬件事件）或快照恢复后（状态被重置）遇到低熵条件。Docker 容器共享主机内核的 RNG，因此容器无法直接测试底层熵的质量。针对 VM 部署的测试包括：(1) 测量 /dev/random 读取完成所需的时间——长时间等待表示熵不足。(2) 测试并行 VM 实例生成的 UUID 或密钥是否重复（这是云部署中已有文档记录的真实故障模式）。(3) 验证 VM 中是否已加载 VIRTIO-RNG（virtio_rng.ko）——它负责将主机熵注入客户机。(4) 审查应用程序启动顺序：密钥生成是否发生在有足够熵可用之前？

测试 RNG 的分叉安全性可以防止一种隐蔽的漏洞：进程进行分叉时，父进程和子进程会共享相同的 DRBG 状态，导致它们生成相同的序列。检测方法：生成 N 个子进程，在每个进程中生成一个 UUID，并验证所有 UUID 都是唯一的。如果任意两个 UUID 相同，则 RNG 不具备分叉安全性。OpenSSL 在 2020 年修复了一个分叉安全漏洞（CVE-2020-1971 并不直接涉及 DRBG，但模式相似）。当前的 OpenSSL 使用基于 PID 的种子更新机制：如果 PID 自上次调用后发生了变化（表示发生了分叉），DRBG 就会自动重新播种。测试方法：在分叉前后分别运行测试，并通过验证输出不同来确认重新播种已经发生。

RNG 实现的实用审计清单：(1) RNG 是否从 OS（getrandom、BCryptGenRandom）初始化，而不是使用基于时间的种子？(2) DRBG 类型是否为 NIST SP 800-90A 批准的机制（哈希、HMAC、CTR）？(3) 对于所声明的安全强度，种子长度是否足够？(4) 是否会定期重新播种，或在固定次数的生成调用后重新播种？(5) 实现是否能够处理分叉安全性（分叉后重新播种）？(6) 是否启用了健康测试，并且是否会在测试失败时停止系统？(7) 关闭时是否会将状态清零？(8) 是否在 CI/CD 中运行 CAVP 测试向量？(9) 熵估计是否已记录并经过验证？(10) 对于 FIPS 要求：模块是否已通过 FIPS 140-3 认证？

历史上的 RNG 故障说明了问题的严重性。Debian OpenSSL（2006—2008 年）：一个补丁意外删除了两行熵收集代码，将种子池缩减为 15 位的 PID 空间——整个 Debian 用户群中生成的 SSH 密钥只有 32,767 种可能。所有由 Debian 生成的 SSH 主机密钥和用户密钥都需要更换。Android 比特币钱包（2013 年）：Android 的 SecureRandom 使用了 Java 层面的播种机制，该机制在某些设备上失效，导致 ECDSA 签名中的 k 值重复——这会直接泄露私钥。Sony PS3（2010 年）：其 ECDSA 固件签名使用了固定的随机数，使得攻击者能够从两个签名中提取私钥（不同消息使用相同的 k 时，通过简单代数运算即可得到密钥）。

统计测试（NIST SP 800-22、TestU01 BigCrush、PractRand）可以验证输出质量，但无法证明密码学安全性。CAVP 已知答案测试可以验证 SP 800-90A 实现的算法正确性。SP 800-90B 熵源测试（最小熵估计、健康测试）可以验证种子输入。连续 RNG 测试（CRNGT）可以实时检测卡住的输出。VM 和容器部署需要进行熵注入（VIRTIO-RNG）并检查启动时的熵。分叉安全测试可以验证子进程不会继承父进程的 DRBG 状态。现实世界中的故障（Debian、Android）表明，RNG 错误会直接导致密码学密钥泄露。审计清单将这些检查正式化，以便用于生产部署。