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

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

本文翻译自:​https://blog.cryptographyengineering.com/2011/09/29/what-is-random-oracle-model-and-why-3/如若转载,请注明原文地址

 

碰巧我今天计划教一门关于可证明安全的课程,还有一门叫做“随机预言模型(Random Oracle Model)”的课程。 在整理我的想法的时候,我突然想到: a)这个主题可能会引起那些不是我的研究生的人的兴趣; b)对于这个知识点似乎还没有一个好的给“外行人”学习的介绍文章。 在大多数情况下,我喜欢谈论加密是如何实现的。 但是,如果你从不安全的原语开始,那么实现就无关紧要了。

因此,冒着疏远我那些微不足道的读者群的风险,我打算暂停一下我们定期安排的“密码系统是如何变坏的”编程内容,来谈谈这个学究般的话题——正如我们稍后会看到的,这本身就是密码如何变坏的另一种味道。

傻瓜式哈希函数

在我们讨论随机预言之前,我们首先需要讨论哈希函数。 这些函数接受(可能)长的输入,并将输入经“哈希”处理得到固定大小的值,我们称之为“消息摘要”。

我们在密码学中经常使用哈希函数。 在数字签名方案中,它们的出现受到了极大的关注,但也出现在许多加密方案中。 事实上,在整个球场上,扔一块石头而没有接触到它则是很难的事情。

在大多数情况下,密码哈希函数必须至少满足以下一些属性。 首先,我们希望它是“单向的” ,这意味着很难“颠倒”函数,也就是说,只给出一个消息摘要就可以找到原始消息。

其次,哈希函数应该是“防碰撞”的。 换句话说,应该很难找到两个不同的消息(M,M’) ,也就是Hash(M) == Hash(M’)。 此属性对于数字签名非常重要,因为我们通常不直接对消息签名,而是对消息的哈希进行签名。 如果攻击者能够找到两个哈希值相同的消息,那么一个消息上的签名(哈希)也就是另一个消息上的签名。 实际上,这可能会导致不好的后果。

有时候我们对哈希函数的要求甚至更高。 棘手的部分是知道我们还能要求多少。 为了说明这一点,让我先举一个例子。

Delphia 中的加密技术

想象一下你生活在 Delphia,一个禁止所有加密算法的国家。 尽管如此,你还是有秘密要保守。 你注意到你的政府并没有禁止哈希函数。 这给了你一个想法: 也许你可以从哈希函数中‘黑掉’一个加密方案。

这并不疯狂。 许多哈希算法的输出看起来非常随机。 也许你可以使用哈希函数来构建流密码。 基本上,你将使用一个哈希函数来哈希一个秘密密钥(以及某种计数器值) ; 这将产生一个“随机查找”的字节流,然后你可以使用明文进行 XOR。

问题是: “单向”和“防碰撞”哈希函数是否足以确保该方案是安全的? 我给你一个直截了当的提示: 否。 从技术上讲,这两个属性都不意味着哈希函数的输出是“随机查找”的。 你可以设想满足这些保证的哈希函数,但是产生的输出对于构建流密码毫无用处(比如,它们可能包含由可预测值组成的长字符串)。 如果你使用这些来构建密码,那么你将非常失望。

球形马

当密码学家第一次开始思考类似上面的问题时,他们的问题是他们想从“理想”哈希函数中得到什么。 对于一位数学家来说,答案显而易见。 他们希望它表现得像一个随机函数。 这个术语有一个非常具体的数学定义; 为了这次讨论的目的,我们将使用一个更容易讨论的等价术语。

假设我们想要实现一个理想的哈希函数。 与其设计一个使用混淆与扩散的小算法(就像我们对大多数真正的哈希函数所做的那样) ,我们还不如创建一个大的硬编码表。 该表的某一列中包含输入消息,另一列中包含相应的输出。

关于这个表,重要的是每个输出值都是一个独立的随机字符串。

       Input (binary)                  Output                      
       0                               Totally random bitstring 1
       1                               Totally random bitstring 2
       00                              Totally random bitstring 3
       01                              Totally random bitstring 4
       10                              Totally random bitstring 5
       11                              Totally random bitstring 6
       ...

显然,一个有用的哈希函数的完整表非常的大。 有多大呢? 好吧, SHA1 最多可以接受长度为2 ^ 64字节的消息。 所以答案是: 太大了,这篇博文都放不下。 事实上,整个表格中的条目比宇宙中原子的数量还要多。

