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

第一部分: 介绍

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

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

第四部分：ROM 使用案例

大约八年前，我开始写一篇特别不够正式的文章，讨论一种特定的密码建模技术，称为“随机预言模型”。这要追溯到2011年的美好时光，那是一个密码学更加天真和温和的时代。当时没有人预见到我们所有的标准密码学最终都将被弄的漏洞百出; 你不需要被提醒“加密就是密码学”的意思。人们甚至用比特币来购物。

第一篇随机预言的文章不知怎地就出现了三个结局，并且一个比一个更荒谬。我想，在某种程度上，我对整件事感到很尴尬——说实话，这件事挺俗气的——所以我有点半途而废打算放弃了。这是我后悔的主要原因之一，因为我一直计划要发表第五篇文章，也是最后一篇文章，来结束这一团糟的事情。这篇文章将是本系列文章中最好的一篇，也是我一直想写的一篇。

为了给你提供一些上下文，我会简要地说明随机预言模型是什么，以及你为什么应该关心它。(当然你最好还是读读这个系列的前几篇文章。)

随机预言模型是一种对哈希函数进行建模的疯狂方法，我们假设这些函数实际上是随机函数，并利用这一假设来证明密码协议中的一些事情，如果没有这样一个模型，这些事情是很难证明的。几乎所有我们今天使用的“可证明的”密码学都依赖于这个模型，这意味着如果这些证明是“错误的” ，那么这些证明中的许多东西将会受到质疑。

为了梳理这篇文章的其余部分，我将引用第四部分的最后一段话，以下面的内容结束:

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

正如我之前所承诺的那样，这篇文章会讲述那次“崩溃”，以及它对密码学家、安全专家和我们其他人意味着什么。

首先，为了使这篇文章更加自成一体，我想回顾一下我在本系列文章前面讨论过的一些基本内容。如果你读过前面的几篇文章，你可以跳过这一部分。

我们将(很快)提醒读者什么是哈希函数，什么是随机函数，什么是随机预言

正如在本系列的前几篇文章中所讨论的，哈希函数(或哈希算法)是计算机科学的许多领域中使用的标准原语。它们接受一些输入，通常是一个可变长度的字符串，并可重复地输出一个短的、固定长度的“摘要”。我们经常这样表示这些函数:

加密哈希使用这个基本模板并利用加密应用程序所需的一些重要安全属性。最著名的是，它们提供了一些众所周知的属性，比如抗碰撞性，这是数字签名等应用程序所需要的。但哈希函数在密码学中到处都会出现，有时出现在意想不到的地方，从加密到零知识协议，有时这些系统需要更强的特性。这些有时很难用形式化的术语表示: 例如，许多协议需要一个哈希函数来产生极其“随机”的输出。 

在可证明安全性的早期，密码学家意识到理想的哈希函数的行为类似于“随机函数”。这个术语指的是从所有可能的函数集中均匀采样的函数，这些函数具有适当的输入 / 输出规范(域和范围)。在一个完美的世界里，你的协议可以，例如，在设置时随机抽取大量可能的函数中的一个，将该函数的标识符放入一个公钥或其他什么东西中，然后你就可以开始工作了。

不幸的是，在实际协议中不可能真正使用随机函数(适当规模的域和范围)。这是因为抽样和评估这些函数的工作量太大了。

