如何检查随机数生成器的随机性?

信息安全 密码学 随机的 智能卡
2021-08-30 08:12:49

假设我有一个智能卡,它在接收到命令时返回一个 8 字节(例如)随机值。问题是:

我如何检查这个值是否真的是随机的? (我无权访问实现和机制。我只看到一个 8 字节的十六进制数字。)

在另一个世界,有没有办法根据输出检查随机发生器输出的随机性?还是唯一的方法是分析生成器的实现和机制?

4个回答

NIST 在NIST 特别出版物 800-22中定义了一组广泛的统计测试,用于验证随机性来源。

然而,虽然这足以断言 RNG 没有明显损坏,但不足以断言 RNG 是“好”的。非常细微的缺陷可能导致 RNG 的破坏,这是 RNG 的本质。检查RNG稳健性的唯一正确方法是查看实现。

真正的“随机性”归结为样本中的熵量。正如其他人指出的那样,熵或多或少不可能在黑盒测试中获得资格。一个好的调节函数和一个信息很少的简单输入可以通过统计测试。因此,测试只能指出在产生数字的方式中存在或不存在一些固有的统计弱点,它们无法真正确认它们是不可预测的。

在评估 RNG 的随机性、不可预测性或其熵时,有几个因素很重要:

  1. 您需要确定您是在谈论具有实时熵源的真正 RNG,还是具有初始种子(或两者的组合)的 DRNG。
  2. 如果有现场噪声源,您肯定需要检查噪声(熵)源的实现以及基础理论。为此使用物理或随机模型。
  3. 当您对上述 RNG 产生的输出进行统计测试时,需要对在应用调节/压缩功能之前收集的数据进行测试,以便清楚地了解您正在使用的实际熵量。
  4. 如果 RNG 不是真正的 RNG,这意味着您正在查看确定性 RNG,则需要验证 DRNG 算法的实现。这可以用测试向量来完成。
  5. 最后,对于没有实时熵源的 DRNG,需要评估初始种子质量。如果种子来自真正的 RNG,则适用上述 1-3。

最近RNG评估越来越受到关注,标准也越来越严格。您可以查看 NIST SP800-90A/B/C 系列以获得 RNG 设计的一个很好的概述,尤其是用于熵源评估的 SP800-90B(仍然草案)。BSI 在 AIS20/31 中也有说明如何评估 RNG 的指南。

最后,正如已经指出的那样,NIST 的 STS 800-22a 是一个很好的测试套件。还有 BSI 的 AIS20/31 测试套件和 Dieharder 测试套件。

你不能。不可能验证声称的随机发生器的输出对于密码学来说是足够随机的。(可以验证它对于某些应用程序(例如蒙特卡洛数值方法)是否足够随机,但不能用于生成加密密钥。)

存在密码安全的伪随机数生成器,即确定性但与真正的随机序列无法区分的随机数生成器。我们不知道如何区分 CSPRNG 的输出和真正的随机序列:给定 CSPRNG 的部分输出,我们不知道如何重建我们没有给出的输出。

(我们实际上无法从数学上证明 CSPRNG 存在,但是有建立在 AES 和 SHA-2 等加密原语上的 CSPRNG,它们是基于相同假设的 CSPRNG,使得 AES 适合从中派生加密算法,以及 SHA-2一个密码散列函数。)

由于 CSPRNG 是确定性的,如果你知道它的初始状态,你就知道它的输出;更一般地说,如果您在某个时候知道它的内部状态,那么您就知道所有后续输出。因此,只有在对手不知道内部状态的情况下,CSPRNG 才是生成加密密钥和其他用于加密的随机值的合适方法。

内部状态为对手所知(不适合加密)的 CSPRNG 与内部状态在智能卡之外未知(适合加密)的 CSPRNG 无法区分。因此,仅从其输出来测试 RNG 的质量是不可能的您可以从输出中看到的是检测一些严重缺陷,但不是所有严重缺陷。

为了验证 RNG 是否完成其工作,有必要查看内部。这分两部分完成:

  • 验证 CSPRNG 使用适当的算法并正确实施。
  • 验证 CSPRNG 是从对手不知道的材料中播种的。

(仅基于物理过程的 RNG 几乎总是具有可检测的偏差,因此物理 RNG 不直接使用,而是作为熵输入(即种子)馈送到 CSPRNG。)

CSPRNG 实现通过检查源代码、检查算法是否良好(通常首选甚至强制使用NIST SP 800-90A等标准的算法)以及进行一些测试来检测实现错误(例如存储结果在错误的地址。

RNG 的播种更容易验证。一些系统包括一个“真正的随机数发生器”,即一个硬件,它基于不可预测的物理过程(如放射性衰变或混沌振荡器)返回不可预测的位。验证这些是通过统计测试进行的,这些测试证明 TRNG 的输出具有足够的

请注意,TRNG 实际上可能不是“真正随机的”:它可能有偏差。重要的是它具有足够的随机性,因此正确预测其下一个输出的概率非常低,以至于对手无法做出明智的猜测。这些偏差是 CSPRNG 应用于 TRNG 输出的原因:使用加密“混合”函数将可观察到的相关性(例如,如果一个位为 0,那么下一个位有 52% 的机会也为 0)转化为相关性这是无法计算的。

也可以通过一次性为 CSPRNG 播种一个秘密值来制作 RNG。只有您确定 PRNG 的内部状态不会泄漏,这才是可行的。种子值本身必须随机生成,最终来自某种形式的 TRNG;但是这样一来,TRNG 就可以在工厂中,而不是在 RNG 运行的设备中。

作为智能卡的购买者,您无法从内部查看卡在做什么。(无法查看内部是智能卡的一个重要特性。)但是,您使用的卡可能已经过安全实验室的评估。有一些标准可以评估智能卡的安全性,例如通用标准 保护配置文件您可以检查您的卡是否已通过认证. CC 不是唯一的此类认证。Visa和Mastercard等信用卡公司有自己的认证流程。如果该卡已经过评估,您的供应商应该将您指向证书 - 这是一个营销论点。有许多智能卡认证,它们测试不同的东西,所以请检查证书所保证的内容。您不会确切地了解 RNG 的工作原理(通常是交易电路),但您会知道安全实验室对其进行了调查并没有发现任何缺陷。

使用它来生成图像:随机 x、y、r、g、b... 发现任何图案...?

更新:虽然我同意 1)这不是一种非常科学的方法,并且 2)它并不能证明 RNG 在密码学上是安全的,但它是一种快速简便的方法来检查 RNG 是否不是随机的......例如这是 .net 的 System.Random 的可视化:

从 System.Random 生成的带有 x/y/argb 的随机散点图