什么是“随机Oracle模型”？为什么有争议？

#1 楼

以下模型描述了一个随机预言机：


有一个黑匣子。盒子里有一个侏儒，里面有一本大书和一些骰子。
我们可以在盒子里输入一些数据（任意序列）。
给出一些他事先没有看到的输入， gnome使用他的骰子在某些常规空间（oracle输出空间）中均匀且随机地生成新输出。 gnome还会在他的书中写下输入和新生成的输出。
如果给出了已经看到的输入，则gnome将使用他的书来恢复他上次返回的输出，然后再次返回。 >
所以随机预言就像是一种哈希函数，因此我们对给定输入消息$ m $所获得的输出一无所知，直到我们实际尝试$ m $为止。这是用于安全证明的有用工具，因为它们可以根据对oracle的调用次数来表达攻击的努力。一个真正的“随机”甲骨文。首先，没有证据表明不使用gnome就能真正存在随机预言。然后，我们可以看看候选对象是什么：哈希函数。安全散列函数旨在抵抗冲突，原像和第二原像。这些属性并不意味着该函数是随机预言。

实际上，请参见SHA-256（或SHA-512，如果需要）。它遭受了一种称为“长度扩展攻击”的问题。这是来自Merkle–Damgård构造的伪像：为对消息$ m $进行哈希处理，首先将消息拆分为固定大小的块（对于SHA-256为64字节），最后一个块填充有一些比特，包括长度$ m $，以及一些1和0，这样我们最后得到一个完整的块。然后在运行状态下处理每个块，哈希输出是最后一个块值。

因此，假设有一条消息$ m $，我不知道，但是我知道$ m $的长度及其哈希值$ h（m）$。有了这些信息，我就可以重建添加的填充位（我们称它们为$ \ pi $）。然后，我可以设想消息$ m'$：
$$ m'= m || \ pi ||对于我任意选择的某个值$ x $ x $$
。然后，我知道$ h（m'）$的计算将从拆分$ m ||开始。 \ pi $放入块中并进行处理，并且在处理完$ \ pi $的最后一位之后，当前的“运行状态”将恰好是$ h（m）$。因此，如果我知道$ h（m）$，我可以从那里获取$ h（m'）$来完成计算，而我却不知道$ m $就可以这样做。特别是，我最终得到了$ h（m'）$，而没有将$ m'$呈现给gnome。

此属性证明SHA-256不是随机的Oracle。但是，它绝不危害SHA-256对碰撞或原像的抵抗力。因此，作为随机预言似乎比作为安全散列函数要严格得多。具有以下含义：可以构建病理签名和非对称加密方案，当它们在内部使用随机预言机时是安全的，但是每当使用实际的可计算功能而不是神话般的开箱即用时，它们都是不安全的。

摘要：随机oracle模型中的证明很好，但其完整性还不足以覆盖实际的实现：我们知道，将用来代替随机oracle的任何函数都不会是随机oracle ;因此，安全性是基于强烈的希望，即实际功能不是随机预言的部件不会影响安全性。这证明了一点不信任。尽管如此，随机预言模型中的证明总比没有证明要好得多。

#2 楼

熊描述了一种用于选择和计算一个统一的随机函数的过程，该函数涉及盒中的侏儒，但这并没有真正说明在证明安全性降低的情况下随机预言模型是什么。共有三个部分：统一随机函数，由哈希函数构建的密码系统和随机预言证明。


统一随机函数。可能的结果{1,2,3,4,5,6}。当结果是公平的掷骰时，结果的均等概率为1/6，在这种情况下，我们称分布为均匀。对于任何有限集可能的结果。

我们还可以对$ t $位到$ h $位函数$ H \ colon \ {0,1 \} ^ t \ to \ { 0,1 \} ^ h $。函数的空间是一个有限集：您可以根据输入的$ t $位，为$ h $位输出的每一位写下一个有限的真值表，因此正好有$（2 ^ h）^ {2 ^ t} $个这样的函数；在均匀分布中，每个函数具有相等的概率$ 1 /（2 ^ h）^ {2 ^ t} $。

随机地均匀选择该函数的一种方法是在巴别塔（Babel）并选择一本有$ 2 ^ t $页的书，每页上都有一个$ h $位的字符串，因此页面$ x $的内容为$ H（x）$。另一种方法是将一个侏儒装在一个装有硬币和一本空着$ 2 ^ t $页的书的盒子里。因此，当您请求侏儒输入$ x $时，侏儒会查询书中的页面$ x $，如果它为空，则将硬币$ h $翻转一次并记下结果。另一种方法是自己动手硬币$ h 2 ^ t $次，并写下一个巨大的真值表。

