随机数生成器具有密码安全性意味着什么？

#1 楼

使RNG加密安全的标准是什么？


简而言之，如果计算受限的攻击者拥有DRBG [确定性随机位生成器]，则其在形式上被视为计算安全将其与真正的随机源区分开来没有优势。

这是什么意思？给定一个DRBG F和一个真正随机的Oracle G，令A是一个概率“攻击者”，接受F或G并在查询给定的函数后输出1或0。我们将攻击者的优势Adv定义为|Pr[A(F)=1] - Pr[A(G)=1]|。如果Adv不可忽略地大于零，则认为DRBG已损坏。在此定义中，请注意，返回1或0的“均值”无关紧要，只是我们仅在给定A和F的情况下，G返回另一个的可能性不同，就可以了。 >用英语来说，如果存在一个可计算的函数，该函数可以可靠地区分黑匣子DRBG和黑匣子真正随机函数之间的区别，那么我们认为这是DRBG的突破。 br />为什么您的RNG必须是加密安全的？也就是说，如果不这样做会带来什么后果？


这样的问题可能范围太广。在某些情况下，不一定必须如此。在某些情况下，即使是轻微的弱点也可能导致机密性或真实性几乎完全丧失。弱RNG的含义完全取决于使用它的系统和上下文。


安全和不安全RNG的示例



有多种DRBG，用于不同目的。

Yarrow和后来的Fortuna是一种算法，它们接受质量未知的熵源作为输入，对其进行混合，并产生具有强大保证的熵流作为输出。它们具有自我修复特性，可以抵抗注射攻击。即使攻击者控制了几乎所有的输入，在有限的时间后，输出也将变得与攻击者无法区分。

对于系统RNG（例如用于系统内核，并通过/dev/urandom，getentropy(2)和CryptGenRandom()提供给用户空间（注意：这些接口实际上可能会或可能不会使用Yarrow或Fortuna，它们只是这些算法设计用于的系统RNG类型的示例）。

ChaCha20之类的流密码或CTR之类的流模式中的分组密码实际上只是加密播种的DRBG。这些算法的设计或意图不在于防止攻击者像上述算法那样注入可预测的输入，但在给定较小的初始随机密钥和IV的情况下，它们可以非常高的速度生成几乎无限的随机流。然后可以将这些流与明文进行XOR运算，以生成密码学上强的密文。更好的是，这些算法通常是可寻找的。给定密钥，IV和长密文，您通常可以深入研究密文并解密各个位，而无需计算整个流。列出的太多了，一般的假设应该是DRBG不安全，除非另有说明。



非伪随机数生成器在密码上是否安全？例如。一种基于粒子放射性衰变的物质


非伪随机数生成器是唯一甚至能够在信息理论上安全的生成器，这是一种比计算安全性强得多的度量标准。通过计算安全的DRBG，n位的一小种子被扩展为更大的密码流；更大的流仍然只是最多2^n个可能流中的一种。

从物理上讲，诸如放射性衰变和热噪声之类的大量随机性源是真正随机的。

#2 楼

我尝试使用大多数非术语来使它比当前的最佳答案更容易理解。


使RNG加密安全的标准是什么？


来自en.wikipedia.org/wiki/CSPRNG：


鉴于到目前为止的所有输出，一定没有任何算法可以比猜测更好地预测未来的输出。如果您可以说“下一位有50.0001％的机率将是1而不是0”，则它不是CSPRNG。
即使在给定无数个输出之后，也无法计算先前的输出第一个输出。


为什么必须对RNG进行加密保护？即，如果不这样做会带来什么后果？


想象一下您正在开彩票，有人检查您是否使用Mersenne Twister算法（这是一种非常常见的算法，因为它的速比比） ）。经过大约600次抽奖后，该人将能够预测下一个中奖号码。

这是因为Mersenne Twister不是CSPRNG，而是“仅” PRNG。它被设计为快速且具有良好的随机性，但是对于试图基于输出来计算其内部状态的人员而言，并不是安全的。该算法非常适合依赖随机事件的视频游戏和模拟。这是运行彩票，托管在线扑克游戏（重新安排甲板成为可预测的），生成用于HTTPS的随机密码或安全密钥等的糟糕选择。在某些情况下，人们使用PRNG（而不是CSPRNG）并被他人嘲弄，损失大量金钱（或信息，以防加密遭到破坏）。


