將來我們能完全破解 MD5 嗎？
即使在今天，MD5（遺憾地）仍然在某些應用程序中大量使用。甚至像 ApacheMD5 這樣的大工具。但即使在今天，仍然有足夠多的 MD5 雜湊值仍未破解。
根據 Wikipedia的說法，在撰寫本文時，最強的攻擊似乎是針對 MD5 的原像攻擊，該攻擊於 2009 年 4 月發布，該攻擊打破了 MD5 的原像抵抗力。這種攻擊只是理論上的，計算複雜度為 $ 2^{123.4} $ 完整的原像。
但是在未來使用 Quantum 電腦，我們能否獲得所有已知的 MD5 明文（或讓它們發生衝突）？擁有量子電腦的人會為此付出努力嗎？
如果您按照所謂的對 MD5 的原像攻擊的參考進行操作，您會發現雖然時間成本是 $ 2^{123.4} $ 步驟，記憶體成本為 $ 2^{45} \times 11 $ 記憶體的話，它比聰明的攻擊者使用的面積*時間成本要高得多——聰明的攻擊者會將 32 個 CPU 核心或 MD5 電路並行安裝到小得多的晶片區域中，並更快地得到答案，在 $ 2^{123} $ 時間。因此，這種攻擊沒有理由將 MD5 的原像抗性視為低於其宣傳水平。
但所宣傳的水平——128 位散列可以提供的最佳原像抗性——並不是很高。聰明的攻擊者會做得更好：聰明的攻擊者將使用彩虹表的並行蠻力機器一次攻擊多個目標，並在其中找到一個原像 $ n $ 並行化機器上的目標雜湊 $ n^2 $ 有機率的方法 $ p $ 面積時間成本約為 $ 2^{128}p/n $ MD5 的評估——比大約 $ 2^{128}p $ 對單個目標的攻擊，並且在* $ 2^{128}p/n^3 $ MD5的連續評估。這不是特別針對 MD5 的攻擊；這是對任何128 位雜湊的一般攻擊。這在實踐中會發生嗎？它在人類可行的範圍內，即使對於一個不容易猜到的密碼片語的原像也是如此。
有一個數組 $ k $ 大到足以執行Grover 算法的量子電腦，您可以找到單個 MD5 原像的機率 $ p $ 在大約 $ 2^{64}\sqrt{p/k} $ 時間。這是否會比標準的通用經典並行蠻力攻擊**更便宜，取決於能夠執行 Grover 的量子電腦的建構和供電成本有多便宜——目前，它們根本不存在。（研究量子多目標的故事留給讀者作為練習。）
這並不一定意味著您會找到原始輸入字元串——除非您了解原始輸入字元串的分佈並將您的搜尋限制在此範圍內，否則您可能會發現恰好與原始輸入字元串具有相同散列的亂碼。（事實上，僅僅知道一個 MD5 雜湊——一個 128 位的字元串——並不意味著曾經有一個“原始輸入字元串”。這是一個範例：914c24484128dfe05c3060632ee16e3f。也許你可以找到一個原像，但我只是把它從 /dev/urandom 中拉出來。）所以它主要用於（a）填充大型文件的非常短的未知高熵細節，其餘的您知道，或者 (b) 發明具有相同雜湊值的替代字元串，並且僅在對仍然使用 MD5 作為身份代理的系統進行主動攻擊時有用。
至於計算衝突——尋找消息對 $ m_0 \ne m_1 $ 和 $ \operatorname{MD5}(m_0) = \operatorname{MD5}(m_1) $ ，無法控制公共雜湊值可能是什麼——你不需要量子電腦來做到這一點。在這一點上，這實際上是一個小技巧，花費不到 100 萬次 MD5 計算來製作新的，更不用說將現有的碰撞擴展到更長的碰撞，根本不需要計算。