计算哪些字符串将具有相同的哈希值

Question

使用SHA-1可以确定哪些有限字符串将呈现相等的哈希值？

Answer 1

您正在寻找的是碰撞问题的解决方案(另请参见碰撞攻击).设计精良且功能强大的加密哈希函数的设计目的是尽可能多地模糊数学,以尽可能地解决这个问题.

实际上,良好散列函数的一个衡量标准是难以发现碰撞.(在其他措施中,反转哈希函数的难度)

应该注意的是,在输入为任意长度的字符串并且输出是固定长度字符串的散列中,Pigeonhole原则确保任何给定字符串至少存在一个碰撞.但是,找到这个字符串并不容易,因为它基本上需要对基本上无限的字符串集合进行盲测和检查.

读入理想的散列函数可能很有用.散列函数被设计为函数

• 输入的微小变化会导致输出的根本性和混乱性变化
• 碰撞减少到最低限度
• 反向很难或者理想情况下是不可能的
• 没有任何输入无法获得的散列值(这一点对于加密目的来说非常重要)

理论上的"完美"哈希算法将是一个"随机预言" - 也就是说,对于每个输入,它输出一个完全随机的输出,条件是对于相同的输入,输出将是相同的(这个条件满足于神奇的,由宙斯和小精灵的手,或以一种人类无法理解或弄清楚的方式)

不幸的是,这几乎是不可能的,并且最终,根据他们拥有多少这些品质以及在何种程度上,所有哈希都被判断为"强大".

像SHA1或MD5这样的散列将非常强大,或者在计算上或多或少地找不到(在合理的时间范围内)冲突.最终,您不需要找到无法找到冲突的哈希值.你实际上只需要一个难度很大而计算成本太高的地方(即发现碰撞的十亿或一万亿年)

由于所有哈希都不完美,人们可以分析它的内部运作,看到数学模式和启发式,并试图找到沿着这种模式的碰撞.这类似于哈希函数%7 ...哈希数字13将是13%7 = 6,89%7 = 5.如果你看到哈希值为3,你可以使用你对模数函数的数学理解来容易发现碰撞(即10)¹.对我们来说幸运的是,更强大的哈希函数有更多,更难以理解的数学基础.(理想情况下,没有人会理解它!

一些数字:

• 使用数学中固有的模式,查找单个给定SHA-0哈希的冲突需要在世界顶级超级计算机上运行大约13天的计算.
• 据一位有用的评论者称,MD5碰撞可以"快速"生成,对于敏感目的来说可能不够理想.
• 到目前为止,尚未发现或证明SHA-1的可行或实用/可用的碰撞发现方法,尽管如评论中所指出的,已经发现了一些弱点.

这是一个类似的SO问题,答案比我的更聪明.

¹ _{请注意,虽然这个散列函数对于碰撞来说很弱,但是如果你的散列是4,那么完全不可能倒退并找到给定的密钥是非常强大的.有无限量(即4, 11,18,25 ......)}

Answer 2

答案显然是肯定的,因为至少你可以遍历给定长度的每个可能的字符串,计算所有字符串的哈希值,然后看看哪些是相同的.更有趣的问题是如何快速完成.

进一步阅读:http://en.wikipedia.org/wiki/Collision_attack