密码散列函数中的第二原像抗性和碰撞抗性的区别

信息安全 密码学 哈希
2021-08-27 02:59:13

我正在研究这些笔记中的主题。然而,尚不清楚密码散列函数的“第二预映像抗性”和“碰撞抗性”属性之间的区别是什么。

正如注释在“第二原像电阻”中所说,给定 x1,推导出 x2 使得 h(x1) = h(x2) 在计算上是不可行的。这里的 x1 和 x2 是什么关系?

在“碰撞阻力”处,要找到 x1 != x2 使得 h(x1)=h(x2) 在计算上是不可行的。那是“第二预像抵抗”的子案例,其中 x1 != x2?

你能澄清这两者之间的区别吗?

2个回答

碰撞阻力是关于找到两个不同的输入mm'使得h ( m ) = h ( m' ) 的不可行性。攻击者可以任意选择mm',只要他最终得到两条不同的消息,它们的哈希值相同。

第二原像抗性非常相似,只是攻击者无法选择m取而代之的是,我们给他中号,并与寻找挑战他M '(有别于),使得^ h)= ^ hM' )。

第二个原像也是一个碰撞,但我们保持概念不同,因为第二个原像应该更难。如果散列函数的输出为n位并且是“完美的”(没有已知的弱点),那么发现碰撞的成本是 2 n /2,而发现第二个原像的成本是 2 n(即很多更多的)。


假设我们正在谈论签名。由于签名算法首先对要签名的数据进行散列处理,然后仅使用生成的散列值,因此如果h ( m ) = h ( m' ),则消息m的签名s也将是消息m'上的有效签名攻击者的目标是伪造一个签名,即获得一个似乎对他选择的消息有效的签名。

如果攻击者看到一个有效的、签名的消息m,那么他可能想要找到一个散列到相同值的消息m' 。这是第二原像模型。为了使签名系统具有鲁棒性,散列函数必须提供第二原像抗性。

另一方面,在这种情况下,不需要碰撞阻力。但是,有必要使用另一种模型,在该模型中,攻击者可以获得看起来无害的消息m上的签名,并希望该签名在具有较少良性内容的消息m'上也有效。例如,我是攻击者,我向您发送一份合同,您承诺向我发送 1 美元。但是,我制作了该合约m,使其与稍微不同的合约m'发生冲突(哈希到相同的值) ,您承诺向我发送 1000000 美元。如果我能让你签署第一份合同,那么由于碰撞,你的签名也适用于第二份合同(你输了)。

因此,抗碰撞性和抗二次原像性是两个不同的概念,您需要什么取决于上下文。在签名的情况下,您至少需要第二原像抗性;但是如果上下文使得攻击者可以获取他选择的数据的签名,那么还需要抗碰撞性。这已经MD5 作为哈希函数和 X.509 证书进行了证明(注意细节:对 MD5 的冲突攻击可以应用于证书,因为研究人员发现了一个以可预测的方式生成证书序列号的 CA)。

第二原像抗性只是比抗碰撞性具有更多的限制。

在您的示例中,x1 和 x2 是输入,而 h(x1) 和 h(x2) 是输出。

对于第二个原像电阻,给定 x1,并且必须找到一个哈希到相同输出值的输入 (x2)。在这次攻击中你不能选择 x1。

抗碰撞性没有这样的限制。您可以自由选择x1x2 以尝试找到输出的冲突。