Hash

偽造一個用 CRC32、MD5 和 SHA-1 三個函式散列的文件有多容易?

  • August 29, 2021

文件 A 使用 CRC32、MD5 和 SHA-1 進行雜湊處理。

創建一個與文件 A 具有相同雜湊值的假文件 B 有多容易?CRC32、MD5 和 SHA-1?

具有 GPU 的普通 PC 可以計算文件 A 的三重雜湊衝突嗎?需要多長時間?

創建一個與 file-a 具有相同雜湊值的假 file-b 有多容易?crc32、md5和sha1?

這在密碼學界被稱為“第二原像”問題。

使用 CRC32,這很容易;只需獲取原始消息並添加(即異或)CRC多項式的一些移位副本,這不會改變雜湊值。如果您沒有原始文件-a(您只有雜湊),那麼建構文件-b 將涉及求解 32 個聯立布爾方程 - 只是稍微難一些。

對於 MD5 和 SHA-1,沒有已知的實用方法。在這兩種情況下,我們最好的方法是嘗試大量的任意文件 b,直到我們偶然發現一個具有預期雜湊值的文件——這在兩種情況下都是不可行的工作量。

現在,使用 MD5 和 SHA-1 已知的是如何構造具有相同雜湊的兩個不同文件。但是,這些方法需要能夠指定兩個文件,並且如果其中一個文件已經給出,則不適用。

帶有gpu的平均pc可以計算file-a的三重雜湊衝突嗎?

沒有已知的方法可以做到這一點(在實際時間,例如在太陽變成紅巨星之前……)

正如雨披所寫,我們實際上不知道如何找到 SHA1 或 MD5 的第二個原像,更不用說同時匹配兩者的原像了。

但是,我們確實知道如何找到碰撞。由於 MD 構造的性質,我們可以輕鬆地將碰撞轉換為多重碰撞。這意味著我們可以創建許多會發生衝突的消息,我們可以建構許多 SHA-1(更廣泛的雜湊)的衝突,並通過生日攻擊獲得其餘的。如此處所述:同時生成 MD5 和 SHA1 衝突有多難?

所以這三個的第二個原像似乎遠遠超出了我們的範圍。但是 SHA-1 和 MD5 的衝突將花費 $ 2^{67} $ 操作。我們可以再次這樣做 16 次以在兩者上建構多重碰撞。並找到 CRC32 的衝突(或任何 32 位散列,甚至是強散列)。這將使總成本 $ 2^{71} $ 構造兩條在所有 3 個雜湊中發生衝突的消息。但這將是攻擊者選擇兩條消息而不是提供一條消息時。這遠遠超出了單個強大的 PC 所能做的,但並不超出一個民族國家或大型公司的手段。

引用自:https://crypto.stackexchange.com/questions/93652