通过伪随机数流加密的缺陷(来自 PGP 文档)

信息安全 密码学 加密 已知漏洞 随机的 pgp
2021-08-31 05:59:21

我正在阅读PGP 文档,偶然发现了 Phil Zimmermann(PGP 的创建者)所写的部分,这激起了我的好奇心:

当我在 70 年代初上大学时,我设计了一个我认为是出色的加密方案。一个简单的伪随机数流被添加到明文流中以创建密文。这似乎会阻碍对密文的任何频率分析,即使是最足智多谋的政府情报机构也无法破解。我对自己的成就感到非常自鸣得意。

多年后,我在几本介绍性密码学文本和教程论文中发现了同样的方案。多好。其他密码学家也想过同样的方案。不幸的是,该方案是作为一个简单的家庭作业提出的,关于如何使用基本的密码分析技术来简单地破解它。我的绝妙计划就这么多。从这次卑微的经历中,我了解到在设计加密算法时很容易陷入错误的安全感。

什么技术能够轻松解密以这种方式编码的文本?它似乎几乎等同于一次性填充物(没有填充物是牢不可破的),前提是伪 RNG 足够复杂(周期比加密文本长得多;添加到每个字符的平均大小显着大于字符大小)和一个适当复杂的种子(所以你不能蛮力每颗种子)。

例如,使用Mersenne-Twister(周期为 2^19937 -1 ~ 4.3x10^6001 )和生成随机 256 位种子的密码;如果没有种子,它似乎是无法破解的。

或者他们是否生成了周期为 2^32 - 1 ~ 43 亿的简单随机数生成器(那是 70 年代;Mersenne Twister 直到 1990 年代中期才被发明);您可以在哪里暴力尝试 43 亿个随机种子中的每一个,并快速检查密文以查看是否出现字典单词或简单的频率分析(大量空格和 e)?

4个回答

一个“好”的 PRNG(具有很强的统计随机性保证,比如说,加上有很长的周期)没有说明它的安全性。请参阅此线程中的例如讨论

该线程讨论了以下之间的区别:

  • 一次性护垫(原则上是牢不可破的,只要它们既不泄漏也不重复使用,但通常不切实际)
  • 流密码(可以根据需要变得安全,并且非常实用)
  • 用作流密码的 PRNG(并非设计用于加密安全)(通常很容易破解)

Phil 应该使用的是流密码,而不仅仅是任何旧的 PRNG。MT(和更早的 PRNG)不适合用作流密码。Salsa20/ChaCha(作者 Dan Bernstein)和ISAAC是两个特定的流密码。ISAAC 被shred使用。Salsa20 是欧盟eSTREAM/ECRYPT计划的一部分。当然,Phil 没有使用流密码是可以原谅的:RC4(它被认为是损坏的——它的弱点是导致 WEP 不安全的部分原因——但它是 ISAAC 的基础)是在 1987 年才发明的。

普通 PRNG(包括 MT 和 Wichmann-Hill)的加密弱点导致了例如 TCP 序列号攻击中的漏洞。这些漏洞有时会使用不同类型的 CSPRNG 来解决,该 CSPRNG 会“随时”收集熵(例如,来自鼠标/定时抖动)。为了适合用作流密码,CSPRNG 必须在开始时拥有所有可用的输入熵,而不是在运行时收集它。请参阅有关CSPRNG/dev/[u]random的维基百科页面。

我不知道菲尔齐默尔曼最初用于加密的方法是什么,所以我真的不能说什么。

但是,可以将 Mersenne-Twister 制成“安全”流密码,例如CryptMT不过,CryptMT 随后被破解:Distinguishing Attack on CryptMT阅读那篇论文可能会很好地了解如何攻击 Mersenne-Twister 及其同类。


实际上,我做了更多的调查。首先,我引用的论文随后已被作者编辑,请参阅此处的讨论,它针对的是 CryptMTv1,而不是当前版本的 CryptMTv3 没有针对 CryptMTv3 的已知攻击。我发现的最接近攻击的是On the Security of Stream Cipher CryptMT v3,它明确表示:

但是,我们没有发现任何关于密钥流输出的非随机性。

此外,CryptMT 的 eSTREAM 最终报告说:

