不同長度的輸入是否存在 MD5 衝突？
有很多 MD5 衝突的例子（其中一些可以在這裡找到是否有兩個已知的字元串具有相同的 MD5 雜湊值？）。但據我所知，兩個輸入應該具有相同的長度以具有相同的 MD5（或通常相同的雜湊）。這是對的嗎？有任何證據嗎？
或者其他具有相同 MD5 的不同長度的輸入範例？
因此，不同大小的 MD5 碰撞的問題在於我們的碰撞查找工具還不夠強大，無法有效地找到它們。
首先，我們需要了解 MD5 是如何工作的粗略概念，使用Merkle-Damgård 結構，基本上你保持一些狀態 $ s $ 和一些目前輸入塊 $ m $ ，將它們與壓縮函式結合起來，並將輸出用作新狀態 $ s $ ，最後一個狀態實際上是輸出。
現在我們目前的技術可以實現的是給定（任意）狀態 $ s_1\neq s_2 $ ，他們可以找到一系列消息塊 $ (m_1,m_1’,\ldots) $ 和 $ (m_2,m_2’,\ldots) $ 當輸入散列函式時，將產生相同的更新狀態 $ s_1’=s_2’ $ （這被稱為“選擇前綴衝突攻擊”）。
問題是，之後 $ s_1’,s_2’ $ 消息需要相等（包括長度）以保持衝突，否則如果您再次提供不同的消息，則必須再次重新統一狀態。這是一個問題，因為 MD5 將已處理消息的長度附加到消息中，然後將其饋送到最終的壓縮函式呼叫。特別是這意味著當您使用不同長度的消息時，您的最後一個塊會有所不同，因為它是最後一個塊，您不能只提供消息塊來再次彌補這種差異。
從理論上講，您可以嘗試通過在壓縮函式上發現一個衝突來解決這個問題，該衝突涉及對最後幾個字節的這個小控制，但實際上似乎沒有人這樣做（還）。
但是，如果您正在尋找蠻力碰撞，這將需要大約 $ 2^{64} $ 預期工作和 $ 2^{128}+1 $ 最壞情況下的工作，你只能有一個 128 位計數器 $ \mathbb i $ 並不斷散列 $ \mathbb i $ 和 $ \mathbb i|\mathbb i $ ，尋找出現在兩組中的雜湊值。任何此類條目，保證在之後存在 $ \mathbb i $ 循環通過其整個範圍將是不同長度的碰撞。
TLDR：沒有。據我所知，尚未發現 MD5 與不同長度消息的衝突。通過蠻力發現這種碰撞肯定是可行的，也許通過適應現有的攻擊。
當我們採用具有 128 位輸出的隨機函式時，雜湊 $ 2^{64} $ 一種長度的輸入，和 $ 2^{64} $ 另一個長度的輸入，我們期望與機率發生碰撞 $ >63% $ . 在 MD5 的那個看似合理的模型下，很可能在 8 字節和 9 字節的消息之間存在衝突，我們可以通過散列所有 8 字節消息找到，並且不到 1/256 的 9 字節消息。我們試探性地預計較大消息會發生許多衝突。
但據我所知，沒有更好的方法來生成具有相同 MD5 雜湊的兩條不同大小的消息。在實踐中，我們需要更多的雜湊值來節省記憶體並允許並行化，比如 $ 2^{66} $ 雜湊。這是可行的，但仍然需要付出相當大的努力：GPU 的雜湊速度為 40 GH/s，我們說的是 ≈100 GPU·年。我不知道這項努力已經完成。
我們不能輕易地調整現有的以低成本發現 MD5 衝突的攻擊。問題是，MD5 使用Merkle Damgård 結構，其中最後一個散列填充消息塊包括消息大小和一個填充，導致在嚴格約束的位置至少有 2 位對於不同大小的消息不同，並約束這些中的其他幾個位最後兩個消息塊。例如，如果我們試圖找到 2 塊消息之間的衝突，一條長度為 123 字節和 122 字節的消息，則填充消息的最後三個 32 位字必須是
80xxxxxx 000003D8 00000000 (for the 123-byte message) 0080xxxx 000003D0 00000000 (for the 122-byte message)這以高機率打破了我們在早期區塊中可能遇到的任何碰撞，除非考慮到創建碰撞的攻擊本身。據我所知，對現有攻擊的必要適應尚未完成。它需要使用 ≈80 個強加位，包括至少 2 個強加到兩個塊中不同值的規定位。這是不平凡的。
如果我們真的想通過蠻力搜尋兩條這樣的消息，我們可以使用一種通用的碰撞搜尋方法。原則上，我們會定義
$$ \begin{array}{rl} F:{0,1}^{128}&\to{0,1}^{128}\ x&\mapsto\begin{cases}\operatorname{MD5}(x)&\text{ if the last bit of }x\text{ is }0\ \operatorname{MD5}(x|\mathtt{0x42})&\text{ if the last bit of }x\text{ is }1\ \end{cases}\end{array} $$
現在我們取一個隨機起點，並進行迭代，直到找到碰撞，也許使用Floyd 的循環查找。這種衝突有 50% 的可能性是針對具有不同最後一位的輸入，這會導致兩條不同長度（16 和 17 字節）和相同雜湊的消息。
通過一些調整，我們可以在多台機器或併行 GPU 執行緒之間分配搜尋。參見 Paul C. van Oorschot 和 Michael J. Wiener，Parallel Collision Search with Cryptanalytic Applications，密碼學雜誌，1999 年（免費訪問）。