彩虹表可以从md5值中提取简单的明文密码吗？

Question

我知道一个散列值(例如: md5值)可以连接多个值，例如‘^&#%we242eweqweqweqwinfdfdfffff 2’，'%$#%3423efffe435%%^#‘。

但是，由于大多数用户实际上使用的是非常简单的密码，这些md5值是否只能与有限的简单清除密码有关系？

我的意思是，如果'cfcd208495d565ef66e7dff9f98764da‘只与'0’、'tom123‘、'goodcar’这样的30个简单值有关联，那么从数据库中获取md5数据的黑客就会很容易地找出用户名与其明文密码之间的关系，然后就可以利用这个值在其他网站上破解同一个帐户。

那么，是否任何指定的md5值只对有限的简单值负责？

PS:我知道我可以添加盐或者使用更好的方法，比如sha512，sha3，但是我对上面的问题很好奇。

Answer 1

这个问题取决于你对“简单价值观”的理解。一般来说，密码散列函数试图模拟任意长度输入到固定长度输出的随机映射。这些密码哈希的最基本的安全概念是所谓的抗碰撞，即不可能找到一对输入消息，这些输入消息散列到相同的固定长度输出。正如您已经演示的那样，这个概念现在已经被md5打破了，因为您可以构造在md5下确实发生冲突的特殊消息。

但是，当您谈论“简单值”时，我假设您排除了这些人工构建的消息，然后我们仍然可以将md5视为一个随机映射。

对于这样的随机映射，碰撞的概率仅取决于输入域的大小。例如，如果您查看字符集{ as、as、0-9}中的所有6个字符密码，您可以确保不会发生冲突(甚至可以像Chris指出的那样亲自尝试)。但是，如果将该大小扩展到同一个字符集中的25个字符，则肯定会发生冲突，因为现在有比可用的散列值更可能的密码。

估计碰撞的可能性被称为生日问题。作为一个简单的估计，如果您有k可能的输出值，那么当您到达sqrt(k)输入值时，可能会发生冲突。因此，对于md5和k=2^128，如果您的输入值集接近2^64的大小，就会发生冲突。