随机预言模型（二）【转】

calendar Aug 5, 2020 · 2 分钟 阅读 · cryptography

https://www.4hou.com/posts/E6Dv

本文翻译自：https://blog.cryptographyengineering.com/2011/10/08/what-is-random-oracle-model-and-why-2/如若转载，请注明原文地址

 

这是关于随机预言（Random Oracle）模型系列文章的第二部分。第一篇文章请参见“第一部分: 介绍”。

在之前的那篇文章中，我承诺要解释什么是随机预言模型，更重要的是，为什么你应该关心它。 我想我已经起了一个好的开头，但是我意识到我还没有回答其中的任何一个问题。

相反，我做了很多关于哈希函数的讨论。 我描述了一个理想的哈希函数应该是什么样的，即一个随机函数。 然后我花了大部分时间解释为什么随机函数是完全不切实际的(重述一下: 存储太大，计算太慢)。

最后，我们得出了以下结论: 随机函数当然可以构成很棒的哈希函数，但不幸的是我们不能在现实生活中使用它们。 尽管如此，如果我们不能通过任何其他方式获得安全性证明，那么假设一个哈希函数可以表现得像一个随机函数也许是有用的。 当然，当我们实际部署这个方案时，我们必须使用一个真正的哈希函数，比如 SHA 或 RIPEMD ——绝对不是随机函数——在这种情况下，我们的证明意味着什么还不清楚。

不过，这也不是完全没用。 如果我们能够完成这样一个安全性证明，我们至少可以排除“明显的”攻击(基于真正的方案设计者往往倾向于制造的那种小故障)。 对该方案的任何特定攻击基本上都与哈希函数的属性有关。 这仍然是一个很好的启发式方法。

正如你所看到的，这有点技术性，在文章的末尾会有一点技术性的结论。 如果你已经掌握了足够的背景知识，可以直接跳到本系列的下一篇文章，我将在这篇文章中介绍这个模型的使用(提示：所有现代的 RSA 签名和加密!) 以及它对密码学实践的意义。

实质问题

安全性证明通常考虑两个或多个当事方的交互，其中一方是就是我们的对手。 在一个典型的例子中，大多数玩家都是“诚实的” ，这意味着他们会按照一个明确的安全协议进行操作。 另一方面，对手可以为所欲为。 她的目标是破坏这个计划。

通常我们会详细说明各方将要玩的游戏。 对于加密方案，该游戏规则允许对手做能够在“真实世界”环境中可以做的事情。 例如: 她可能能够获得选择明文的加密和选择密文的解密。 在大多数情况下，她会拦截由一个诚实的加密器传输的合法密文。 通常她的目标是学习(关于)潜在的明文。

标准的做法是假设各方都知道方案或协议，包括如何计算使用的哈希函数。 这是一个常识性的假设，有时也被称为科克霍夫斯原理（Kerckhoffs 原理）。 此外，我们通常假设对手在某些方面是有限的——她没有无限的计算能力或时间，这意味着她不能暴力破解解密的密钥。

随机预言机模型中的安全性证明。 所有参与者(Encryptor、 Decryptor 和对手)都可以调用随机预言，后者为它们计算哈希函数并向所有参与者提供一致的响应。

为什么是预言？ 好吧，因为预言是团体的“外部”，所以它们不再需要携带一个描述的哈希函数，也不需要计算它的工作。 这很好，因为——正如我在前一篇文章中所提到的—— 对一个随机函数的完整描述大得离谱，因此计算时间也长得离谱。 通过把它放入预言模型，我们就可以把这些丑陋的东西抛掉。一个随机预言的安全性证明就是这样的，但是我们做了进一步的调整。 尽管每个人都被允许计算哈希函数，但是他们不能自己完成。 哈希是由一个叫做“预言”的新魔法团体完成的。 如果任何一方需要对某些内容进行哈希操作，他们需要将消息(通过一个虚构的安全通道)发送给预言模型，由 预言模型计算哈希并将其发回给他们。

我们将对随机预言设置两个限制。 首先，它必须实现一个真正的随机函数(在游戏开始时采样) ，具有与我们可能使用的实际哈希函数相同的输入 / 输出配置文件(例如，我们最终要使用 SHA256实现256位输出字符串)。

