你必须知道的密码学理论：随机预言模型（四）

这是关于随机预言模型系列文章的第四部分。 点击下面的链接查看以前的文章:

第一部分: 介绍

第二部分: ROM 的形式化，方案和证明简介

第三部分: 我们如何滥用 ROM 来使我们的安全证明工作

这是关于随机预言模型的倒数第二篇文章。我最初希望的是，这篇文章要简短、整洁，对于那些对密码学家的工作感兴趣的非专业人士来说，这篇文章很容易理解。 更重要的是，我期望现在确实已经是这样了。

但是终点已经在眼前，我觉得只剩下几件事情我想说了。更妙的是，其中一个主题非常实用，这是本博客的主题一致。

具体来说: 我一直在谈论随机预言模型，但它对生活有什么影响？ 这东西在哪里使用？

对这个问题给出一个完整的答案是困难的——这有点像列出所有成分表中含有苯甲酸钠成分的食物。 所以在这篇文章中，我至少会提及几个亮点，也就是说: 这些方案可能与我们的日常安全生活最相关。

RSA 签名和加密

RSA 可能是目前使用的最著名的密码系统。 我不知道为什么它如此受欢迎，但我怀疑其中有几个原因。 首先，RSA 是灵活的，它在一个方案中提供签名和加密。 它相对简单——你可以用计算器计算简单的加密。 它已经存在一段时间了，还没有被打破。 如果我没有提到 RSA 目前没有专利，那我就是失职了。

这一切都很好，但从某种意义上说，这也太糟糕了。 在过去的二十年里，对因数分解问题(也就是 RSA)的攻击一直处于边缘状态。 这意味着 RSA 密钥的大小必须变得更大才能跟得上。 我们迟早会输掉这场比赛。 

对我来说，更有趣的是 RSA 作为一种可证明安全的密码系统的地位。 人们普遍认为 RSA 加密在 RSA 问题困难的情况下是可证明安全的。 然而，事实并非如此，至少考虑到大多数人传统上使用 RSA 的方式。 你可以对 RSA 假设进行简化，但需要采取一些非常具体的步骤。 最重要的是: 你需要调用随机预言模型。

为了解释这一切，我需要带你回到20世纪90年代末，我需要谈谈填充。

如果你曾经看过一个真正的 RSA 实现，你可能知道我们不使用普通的“教科书” 上的RSA (“m^e mod N“)来加密或签名原始消息。 这其中有很多原因。 其中之一就是普通的 RSA 没有随机化，这意味着给定的消息将总是在加密后得到相同的密文。

另一个原因是 RSA 具有可塑性，这意味着你可以用创造性的方式对密文和签名进行处理——例如，用你选择的常数乘以它们。 当你这样做时，解密(resp:verified)消息将以可预测的方式进行更改。 这不利于加密。 对于签名来说，这简直是糟糕透顶。

在对消息进行加密或签名之前，我们通过对消息应用填充来处理这些问题。 填充方案可以添加随机性，在签名的情况下应用哈希，最重要的是，它们通常添加结构，让我们知道消息何时被篡改。

一些历史背景: 在 ROM 之前的 RSA

第一个广泛使用的标准填充方案是在 RSA 的 PKCS#1 标准中描述的。 现在，我们将这些标准称为“PKCS#1 v1.5”标准，这意味着该标准(现在是2.1版本)已经将它们抛在了后面。

回到90年代，这些标准是唯一的游戏。 当然，也有一些迂腐的密码学家反对该标准缺乏正式的安全理由。 但这些麻烦制造者主要局限于学术机构，这意味着真正的安全专业人员可以继续从事业务。

这项业务就是在所有地方实现 PKCS 填充标准。 PKCS #1 v1.5 填充仍然出现在我评估的产品中。 当时最值得注意的是，它使用的是一个名为 SSL 的年轻标准，一些人使用 SSL 来加密通过互联网传输的信用卡号码。

现在，我可以说，几乎没有一个有实际经验的人对 PKCS 有意见。 一个值得注意的例外是来自贝尔实验室的一位聪明的密码破译者，名叫丹尼尔 · 布莱申巴赫。

布莱申巴赫博士对 PKCS 填充标准有一个真正的问题。 事实上，可以说他一生的使命就是摧毁它们。 这种仇恨在2006年达到顶峰，当时他展示了如何用铅笔和纸打破 PKCS 签名的常见实现，不久之后，他驾驶一辆载满烟花的小型货车进入 RSA 数据安全公司的总部。

1998年，布莱申巴赫在 CRYPTO 第一次加入 PKCS。 在一篇可读性惊人的论文中，他提出了针对“使用 PKCS#1”加密标准的协议的第一个实用的自适应选择密文攻击。 因为，正如我刚才提到的，符合这种描述的主要协议是 SSL，这是一件非常了不起的事情。

