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

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

atp7bkil 资讯 2020-04-04 09:30:00
1172315
收藏

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

本系列文章的译文:

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

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

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

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

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

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

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

实质问题

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

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

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

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

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

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

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

建立随机预言模型

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

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

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

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

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

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

回到 Delphia

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

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

    将 IV 设置为 1。

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

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

C1 = H(key || IV)       ⊕ M1

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

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

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

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

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

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

扫码支持

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

发表评论

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