瞭解SHA-1碰撞弱點

Question

據各種消息來源，攻擊尋找SHA-1的碰撞已經被提高到2^52的操作：

http://www.secureworks.com/research/blog/index.php/2009/6/3/sha-1-collision-attacks-now-252/

我想知道的是蘊涵這些發現在沒有受到攻擊的系統上。意思是如果我散列隨機數據，碰撞的統計可能性是多少？換句話說，最近的研究表明，暴力生日攻擊有更高的機會找到最初提出的衝突嗎？

一些類似上面的文章說，通過蠻力獲得SHA-1衝突需要2^80次操作。大多數消息來源說，2^80是一個理論數字（我假設，因爲即使在其摘要空間中，哈希函數也沒有真正分佈）。

那麼，基本散列分佈中的任何sha1碰撞弱點都是如此嗎？或者僅僅是指導數學攻擊的結果，碰撞的可能性增加了嗎？

我意識到最終它只是一個可能性的遊戲，而且它們是一個無限小的變化，您的第一個和第二個消息將導致碰撞。我也意識到，即使2^52是一個非常大的數字，但我仍然想要了解系統不受攻擊的影響。所以請不要回答「不要擔心」。

Answer 1

在您的鏈接中公佈的結果是攻擊，這是一系列仔細的算法選擇步驟，比隨機攻擊產生的衝突概率更高。這不是散列函數分佈的一個弱點。那麼，好吧，它是，但不是那種讓2^52的順序隨機攻擊成功的那種。

如果沒有人試圖在散列輸出中產生衝突，這個結果不會影響到你。

Answer 2

好的散列函數可抵抗3種不同類型的攻擊（如文章所述）。

在實際意義上最重要的阻力是第二個前映像電阻。這基本上意味着給定消息M1和哈希（M1）= H1，很難找到M2使得哈希（M2）= H1。

如果有人找到了一種有效的方法，那會很糟糕。此外，原像攻擊不容易受到生日悖論的影響，因爲消息M1對我們是固定的。

這不是一個預映像或第二個形象前攻擊，只是一個碰撞發現攻擊。 要回答你的問題，沒有蠻力攻擊不會有更高的找到衝突的機會。這意味着，天真的強力方法，結合研究人員的方法導致在2^52之後發現碰撞。標準的暴力攻擊仍然需要2^80。

Answer 3

關鍵問題是「攻擊者是否可以修改m1和m2消息」？如果是這樣，攻擊者需要找到m1，m2，使得hash（m1）= hash（m2）。這是生日攻擊，複雜性顯着降低---成爲平方根。如果散列輸出是128位（MD5），則複雜度爲2^64，與當前計算能力相差無幾。

給出的通常例子是賣家要求他的祕書鍵入消息「我將以1000萬美元的價格出售」。策劃祕書創建了兩個文件，一個表示「我將賣出1000萬美元」，另一個表示「我將以x美元出售它」，其中x遠低於10，通過增加空格修改兩個消息，大寫字等，修改x，直到散列（m1）=散列（m2）。現在，祕書向賣方顯示正確的消息m1，並用他的私鑰對其進行簽名，從而得到h。祕書切換信息併發出（m2，h）。只有賣方纔能訪問他的私鑰，因此他不能否認並說他沒有簽署該消息。

對於輸出160位的SHA1，生日攻擊將複雜度降低到2^80。這應該是30年或更多的安全。新的政府規定，4G 3Ggpp規格開始需要SHA256。

但是，如果在您的用例中，攻擊者無法修改這兩個消息（preimage或第二preimage場景），那麼對於SHA1，複雜度爲2^160。除非發現非暴力攻擊，否則應該永久安全。