SHA-256 是否具有（128 時間 + 128 空間 = 256 整體）位的抗碰撞性？
首先，我們考慮那些實際上可以提供 256 點陣圖像前安全性的散列函式，而不是像
SHAKE128<l=256bits>海綿參數僅提供 128 位安全能力的情況。我們知道密碼分析不僅有時間維度——它還有空間維度，即執行密碼分析算法所需的工作記憶體量。因此，如果我們期望在大約之後發現 SHA-256 衝突 $ 2^{128} $ 嘗試，這在理論上也意味著它需要 $ 2^{128} $ 保存候選碰撞輸入的空間。
這是真的嗎？這是否意味著考慮到空間時SHA-256 具有 256 位的整體抗碰撞性？
不，打破 SHA-256 的碰撞屬性不需要任何接近 $ 2^{128} $ 空間。我們知道如何在任何情況下展示碰撞 $ n $ 位雜湊 $ H $ 和 $ \mathcal O(2^{n/2}) $ 雜湊評估和 $ \mathcal O(n) $ 空間。
最簡單的合適方法是Floyd 的循環發現，它將以非消失機率展示兩個不同的 $ n $ 位位串 $ r $ 和 $ s $ 和 $ H(r)=H(s) $ , 在軌道上給定的初始點 $ t $ 迭代時 $ H $
$ m\gets\lceil,2^{n/2+1},\rceil $ （增加 $ +1 $ 減少故障）。
$ u\gets H(t) $ .
$ r\gets u $ ; $ s\gets H(u) $ .
儘管 $ r\ne s $ : (找循環)
- 如果 $ m=0 $ 然後停止失敗（長軌道，罕見）。
- $ m\gets m-1 $ .
- $ r\gets H(r) $ ; $ s\gets H(H(s)) $ .
如果 $ t=s $ 然後停止失敗（ $ t $ 在循環中，非常罕見）。
$ s\gets H(s) $ .
儘管 $ r\ne s $ ： （抵消 $ u $ 一個週期）
- $ s=H(s) $ ; $ u=H(u) $ .
儘管 $ t\ne u $ : (定位碰撞)
- $ r\gets t $ ; $ s\gets u $ .
- $ t\gets H(t) $ ; $ u\gets H(u) $ .
輸出 $ (r,s) $ 並停止成功。
線上嘗試！用於 24 位散列的衝突（第一個 $ k=3 $ SHA-256 字節）。如果增加，請善意在您的機器上執行此 Python 程式碼 $ k $ .
該方法使用的軌道 $ t $ ，定義為 $ u $ 通過迭代達到 $ u\gets H(u) $ 從…開始 $ u=t $ , 傾向於在內部循環 $ \mathcal \Theta(2^{n/2}) $ 腳步。算法檢測到一個循環是否到達，找到 $ u $ 經過盡可能多的步驟 $ t $ 作為循環的長度，然後進入循環的位置，這會產生碰撞。可以證明對於隨機函式 $ H:{0,1}^*\mapsto{0,1}^n $ 除了非常小的 $ n $ , 該算法從任意起點的成功機率 $ t $ 至少是 $ 3/4 $ （失敗是因為軌道過長 $ t $ ，或者當 $ t $ 屬於一個循環）。
如果發生故障，從另一個隨機點重新啟動通常就足夠了。這通常適用於常見的加密雜湊 $ H $ ，但即使對於這些，大多數起點也可能導致循環太大而無法找到。在一般情況下，我們希望切換到使用算法 $ H’ $ 被定義為 $ H’(x)=H(F(x)) $ 用於適當隨機有效可計算且可逆的注入 $ F $ 在算法開始時選擇。這是如此表現出碰撞 $ H’ $ 使用該算法表現出碰撞 $ H $ ， 但 $ H’ $ 可以有不同的循環結構。對於大多數 $ n $ 位雜湊 $ H $ 適合加密使用， $ F $ 可以與一個固定的 XOR $ n $ -bit 位串，或添加固定前綴或/和後綴。這在上面的虛擬碼和連結的 Python 程式碼中沒有說明。
可以將工作分佈在許多並行執行的機器上，每台機器的記憶體很少，通信量適中，額外工作量適中。參見 Paul C. van Oorschot 和 Michael J. Wiener，密碼分析應用程序的並行碰撞搜尋，密碼學雜誌，1999 年。