根据Wikipedia，在撰写本文时，最强烈的攻击似乎是针对MD5的原像攻击，该攻击于2009年4月发布，打破了MD5对原像的抵抗。这种攻击只是理论上的，完整原像的计算复杂度为$ 2 ^ {123.4} $。
但是在将来使用Quantum计算机时，我们能否获得MD5的所有已知明文（或使其冲突）？拥有量子计算机的人还会努力吗？
#1 楼
如果您遵循有关MD5的所谓原像攻击的参考，您将看到，尽管时间成本为$ 2 ^ {123.4} $步，但是内存成本为$ 2 ^ {45} \ times 11 $内存字，其中有一个比智能攻击者使用的面积*时间成本高得多-聪明的攻击者可以在$ 2 ^ {123} $的时间内，将32个CPU内核或MD5电路并行安装到更少的芯片面积中，并更快地得到答案。因此，这种攻击没有理由将MD5的原像电阻降低到广告水平以下。广告水平-128位哈希可以提供的最佳原像电阻-并不是很高。聪明的攻击者会做得更好：聪明的攻击者将使用彩虹表使用并行蛮力机一次攻击许多目标，并在概率为$ n ^ 2 $的并行化机器上的$ n $目标散列中找到一个原像。 p $对MD5的评估所花费的时间成本约为2 ^ {128} p / n $，远低于对单个目标进行攻击所需的约2 ^ {128} p $的成本对MD5的$ 2 ^ {128} p / n ^ 3 $顺序评估。这并不是针对MD5的攻击；这是对任何128位哈希的一般攻击。在实践中会发生这种情况吗？即使对于不是容易猜出的口令的原像，这也是人类可行的范围。
拥有足够大的$ k $量子计算机阵列，可以运行Grover的算法，您可以找到一个MD5在大约$ 2 ^ {64} \ sqrt {p / k} $的时间内，概率为$ p $的原像。这是否会比标准的通用经典并行蛮力攻击便宜呢？这取决于能够制造和供电能够运行Grover的量子计算机的廉价程度-目前，它们根本不存在。 （研究量子多目标故事留给读者练习。）
这并不一定意味着您会找到原始输入字符串-除非您对原始输入字符串的分布有所了解，并将搜索限制在此范围之内，否则您可能会发现乱码与原始输入字符串具有相同的哈希值。 （实际上，仅了解MD5哈希（128位字符串）并不意味着会有“原始输入字符串”。这是一个示例：914c24484128dfe05c3060632ee16e3f。也许您可以为此找到一个原像，但我只是拉了它）因此，它主要用于（a）填写大文件的非常简短的未知高熵细节（您知道其余部分），或（b）发明将具有以下内容的替代字符串：相同的散列，并且仅在对仍使用MD5作为标识代理的系统进行主动攻击时有用。
与计算冲突一样，使用$ \ operatorname {MD5查找消息对$ m_0 \ ne m_1 $ }（m_0）= \ operatorname {MD5}（m_1）$，无法控制通用哈希值可能是什么-您不需要量子计算机来执行此操作。在这一点上，这实际上是一个小技巧，花费一百万个MD5计算来进行新的计算，更不用说将现有的碰撞扩展为更长的碰撞了，而这根本不需要任何计算。
评论
$ \ begingroup $
有了一系列$ k $量子计算机，您可以在大约$ 2 ^ {64} / k $的时间内找到一个MD5原像；真的吗？我一直在寻找Grover的并行版本，而我能找到的最好的是$ 2 ^ {64} / \ sqrt {k} $时间。您有高效并行版本的参考吗？
$ \ endgroup $
–雨披
17年7月26日在15:08
$ \ begingroup $
不！我错误地引用了我引用的论文。立即修复。
$ \ endgroup $
–吱吱作响的s骨
17年7月26日在15:12
$ \ begingroup $
感谢您的参考；我以为是这种情况，现在我有证据了...
$ \ endgroup $
–雨披
17年7月26日在15:16
$ \ begingroup $
当涉及破坏哈希算法时，我认为寻找原始输入不是目标。例如，如果某个站点正在分发可执行二进制文件并发布文件的大小和MD5哈希，则攻击者的目标不是找到原始输入，而是创建相同大小的恶意文件。会产生相同的哈希值，使他们可以诱骗用户进行下载和执行。
$ \ endgroup $
–马丁
17年7月27日在7:00
$ \ begingroup $
@martin：那肯定是一个应用程序！ OP的问题似乎在于恢复原始明文的内容，因此我专注于该目标。您描述的内容与（a）相似，除了不了解原始输入是什么，我们不在乎，只需在其中填充垃圾以匹配目标哈希即可，例如比特币块。
$ \ endgroup $
–吱吱作响的s骨
17年7月27日在7:11
评论
他们没有被破解，因为没有人愿意去破解它们。拥有所有哈希的完整查找表不会影响使用apache-md5密码的人们：由于各种原因，它们已经被搞砸了。即使到今天，MD5在某些应用程序中（仍然）仍被大量使用，我不会这么说。当与非安全性相关的事物（例如rsync协议）使用时，MD5完美无缺。不是最好的解决方案。
仅当您可以确保没有其他人可以控制要同步的文件块时，MD5才适合rsync。它们是否包含某人发送给您的电子邮件？ Bzzzt：不好。它们是否包含您访问过的网站的浏览器缓存？ Bzzzt：不好。它们是否包含您从某人克隆的Git存储库？ Bzzzt：不好。对于rsync之类的通用工具，当一个人声称可以的时候就站不住脚了–与安全性无关。
但是，使某人的rsync有意失败的情况最终是与任何人的利益相关的-破坏为可追溯性而建立的备份系统，故意破坏，当有人通过“干” rsync检查更改/篡改时隐藏更改。听起来像是违反安全规定。
@Navin：[需要引用]除了Snefru明显的例外，据我所知，没有任何宣传为抗原像的严重加密原语能够打破其原像抗性。