是什么让随机数生成器如此脆弱?

信息安全 加密 密码学 随机的
2021-08-21 07:35:12

在我看来,生成随机数的硬件组件非常简单——只需用传感器测量硬件中的微小振动,对吗?也许我错了,但如果您以非常高的精度测量振动,您似乎可以轻松生成无法猜测的随机数。

但是,我是一个密码学菜鸟,并且知之甚少。所以我正在阅读,一篇文章说:

而且你不需要那么复杂来削弱随机数生成器。这些发电机已经非常脆弱,并且很难检测到何时损坏。Debian 的维护人员早在 2008 年就很好地说明了这一点,当时错误的代码清理将 OpenSSL 的有效熵减少到仅 16 位。事实上,RNG 是如此脆弱,以至于这里的挑战不是削弱 RNG——任何有键盘的白痴都可以做到——它这样做不会使实施对其他人微不足道。

我肯定错过了一些关于随机数生成如何“脆弱”的关键细节。有人可以解释吗?

4个回答

硬件与软件 RNG

您提到的第一件事是硬件噪声源。一些亚稳态现象的高精度测量足以产生不可预知的数据。这可以通过反向偏置齐纳二极管、环形振荡器、ADC,甚至盖革计数器来完成。我甚至可以测量击键之间的纳秒级延迟。如果硬件本身开始出现故障,这些噪声源可能会出现故障。例如,如果晶体管不是专门设计为在高电压下反向运行,它可能会发生故障。尽管这些技术具有不同程度的脆弱性,但这并不是您引用的文本中讨论的内容。

您提到的第二种 RNG 是一种称为伪随机数生成器 (PRNG * ) 的软件 RNG。这是一种算法,它需要一个种子,就像一个加密密钥,并将其扩展为无穷无尽的数据流。它试图确保在不知道算法开始时使用的秘密随机种子的情况下,无法预测数据,或者除了纯粹的随机性之外无法告知数据。在这种情况下,PRNG 是在纯软件中实现的,所以破解它只需要在代码中引入一个错误,这就是你引用的文本所说的。它只是脆弱的代码,如果对代码的更改偏离了算法的预期行为,则可能会完全失败。

PRNG 可以被认为是一种重新使用的加密算法。事实上,您可以通过使用像 AES 这样的密码来加密计数器来创建加密安全的 PRNG。只要加密密钥(种子)是秘密的,就无法预测输出,也无法发现种子。当你以这种方式思考时,就会更容易理解代码中一个小的、无关紧要的更改是如何完全破坏算法的安全性的。

收集随机性

那么现代设备实际上是如何收集随机性的呢?让我们在某个数据中心的某个地方安静地运行一个服务器。为了支持 TLS 之类的东西,它需要大量完全不可预测的数据,这些数据无法与真正的随机流区分开来。如果没有专用的硬件噪声源,随机性必须来自内部。计算机努力实现完全确定性,但它们有大量来自非确定性设备的输入。进入……打断!

在现代硬件中,中断是硬件发出的信号,用于提醒 CPU 状态变化。它允许 CPU 避免快速轮询每个硬件设备以获取更新,而是相信设备会在时机成熟时异步提醒它。当中断发生时,会调用中断处理程序来处理信号。事实证明,这个处理程序是获得随机性的理想场所!当您测量纳秒级的中断时序时,您可以快速获得相当多的随机性。这是因为各种事情都会触发中断,从到达 NIC 的数据包到从硬盘驱动器读取的数据。其中一些中断源是高度不确定的,例如依赖于执行器物理运动的硬盘驱动器。

一旦操作系统收集到足够的随机位,就可以将至少 128 位的小种子输入加密安全的 PRNG,以生成无限的伪随机数据流。除非有人能够准确地预测过去每次中断发生的时间,精确到纳秒级,否则他们将无法推导出种子,也无法预测未来的 PRNG 输出。这使得输出完全适合 TLS 密钥。

