伪随机与真随机

信息安全 密码学 AES 随机的 伪随机数发生器
2021-08-19 13:49:06

正确的安全算法需要真正的随机数。例如,密钥和初始化向量不应该是真正随机的。

但是,使用 Java 的Random库或 C 的srand()初始化生成数字 & thenrand()只能生成伪随机数。据我了解,由于诸如srand()从系统时间等某些来源收集种子之类的功能,并且 24 小时时间是循环的,因此它并不是真正随机的。如果这个假设有缺陷,请纠正我。

此外,真正随机数的一个例子是,如果我们使用来自假设音频文件的种子,并在文件中选择一个伪随机位置,然后获取该位置的音频频率。由于只有位置是伪随机的,但该位置的频率不是,所以该值是真正随机的。如果这个假设有缺陷,请纠正我。

最后,为进一步复杂化这个问题道歉,如果使用伪随机值,它究竟会给系统带来多大的脆弱性?我了解到 AES 128 实际上足以保护系统(在 ECC Asym 和 Sym 密码的背景下,128 位安全性在 2020 年仍然被认为是强大的吗?)。对于军用标准,采用了 192 和 256(为什么大多数人使用 256 位加密而不是 128 位?)。使用真正的随机值是否也类似于遵循这种毫无根据的标准,或者它实际上是否至关重要?

4个回答

在这个问题中有一个(常见的)误解,即存在“真正的”随机性,这对安全性很重要。事实上,是否存在“真正的”随机性是一个哲学问题(物理学给出了部分答案),与安全性无关。

随机性有很多概念。与安全相关的是不可预测性安全性被定义为防范对手。出于安全目的,如果您的对手无法找到或猜到它,则该值是“随机的”。

在安全的上下文中,“真正的随机”有时用来表示一个值是基于某个对手无法复制的物理过程。例如,从这个意义上说,掷硬币通常是真正随机的。但如果硬币偏差过大,并且对手可以看到硬币翻转的结果,则不会。在摄像机前进行 128 次抛硬币不会给你一个安全的 128 位随机数。(它确实为您提供了一个无法提前预测的值,这对某些事情有利但不利,例如,作为加密密钥。)

相反,只要攻击者无法学习随机生成器的种子或内部状态,由密码安全伪随机生成器(CSPRNG)以确定性方式计算的值作为随机值是完全可以的。除了种子的生成之外,仅涉及确定性物理过程,并且相同的种子被用于生成其他随机值,这一事实不会损害随机值的安全性(假设 CSPRNG 被正确设计和实施 -适用于任何安全处理的假设)。

“真正的”随机性对于安全性是必要的,因为您必须以某种方式播种 CSPRNG。您可以使用 CSPRNG 的输出为 CSPRNG 播种,但最终,您必须从一个不确定的或未充分精确建模的物理过程开始。

只有当它足够不可预测时,随机值才足够好12729af5a51075a68db9d4b05ce7981a如果我告诉你我在和之间随机选择了我的密钥fc42099f25ee1eb5a8dc1178c35868b8,那对我不利:事实上我确实随机生成了这两个值,你不知道它是哪一个,但你仍然可以在最多两个猜测。值的不可预测性或未知性的度量称为(请注意,有许多相关但不同的概念称为)。一个完全已知的值的熵为 0。一个具有相同机会成为两种已知可能性之一的值的熵为 1。通过告诉您我的密钥是这两个值之一,我已将其熵减少到 at大多数 1 位,无论这两个值是如何随机生成的。

一个音频文件可能有也可能没有大量的熵。在一种极端情况下,如果对手拥有相同的文件,则熵为 0。如果对手有相同声音的不同录音,由于麦克风质量和位置可能会出现伪影,但音频压缩往往会消除这些伪影. 麦克风白噪声可能是一个不错的熵源,但您应该直接从硬件中获取它:当您获得录音时,很难确保噪声已被保留并且相同的噪声未被复制别的地方。

