弱电阻和强电阻之间有什么区别？

Question

弱电阻和强电阻之间有什么区别？

49

我读了一些关于强碰撞抵抗和弱碰撞抵抗的文章，但是我无法理解它们之间的区别。我唯一能理解的就是，具有弱碰撞抵抗性的哈希函数中发生碰撞的概率较低，而在具有强碰撞抵抗性的哈希函数中发生碰撞的概率较高。我无法理解这些参数的实际意义。请问有人可以帮助解答吗？

- phoxis

1

接受的答案并不完全正确。请参见下面的答案：https://dev59.com/a2oy5IYBdhLWcg3wfOB4#52957495 - kelalaka

3个回答

12

我写这篇答案是因为Alexander的评论; 所有定义都来自于P. Rogaway和T. Shrimpton的Cryptographic Hash-Function Basics: Definitions, Implications, and Separations for Preimage Resistance, Second-Preimage Resistance, and Collision Resistance。

- 预像抗性 - 对于基本上所有预先指定的输出，找到任何散列到该输出的输入是计算上不可行的，即找到任何预像x'使得当给定任何没有已知相应输入的y时，h(x')=y。 - 第二像抗性，弱碰撞 - 计算上不可能找到任何第二个输入与任何指定输入具有相同的输出，即给定x，找到一个2nd-preimage x' != x，使得h(x) = h(x')。 - 碰撞抗性，强碰撞 - 计算上不可能找到任何两个不同的输入x，x'，它们散列到相同的输出，即h(x) = h(x')。

事实1：碰撞抗性暗示了哈希函数的第二像抗性。

事实2：第二像抗性意味着预像抗性。

正如亚历山大所指出的，根据鸽笼原理，在哈希函数的输出空间小于输入空间时，冲突是不可避免的。

- kelalaka

1

如果时间不够用，请阅读以下摘要：

强碰撞抗性 => 找不到任何两个值X, Y，使它们的哈希值相同
弱碰撞抗性 => 给定一个特定的X, 找不到任何Y，使它们的哈希值相同

以文件哈希（SHA256）为例：

你找到两个具有相同SHA256哈希的任意文件 => 你刚刚破解了SHA256的强碰撞抗性
有人给你一个特定的文件（但你事先不知道是哪一个），然后你找到另一个具有与给定文件相同的SHA256哈希的文件 => 你刚刚破解了SHA256的弱碰撞抗性

哪个更容易被破坏，而且“破坏”后会更糟糕？

破坏弱碰撞抗性比破坏强碰撞抗性更为严重。

例如，您从互联网上下载一个文件，并希望证明它没有被篡改。假设您知道该文件的SHA256哈希值，您只需下载文件，对其进行哈希运算，并将结果与您所知道的文件应该具有的哈希值进行比较。如果它们匹配，则文件是安全的；如果不匹配，则文件已被篡改。

现在，如果有人破解了SHA256的强碰撞抗性，这意味着他们只是找到了任意两个具有相同哈希值的文件，但这两个文件中任何一个与您希望的文件相同的概率极小，因此对于攻击者来说并没有什么用处。

但是，如果有人破坏了弱碰撞抗性，这意味着他们可以生成另一个与您要下载的文件具有完全相同哈希值的文件。这将使攻击者能够用他篡改过的文件替换您要下载的文件，而您永远不会注意到，因为它们的哈希值相同。

听起来很可怕，对吧？确实如此！但并非一切（立即）都完蛋了，即使弱碰撞抵抗性被破解。虽然攻击者可以生成另一个具有相同哈希值的文件，但弱碰撞抵抗性并不能说明该文件是“有效”的文件。例如，如果你正在下载一个Python脚本，攻击者可能能够生成另一个二进制块，其哈希与你的Python脚本相同，但它不是一个有效的Python脚本，在Python解释器运行时会出错。

从“能够生成一个具有与我们的Python脚本相同哈希值的二进制块”到“能够生成另一个具有与我们的Python脚本相同哈希值的有效Python脚本”，需要更多的计算工作量。即便如此，这也不能说明它是一个能够窃取数据或进行一些邪恶操作的Python脚本。这需要更多的计算工作量。

所以，即使弱碰撞抵抗在将来的某个时候被破解了，用一句著名电影的台词来说，“不太好，也不太糟”，但这仅适用于“现在”。如果长时间放置不管（这给对手更多时间来改进他们的碰撞查找算法和/或更多计算时间来暴力破解正确的恶意输入），情况将变得非常糟糕。此外，这在很大程度上取决于破损的哈希函数用于何种目的以及最终应用程序对输入的验证程度。例如，在我们的Python脚本下载示例中，我们只是因为Python解释器不接受随机二进制数据块而得以保存，这并不是一个强大的安全保证...