* 面向安全的 PRNG 称为加密安全 PRNG,或 CSPRNG。当应用程序调用 CSPRNG 时使用常规 PRNG 可能会导致安全漏洞。

从历史上看,适用于加密的硬件 RNG 在 PC 上并不常见:例如,根据这个问题, AMD 几年前才增加了支持,所以即使在今天,软件供应商也不能简单地假设它会可用。这大概就是为什么 OpenSSL(如您的报价中所讨论的)使用软件 RNG 的原因,使其容易受到代码中发现的错误的影响。

(正如评论中广泛讨论的那样,标准 PC 确实包含许多软件 RNG 可以利用的“熵源”——我相信 OpenSSL 确实如此,尽管我对它并不十分熟悉——但显然在那场景软件中的错误可能会导致错误的随机数,正如确实发生的那样。)

还有人担心硬件 RNG 可能已被后门,导致人们将硬件 RNG 与其他熵源结合起来,而不是按原样使用它们。(在您的链接文章中也提到了后门硬件,比您引用的内容高出几段。)

还应该提到的是,硬件 RNG 的实现并不像您的问题所暗示的那么简单……一方面,幼稚的实现可能容易受到各种物理攻击,例如,如果您基于振动生成随机位,如果有人用超声波瞄准它会发生什么?即使在理想条件下,结果中也可能存在某种偏差,这可能使生成的位对加密使用不安全。

这就是为什么现实世界的实现会使用硬件噪声但也会对其进行加密处理但是到那时,您又回到了算法(或其实现)是否被故意破坏的问题,或者可能没有人们认为的那么健壮。

因为它们很难测试

虽然很容易测试随机数生成器是否以正确的格式生成输出,但确定它是否在统计上是随机的则要复杂得多,而且不太可能包含在自动化测试套件中。如果你打破它,许多其他代码会更加明显。

加密货币需要是正确的

一般来说,确保代码正确是很困难的。许多代码的一个可取之处是,只有一小部分正确性错误会导致安全漏洞。但是对于加密代码——包括随机数生成器——许多正确性错误会导致漏洞。加密代码需要正确、安全,并且很难确保其正确。

Debian 维护者犯了一个重大错误

代码实际上并不那么脆弱。要使它变得不安全,需要维护者的重大失败。仅仅粗略地检查它没有破坏任何东西,就删除产生警告的行,这是相当粗制滥造的

编辑:这不仅仅是维护者的错,请参阅天使的评论

任何随机生成器最重要的方面之一是每个随机位的值不仅必须完全独立于它生成的所有其他位的值,而且还必须完全独立于对手可能在宇宙中的所有其他事物观察或影响不幸的是,该属性通常是最难真正保证的属性之一。通常可以做的最好的事情是以一种不太可能与宇宙中任何其他事物有任何可利用关系的方式生成比特。

举个简单的例子,如果一个拥有高度集中射频发射器的对手有能力影响你的随机数发生器,那么他选择的某些样本有 95% 的概率产生,而其余的只有 5%这样做的概率。如果从这样的生成器中简单地读取 128 位并将它们构建为 128 位密钥,那么将暴力攻击集中在接近用于影响生成器的位模式的攻击者将有更大的可能性与生成器没有偏见相比,它取得了快速的成功。然而,假设不是一次挑选一个位,而是挑选一组 7 个位并将它们异或在一起。这样做会使生成 128 位密钥的时间增加七倍,但攻击者的影响力将从 95/5 减少到 74/26,

作为替代方案,假设要生成 128 个随机位,以某种方式对它们进行哈希处理,然后将它们与另外 128 个随机位进行异或。这只需要生成 256 位而不是 896 位,但会使攻击者很难利用生成器中的任何偏差。即使枚举最可能的 95,000,000,000 位 128 位模式将有大约 50% 的机会匹配在散列之前使用的一组 128 位,或者与散列值异或的一组,异或之后的最终分布不太可能有任何可利用的偏见或信息泄漏。