安全和不安全的RNG的示例


：不安全：



rand() = (seed*=7) % 100（非常简单，但仅举一个具体例子）。

我知道的所有编程语言中的Random / random / rand包或函数：C，Java，PHP，C＃，Python，JavaScript等。这是设计使然，因为一个人通常只需要随机采样，并且对以下情况不会产生安全影响：有人猜出了输出。
（我个人认为，应该将这些函数重命名为清楚区别的函数，例如secure_random()和fast_insecure_random()，因为这两个函数经常混淆。）或者，因为您正在阅读此问题，所以您自己。

安全：例如，用于/dev/urandom和CryptGenRandom的算法。
算法Yarrow和Fortuna，但是您需要提供它们的熵，因此依靠操作系统来收集它们是更好的方法。要获得从0到11的随机数是不安全的（此处有更多信息），则应使用random_bytes(n)。
掷骰子或给定好骰子或洗牌良好的卡片组。


非伪随机数生成器在密码上是否安全？例如。一种基于粒子的放射性衰变的方法


目前尚无已知的预测衰变的方法，因此，按定义，这是加密安全的。与我们使用伪随机数生成器（算法）生成的伪随机性相反，此类事物被认为是真正的随机性。

需要注意的是，您必须正确使用真正的随机源。例如，如果一个粒子（平均）每30纳秒衰减一次，并且每次发生时您都记下当前时间，则该数字不是很随机，因为时间不断增加，并且下一个事件几乎肯定小于X上一个秒后的纳秒。攻击者可以猜测0到X之间的几个可能值。只能使用每个衰减事件的时间变化，例如，通过获取粒子衰减的纳秒级的最后一位。这将给出从0到9的均匀分布，因此只有几分熵/随机性……当且仅当您的时钟精确到该纳秒，并且没有攻击者可以获悉的中断时，这可能很难验证。

因此，尽管它确实是随机的，但从这些来源提取熵的设计方法并不一定是直观或容易的。评论有什么我需要澄清的。

#3 楼

使RNG加密安全的标准是什么？数字生成器，但我们可以将其简化为三类。给定攻击者的计算能力有限（只能执行有限数量的计算）：



计算安全性：看到PRNG的某些输出但没有PRNG输出的攻击者种子或状态，不能预测其他输出（较早或较晚的输出）。

前向机密性：如果攻击者确实在某个时间点看到了PRNG的状态，则它们仍然是无法重建早期的输出。通常通过注意PRNG以“单向”方式转换其状态的方式来实现，这种方式在密码上很难逆转。

预测阻力：如果攻击者在某一时刻看到PRNG的状态及时地，他们只能在非常有限的时间范围内预测其未来的输出。这是通过从外部来源收集熵并使用它在较短的时间间隔内扰乱PRNG的状态来实现的。

请注意，第一个是CSPRNG必须提供的最低要求。第二种和第三种在以下应用程序中是理想的：


生成私有（一方）秘密，例如在两方之间不共享的密钥；
生成公共价值，必须是不可预测的（例如，用于CBC加密的初始化向量）。

，但是在某些应用程序中，例如在流密码（两方使用相同的CSPRNG并且种子扩展共享秘密）。那些只想要＃1。

此外，仅满足＃1或仅满足＃1和＃2的RNG仍然具有相关性，因为满足所有这三种要求的PRNG通常是“像洋葱一样建造的”-最内层仅满足＃1，中间层在其之上添加＃2它，外层负责＃3。请参阅有关Fortuna PRNG的Ferguson等人的章节（可在线获得；这是PDF的直接链接）。




为什么必须对RNG进行加密安全？也就是说，如果不这样做会带来什么后果？




如果RNG不安全，则监视其输出子集的攻击者将能够重构该部分（如果（不是全部）其未来或过去的产出。例如，许多加密协议（例如SSL，SSH）的工作方式如下：