结论

总结一下，强碰撞抵抗力在保持时提供更强的安全保证，但由于它提供了如此强大的声明，因此更容易被破解。但即使被破解，也不会太可怕，因为我们仍然有弱碰撞抵抗力来保护我们！因此，即使强碰撞抵抗力被破解，哈希函数在实践中仍然可以使用相当长的时间，因为弱碰撞抵抗力仍然具有相当“强大”的悖论性。但如果弱碰撞抵抗力也被破解（或接近被破解），那么就是时候前进了，而不是等待攻击者提高他们的碰撞检测算法，而我们的数据只受到一些脆弱（或意外）的应用程序验证的保护。

Cloudflare在这个主题上的相关博客文章：为什么伪造SHA-1证书比找到SHA-1碰撞更难

注意：在TLDR中，X和Y必须是不同的值（即不能是相同的值），而“找不到”指的是在合理的时间内无法找到（即不能花费100年来找到碰撞）。

- 0xZ3RR0

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- emboss · Accepted Answer

弱碰撞抗性有时也被称为“第二原像抗性”:

给定任意 x，不存在 x'（x' != x）使得 h(x) = h(x')。

另一方面，强碰撞抗性定义为：

不存在 x 和 x' （x != x'）使得 h(x) = h(x')。

它们定义上的显然区别在于，在弱碰撞抗性中，我们假设被绑定到特定的x选择，而在强碰撞抗性的定义中，我们可以任意选择x和x'。尽管如此，它们似乎非常相似，因此让我们看两个例子。

弱碰撞抗性的一个很好的例子是简单密码存储方案。假设我们通过存储密码哈希值来存储用户提供的密码，并且验证将成功当提供的某个密码的哈希值与之前存储的值相等时（尽管这是一种固有不安全的方案，但请暂时接受它）。现在，在这种情况下，给定的x是先前提供的（未知的）原始密码。如果攻击者能够有效地解决“第二原像”问题，则可以获得一个x'，其哈希值与原始x的哈希值相同，并且因此将成功验证身份。请注意，在一般情况下，能够产生任意碰撞（即解决强碰撞问题）的能力在此场景中是没有用处的，因为获取的x和x'不太可能与已经存储在数据库中哈希值相同的实际密码类似。

另一种情形是我们关注强碰撞抗性的应用程序，例如希望能够通过唯一id查找存储在数据库中的任意数据。您可以计算数据的哈希值而不是对原始数据发出查询（由于数据的潜在无界大小，这通常会非常缓慢），哈希值非常紧凑，大小有限，因此可以查询得到更高效。事实上，在这些情况下，您通常不需要考虑哈希函数的（第二个）预像抵抗性属性，主要是因为预像本身并不是秘密的。但是，您确实关心的是，绝对不希望两个不同的数据集哈希到相同的值，这实质上是一种碰撞。您不关心任何特定的碰撞，但是您希望这个属性在全局范围内成立 - 即您不希望任何两个数据集哈希到相同的值（想象一下该列定义了“唯一约束”）。由于这些应用程序通常不涉及安全问题，因此我们经常使用非加密哈希算法，主要是因为它们的性能更好。

直观上来看，强碰撞抗性似乎比弱碰撞抗性更难提供。幸运的是，在随机预言模型下，我们可以证明这一点。通过反证法，我们可以假设如果我们有一个有效的概率多项式算法来解决“第二原像”，那么这也将为我们提供一个有效的算法来解决“碰撞”。

考虑哈希函数h和以下简单的概率算法[1]:

让2ndPreimage成为另一个概率（e，Q）-算法，该算法解决哈希函数h的“第二原像”问题。

Choose x uniformly at random
value = 2ndPreimage(h, x)
case value == failure -> return failure
case value == x' (!= x) -> return (x, x')

很容易看出这也是一个解决强碰撞问题的(e, Q)-算法。这意味着如果我们有一个解决"第二原像"的算法，我们也可以使用这个算法来产生碰撞。由于我们对基础哈希函数h没有任何假设，因此现在我们可以安全地说：

强碰撞抗性意味着弱碰撞抗性，但反之不一定成立。

[1] e是算法的成功概率，0 <= e < 1。Q是最大的oracle查询次数（即算法的“评估”次数）。在成功的情况下，该算法返回一个有效的解决方案，否则它将返回一个表示失败的值。