但是，对于任何特定功能$ f \ colon \ {0,1 \} ^ t，您随机地统一选择函数$ H $，无论是通过像文明人一样随机浏览库，还是通过像野蛮熊一样奴役地精\ to \ {0,1 \} ^ h $，获得该功能的概率$ \ Pr [H = f] $为$ 1 /（2 ^ h）^ {2 ^ t} $。另一种表达方式是，对于任何特定的输入$ x $和输出$ y $，$ \ Pr [H（x）= y] = 1/2 ^ h $-每个不同输入的值都是独立的，因此$ \ Pr [H（x_1）= y_1，\ dots，H（x_ \ ell）= y_ \ ell] = 1/2 ^ {h \ ell} $如果$（x_1，\ dots，x_ \ ell）$是全部不同。此属性使统一随机函数的模型易于推理。


基于哈希函数构建的密码系统。
一些密码系统是根据哈希函数定义的。例如，RSA-FDH（全域散列）将散列函数$ H $用于公钥签名：


公钥是一个大整数$ n $。 >消息$ m $上的签名是整数$ s $，因此$$ s ^ 3 \ equiv H（m）\ pmod n。$$

要进行签名，谁知道方程式$ 3 d的秘密解$ d $ \ equiv 1 \ pmod {\ lambda（n）}，$$计算$$ s：= H（m）^ d \ bmod n。$$


在签名中使用哈希对安全至关重要，正如Rabin在1979年首次观察到的[1]：如果我们改为使用签名方程$ s ^ 3 \ equiv m \ pmod n $，那么任何人都可以立即在消息0上伪造签名0，或者采用两个消息/签名对$（m_0，s_0）$和$（m_1，s_1）$伪造第三美元（m_0 m_1 \ bmod n，s_0 s_1 \ bmod n）$，或在任何整数立方体$ m $上伪造签名$ \ sqrt [3] {m} $，等等。

公式用$ H $表示，所以您可以编写一个以$ H $作为参数来计算密码系统各个部分的过程ll其他：

def sign(H, n, d, m):
    s = modexp(H(m), d, n)
    return s
def verify(H, n, m, s):
    return modexp(s, 3, n) == H(m)

我们需要$ H $有哪些属性？通常是原像抗性，抗碰撞性等的某种组合。对于均匀的随机函数，找到原像或发现碰撞的预期成本很高。我们可以想象将一个侏儒奴役在一个盒子里，然后使用sign(gnomebox, n, d, m)和verify(gnomebox, n, m, s)：功能，因此我们需要每个人共享相同的gnome。共享侏儒并不是通过互联网进行交易的可扩展方式，这是资本主义不选择依靠这种特定奴隶制来集中财富的唯一原因。
当我们实际使用时这个密码系统，我们同意通过，比方说，SHAKE128-2047为$ H $，当我们选择了$ n $的是2048位长：s = sign(shake128_2047, n, d, m)，verify(shake128_2047, n, m, s)

当我们使用一个特定的哈希函数像SHAKE128与$ s ^ e \ equiv H（m）\ pmod n $之类的特殊奇特数学一起，散列函数原则上可以以破坏安全性的方式与奇特数学交互，但是我们选择的哈希函数已针对很多年的时间来使人确信它除了评估便宜外没有其他有用的属性，即使它确实具有不良的交互作用或不良的属性-例如，因为我们使用了SHAKE128，但是精美的数学运算内部使用了Keccak排列的逆函数由于某种原因，或者因为我们将MD5用作$ H $，我们可以交换不同的哈希函数

如果我们错误地选择了散列函数，则可能会根据散列函数的选择进行简单的攻击，例如计算$ H（m \ mathbin \ | m'）$给出了$ H（m）$而不是$ m $，从而伪造了带有未知前缀的消息散列，或者像发现MD5冲突那样破坏了伊朗的核计划。但是也可能存在不依赖于哈希函数选择的攻击。关于加密系统的其余部分，我们能否大致说些什么？


随机Oracle证明。
为了使人相信伪造签名很难，我们证明了伪造器可以用作子例程来解决RSA问题，并为统一的随机$反转$ x \ mapsto x ^ 3 \ bmod n $ x $。我们认为解决RSA问题很困难。因此，如果可以使用伪造者来解决RSA问题，那么伪造就比解决RSA问题要容易得多。

具体地说，我们为伪造者提供了$ H $的公钥访问权限，以及在伪造者选择的任何消息上返回签名的签名Oracle：

