随机数生成器的弱点如何导致整个加密过程的妥协?

信息安全 加密 密码学 随机的
2021-08-12 08:14:30

在新闻中,有几篇文章(这里这里技术观点)与随机数生成器的弱点有关。

这个问题有点双重。弱 RNG 表现出什么症状?例如,这是否意味着几个不同的种子会给出相同的结果?还是我错过了他们所说的“弱”?

而且,如何从发现存在弱 RNG 到完全破译加密流量?

2个回答

当您生成私钥时,您会使用随机源。如果那个随机源可以输出N个不同的比特流,那么,你最多可以得到N个不同的私钥。这就是我们喜欢谈论熵的地方,它是N有多大的度量当说随机源提供“100 位熵”时,这意味着(大致)N = 2 100

攻击者将想要获取您的私钥。如果他知道你使用了一个低N的弱源(例如,只有 40 位熵),那么他可以在自己的机器上枚举来自随机源的所有可能输出并计算出相应的私钥。

例如,假设您使用以当前时间为种子的 PRNG,以微秒为单位。这是您的机器已知的时间。攻击者假设您的机器与当前时间设置得相当好,比如在 10 秒内。因此,从攻击者的角度来看,您的 PRNG 的种子在 10 秒范围内是已知的;由于 PRNG 以微秒为单位使用时间,因此他有N = 10000000 个可能的种子。然后攻击者对自己说:“如果那个人用作种子值x,那么他的代码产生了私钥值K x;让我们看看它是否与他的公钥匹配......不。所以他没有使用x。让我们再试一次x+1等等)。”

因此,在这种情况下,弱 PRNG 是致命的。

如何检测弱 PRNG ?好吧,大多数时候,你不能。一个非常差的 PRNG 可能从一开始就很差;例如,如果您生成两个私钥并获得两次相同的私钥,那么可能有问题......但是,正如“时间作为种子”示例所示,这并不总是很容易检测到:时间连续流动,所以你永远不要重复使用种子。然而,这很弱。因为弱点来自于猜测随机源的内部状态有多难,这与统计上的偏差不同。

可以检测到很大的统计偏差,这是一个明显的弱点;但是 PRNG 可能很弱而无法被检测到。

如果你是一个坏人并且想要制作一个无法检测到的弱 PRNG,那么你可以采用一个好的分组密码(比如AES),选择一些密钥值K,然后加密一个计数器的连续值,从 0 开始。这个会产生很长的伪随机字节流,没有人能够证明它是非随机的,这正是因为 AES擅长加密事物。但是你,作为坏人,知道K,所以你可以很容易地自己预测整个流。

检测弱 PRNG 的唯一可靠方法是检查 PRNG 工作的确切方法,直至细节:它收集了哪些物理事件,为什么这些事件可以被认为是“随机的”,它们如何与密码混合在一起产生伪随机字节的算法。你不能用不透明的硬件 RNG 做到这一点,因此目前有很多谣言。

根据定义,弱 RNG 难以检测(在随机流中,所有序列的概率均等,因此需要无限流来证明非随机性),但一个好的定义是您是否可以(显然)可靠地预测下一个数字在随机流中比“机会”更好。同样,这只有在你有一个无限流时才能证明,但对于破解加密来说,这并不像从观察中假设一个弱 RNG 并使用假设来实际破解加密那么重要(即使用你的假设(伪)随机模式生成这是证明弱RNG的更好方法,而不是等待生成无限流并对其进行分发测试)。

一旦您确定/猜测了如何预测随机流中的模式,如果该流已用于生成密钥或一次性填充,您就有一种方法可以使用预测分布来减少 (秘密)密钥猜测或在转置密码等中寻找分布。对于一次性垫,这尤其是一个问题,因为您有办法反转垫(如果您知道任何大量的密钥,这很简单)。

当然,所有密码算法都容易受到不同程度的随机性差的影响,有时“伪”就足够了。