攻击是这样进行的。

每当有人通过 SSL 连接将他们的信用卡信息发送到网络服务器时，他们的浏览器和服务器就会执行握手协议以获得一个秘密密钥。 特别是，在协议的一个步骤中，浏览器对服务器的 RSA 公钥下称为“ pre-master secret”（预万能密钥）的非常重要的值进行加密，并通过网络将产生的密文发送给它。

这种加密很重要，因为任何人只要立即解密或五年后解密密文，就可以最终恢复 SSL 传输密钥，从而解密服务器和浏览器之间的所有通信。

布莱申巴赫指出的是大多数 web 服务器处理 RSA 消息的具体方式。 具体来说，每当服务器接收到 RSA 密文时，它首先对其解密，然后检查填充是否有效。 对于一个典型的 RSA 密钥，PKCS#1 填充 如下所示:

0x 00 02 { at least 8 non-zero random bytes } 00 { message }

当 SSL 网络服务器不像它看到的填充那样，它可能会反馈一个特定的“坏填充”错误。 布莱申巴赫首先展示了如果他能在网络上拦截一个合法的 RSA 密文“C = M^e mod N” 然后他就可以用选定的值“篡改”它。 换句话说，给定一些C，他会选择一些“s”然后计算:

C' = C * s^e mod N

这个值 C’将解密为“M * s mod N”。 布莱申巴赫表明，对于“s”的某些值，这个被篡改的消息也可能是一个有效的 PKCS 填充消息，这意味着它将以“0x00002”等开头。 这并非完全不可能，主要是因为仅仅查看几个字节本身就是一个非常糟糕的填充检查。

服务器通过一些特殊的错误代码(比如“BAD PADDING”)将填充检查的结果泄漏给发送方是很常见的。 即使他们没有这样做，你有时也可以通过测量服务器返回到你的时间来检测填充检查中的故障。

布莱申巴赫的主要技巧是指出，导致成功的填充检查的“s”值也可以用来学习原始消息 M 的一些东西。长话短说，他展示了如何自适应地选择这些值，以便逐渐将注意力集中到实际的明文上，直到他只有一个候选者。 这就是比赛的情况。

实际的攻击平均需要几百万次解密查询。 这听起来似乎很多，但这意味着你可以在一夜之间解密 SSL 会话，只要没有人关注服务器日志。

随机预言的救赎

出于各种原因，布莱申巴赫的攻击方法是一件大事。 首先，它是实用的。 它在一个广泛部署的系统上工作，甚至可以由非专家实现和执行。 它完全否定了 SSL 提供的保护，除非你愿意日夜监控你的 SSL 网络服务器。

但是对密码学家来说，这次攻击有着特殊的意义。 首先，它证明了自适应选择密文攻击是一个真正的问题，而不仅仅是一个空洞的学术话题。 我怀疑，即使是在这个领域工作的密码学家也对此感到有点惊讶。 有些人可能已经开始寻找一些没什么用的话题。

更重要的是，布莱申巴赫的演示被视为可证明安全的支持者的胜利。 到目前为止，他们的担忧大多被置若罔闻。 现在很多人都在听。

更妙的是，密码研究团体有话要对他们说。 压倒性的共识是立即切换到早在1994年就提出的新的 RSA 填充方案。 这个方案被称为最优非对称加密填充(OAEP) ，它只比 PKCS#1稍微复杂一点。 更好的是，与 PKCS#1不同的是，在随机预言模型中，使用 OAEP（Optimal Asymmetric Encryption Padding） 的 RSA 加密可以被证明减少 RSA 问题的难度。

OAEP 的成功也导致了 PSS 填充方案的采用，它对 RSA 签名基本上也起到了同样的作用。

现在，听一些人说，这就是故事的结局。 这是一个好故事——坏的，未经证实的安全协议被破坏。 新的、可证明安全的协议介入并挽救了局面。

大多数情况下，这个故事是真实的，但也有一些重要的警告。

第一个就是与实现相关的。 正如 PKCS#1由于服务器提供了太多详细错误而被破坏一样，如果服务器泄漏了太多关于其错误条件的信息，即使 OAEP 加密也可能被破坏。 当 OAEP 实现出现问题时，它们真的会变得很糟糕。 James Manger 展示了你可以在1100个查询中破解1024位 RSA-OAEP，假设你的服务器泄漏了一点点关于解密尝试出错的信息。 ****

但是，即使你正确地执行所有操作，OAEP 的安全性证明也只适用于随机预言模型。 这意味着，只有在哈希函数是理想的情况下，它才能提供有效的保证。 这是一个很好的启发式方法，意味着 OAEP 不太可能充满明显的缺陷。