book = {}
def gnomebox(m):
    if m not in book:
        book[m] = random(2**h)
    return book[m]

这里我们显然会将lambda m: sign(H, n, d, m)传递为$ S $;关键是伪造者只能调用签名的预言家$ S $，而不能检查它或查看秘密密钥$ d $是什么。在给定(m, s) = forge(H, n, S)的情况下，结果消息和签名对通过verify(H, n, m, s)，但要受以下限制：$ m $不能传递给签名oracle $ S $。 （否则，伪造者可以通过向$ S $要求在消息上签名并返回该伪造者来获胜，这不会给任何人以伪造的方法打动。）显然，伪造者可能会通过随机猜测一个签名而获胜，该签名具有给出非常小的但非零的成功概率。

给出这样的伪造方法，我们将展示如何以可比较的成功概率计算以$ n $为模的立方根：具体来说，是使用cbrt作为子例程，如果forge则获胜。假设伪造者最多对散列的oracle $ H $或签名的oracle $ S $进行$ q $查询。

我们将为伪造者制作特制的散列和签名的oracle。使用：它们将经过特殊设计以让我们提取RSA问题解决方案，但是我们构造的哈希Oracle仍然具有统一的分布，并且我们构造的签名Oracle仍然为使用特制哈希Oracle实例化的密码系统生成有效的签名。 />

def forge(H, n, S):
   ... S(m0) ... S(m1) ...
   return (m, s)

（此过程是Mihir Bellare和Phil Rogaway [2]，定理3.1的RSA-FDH安全性的标准证明。）

当伪造者返回尝试进行伪造时$（m，s）$，则很有可能会将$ m $传递给哈希；有$ 1 / q $概率是对散列的$ j ^ {\ mathit {th}} $查询，在这种情况下，我们从精心设计的散列中返回了$ y $；那么如果伪造者成功了，我们就会希望$ s ^ 3 \ equiv y \ pmod n $。

当然，伪造者偶然地偶然偶然地成功伪造的机会很小，另一条消息被馈送到散列预言机，但是发生的概率为$ 1 / n $，这非常非常非常非常小。还有一个机会，我们的多维数据集根过程可能会在没有伪造者帮助的情况下偶然碰到成功的立方体根，但是同样，伪造者的每个查询的概率为$ 1 / n $，这非常非常非常非常小。 br />因此，如果伪造者的成功概率为$ \ varepsilon $，则我们的立方根过程的成功概率约为$ \ varepsilon / q $，而对modexp(cbrt(n, y), 3, n) == y的更多调用需要一些额外的计算。这表明，如果有一种廉价的算法可以使用$ q $ oracle查询来计算伪造品，那么就有一种算法可以解决RSA问题，其花费仅为$ q $倍。 br />
这是一个特别简单的ROM证明；其他人则使用更复杂的技术，例如分叉引理，在该算法中，我们以相同的随机选择重新运行对手的算法，但是使用了不同的预言片[3]。 ？
实际上，这没有争议：只有象牙塔中的学术密码学家才对此担心，而从业人员几十年来一直使用基于ROM的密码系统而没有任何麻烦。像MD5这样的哈希函数已经变质，允许发生碰撞，并且Merkle-Damgåard结构允许长度扩展，但是这些问题在非RO证明中同样引起问题。那么他们的反对是什么呢？

很容易得出以下结论：如果我们使用特定的哈希函数（例如SHAKE128）实例化它，只要该哈希函数没有被严重破坏。


显然，如上所述，我们可以设计一个密码系统，如果您可以使用SHAKE128实例化它，但是如果您使用几乎任何其他哈希函数实例化它，都可以正常工作。 Ran Canetti，Oded Goldreich和Shai Halevi在学术上证明了非常可爱的结果：在随机预言模型中存在一个安全的签名方案，这意味着上面有一个随机预言证明，显示了如何将伪造者转化为算法来解决某些问题。这个难题很棘手，但是用任何实际的实例化方法都是不安全的[4]。



使用密匙$ \ mathit {sk} $，



签署消息$ m $如果$ m $的形式为$（i，\ pi）$，其中$ \ pi $是$（i，H（i））$在$ i ^ {\ mathit {th}的图中的证明} $多项式时间函数中的某些枚举，*则签名为$（\ mathit {sk}，S_ \ mathit {sk}（m））$。 （这样的证明可以在多项式时间内进行验证。）否则，签名为$（\ bot，S _ {\ mathit {sk}}（m））$。


