Tho*_*nin 10
在数学意义上,对于给定的散列函数必然存在冲突:可能的输入多于可能的输出,因此必须有两个输入映射到相同的输出.现在证明碰撞的存在,实际上找到一个,是两件不同的事情.如果我在海洋中间放一颗钻石,我肯定知道现在海洋中有一颗钻石 - 但如果我想恢复它,我会感到很茫然.
对于具有n位输出的"通用"散列函数,存在查找冲突的通用方法,平均成本为2 n/2的函数评估(参见本页).取决于n,这可以从简单到完全不可行.MD5的输出为128位,2 64为"非常高":你可以这样做,但它需要几千台机器和数月的计算.
现在MD5中存在已知的弱点,即可以利用一些内部结构来更容易地产生碰撞.到目前为止,对MD5的最佳攻击需要少于2 21个函数调用,因此这在基本PC上只需几秒钟(最多).@Omri指出他对MD5碰撞的一个很好的例子的回应,其中碰撞消息实际上是具有不同行为的可执行文件.
对于SHA-1,输出的大小为160位.这意味着一般的碰撞攻击花费大约2 80,这是现有技术无法实现的(嗯,人类可以做到,但肯定不是谨慎的:它应该可以用,比如相当于一年的预算整个美国陆军).然而,与MD5一样,SHA-1也存在已知的弱点.目前,这些弱点仍然是理论上的,因为它们会导致碰撞攻击成本为21 61,这对于任何一个加密研究实验室而言都太昂贵了,因此还没有完全进行(已宣布攻击成本为2)51但它似乎是一个哑弹 - 分析是有缺陷的).因此,没有实际的碰撞显示(但研究人员非常确定2 61攻击是正确的,如果有人找到了预算,它会起作用).
使用SHA-256时,没有已知的弱点,256位输出大小意味着通用成本为2 128,远远超出了今天和未来技术的可撤销性.