如何(如果有的话)可预测的随机数生成器在SHA-1输出后变得更安全？

Question

这篇文章指出

尽管Mersenne Twister是一个非常好的伪随机数生成器,但由于一个非常简单的原因,它本身并不具有加密安全性.可以从发电机在任何给定时间具有的状态确定发电机的所有未来状态,并且624个32位输出或19,937个一位输出足以提供该状态.在Mersenne Twister的输出上使用加密安全散列函数(如SHA-1)已被推荐为获取密码学中有用的密钥流的一种方法.

但是没有提及为什么消化输出会使它更安全.老实说,我不明白为什么会这样.Mersenne Twister的周期为2 ^ 19937-1,但我认为我的推理也适用于任何周期性PRNG,例如线性同余发生器.由于安全单向函数h的特性,人们可以将h视为内射函数(否则我们可以产生碰撞),从而简单地将值从其域映射到其范围中以一对一的方式.

考虑到这一点,我认为散列值将产生与原始Mersenne Twister完全相同的周期性行为.这意味着如果您观察到一个周期的所有值并且值开始重复,那么您完全能够预测所有未来的值.

我认为这与在基于密码的加密(PKCS#5)中应用的原理相关- 因为密码域不能提供足够的熵,只是哈希密码不会增加任何额外的熵 - 这就是你需要的原因在哈希之前加密密码.我认为完全相同的原则适用于此.

一个简单的例子最终说服了我:假设你有一个非常糟糕的PRNG,总是产生1的"随机数".那么即使SHA-1是一个完美的单向函数,将SHA-1应用于输出也是如此总是产生相同的值,从而使输出不比以前更容易预测.

尽管如此,我还是要相信这篇文章有一些道理,所以我肯定忽视了一些事情.你能帮我吗？在很大程度上,我从我的论点中遗漏了种子价值 - 也许这就是魔术发生的地方？

Answer 1

mersenne twister的状态由先前的n输出定义,其中n是复发程度(常数).因此,如果您n直接从mersenne twister 给出攻击者输出,他们将立即能够预测所有未来的值.

通过SHA-1传递值会使其变得更加困难,因为现在攻击者必须尝试反转RNG.但是,对于32位字大小,这不太可能成为坚定的攻击者的严重障碍; 他们可以构建彩虹表或使用其他标准方法来反转SHA-1,并且在发生碰撞时,根据它们是否产生观察到的RNG流来过滤候选者.因此,mersenne twister不应该用于加密敏感的应用程序,SHA-1屏蔽或不.可以使用许多标准CSPRNG代替.

Answer 2

攻击者能够根据相对较少的输出来预测MT的输出,不是因为它在如此短的时间内重复(它没有),而是因为输出泄漏了有关PRNG内部状态的信息.散列输出会掩盖泄露的信息.正如@bdonlan指出的那样,如果输出大小很小(例如32位),这无济于事,因为攻击者可以轻松枚举所有有效的明文并预先计算其哈希值.

使用超过32位的PRNG输出作为哈希的输入将使这变得不切实际,但如果您需要此属性,则加密安全的PRNG仍然是更好的选择.