CryptMT v3。密码 CryptMT 具有非常不寻常的设计,可提供非常合理的性能。虽然在 eSTREAM 的最后阶段没有针对密码的负面密码分析结果,但我们有点担心密码的安全性,特别是非线性滤波器组件,可能还没有像某些其他决赛选手。我们预计 CryptMT 的元素将继续引起加密社区的兴趣,我们希望能够评估 CryptMT v3 中体现的方法的全部优势。但是,我们目前对该算法的设计和安全性没有足够的信心,无法将其包含在最终的投资组合中。

几乎没有负面的优点!

此外,看看上面在eBASH上提到的“非常合理的性能” ,似乎 CryptMTv3 为长消息提供了惊人的性能(例如,对于长消息,每字节 1.82 个周期),通常只有 Salsa20/8 才能击败,其中 Salsa20/ 8 已经被破解(几乎没有,而且 Salsa20/12 仍然非常安全)。

所以我会说 CryptMT 绝对是流密码的竞争者,即使它还没有得到足够的分析!

任何使用密钥初始化 PRNG 的简单 XOR/PRNG 密码都容易受到复杂度为 1 的已知明文攻击:

  1. 加密明文至少与未知密文一样长。
  2. 将已知明文与其密文异或。这为您提供了keystream
  3. 将密钥流与未知密文进行异或运算:这将为您提供原始明文。

如果您可以加密由全“0”组成的明文,则可以跳过第 2 步:加密过程的输出密钥流。

你使用什么 PRNG 并不重要:从RANDUFortuna 的所有东西都容易受到这种密钥流恢复攻击。

请注意,有些密码使用“将明文与密钥流异或”作为其操作的核心。但是,他们采取了预防措施来防止这种攻击:一次性密码从不重复使用密码,流密码要么需要一次性密钥,要么需要称为nonces的一次性值,并且输出反馈和计数器分组密码操作模式同时使用两者密钥和称为初始化向量的第二个一次性值,以确保 RNG 永远不会以相同的方式播种两次。

我认为作为密码学外行来解决这个问题的最佳方法是远离现代密码学,转而考虑经典的纸笔密码。在这种情况下,可能要考虑的最佳示例是运行密钥密码

在经典密码学中,运行密钥密码是一种多字母替换密码,其中通常来自书籍的文本用于提供非常长的密钥流。

基本上,这样的密码采用明文和同样长的自然语言文本(例如,小说中的一段),并通过将明文的每个字母移动一个取决于其相应密钥流字母的数量来加密明文的每个字母。

这样的密码很容易破解:

[I]f(像往常一样)运行密钥是自然语言的文本块,安全性实际上变得相当差,因为该文本将具有可用于帮助密码分析的非随机特征。结果,明文和运行密钥的每个字符的熵都较低,并且组合操作容易反转。

为了攻击密码,密码分析员沿着密文运行猜测的可能明文,从每个可能的位置中减去它们。当结果是一大块可理解的东西时,猜测的纯文本很可能在那个位置是正确的(作为实际的纯文本,或者是运行密钥的一部分)。然后,“可理解的大块”通常可以在任一端进行扩展,从而提供更可能的明文——进而可以扩展,等等。最终很可能会识别出运行键的来源,并且夹具已启动。

此类攻击起作用的原因是:

  1. 攻击者通常有一些关于明文的部分信息。在经典密码学中,这可能是明文语言和主题(这意味着字母和单词的频率以及连续字母和单词之间的依赖关系)。在现代密码学中,这可能是被加密的通信协议(例如,基于 SSL 的 HTTP)、连接的端点(例如,Google)等。
  2. 自然语言密钥流具有这样的模式,即给定密钥流中的几个字母,您以非常高的概率猜测接下来的几个字母。现在要观察的关键是非加密 PRNG 也具有此属性,因此它们承认类似的攻击。

这个博客系列描述了如何打破简单的线性同余 RNG 和 Mersenne Twister。对于java.util.RandomRNG,如果intPRNG有两个连续的s 输出,则足以重建其状态并预测伪随机流的其余部分(正向和反向)。因此,如果您使用该 PRNG 来生成您的密钥流,那么知道或猜测密文的任何八个连续字节的攻击者可以应用正在运行的密码攻击的变体和博客系列的 PRNG 破解技术来破译其余的信息。

博客系列的第 3 部分描述了如果您可以获得 624 个连续的输出词,您如何可以类似地预测 Mersenne Twister 的输出。所以它比线性同余生成器更难,但仍然很脆弱。