Implementation
針對 SHA-1 的攻擊可以並行化嗎？
這種攻擊可以並行嗎？它是一個 $ 2^{57} $ 基於乾擾向量的SHA-1複雜性碰撞攻擊。
如果可行的話，在 GPU 上很容易（ $ \approx1.1 $ GPU 天數）。如果它是完全順序的，它會更加乏味但仍然可能（ $ \approx556 $ 3GHz CPU 上的天數）。
這兩個數字都小到足以引發“為什麼沒有人這樣做？”的問題。
根據Maarten Bodewes 在評論中提到的同一作者針對 SHA-1 的碰撞攻擊的最新干擾向量，最初的攻擊/複雜性是樂觀的/錯誤的。該算法實際上導致了一個已經發布的干擾向量：
使用我們的算法和那些成本函式，我們檢索了所有先前已知的向量，發現最有效的干擾向量是 Jutla 和 Patthak 首次報告為 Codeword2 的一個，這是 SHA-1 擴展程式碼最小權重的匹配下限。
基於原始來源的該攻擊的估計複雜度為 $ 2^{62} $ . Stéphane Manuel 後來的論文引用了兩個估計 $ 2^{65} $ 和 $ 2^{69} $ 取決於所使用的成本函式，並提供一些證據表明即使是那些也可能是樂觀的：
此外，下一節中描述的局部碰撞保持機率的統計評估表明，局部碰撞不是獨立的。因此，這種類型的成本函式只為估計攻擊的複雜性提供了一個粗略的基礎。
無論哪種方式，這都比最近執行的自由啟動碰撞攻擊更昂貴（ $ 2^{57.5} $ )，並且與 Stevens 提出的完全碰撞攻擊相似或慢。這就解釋了為什麼到目前為止還沒有執行。
關於並行化的原始問題，是的，這些類型的攻擊應該是“容易”並行化的（達到在 GPU 上實現它們很容易的程度）。