9

根据各种消息来源,寻找 sha-1 碰撞的攻击已改进为 2^52 次操作:

http://www.secureworks.com/research/blog/index.php/2009/6/3/sha-1-collision-attacks-now-252/

我想知道的是这些发现对未受到攻击的系统的影响。这意味着如果我散列随机数据,碰撞的统计几率是多少?换句话说,最近的研究是否表明暴力生日攻击更有可能找到最初提出的碰撞?

一些文章,如上面的文章,说通过蛮力获得 SHA-1 冲突需要 2^80 次操作。大多数消息来源说 2^80 是一个理论数字(我假设是因为没有散列函数真正完美地分布在其摘要空间中)。

那么在基本哈希分布中是否有任何已宣布的 sha1 冲突弱点?还是碰撞几率的增加仅仅是引导数学攻击的结果?

我意识到这最终只是一个赔率游戏,而且它们是一个非常小的变化,你的第一条和第二条消息将导致冲突。我也意识到即使 2^52 也是一个非常大的数字,但我仍然想了解对未受到攻击的系统的影响。所以请不要回答“别担心”。

4

3 回答 3

6

好的散列函数可以抵抗 3 种不同类型的攻击(如文章所述)。

在实际意义上最重要的阻力是第二原像阻力。这基本上意味着给定消息 M1 和 Hash(M1)=H1,很难找到 M2 使得 Hash(M2)=H1。

如果有人找到了一种有效地做到这一点的方法,那就太糟糕了。此外,原像攻击不易受到生日悖论的影响,因为消息 M1 对我们来说是固定的。

这不是原像或第二原像攻击,只是碰撞发现攻击。要回答您的问题,没有蛮力攻击没有更高的发现碰撞的机会。这意味着朴素的蛮力方法与研究人员的方法相结合会导致在 2^52 之后发现碰撞。标准的蛮力攻击仍然需要 2^80。

于 2009-07-20T16:54:38.853 回答
5

在您的链接中宣布的结果是一次攻击,这是一系列经过仔细算法选择的步骤,这些步骤产生的碰撞概率比随机攻击更大。这不是散列函数分布的弱点。好吧,是的,但不是那种使随机攻击可能在 2^52 的数量级上成功的那种。

如果没有人试图在您的哈希输出中产生冲突,则此结果不会影响您。

于 2009-07-18T15:48:06.367 回答
5

关键问题是“攻击者能否同时修改 m1 和 m2 消息”?如果是这样,攻击者需要找到 m1,m2 使得 hash(m1) = hash(m2)。这是生日攻击,复杂性显着降低——变成平方根。如果哈希输出为 128 位(MD5),则复杂度为 2^64,以当前的计算能力完全可以达到。

给出的通常示例是卖方要求他的秘书输入消息“我将以 1000 万美元的价格出售它”。诡计多端的秘书创建了两份文件,一份说“我将以 1000 万美元的价格出售它”,另一份说“我将以 x 百万美元的价格出售它”,其中 x 远小于 10,通过添加空格来修改这两个消息,大写单词等,修改 x,直到 hash(m1) = hash(m2)。现在,秘书将正确的消息 m1 显示给卖方,他使用他的私钥对其进行签名,从而产生哈希 h。秘书切换消息并发出(m2,h)。只有卖家可以访问他的私钥,所以他不能否认并说他没有签署消息。

对于输出 160 位的 SHA1,生日攻击将复杂度降低到 2^80。这应该是安全的 30 年或更长时间。新的政府法规,4G 3gpp 规范开始需要 SHA256。

但是,如果在您的用例中,攻击者无法同时修改消息(原像或第二个原像场景),那么对于 SHA1,复杂度为 2^160。除非发现非暴力攻击,否则应该是永久安全的。

于 2010-10-20T19:12:49.230 回答