抵抗力和抵抗力有什么区别 [英] What is the difference between weak and strong resistance
问题描述
我已经阅读了一些有关强抗碰撞性和弱抗碰撞性的文章，但是我无法理解它们之间的区别.我唯一能理解的是，在具有较弱抗冲突性的哈希函数中发生冲突的可能性较低，而在具有强大抗冲突性的哈希函数中发生冲突的可能性较高.我不明白什么是真实的东西，这些参数的意义是什么.有人可以帮我吗?
I have read some texts about strong collision resistance and weak collision resistance, but I was unable to understand the difference. The only thing I can understand that there is a low probability of collision in hash functions which have weak collision resistance, and a higher probability of collision in strong collision resistance hash functions. I could not understand what is the real thing, what is the significance of these parameters. Can anyone help me on this ?
推荐答案
弱的抗碰撞性能有时也称为第二原像抗性:
The weak collision resistance property is sometimes also referred to as second preimage resistance:
给定任意x，则x'！= x不存在x'，因此h(x)= h(x')
Given an arbitrary x there exists no x' with x' != x so that h(x) = h(x')
另一方面，强烈的抗碰撞性定义为:
Strong collision resistance on the other hand is defined as:
不存在x和x'，其中x！= x'使得h(x)= h(x')
There exist no x and x' with x != x' so that h(x) = h(x')
它们在定义上的明显区别是，对于弱耐碰撞性，我们假定绑定到x的特定选择，而在强耐碰撞性的定义中，我们可以自由选择x和x'.仍然看起来非常相似，因此让我们看两个示例.
The obvious difference in their definitions is that for weak collision resistance we assume to be bound to a particular choice of x, whereas in the definition of strong collision resistance we are free to arbitrarily choose our x and x'. Still this seems to be very similar, so let's look at two examples.
抗碰撞性弱
一个简单的密码存储方案就是一个很好的例子，我们实际上只对较弱的碰撞抵抗力感兴趣.假设我们通过存储用户提供的密码将其哈希值存储在数据库中.当用户提供的某些密码的哈希值等于先前存储的值时，身份验证将成功(虽然这本质上是不安全的方案，但请耐心等待).现在，在这种情况下，给定的x是先前提供的(未知)原始密码.如果攻击者能够有效解决第二个原像"问题，则他可以获得一个哈希值与原始x相同的x'，从而可以成功进行身份验证.请注意，在这种情况下，产生任意冲突(即解决强冲突问题)的能力通常是没有用的，因为我们得到的x和x'不太可能类似于已经存储在数据库中的实际密码
A good example where we are actually only interested in weak collision resistance would be a simple password storage scheme. Assume we store user-provided passwords in a database by storing their hash. Authentication would succeed when the hash of some password a user provides is equal to the value that was stored previously (this is an inherently insecure scheme though, but please bear with me for the moment). Now in that case, the given x is the (unknown) original password that was provided earlier. If an attacker were capable of solving the "second preimage" problem efficiently, he could obtain an x' whose hash value is the same as that of the original x, and would thus be authenticated successfully. Please note that the capability to produce arbitrary collisions (i.e. solving the strong collision problem) is useless in general in this scenario because it is not too likely that the x and x' we get resemble actual passwords whose hashes have already been stored in the database.
强大的耐碰撞性
我们关注的是强烈的抗碰撞性，这是另一个不同的情况，例如，您希望能够借助唯一ID查找存储在数据库中的任意数据的应用程序.而不是对原始数据进行查询(由于数据的潜在无限制大小，这通常会很慢)，而是计算数据的哈希值.哈希非常紧凑，大小受限制，因此可以更有效地进行查询.实际上，在这些情况下，您通常根本不介意哈希函数的(第二个)前映像抵抗属性，这主要是因为前映像本身不是秘密.但是，您真正关心的是，您绝对希望避免将两个不同的数据集散列为相同的值，这本质上是冲突.您并不特别在意任何冲突，但是您希望此属性具有通用性-即，您不希望 any 两个数据集散列为相同的值(假设存在唯一约束" (在该列上定义).由于在这些应用程序中安全性通常不是问题，因此我们经常使用非加密哈希，主要是因为它们具有更好的性能.
A different scenario where our concern is strong collision resistance instead is for example an application where you want to be able to look up arbitrary data stored in a database with the help of unique ids. Instead of issuing queries on the original data (which would often be very slow due to the potentially unbounded size of the data), you would compute hashes of the data instead. Hashes are very compact, limited in their size and can thus be queried much more efficiently. As a matter of fact, in these cases you often don't mind the (second) pre-image resistance property of a hash function at all, mostly because the preimages themselves are no secret. What you do care about, though, is that you would absolutely want to avoid two distinct data sets to hash to the same value, which is essentially a collision. You don't care about any collision in particular, but you want this property to hold universally - i.e. you don't want any two data sets hash to the same value (imagine there is a 'unique constraint' defined on that column). Because security is often no issue in these applications, we often use non-cryptographic hashes, mostly because they perform better.
两者之间的关系
直观地并且也隐含了它们的名称，我们将假定强抗碰撞性比弱抗碰撞性更难提供.对我们来说幸运的是，在随机Oracle模型下，我们的直觉可以被证明是正确的.我们可以通过假设如果我们有一个有效的概率多项式算法来解决第二原像"，那么就可以证明这一点.相反，这也将为我们提供一种解决碰撞"的有效算法.
Intuitively and also implied by their names, we would assume that strong collision resistance is something that is harder to provide than weak collision resistance. Luckily for us, our intuition can be proven to be correct under the Random Oracle Model. We can prove this by contrapositive by assuming that if we had an efficient probabilistic polynomial algorithm for solving "second preimage", then this would also give us an efficient algorithm for solving "collision".
考虑一个哈希函数h和下面的简单概率算法[1]:
Consider a hash function h and this following simple probabilistic algorithm [1]:
让2ndPreimage是另一个解决散列函数h的第二原像"的概率(e，Q)算法.
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进行任何假设，因此我们现在可以放心地说
It is easy to see that this is also an (e, Q)-algorithm that solves the strong collision problem. This implies that given we have an algorithm to solve "second preimage", we can also use this algorithm that is likely to produce a collision. As we made no assumptions on the underlying hash function h, we can now safely say that
强的抗碰撞性意味着较弱的抗碰撞性，但相反的情况不一定成立.
Strong collision resistance implies weak collision resistance but the opposite doesn't necessarily hold.
[1] e是算法的成功概率，0 <= e <1. Q是oracle查询的最大数量(即算法的评估").如果成功，该算法将返回有效的解决方案，否则将返回指示失败的值.
[1] e is the success probability of the algorithm, 0 <= e < 1. Q is the maximum number of oracle queries (i.e. "evaluations" of the algorithm). In case of success, the algorithm returns a valid solution, otherwise it returns a value indicating failure.
这篇关于抵抗力和抵抗力有什么区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