例如，使用很少的256位输入并生成256位摘要的不同函数的数量是令人难以置信的(2 ^ {256}) ^ {2 ^ {256}。简单地“写下”你所选择的函数的恒等式将需要在函数输入长度中呈指数级的内存。由于我们希望我们的加密算法是有效的(意思是，稍微正式一点，它们在多项式时间内运行)，使用随机函数几乎是不可用的。

所以我们不使用随机函数来实现哈希。在“现实世界”中，我们使用比利时人或国家安全局开发的奇怪函数，比如 SHA256、 SHA3和 Blake2。这些函数具有极快的运算速度和微小的算法来执行计算，其中大多数只占用几十行或更少的代码。它们当然不是随机的，但据我们所知，输出看起来相当混乱。

尽管如此，协议设计者仍然渴望使用真正的随机函数能够给他们的协议带来安全性。他们会问，如果我们折中一下，结果会怎样?如果我们使用随机函数来建模我们的哈希函数——只是为了编写我们的安全证明——然后当我们实现(或“实例化”)我们的协议时，我们将使用高效的哈希函数，比如SHA3，会怎么样呢?当然，这些证明并不完全适用于实例化的实际协议，但它们可能仍然很好。

使用这种范式的证明被称为随机预言模型(ROM)中的证明。关于 ROM 如何工作的完整机制，可以翻阅我之前发表的该系列文章。你现在需要知道的是，在这个模型中的证明必须以某种方式绕过，即计算一个随机函数需要花费大量指数级的时间。这个模型处理这个问题的方法很简单: 它没有给每个协议参与者一个关于哈希函数本身的描述(哈希函数对任何人来说都太大了) ，而是给每个参与者(包括对手)一个神奇的“预言” ，这个预言可以有效地评估随机函数 H，并将结果返回给他们。

这意味着任何时候其中一方想要计算函数，他们自己并不能独自完成。相反，它们会调用第三方，即“随机预言”，“随机预言”拥有一个巨大的随机函数输入和输出表。在高层次上，这个模型看起来有点像下面这样:

因为系统中的所有参与方都与同一个预言在“对话” ，所以当他们要求预言对给定的消息进行哈希时，都会得到相同的哈希结果。对于真正的哈希函数来说，这是一个相当好的替代函数。使用外部的预言可以让我们“掩盖”评估随机函数的成本，这样就没有人需要花费一个指数级的时间来评估一个函数。在这个人工模型中，我们得到了理想的哈希函数，而且没有任何麻烦。

这看起来已经很可笑了……

绝对是这样！

然而，我认为在你认为随机预言模型是个空洞的事物之前，你应该知道几件非常重要的事情:

1. 当然，每个人都知道随机的预言证明不是“真的”。大多数认真的协议设计者都会承认，在随机预言模型中证明某些东西是安全的，并不意味着它在“现实世界”是安全的。换句话说，随机的预言模型证明是伪造的这一事实，这并不是我想让你们知道的秘密。。

2. 总之: ROM 证明通常被认为是一种有用的启发式方法。对于那些不熟悉“启发式”这个术语的人来说，“启发式”是一个成年人用来保护你毕生积蓄的词，因为他们使用的密码学无法证明任何事情。

OK，开个玩笑！事实上，随机预言证明仍然是很有价值的。这主要是因为它可以经常帮助我们检测方案中的缺陷。也就是说，虽然随机预言证明在现实世界中并不意味着安全性，但不能编写这样的证明通常是协议的危险信号。此外，ROM证明的存在有希望表明协议的“核心”是正常的，并且任何现实世界中出现的问题都与哈希函数有关。

3. 经过ROM验证的方案在实践中有着相当不错的记录。如果 ROM 验证每隔一天就会提出一些荒谬而被破坏的方案，我们很可能就已经放弃了这种技术。然而，我们使用的密码学几乎每天都在 ROM 中得到验证(仅仅是验证) ，而且大多数情况下它确实奏效。

这并不是说，当用特定的哈希函数实例化时，经过 ROM 证明的方案从未被破坏。但通常情况下，这些破坏是因为哈希函数本身明显存在缺陷(正如 MD4和 MD5不久前都break 掉时所发生的情况) ，尽管如此，这些缺陷通常可以通过简单地切换到一个更好的函数来进行修复。此外，从历史上看，实际攻击更可能来自明显的缺陷，比如发现哈希碰撞破坏了签名方案，而不是来自某种奇特的数学缺陷。这就让我们注意到了最后一个关键的点..。

4. 多年以来，许多人相信只读存储器实际上是可以被保存的。这种希望是由这样一个事实驱动的：即 ROM 方案在实现了强哈希函数时似乎工作得很好，所以也许我们所需要做的就是找到一个哈希函数，使 ROM 证明变得有意义。一些理论家希望像密码混淆这样的奇特技术能够以某种方式使具体的哈希算法运行良好，使(某些) ROM 证明可以实例化。 

所以这就是 ROM 的状态，或者至少是直到20世纪90年代末的状态。我们知道这个模型是人造的，但它固执地拒绝爆炸或产生完全无意义的结果。

然后，在1998年，一切都变糟了。

CGH98: 一个“不可实例化”的方案

对于理论密码学家来说，随机预言模型的真正破裂点来自于 Canetti，Goldreich 和 Halevi (以下简称 CGH)在1998年发表的一篇 STOC 论文。我打算把剩下的时间来解释他们发现的要点。

CGH 所证明的是，实际上，有一些加密方案可以在随机预言模型中被证明是完全安全的，但是，当你用任何具体函数实例化哈希函数时，这种安全性就会变得非常危险。

这是一个非常可怕的结果，至少从可证明的安全社区的角度来看是这样。从理论上来说，你的证明可能不够有力，这是一回事。而另一回事则是，你要知道，在实践中，有些方案可以直接通过你的证据，就像终结者渗透到抵抗组织，然后以最严重的方式在你身上爆发。

在我们详细介绍CGH及其相关结果之前，有几点需要注意。

首先， CGH很大程度上是一个理论结果。解决这个问题的密码“反例”方案通常看起来不像我们将在实践中使用的真正的密码系统，尽管后来的作者提供了一些更“现实”的变体。事实上，这些变体是被设计用来做一些“真实的”方案不会做的但却是非常“人为的”事情。这可能会导致读者会以“人为的”这一理由对它们不屑一顾。

这种观点的问题在于，外表并不是判断一个方案的特别科学的方法。如果证明是正确的，那么“真实的”和“人为的”方案都是有效的密码系统。这些具体的反例的要点是故意做“人为的”事情，以突出问题的 ROM。但这并不意味着“现实的”方案不能解决这些问题。

这些“人为”的方案的另一个优点是，它们使基本概念相对容易解释。作为对这一点的进一步说明:而不是解释CGH本身，我将使用一个由Maurer, Renner和Holenstein (MRH)提出的相同基本结果的公式。

一个签名方案

CGH-style 的反例的基本思想是构造一个“人为的”方案，这个方案在 ROM 中是安全的，但是当我们使用任何具体的函数“实例化”哈希函数时，它就完全崩溃了。

虽然 CGH 可以应用于许多不同类型的密码系统，在这个解释中，我们将使用一个相对简单的系统类型开始我们的例子: 一个数字签名方案。

你可能还记得本系列的前几章内容，一个普通的签名方案由三个算法组成: 密钥生成、签名和验证。密钥生成算法输出一个公钥和私钥。签名使用秘钥对消息进行签名，并输出签名。验证采用结果签名、公钥和消息，并确定签名是否有效: 如果签名检查出来，则输出“True” ，否则输出“False”。

传统上，我们要求签名方案(至少)在选择消息攻击(UF-CMA)下是不可伪造的。这意味着我们可以考虑一个高效的(多项式时间有限的)攻击者，他可以在选择的消息上要求签名，这些消息是由包含私钥签名密钥的“签名预言”生成的。我们对安全方案的期望是，即使给出了这种访问权限，也没有攻击者能够在一些他没有要求签名的新消息上签名，除非有极小的可能性。 

在解释了这些基本知识之后，让我们来讨论一下我们将如何使用签名。这将涉及以下几个步骤:

第一步: 从一些现有的安全签名方案入手。我们从哪个签名方案开始并不重要，只要我们可以假设它是安全的(根据上面描述的 UF-CMA 定义) ，这个现有的签名方案将用作我们要构建的新方案的构建块。我们将这个方案命名为 S。

步骤2: 我们将使用现有的方案 S 作为构建块来构建一个“新的”签名方案，我们将调用这个方案。构建这个新方案主要是将奇怪的花哨功能嫁接到原方案 S 的算法上。

步骤3: 接下来是详细的工作描述，我们认为它是完全安全的ROM。自从我们开始(假定)安全的签名方案后，这个论点主要归结为我们在上一步中的随机预言模型附加功能中添加的功能并不是可攻击的。

步骤4: 最后，我们将证明，当你使用任何具体的哈希函数实例化随机预言时，无论它看起来多么“安全” ，这种情况都是完全不存在的。简而言之，我们将展示如何用真正的哈希函数替换随机的预言，这里有一个简单的攻击方式，这种攻击总是能够成功地伪造签名。

欲知后事如何，请听下回分解！

参考及来源：https://blog.cryptographyengineering.com/2020/01/05/what-is-the-random-oracle-model-and-why-should-you-care-part-5/