三路雜湊衝突
根據生日悖論，我們需要大約 $ O(|T|^{1/2}) $ 從標籤空間中採樣以查找雜湊函式的衝突 $ h:K\times M \to T $ . 但是需要多少樣本才能找到一個三向碰撞，即 $ h(a) = h(b) = h(c) $ 三個消息 $ a,b,c \in M $ 用相同的密鑰散列 $ k\in K $ ?
我以為會是 $ O(|T|^{1/2}) $ 去尋找 $ h(a) = h(b) $ 和另一個 $ O(|T|^{1/2}) $ 找到第三個，但一想起來，感覺不對。我該如何計算？
揮手的論點是這樣的：當你積累 $ n $ 雜湊輸出，你實際上是在生產 $ n^3/6 $ 三胞胎，每個人都有機率 $ t^{-2} $ 是一個三向碰撞（其中 $ t = |T| $ ，即輸出空間的大小）。所以你應該預料到第一次三向碰撞會在什麼時候出現 $ n^3/6 = t^2 $ ， IE $ n = 6·t^{2/3} $ . 對於具有 128 位輸出的完美雜湊函式，這意味著您需要大約 $ 2^{88} $ 雜湊函式呼叫。
現在這只是一個近似值，並沒有給出確切的結果，因為三元組並不完全相互獨立；但它產生了適當的數量級。
更重要的是，這假設了一個完美的散列函式。對於一個具體的散列函式，甚至是一個“安全”的散列函式，你可以更快地獲得多重衝突。如Joux 在 2004 年所示，“迭代雜湊函式”（例如 MD5 或 SHA-256）具有內部狀態 $ s $ 位，你只需要生產 $ k $ “簡單”碰撞（個人成本 $ 2^{s/2} $ ) 推導出一個 $ 2^k $ 多重碰撞。什麼時候 $ s $ 等於輸出大小（正如@Codes 所說，這被稱為“窄管道設計”），這遠低於上述成本；即使 MD5 沒有被破壞，它仍然會允許與 cost 發生四向衝突 $ 2^{65} $ ，與成本的八向碰撞 $ 2^{66} $ ，等等……“抵抗碰撞的通常安全屬性高達 $ 2^{s/2} $ “與“超越”並不矛盾 $ 2^{s/2} $ 可能會有一場簡單的多重碰撞狂歡”。