pho*_*xis 38 hash cryptography
我已经阅读了一些关于强碰撞阻力和弱碰撞阻力的文章,但我无法理解其中的差异.我唯一能理解的是,在具有弱碰撞阻力的散列函数中存在低碰撞概率,并且在强碰撞阻力散列函数中具有较高的碰撞概率.我无法理解什么是真实的,这些参数的意义是什么.谁可以帮我这个事 ？
emb*_*oss 66
弱抗碰撞性有时也称为第二原像抗性:
给定任意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来查找存储在数据库中的任意数据的应用程序.您可以计算数据的哈希值,而不是对原始数据发出查询(由于数据的潜在无限大小,这通常会非常慢).哈希非常紧凑,尺寸有限,因此可以更有效地查询.事实上,在这些情况下,你根本不介意散列函数的(第二)前映像电阻属性,主要是因为前映像本身并不是秘密.但是,您真正关心的是,您绝对希望避免两个不同的数据集散列到相同的值,这实际上是一个冲突.您并不特别关心任何碰撞,但是您希望此属性能够普遍存在 - 即您不希望任何两个数据集散列到相同的值(假设该列上定义了"唯一约束").由于安全性在这些应用程序中通常没有问题,因此我们经常使用非加密哈希,主要是因为它们的性能更好.
两者之间的关系
直觉上也暗示着他们的名字,我们会认为强烈的碰撞阻力比弱的碰撞阻力更难以提供.幸运的是,在随机Oracle模型下,我们的直觉可以被证明是正确的.我们可以通过假设如果我们有一个有效的概率多项式算法来求解"第二原像"来证明这一点,那么这也将为我们提供一种解决"碰撞"的有效算法.
考虑一个哈希函数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查询的最大数量(即算法的"评估").如果成功,算法返回有效的解决方案,否则返回指示失败的值.
由于亚历山大的评论，我写了这个答案。复制所有定义；密码学哈希函数基础： P。Rogaway和T. Shrimpton 定义，含义和对原像抵抗，次原像抵抗和碰撞抵抗的分离。
x'，从而h(x') = y在给定任何y时都不知道对应的输入。x的第二原像x' != x，使得h(x) = h(x')。x，x'这些输入散列到相同的输出，即，使得在计算上是不可行的h(x) = h(x')。事实1：抗碰撞性意味着哈希函数的第二原像抗性。
事实2：第二原像电阻表示原像电阻。
正如亚历山大指出的那样，通过信鸽原理，当输入空间大于哈希函数的输出空间时，冲突是不可避免的。