md5 的部分碰撞
讓 $ h $ 是一個位串，讓 $ P(h, n) $ 是的 n 位前綴 $ h $ . 長度的部分衝突 $ n $ , 對於散列函式 $ H $ 是一對 $ (x,y) $ , 這樣 $ P(H(x),n)=P(H(y),n) $ .
對這種類型的碰撞有什麼了解？我對md5特別感興趣。可以調整彩虹表以快速查找這些嗎？什麼價值觀 $ n $ 暴力破解是可行的（也許以優化的方式，比如彩虹表）。
我也想知道原像案例：給定 $ x $ 和 $ P(H(x),n) $ ， 怎麼找 $ y $ 這樣它是一個 $ n $ - 部分碰撞 $ x $ .
如果 $ H $ 在隨機預言模型中是安全的，並且寬度至少 $ n $ ， 然後 $ x\mapsto P(H(x),n) $ 也是安全的，因為 $ n $ -bit hash 可以是（證明草圖：任何可以區分的攻擊 $ x\mapsto P(H(x),n) $ 從一個隨機預言機被簡單地變成一個區分器 $ H $ ）。反之則不成立。
尋找碰撞需要 $ O(2^{n/2}) $ 對 oracle 的查詢（或內部函式的評估） $ H $ ）。更準確地說，它預計需要 $ o(\sqrt{\pi/2}\cdot2^{n/2}) $ 不同的查詢，成功的機率達到 50% $ o(\sqrt{\ln 4}\cdot2^{n/2}) $ 這樣的查詢（這是廣義的生日問題）。關於如何展示這種衝突的標準論文是Parallel Collision Search with Cryptanalytic Applications。
查找原像預計需要大約 $ 2^n $ 對 oracle 的查詢（我計劃有朝一日探勘出正確的公式）。可以通過預計算來加速攻擊，例如使用彩虹表，特別是如果可能的消息集是已知的，或者如果 $ n $ 足夠小。
現在我們限制為 MD5，因此 $ n\le 128 $ .
發現衝突的難度與一個好的散列（ $ \approx 1.3\cdot2^{n/2} $ MD5 內輪）當消息被嘗試時不考慮 MD5 輪函式的內部結構（例如隨機消息或字典中的單詞）。在沒有對消息的限制的情況下，在至少 1024 位的消息中發現任何衝突都是可能的 $ n $ 自從那次突破以來，即使有一些限制也可以工作，現在成本很低，並且最近通過 512 位消息成為可能。較低的 $ n $ 是，它變得越容易。AFAIK 對於嚴重受限的消息沒有捷徑，例如少於 10 個 ASCII 字元的密碼。
找到一個原像的難度大約是一個好的雜湊（大約 $ 2^n $ MD5 內輪）當消息被嘗試時，不考慮 MD5 輪函式的內部結構，也不知道目標值的來源。我不知道有比這更好的實用方法，除非消息位於小於的已知集合中 $ 2^n $ ，這是彩虹桌閃耀的時候；在那種情況下，我看不到降低 $ n $ 改變成本。