你必须知道的密码学理论:随机预言模型(一) - 嘶吼 RoarTalk – 网络安全行业综合服务平台,4hou.com

你必须知道的密码学理论:随机预言模型(一)

atp7bkil 资讯 2020-03-28 10:10:00
966153
收藏

导语:这是随机预言模型系列文章中的第一篇。 对于某些人来说,这可能有点不靠谱,所以如果你对可证明安全不感兴趣,没问题。 一旦我把它从我的博客中删除,我会发布更多关于软件和物理安全的内容。

Pythia.jpg

这是随机预言模型系列文章中的第一篇。 对于某些人来说,这可能有点不靠谱,所以如果你对可证明安全不感兴趣,没问题。 一旦我把它从我的博客中删除,我会发布更多关于软件和物理安全的内容。

碰巧我今天计划教一门关于可证明安全的课程,还有一门叫做“随机预言模型(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 签名方案。

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

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

关于本系列的下一篇文章,请点击这里

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

感谢您的支持,我会继续努力的!

扫码支持

打开微信扫一扫后点击右上角即可分享哟

发表评论

 
本站4hou.com,所使用的字体和图片文字等素材部分来源于原作者或互联网共享平台。如使用任何字体和图片文字有侵犯其版权所有方的,嘶吼将配合联系原作者核实,并做出删除处理。
©2024 北京嘶吼文化传媒有限公司 京ICP备16063439号-1 本站由 提供云计算服务