Alice和Bob分别随机选择一个临时的私钥/公钥对；
Alice和Bob用这些短暂密钥对执行Diffie-Hellman密钥交换，以获得共享的秘密密钥；
Alice和Bob然后交换使用该共享的密钥加密的消息。

一种常用算法＃3是CBC模式，它使用随机生成的初始化向量（IV），这些向量以明文形式传输。如果RNG不好，则窃听者可能能够从IV回溯到Alice和Bob的随机生成的临时私钥，重建Diffie-Hellman交换并解密消息。糟糕！




安全和不安全的RNG的示例



了解普通PRNG的不安全性的一种方法是查看示例程序，使其仅通过观察其输出来破解它们。这一系列博客文章对如何破解两个常见的RNG（java.util.Random和Mersenne Twister）进行了一些非常好的分析。最引人注目的示例是，仅需看连续产生的两个java.util.Random，就很容易预测int的输出。 （但是请注意，该系列中的代码不太正确-这是我固定的第一篇文章的示例版本。）

关于一个安全RNG的示例，它说明了我上面提到的三个属性，让我再次链接Fortuna RNG。




非伪随机数生成器在密码上是否安全？例如。一个基于粒子的放射性衰变的问题




这个问题要么是平凡的“是”，要么是硬“否”，这取决于您如何看待它。一个真正的无偏，独立位随机生成器将非常安全。面临的挑战是：


现实世界中的噪声源通常是有偏差的（1的概率不同于0的概率）或非独立的（1的概率取决于因此，真正的随机数发生器需要对噪声源的输出进行滤波，以提取无偏的独立位。这可能很棘手，因此可能做错了，在这种情况下，输出比您预期的要可预测的多。
执行此操作的实际设备也要克服工程上的挑战。例如，TRNG是否有可能以天真用户无法听到的方式失败，但是聪明的攻击者可以检测和利用？ （始终假设攻击者比您聪明！）

#4 楼

RNG尽可能随机，因此很安全。这意味着它们：


不再重复。早期加密依赖于使用大磁带上的“随机”数字。最终，人们可以确定地知道从磁带读取的下一个随机数是什么，因为磁带在循环。
没有可预测的模式。在添加小数点之前，序列3141592似乎是随机的：3.141592（pi傻）。
如果样本足够大，则无需进行分析。这与第一个一致。 “随机”数字生成器不应返回能够通过对大样本进行统计分析确定的数字。例如，许多视频游戏使用部分源自系统时间的随机数。虽然这对游戏来说很好，但统计分析会揭示出生成数字的时间与其值之间的模式。
依靠熵。熵是一种从某些外部来源获得随机性的方法。传统的（尽管不是量子的）计算机不可能生成随机数，因为可以用二进制位表示的任何等式都依赖于输入和输出，并且对于相同的输入，输出将始终相同。因此，实现密码程序的操作系统依赖于熵池。例如，Linux内核在任何给定时间在/ dev / random中最多具有4096字节的熵，这是由诸如鼠标移动和键盘按下之类的实际操作产生的。或者，如果您曾经使用过TrueCrypt等加密软件，则可以通过在窗口内尽可能随机地移动鼠标来提供熵。

那为什么重要呢？

以一次性垫（OTP）为例。在OTP中，消息中的每个字符都会根据随机键在字母表中移动任意数量的字符。然后，接收消息的人可以使用此密钥来“取消移位”字母并解码消息。参见维基百科； https://zh.wikipedia.org/wiki/一次性记事本

如果某人可以从上一个密钥进行预测，或者以其他方式知道/能够预测下一组随机数，则他们可以为将来的消息预测密钥，从而使整个过程变得不安全。因此，如果您的RNG不安全，那么您的加密就可能毫无用处，因为攻击者可以简单地预测并生成自己的密钥。

安全RNG的示例是Linux的/ dev / random（不要混淆/ dev / urandom，但这完全是另一篇文章）和Microsoft的密码服务提供商：https：//msdn.microsoft.com/zh-cn/library/system.security.cryptography.rngcryptoserviceprovider（v = vs.110）.aspx （尽管可能值得注意的是Microsoft的加密API已被NSA借壳）。尽管python确实具有加密安全的RNG库，但在游戏设计之类的东西中使用了其正常的随机功能。还应注意，随机数据需要很长时间才能生成。 Linux上的/ dev / random可能需要几天才能填满。如果您正在玩游戏，只要速度快也没关系。

