了解sha-1碰撞的弱点

Question

根据各种消息来源,寻找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也是一个非常大的数字,但我仍然想了解对不受攻击的系统的影响.所以请不要回答"不要担心".

Answer 1

良好的哈希函数可抵抗3种不同类型的攻击(如文章所述).

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

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

这不是前映像或第二次前映像攻击,仅仅是碰撞发现攻击.要回答你的问题,没有蛮力攻击没有更高的机会发现碰撞.这意味着天真蛮力方法与研究人员方法相结合,导致在2 ^ 52之后发现碰撞.标准的暴力攻击仍需要2 ^ 80.

Answer 2

在您的链接中公布的结果是攻击,一系列仔细的,算法选择的步骤,与随机攻击相比,产生的碰撞概率更大.它不是哈希函数分布的弱点.嗯,好吧,它是,但不是那种使得随机攻击可能在2 ^ 52的顺序上成功的那种.

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

Answer 3

关键问题是"攻击者能否同时修改m1和m2消息"？如果是这样,攻击者需要找到m1,m2,使得hash(m1)= hash(m2).这是生日攻击,复杂性显着降低---变成平方根.如果散列输出是128位(MD5),则复杂度为2 ^ 64,并且具有当前计算能力.

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

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

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