如果您有兩個長度相同的輸入,理論上 MD5 和 SHA-256 中是否存在衝突?
是否可以有兩條長度相同的消息 M、M’,使得 MD5(M)=MD5(M’) 和 SHA-256(M)=SHA-256(M’)?
讓我們比較兩個文件:如果它們的長度相同,則它們是具有相同內容的候選;如果他們共享 MD5 總和,他們更有可能擁有相同的內容(我知道在相同大小的輸入上存在 MD5 衝突,因此這可能會導致誤報),但是如果他們也共享 SHA-256 總和,則可以我確定文件具有相同的內容嗎?
這種衝突是可能存在的,但由於 SHA-256 是抗衝突的,因此在計算上發現任何衝突都是不可行的。您可以放心地假設,如果兩個文件具有相同的 SHA-256 雜湊,則它們包含相同的內容,而無需進一步檢查。
鑑於目前的密碼學知識,您可以放心地假設根本沒有理由使用 MD5。你可以只使用 SHA-256。事實上,如果可能的話,您應該積極避免使用 MD5。
我的意思是是否有兩條消息 M、M’ 的長度相同,使得 md5(M)=md5(M’) 和 sha256(M)=sha256(M’)?
是的,這樣的一對消息必須存在,因為任何函式的輸入範圍大於其輸出域的範圍都必須有衝突。在數學中,這被稱為鴿巢原理。
我正在考慮的案例是比較兩個文件,如果它們具有相同的長度,則它們是具有相同內容的候選者,如果它們共享 md5 總和,則它們是具有相同內容的更強候選者(我知道有 md5 衝突相同大小的輸入,因此這可能會導致誤報),但是如果它們也共享 sha256 總和,我可以確定文件具有相同的內容嗎?
就純機率而言,理論上兩個不同的文件也可以具有相同的 SHA-256 結果。又是因為鴿巢原理。
但密碼學問題不僅僅是隨機文件對的可能性有多大(= 天文上不太可能),而是壞人惡意建構這樣一對文件的難度有多大。MD5 的問題不在於衝突本身存在;有一些已知的算法可以有效地發現 MD5 衝突,壞人可以使用這些算法來擊敗此類檢查。
但是對於 SHA-256,沒有這樣的算法。所以:
- 給定兩個隨機選擇的文件,它們具有相同的 SHA-256 雜湊值在*天文上是不可能的。*天文學上的不可能與理論上的不可能是不一樣的,但在實踐中卻遠遠不夠接近。
- 即使一個壞人想要製作兩個衝突的文件,他們在實踐中也做不到。