即使我们有足够的空间存储这样一个表,查找输入并找到输出的哈希过程也会非常耗时。 如果我们将哈希表存储在图灵机的磁带上(quintisdential 计算机) ,那么仅仅将磁带头移动到正确的位置(平均而言)就需要一系列的时间步骤,这些步骤与输入的大小呈指数级增长。

当我在我的入门课程中提到这些的时候,一些雄心勃勃的学生试图想出一个聪明的方法,把桌子缩小成我们可以随身携带的东西。 但问题是: 输出字符串的集合是完全随机的。 找到一种在紧凑哈希中表示它们的方法就相当于压缩随机数据。 不幸的是,信息理论告诉我们,这是一大禁忌。

双倍下注

让我们来盘点一下。 到目前为止,我希望我至少说服了你两件事。 首先,密码学家希望他们的哈希函数表现得像随机函数。

其次,“真正的”哈希函数不可能是随机函数,因为那是完全不可行和不切实际的。 如果你看看 SHA1、 SHA512和 RIPEMD160等实用的哈希函数——所有这些函数都有漂亮的、简短的实现,由几个 KB 的代码组成——很明显,不管输出看起来多么’随机’ ,它们都不是随机函数。

马萨诸塞州,剑桥,上午10:35

那么,如果我们在实践中不能使用随机函数,那么有没有另一种方法呢? 也许我们可以将哈希函数建模为随机函数,仅仅为了安全证明的目的。 然后在现实生活中,我们可以用 SHA 或 RIPEMD 或者一些实用的哈希函数来代替。 现在还不能完全确定安全证明是否还有意义,但至少我们可以做点什么。

我将描述好莱坞所呈现的一个场景: 麻省理工学院一间灯光不切实际的办公室。 由 Steve Buscemi 扮演的著名密码学家,刚刚提出将哈希函数建模为随机函数。 他的同事,由凯特 · 温斯莱特扮演,直截了当地告诉了他:

“我做不到,”她解释道,并且悲伤地摇了摇着头,“评估一个随机函数不仅仅是不方便的,还要花上指数级的时间进行计算。 如果我们允许在我们的安全证明中使用这种哈希方法,那么我们将不得不让各方(包括对手)以指数级的时间步长运行。 但我们不能这么做。 我们的整个安全证明是基于这样的想法,即各方只能执行有限的计算,特别是那些可以在多项式时间进行的计算。 如果让各方以指数级的方式进行任意的计算,那么对手可以做任何事情: 他甚至可以暴力破解密钥。”

(好莱坞可能会加强这个对话。)

这个突破来自一个路过的看门人(马特 · 达蒙,重演了他在《心灵捕手》中的角色) : “如果你只是创造一个虚构的世界,其中每个人都被限制在多项式时间的计算上,但哈希方法有一个特殊的例外。 仅仅使用哈希表,根本不需要花费任何时间。 当你试图解决问题的时候,时钟就停止了。”

一个范式

这就是我们现在的处境。 完美哈希是一个随机函数。 但是,随机函数是不切实际的——我们不能在现实生活中使用它们,甚至不能在我们的安全证明中使用它们而不破坏它们。

密码学家是很顽固的人,我们有很好的想象力。 因此,我们想出了一个白日梦,一种假装随机函数是实用的方法——只是为了证明我们的安全性。

这个白日梦的含义既美妙又可怕。 一方面,它允许我们证明那些不能用其他方法证明的方案的安全性。 此外,我们可以非常有效地做到这一点。 另一方面,它导致的安全证明,在技术意义上,是完全没有意义的。

毕竟,我们最终将不得不用一个真正的哈希函数来实现这个方案,比如 SHA,它决不是随机的。 那么一个随机预言安全证明能给我们带来什么呢? 这是自从这个想法产生以来困扰密码学家的一个大问题。

如果你认为这完全是学术性的,那你就错了。 该模型给出了一些应用最广泛的密码原语的安全证明: 包括大多数 RSA 签名和加密,以及 DSA 所基于的 Elgamal 签名方案。

如果你没有从这篇文章中得到任何其他的东西,你应该注意到上面列出的计划是非常重要的事情。 如果我们在做一些有趣的安全证明,人们应该明白它是什么。

在我的下一篇文章中,我将解释什么是“随机预言” ,以及它是如何与我们上面做出的疯狂假设相联系的。 我还将解释我们如何在这个模型中证明事物,并讨论为什么密码学家如此热衷于讨厌它。