据我所知(但我可能错过了一些最近的结果),MD5 上没有已知的 ASCII 兼容冲突。
其主要的概念原因是碰撞发现的工作原理是引入一些小的差异,然后在它们在算法中传播太多之前尝试相互抵消这些差异。也就是说,对于给定的输入消息m,您考虑的消息m'与m相差几位。通过比较m和m'的 MD5 计算中的所有内部值,您可以看到差异传播。同一位上的两个差异可能会抵消,有时概率为 1(如果您翻转同一个位两次,您会回到相同的值),有时概率较低,即它仅适用于某些可能的内部值。这是因为 MD5 中的运算不仅仅是 XOR;还有一些按位非线性函数,还有很多加法。加法意味着进行传播。很多 MD5 密码分析都是关于应对进位传播。
因此,MD5 碰撞攻击主要是关于选择一条差分路径,即m和m'之间的差异,它在整个算法中具有不可忽略的实现概率并自行抵消,从而产生冲突。然后,您尝试了许多因源差异而不同的对(m,m'),直到您走运为止。消息修改技术是通过调整消息对来提高机会的方法,这些消息对不适用于整个差异,但几乎可以工作。无论采用何种技术,您仍然必须使用实现概率不太低的差分路径。
由于进位传播是设计良好差分路径的主要问题,因此有用的工具是修改32 位字的高位。实际上,如果 32 位字u和v仅在最高有效位上有所不同,那么对于(u,v)的所有值, u+v必然等于 0x80000000:对于那个位,没有进位(进位,如果有的话,“脱落”这个词,因为我们使用的是 32 位加法,它将结果截断为 32 位)。这是一个一位输入差异,它产生一个概率为 1 的一位输出差异:一个非常有用的工具。事实证明,大多数(所有?)已知差分路径有足够高的概率产生实际攻击,在某些时候依赖于高位上的这种一位差异。
但是,使用输入字的高位意味着冲突对中至少有一个字节,因此其中一条消息将包含 128-255 范围内的字节值。即一个非ASCII 字节。
我上面解释的很多内容都是基于模糊的挥手,但它应该显示出这个想法的要点:获得 MD5 冲突的“快速”已知方法意味着使用一些消息,并且,现在,这包括一些字节的高位,使冲突消息之一成为非 ASCII。
发现冲突的缓慢方法是尝试随机消息,直到发现冲突,没有约束——因此这些消息可以是完整的 ASCII。如果你生成了很多 11 字符的密码,字符是大写和小写字母和数字,那么当你对其中的大约 2 64 个进行哈希处理时,你应该会遇到冲突,即大约所有可能的 11 字符密码的三分之一。不幸的是,虽然 2 64的努力在技术上是可行的,但它仍然非常昂贵,而且没有人运行它。然而。至少是公开的。
从外部看,您几乎无法确定密码的存储方式。充其量,如果密码验证看起来非常快(服务器在几毫秒内响应),那么您可以证明密码哈希没有充分迭代(除非它使用“胡椒”,在这种情况下它可能在同时-有关术语,请参见此答案)。否则,为了证明使用特定的哈希函数,您需要冲突,因为这是您可以获得的所有信息:给定密码是否适用于给定用户。
如果您可以查看数据库内容(并且散列密码的全部要点是基于可以做到这一点的攻击者的想法),那么您会有很多额外的信息:
- 如果具有相同密码的两个用户获得相同的哈希值,则没有盐(这很糟糕)。
- 如果两个具有相同密码的用户没有获得相同的哈希值,但是相同的用户,将他的密码改回以前的密码,也将他的哈希恢复为旧值,那么就没有真正的盐;用户名被用作盐的(部分)(这也很糟糕,尽管不太好)。
- 您可以直接尝试候选哈希函数。