雜湊兩次如何防止生日攻擊?
比特幣維基說:
比特幣使用兩次雜湊迭代(表示為 SHA256^2 即“SHA256 函式平方”),其原因與對較小但相關的 SHA1 雜湊的部分攻擊有關。自 2005 年起,SHA1 對生日攻擊的抵抗力在 O(2^64) 與設計 O(2^80) 中被部分破壞。雖然 hashcash 依賴於前映像抗性,因此不易受到生日攻擊,但針對生日碰撞攻擊強化 SHA1 的通用方法是對其進行兩次迭代. 迄今為止不存在對 SHA256 的類似攻擊,但是由於 SHA256 的設計與 SHA1 相似,因此使用雙 SHA256 的應用程序可能具有防禦性。這就是比特幣所做的,鑑於 hashcash 對原像安全性的依賴,它沒有必要,但它是針對未來密碼分析發展的防禦步驟。對 SHA1 和原則上其他類似設計的雜湊(如 SHA256)的攻擊也是 NIST SHA3 設計競賽的動機,該競賽仍在進行中。
考慮到在第一個散列之後發現衝突會在第二個散列之後發生衝突,我不明白兩次散列如何防止生日攻擊。
是因為您必須計算兩次雜湊從而減慢處理速度還是有更重要的原因?
任何散列函式中的衝突都會在散列函式的“平方”變體中產生衝突。這很容易看出。如果
hash(x)==hash(y)
,那麼散列輸出也將是相同的。所以wiki條目是錯誤的。要查看雙重雜湊的真正目的,請參閱此問題和答案。
嚴格來說,兩次散列實際上可能會增加碰撞的機會。如果散列函式的兩個輸出發生散列衝突,那麼任何具有該衝突散列的字元串都將是一個新的衝突。
實際上,舉個例子更容易:對於一個可怕的假設雜湊函式 F…
F("Alice") -> "aaa" F("Bob") -> "bbb" F("aaa") -> "ccc" F("bbb") -> "ccc" F(F("Alice")) == F(F("Bob"))