大多数编程语言的标准库中的函数的问题rand()不在于它们是伪随机的,而是它们在密码学上不安全,主要有两个原因:

  • 对手可以找到种子。例如srand(time()),大多数情况下是可预测的(取决于对手知道您的应用程序何时运行的精确程度——这与时间周期无关)。即使对手不知道种子,如果种子是一个 32 位的数字,对手很容易通过蛮力尝试所有可能的种子。如果它是一个 64 位数字,它的成本很高,但仍然可行。
  • 输出不是独立的:给定足够的输出rand(),可以计算其他输出。

安全随机生成器,例如/dev/urandomor CryptGenRandom,没有这些缺陷:它们使用来自安全种子(在现代计算机中,可以从主 CPU 中的组件生成)的 CSPRNG 算法(保证独立输出)。

关于:

此外,真正随机数的一个例子是,如果我们使用来自假设音频文件的种子,并在文件中选择一个伪随机位置,然后获取该位置的音频频率。由于只有位置是伪随机的,但该位置的频率不是,所以该值是真正随机的。如果这个假设有缺陷,请纠正我。

似乎这种方法会产生熵很少的“随机”值。例如,如果音频文件以 44.1 KHZ 采样,并且音频长度为 5 分钟(300 秒),这意味着在这个“随机”数字所在的空间中只有 13,230,000 个可能值 (44100 * 300 = 13230000)发电机产生。了解您的“随机”数字生成器如何工作的攻击者可以轻松地在短时间内遍历所有约 1300 万个值,将每个值用作加密算法中的密钥,直到找到解密密文的正确密钥。请参阅编写 Python 或 C 程序以猜测如何完成此操作的示例(尽管有些人为)的关键。此外,类似的程序hashcat可以john the ripper用来自动化这个过程。

关于您的最后一段:是的,AES-256(甚至 AES-128)被认为是强加密算法 - 但它们的强度取决于强密钥。如果您通过执行: 生成密钥echo -n 'iloveyou123' | sha256sum,那么攻击者可以很快找到您的密钥,再次使用类似hashcator的程序john the ripper

Java 有一个内置函数SecureRandom()在上面链接的页面上,它显示:

此类提供了一个加密的强随机数生成器 (RNG)。

您可能需要考虑使用此功能。

您的第一个假设是不正确的,因为通常系统时间是从实时时钟中提取的,该时钟往往会输出一个在技术上不循环的 unix 时间戳。然而,像流行编程语言中的伪随机数生成器(通常是 mersenne twister)确实会循环,因为它们的性质是确定性函数。如果使用正确的参数初始化生成器,则“周期”的长度或生成的数字的“模式”开始重复之前的时间会很大 (2^19937 – 1)。

您的第二个假设也不完全正确,因为生成的“随机”数仍然是伪随机的(有争议的),因为您只是通过引入更多随机性来“白化”算法。真正的随机性是通过从物理现象(例如辐射和大气噪声)以及/dev/random硬件事件中提取数据来生成的。

伪随机数生成器在技术上是可破解的(在 mersenne twister 的情况下)从种子 [https://github.com/kmyk/mersenne-twister-predictor/blob/master/mt19937predictor.py] 生成的 624 个连续数字,但是在加密环境中,这不是一个容易被利用的漏洞

真正的随机总是更好。不幸的是,这要困难得多常用的技术是在启动时,系统尝试尽可能多地收集随机值:日期和时间(根本不是随机的,但它总是在变化,它是猜测什么时间(以毫秒精度)随机子系统询问它,如果系统只能手动启动,它可以选择尝试从网络、磁盘或操作员那里收集随机值。

从那里,它初始化自己的系统种子。不需要可重复序列的应用程序可以只依赖该系统序列。

提供种子主要是为了测试。如果您想使用随机值控制算法的输出,则使用特定种子允许始终接收相同的序列,因此始终获得相同的输出值,然后可以轻松控制。但是对于生产代码,你永远不应该给自己一个种子。