放射性衰变将是熵的合适来源，因此是随机数据，因为放射性衰变是由于量子力学的性质，现代物理学可以告诉我们）完全随机。因此，是的，如果您真的很偏执，可以将Geiger计数器挂在一个旧的烟雾报警器上，并为您的心脏内容生成真正的随机数。真的很漂亮。

#5 楼

使RNG密码安全的标准是什么？ $ n $可能有许多数字。

还假设$ x_t $是您的RNG在$ t $时间生成的数字。因此，首先生成$ x_0 $，然后生成$ x_1 $，依此类推。

假设$ X_t $是一个随机变量，它接受RNG生成的输出集中的值然后，我认为我们可以说该RNG是加密安全的iff：
$$
\ Pr（X_t = x_t \ big | X_0 = x_0，X_1 = x_1，\ ldots，X_ {t-1} = x_ {t-1}，X_ {t + 1} = x_ {t + 1}，\ ldots）= \ frac {1} {n}
$$

即知道过去或将来的数字并不能帮助您预测当前数字。

我认为，不需要计算安全性。取而代之的是，我们应该选择选择$ n $为开放状态，然后由更高级别的密码算法（例如对称密码，非对称密码，哈希函数等）选择。如果他们需要更多随机性，则可以连接多个随机输出，例如$ x_0 ||。 x_1 || x_2 || \ ldots || x_t $。



为什么您的RNG必须是加密安全的？也就是说，如果不这样做会带来什么后果？




现在您需要查看提供基本安全服务的特定算法。例如。看一下对称密码，非对称密码或哈希函数。此外，请查看它们的使用方式，例如提供诸如数据完整性，数据真实性和数据机密性之类的安全服务。您的安全服务取得足够的成功。

更具体地说：不需要的一方可以更轻松地解密您的消息。

一个例子是：谜。由于Enigma没有充分利用随机性，例如德国运营商未能充分改组其转盘，以及其他错误，因此可以真正快速解密德国消息，并最终导致德国早于第二次世界大战。



安全和不安全的RNG的示例。



安全性是相对论性的术语。随机性也是一个相对论性术语。目的是确保对手仅以$ \ frac {1} {n} $的概率预测序列，其中$ n $是他们尝试预测的输出空间。任何可以确保该可能性都是安全的东西。

如果您查看一次一次性付款机密性的证明，您会发现$ \ frac {1} {n} $概率的使用定义完全保密的标准。这全都归结为达到等于$ \ frac {1} {n} $的预测概率。

但是从绝对意义上讲，我认为所有这些现实传感器都不安全。换句话说，这些现实生活中的传感器（例如，放射性传感器或任何从外层空间采样的奇特传感器）都不是绝对安全的。因为攻击者/攻击者还可以感知相同的来源，或者也可以感知到足够接近来源的来源，以增加预测概率，使其高于$ \ frac {1} {n} $。

从绝对意义上讲，有一个RNG来源可能是绝对安全的：量子随机性。该说法是否成立尚不清楚。但是，一些物理学家认为这可能是正确的。

如果找到依赖量子随机性的源，使其输出遵循均匀分布$ U（0，n）$，那么这是最好的您可能会得到的可能的RNG。



非伪随机数生成器在密码上是否安全？例如。一个基于粒子的放射性衰变的



如果满足：
$$
\ Pr（X_t = x_t \ big | X_0 = x_0 ，X_1 = x_1，\ ldots，X_ {t-1} = x_ {t-1}，X_ {t + 1} = x_ {t + 1}，\ ldots）= \ frac {1} {n}
$$
然后是，否则不。

#6 楼

为什么您的RNG必须是加密安全的？也就是说，如果不这样做会带来什么后果呢？如果RNG不能掩盖清晰的文本，效果就像一个时间垫一样好，那么结果将越来越容易受到加密分析的影响。