要验证公用密钥$ \ mathit {pk} $下消息$ m $的签名$（z，s）$，请计算$ V _ {\ mathit {pk}}（s，m）$ 。 （我们忽略$ z $，它仅用作后门。）

可以证明该签名方案在随机oracle模型中是安全的，因为$（i，H（i））$实际上位于$ i ^ {\ mathit {th}} $多项式时间函数图中的概率对于统一的随机$ H $，它们的任何特定枚举都可以忽略不计，但是，如果您为$ H $选择任何特定的函数族，则很容易构造后门消息，只需在其中使用其索引就可以转储私钥枚举。

这是一种复杂性理论的技巧，旨在设计一种病理签名方案，如果尝试在现实世界中实例化它，则会发脾气。通过反例，Canetti–Goldreich–Halevi方案显示的是，我们想得出的推论在形式上是无效的。

有人可能会推断，有一些技术标准可将此类病理反例与实际上为实际使用而设计的多种基于ROM的协议，例如RSA-FDH，RSA-KEM，RSA-OAEP，RSA-PSS，DH密钥协议等。

一些学者选择离开基于此反例，在垃圾箱中建立了随机的oracle模型，并着重于寻找将对（例如）签名方案的攻击转换为对散列函数的原图像或碰撞攻击的方法，或者找到通过极端扭曲完全避免散列函数的系统-在被动攻击性措辞中被称为“标准模型”的设置，为随机预言模型及其从业者蒙上阴影。这给证明技术的复杂性和由此产生的密码系统的效率带来了可观的代价，无论它们在多大程度上表达出他们的感受，这种情况很少出现在学术期刊和会议论文集之外[5] [6] [7] [8 ]。

另一方面，这并不意味着随机预言证明在实践中毫无用处。带有随机预言的协议在现实世界中大获成功，以至于几乎实践中使用的每个公钥密码系统都利用了它们-作为一种设计原理，它们在抵御历史上第一个安全签名方案的攻击方面非常有效[1]到现代Diffie-Hellman安全性[9]。确实，我们不仅没有理由怀疑RSA-FDH在其存在的四分之一世纪中在实践中的安全性。 ，但很难想象$ q $-查询伪造实际上比解决RSA问题的算法便宜$ q $，因为签名散列符$（h_i {h_i} ^ d \ bmod n）$，与任何人都可以在没有签名预言的情况下计算出的数量分布完全相同，并且由于哈希预言与密钥无关。这表明我们在进行形式化的尝试中可能出了些问题。例如：


没有像SHA3-256 [10] [11]这样的固定哈希函数的抗冲突性形式化。在257位输出上，肯定会发生一些冲突$ x_0 \ ne x_1 $，因此有一种非常便宜的算法可以打印冲突：它简单地打印$（x_0，x_1）$。但是我们不知道如何找到它而不花费精力来计算SHA3-256的预期$ 2 ^ {128} $评估。
几乎肯定有一个128位的字符串$ s $，这样$ E \ mapsto \ operatorname {MD5}（s \ mathbin \ | E（0）\ mathbin \ | E（1））$的第一位就很高-E的优势区分符，来自统一随机置换$ E $ [12]的统一随机密钥$ k $下的$ E = \ operatorname {AES} _k $，这违反了关于AES的PRP优势界限的大多数推断的前提，例如在实践中证明使用AES-GCM是合理的。但是我们不知道如何在不花大量精力的情况下找到$ s $。在实践中，它们也不应该阻止将随机预言机用作设计原则，也不能证明基本上拒绝所有公钥加密都是合理的。


*还有更多技术细节：实际上我们在工作在渐近设置中，一切都由输入大小来参数化，我们考虑由种子作为键并由输入大小进行索引的函数族，并枚举由某些超多项式代价所限制的函数，等等。如果您需要有兴趣。

评论

---

$ \ begingroup $
我发现这一点特别有用：“如果我们对哈希函数的选择不正确，则可能会根据哈希函数的选择进行简单的攻击，但也有可能并非如此。取决于哈希函数的选择。关于加密系统的其余部分，我们能否大体说一句？”
$ \ endgroup $
–路易斯·卡西利亚斯（Luis Casillas）
19年5月17日在21:42

---

$ \ begingroup $
非常有用的答案！我还建议贝勒（Bellare）等人撰写的“ UCE”论文。还有Jost和Maurer的“上下文限制不可区分性”。他们是很好的资源，讨论了不可能结果与基于ROM的“现实世界”构造的明显安全性之间的桥梁。
$ \ endgroup $
– Marc Ilunga
19年5月18日，0：53

---