Hash
同時產生 MD5 和 SHA1 衝突有多難？
我最近讀到 MD5 已“損壞”，因為它很容易產生衝突（如
2^(L/2)）。SHA1（理論上）也好不到哪裡去。解決方案似乎是相比之下非常慢的雜湊算法。我想知道為什麼人們不能結合這些快速算法來獲得最好的安全性和速度？生成同時 MD5 和 SHA1 衝突的時間複雜度是多少？如果它足夠難，這些是否會成為抗碰撞雜湊應用程序的可行候選者？
（通過同時碰撞，我的意思是生成具有相同 MD5 和 SHA1 的字元串）
令人驚訝的是，生成同時衝突似乎不會比為 SHA-1 生成單個衝突更昂貴。
基本思想是形成一個 $ 2^{64} $ SHA-1 上的廣泛多重衝突；那是， $ 2^{64} $ 所有 SHA-1 散列到相同值的不同消息。我們可以通過使用 Joux 的形成找到 64 個不同的碰撞塊的想法來做到這一點 $ B_{i, 0}, B_{i, i} $ 使得所有序列 $ B_{0, a}, B_{1, b}, B_{2, c}, …, B_{63, z} $ 都共享相同的 SHA-1 雜湊；這可以通過查找 64 個連續的 SHA-1 衝突來完成。找到單個 SHA-1 衝突的最佳估計是 $ 2^{61} $ SHA-1 壓縮函式呼叫 (Stevens)；因此尋找 64 個這樣的碰撞的努力是 $ 2^{67} $ 壓縮函式呼叫。
一旦我們有了這樣一個 $ 2^{64} $ 廣泛的多重衝突，我們只是對每個進行 MD5 雜湊，然後尋找 MD5 衝突；這需要 $ 2^{65} $ MD5 壓縮函式呼叫，並且產生碰撞的機率很大。
這會產生與預期的同時 SHA-1 和 MD5 衝突 $ 2^{67} $ 計算工作量。