其次，预言给出的回答必须是一致的。 换句话说，就像通过 SHA1对“Peter Piper”进行哈希一样，总是会产生1c6244929dc8216f5c1024eebefb5cb73c378431 * 这个结果，无论是谁做的，通过随机预言发送给定的字符串都会产生相同的结果，无论哪一方要求它。

建立随机预言模型

关于如何建立随机预言模型，还有最后一个(而且是一种巧妙的)技巧。 在内部，一个随机预言只是实现了一个巨大的表，这个表将输入值映射到随机输出字符串。 既然如此，我们的安全性证明可以“懒惰地”填满这张表。 与其从填满整个表开始分析，不如从一个空表开始分析然后生成它，而不是从整个填满的表开始。它是这样工作的：

  1. 在游戏开始时，预言的表格是空的。

  2. 每当一方要求预言对消息进行哈希时，预言首先检查该输入值是否已存储在表中。

  3. 如果没有，则会生成一个随机输出字符串，将输入消息和新输出字符串存储在表中，并将输出字符串返回给调用方。

  4. 如果预言确实在表中找到了输入值，它将返回已经存储在表中的输出值。

如果稍微思考一下这个问题，你就会意识到，对于各方来说，这种方法“看起来”完全相同，就像是预言从一个完整的表开始。 但是它让我们的生活变得轻松了一点

回到 Delphia

在上一篇文章中，我提议用哈希函数 H() 建立一个流密码 。更具体地说，这个算法的一个版本可能看起来像下面这样:

  1. 随机选择一个密钥(比如128位长)，并与发送方和接收方共享。

将 IV 设置为 1。

  1. 将明文消息切割成等长的块 M1，…，MN，其中每个块的长度正好与哈希函数的输出长度相等。

  2. 使用 || 表示连接，使用 ⊕ 表示独有的 OR 操作,对消息进行加密，如下：

C1 = H(key || IV) ⊕ M1

C2 = H(key || IV+1) ⊕ M2

…

CN = H(key || IV+N) ⊕ MN

  1. 输出 (IV, C1, C2, ..., CN) 作为密文。

  2. 确保在加密下一条消息之前设置IV = (IV+N+1)。

如果你熟悉操作模式，你可能会注意到这个方案看起来很像CTR 模式 加密，只是我们使用的是哈希函数而不是块密码。

证明草图

假设我想证明这个方案在随机预言模型中是安全的，通常我们会使用“安全”的特定定义来处理真正的对手可以做的一些事情。 但由于本文是一篇博文，我们将使用以下简化的描述:

某个诚实的人——加密机——要加密一条消息。敌人会截获密文。如果敌人能够了解除文本长度之外的任何有关潜在明文的信息，那么他就“赢了”。

回想一下，我们处在神奇的随机预言模型中。 这就像现实世界一样，除了每当任何一方计算哈希函数 H()时，他实际上是在向预言发出一个调用，预言将使用一个随机函数来完成哈希过程的所有工作。 每个人都可以称为预言，即使是对手。

根据上面的方案描述，加密者首先选择一个随机密钥(步骤1)。 他把他的明文分成块(步骤2)。 对于每个块 i=1到 N，他查询预言以获得 H(key || i) 。 最后，他用纯文本块(步骤3)对接收到的哈希表进行 XOR 操作，并发送密文(C1，... ，CN)以便敌方拦截(步骤4)。

我们现在可以做以下观察:

1. 在内部，预言从一个空表开始。

2. “每次预言从加密器收到一个新的表单查询，它都会为输出值产生一个新的完全随机的字符串表示输出值。 它将输入和输出都存储在表中，并将输出发送回加密器。

3. 加密器使用这些随机字符串中的某一个对每个消息块进行 XOR 操作，从而形成密文块(C1，... ，CN)。

4. 加密机从来不会对相同的输入字符串请求两次，因为IV总是递增的。最后，我们做一个最重要的观察:

5. 使用完全随机的密钥字符串是一种非常有效的加密方法。事实上，它是一次性的，只要对手不知道随机字符串，结果的密文本身就是随机分布的，因此不会显示关于底层消息的任何信息(除了它的长度)。

