hash - 弱电阻和强电阻有什么区别

Question

我已经阅读了一些关于强抗碰撞和弱抗碰撞的文本，但我无法理解其中的区别。我唯一能理解的是，在抗碰撞性较弱的哈希函数中，碰撞概率较低，而在抗碰撞性强的哈希函数中，碰撞概率较高。我无法理解什么是真实的东西，这些参数的意义是什么。谁可以帮我这个事 ？

Answer 1

弱抗碰撞特性有时也称为第二原像抗性:

Given an arbitrary x there exists no x' with x' != x so that h(x) = h(x')

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

There exist no x and x' with x != x' so that h(x) = h(x')

它们定义的明显区别在于，对于弱碰撞阻力，我们假设受限于特定的 x 选择，而在强碰撞阻力的定义中，我们可以随意选择 x 和 x'。这似乎仍然非常相似，所以让我们看两个例子。

抗碰撞能力弱

我们实际上只对弱抗碰撞性感兴趣的一个很好的例子是一个简单的密码存储方案。假设我们通过存储它们的哈希值将用户提供的密码存储在数据库中。当用户提供的某些密码的哈希值等于之前存储的值时，身份验证将成功(尽管这是一个本质上不安全的方案，但请暂时耐心等待)。现在在这种情况下，给定的 x 是之前提供的(未知)原始密码。如果攻击者能够有效地解决“第二原像”问题，他就可以获得一个x'，其哈希值与原始x 的哈希值相同，从而可以成功认证。请注意，在这种情况下，产生任意冲突(即解决强冲突问题)的能力通常是无用的，因为我们得到的 x 和 x' 不太可能与哈希值已经存储在数据库中的实际密码相似.

抗碰撞能力强

我们关注的是强抗碰撞性的另一种情况是，例如，您希望能够在唯一 ID 的帮助下查找存储在数据库中的任意数据的应用程序。不是对原始数据发出查询(由于数据的潜在无限大小，这通常会非常慢)，而是计算数据的哈希值。哈希非常紧凑，大小有限，因此可以更有效地查询。事实上，在这些情况下，您通常根本不介意散列函数的(第二)原像抵抗属性，主要是因为原像本身并不是 secret 。但是，您关心的是您绝对希望避免两个不同的数据集散列到相同的值，这本质上是冲突。您并不特别关心任何冲突，但您希望此属性普遍保持 - 即您不希望任何两个数据集散列为相同的值(假设在该列上定义了一个“唯一约束”)。因为在这些应用程序中安全性通常不是问题，所以我们经常使用非加密哈希，主要是因为它们性能更好。

两者的关系

直观上，也由它们的名字暗示，我们会​​假设强抗碰撞性比弱抗碰撞性更难提供。幸运的是，我们的直觉可以在随机预言模型下被证明是正确的。我们可以通过假设，如果我们有一个有效的概率多项式算法来解决“第二个原像”，那么这也将给我们一个解决“碰撞”的有效算法，我们可以通过反证来证明这一点。

考虑一个散列函数 h 和以下简单的概率算法 [1]:

Let 2ndPreimage be another probabilistic (e, Q)-algorithm that solves "second preimage" for the hash function 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 做任何假设，我们现在可以安全地说

Strong collision resistance implies weak collision resistance but the opposite doesn't necessarily hold.

[1] e 是算法的成功概率，0 <= e < 1。Q 是 oracle 查询的最大数量(即算法的“评估”)。如果成功，算法返回一个有效的解决方案，否则返回一个指示失败的值。