但是如果你深入研究 OAEP 的安全性证明，你会发现它使用的是可以想象到的最强大的随机预言。 OAEP 的基本概念是使用一对散列函数构造一个微小的可逆 Feistel 网络。 美妙之处在于，每次你加密的时候，本质上就是通过随机预言直接发送信息(和一些随机性) ，这种方式允许各种各样的胡说八道。

然后，还原证明可以看到对手的加密算法是什么，当你构建一个针对选择密文攻击非常安全的系统时，这种加密非常有用。 如果你用一个真正的哈希函数来实现 OAEP，就像在现实生活中实际用来实现它的那些函数一样，那么这将永远不会起作用。

所以在一个非常真实的意义上，我们仍然没有一个实用的，可证明安全的方法来使用 RSA 加密。 此外，我们几乎没有理由相信我们会这样做，因为一系列不可能的结果似乎一直阻碍着我们。 *****

所有这些都提出了一个重要的问题。 考虑到 RSA 的所有限制，为什么我们对它如此痴迷？

数字签名算法(DSA / DSS)

你可能会觉得有点奇怪，我在讨论可证明的安全性时提到了 DSA。 这主要是因为，与 DSA 所基于的 Elgamal 签名不同，DSA 标准没有任何安全证明。 ******

对此没有真正可以辩护的理由。 据我所知，NIST 看了一眼 Elgamal 签名，觉得很可爱，但是签名有点太长了。 所以他们用剪刀剪出了一些看起来基本一样的东西，但是没有像 Elgamal 那样很好地减少了离散对数的假设。

这种行为是意料之中的，说实话，这让我对政府标准机构有点失望。

郑重声明，尽管 DSA 根本不是真正可证明的安全方案，但 Elgamal 方案是可证明的。 但不幸的是，Elgamal 方案只能在随机预言模型中证明是安全的。 这意味着，如果你的散列函数具有完全随机和可编程的特性，Elgamal 签名可以简化为离散对数问题的难度。 除此之外，你只能靠自己了。

关键词推导与超越

可能有数不清的密码系统应该在这里提到，但我们不能涵盖所有的。 不过，还有一类“使用散列函数的东西”可能根本就不安全，除非你愿意对散列函数的属性做出一些非常强有力的假设。

我想到的例子是使用哈希来推导加密密钥。 例如，许多基于密码的加密方案使用散列函数将密码和一些 salt 结合起来，从而得到用于加密的密钥。 这种方法在大多数情况下似乎可行(假设是一个高熵密码) ，但是它没有任何强有力的理论支撑。

一般来说，如果你试图从一个“块状”的、非均匀的密码源(如密码)中提取一个均匀随机密钥，正确的工具是所谓的随机提取器。 这些可以在标准模型中实现(没有随机预言) ，但是所有现有的结构都很糟糕。 这听起来很粗鲁，但实际上这是密码学家用来表示方案复杂而缓慢的一个技术术语。

所以在现实生活中，没有人会用这些东西。 相反，他们只是把密码加盐加密，然后假设结果会很好。 如果他们感到兴奋，他们甚至可能把这个问题解决好几次，这就相当于用 AK-47步枪射击一只火鸡。 这可能没什么问题，虽然从技术上来说，你永远不能排除防弹火鸡。 *******

每当人们费心去正式讨论像这样的方案的安全性时(实际上从来没有) ，通常的争论是这样的: 让我们假设哈希函数是一个随机预言。 当然，在随机预言模型中，每个 hash 函数都是一个完美的提取器。 将任何高熵的源代码放入一个理想的哈希函数中，不管输入的内容是多么“凹凸不平”或者“奇怪” ，你都可以从另一端得到一个非常棒的密钥。

因此，即使你最喜欢的密钥推导没有任何正式的安全证据，你可以打赌，某个地方的某个人，已经提出了这个论点，即使只是为了帮助自己在晚上睡得更好。

总结

这本应该是一篇关于随机预言模型的文章，但是我觉得它有了自己的生命。 这不是一件坏事。 我承诺我会花一些时间来讨论实用的密码技术，我已经做到了。

虽然我可以说出关于随机预言模型的一百万件事情，但我只剩下最后一篇文章了。 在某些方面，这将是最重要的文章。

你看，我们一直都知道这次旅行不会永远持续下去，我们只是觉得我们有更多的时间。 不幸的是，末日即将来临。 就像莱昂纳多 · 德 · 卡普里奥在《盗梦空间》无聊的情节中探索的那个虚构的城市一样，随机预言模型在自身矛盾的重压下正在崩溃。

这种崩溃——以及它对密码学家、安全专家和其他所有人意味着什么——将成为我最后一篇文章的主题。