根据观察(5)，我们所要做的就是证明当预言对“key || i”进行哈希时返回的值是(a)每个返回值都是完全随机的，并且(b)对手不了解这些返回值。如果我们能做到这一点，那么我们就能保证密文(C1，…，CN)将是一个随机字符串，而对手对底层明文一无所知!

最终分析

上面的演示(a)部分是很简单的。当加密器要求预言计算H(key || i)，前提是以前没有要求这个值，那么预言将生成一个完全随机的字符串——在预言如何工作的定义中都有详细说明。而且，加密器从来不会对相同的输入值请求两次，因为它总是更新它的IV值。

(b)部分稍微难一点。有没有什么方法可以让对手知道即使是i从1到N的一个值H(key|| i)的预言输出？预言不会将它的表公开，而且对手无法“侦听”加密器发出的哈希调用。

再仔细想想，你会发现对手也可以通过一种方法来学习这些字符串:她也可以查询预言。具体来说，她所要做的就是在“key|| i”上查询任何1 <= i <= N的预言，她将得到加密器用于加密密文的一个字符串。如果对手掌握了这些字符串中的一个，她可以很容易地恢复(至少部分恢复)明文，我们的论证就不再有效了。

这里有一个明显的问题，至少从对手的角度来看: 她不知道钥匙。

因此，为了在“key || i”上查询，对手必须猜测密钥。 每次她向预言提交一个猜测“guess || i”时，她要么是错的——在这种情况下，她得到的是一个无用的随机字符串。 或者她是对的，在这种情况下，我们的计划将不再安全。

但是对我们来说幸运的是，密钥是随机的，而且相当大(128位)。 这告诉了我们一些关于对手成功概率的信息。

具体来说: 如果她只做了一个猜测，那么她猜对正确的密钥的概率是相当小的: 可能的密钥数中的一个。 对于我们的具体例子来说，她的成功概率是1/(2^128) ，这是个天文数字。 当然，她可以尝试多次猜测; 当然，她可以试着猜测不止一次;如果是q，那么成功概率上升到q/(2^128)。

我们开始时的基本假设是，对手的计算能力有限。 这意味着她只能执行一定数量的哈希。 在正式的安全性证明中，我们可以使用多项式和指数时间。 但是，与其这样做，不如让我们插入一些具体的数字。

假设对手只有时间计算2^40(1.1万亿)哈希值。 假设我们使用了一个128位的密钥，那么她猜测密钥的概率最多是(2 ^ 40) / (2 ^ 128)1 / (2 ^ 88)。 这仍然是一个相当小的数字。

你认为在现实世界中对手能够计算超过2^40的哈希值吗？ 没问题。代入你自己的数字——计算保持不变。如果你认为这个方案不够安全，你可以尝试让密钥变长。

这里的要点是，我们已经证明了在随机预言模型中，上面的方案“与密钥一样安全”。**换句话说，对手攻击该方案的最大希望是通过暴力猜解的方式找到密钥。只要密钥足够大，我们就可以有把握地得出这样一个“现实的”结论，即对手知道信息的概率很低，或者至少是可以计算的。

总结

根据你的观点，这可能看起来有点技术性。 或者不是。 无论如何，这绝对超出了我在前一篇文章中所承诺的“外行人的介绍”。 此外，它还不够专业，因为它没有捕捉到密码学家在使用随机预言模型时可以“欺骗”的所有方法。 ***

在下一篇文章中，我将尽我最大的努力来解决这个问题，在这篇文章中，我们将讨论一些关于随机预言模型中证明的实际方案，以及——更重要的是——为什么密码学家愿意忍受这种事情。

备注：

  • 这个结果来自一个不可信的 SHA1在线计算器。 YMMV.

* * 当然，在一个真正的证明中，我们会更加正式，我们也会考虑这样一种可能性，即对手至少能够获得一些选定明文的加密。 这将在我们使用的安全游戏中被捕获。

*** 有些人可能会注意到，我并不需要将哈希函数建模为随机预言来实现这个示例。如果我调用了一个密钥哈希函数，我可能会使用一个较弱的假设(在本例中，弱是好的!)，即H()是伪随机的。但这确实是另一篇文章的主题。我选择这个例子是出于教学上的原因(很容易理解!)，而不是因为它对随机预言分析的独特需要。