随机预言模型(二)【转】

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()是伪随机的。但这确实是另一篇文章的主题。我选择这个例子是出于教学上的原因(很容易理解!),而不是因为它对随机预言分析的独特需要。