9

这篇文章指出

尽管 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 应用于输出也会总是产生相同的值，从而使输出的可预测性不亚于以前。

尽管如此，我还是愿意相信那篇文章是有道理的，所以我肯定忽略了一些东西。你能帮我吗？在很大程度上，我从我的论点中遗漏了种子值——也许这就是魔法发生的地方？

4

2 回答 2

15

mersenne twister 的状态由先前的n输出定义，其中n是递归度（一个常数）。因此，如果您n直接从 mersenne twister 向攻击者提供输出，他们将立即能够预测所有未来值。

通过 SHA-1 传递值变得更加困难，因为现在攻击者必须尝试反转 RNG。但是，对于 32 位字长，这不太可能成为坚定的攻击者的严重障碍；他们可以建立一个彩虹表或使用其他一些标准方法来反转 SHA-1，并且在发生冲突时，通过它们是否产生观察到的 RNG 流来过滤候选者。因此，mersenne twister 不应用于加密敏感应用程序、SHA-1 掩码或否。有许多标准的 CSPRNG可以替代使用。

于 2011-07-08T00:59:55.083 回答
5

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

使用超过 32 位的 PRNG 输出作为散列的输入会使这不切实际，但如果您需要此属性，加密安全的 PRNG 仍然是更好的选择。

于 2011-07-08T02:28:18.997 回答