嵌入暴力破解的時間複雜度MD5sum

我一直在回答很長時間的問題 - 尋找包含靜態嵌入其中的相同MD5的編譯二進制文件的MD5sum的時間複雜度是多少比如說，作爲一個字符串？嵌入暴力破解的時間複雜度MD5sum

編輯：如果這還不清楚。我正在尋找時間複雜度和說明它的答案。

來源

2011-03-15 atx

+1好問題。 – rook 2011-04-01 22:08:03

相關問題：http://stackoverflow.com/questions/235785/is-there-an-md5-fixed-point-where-md5x-x – 2011-04-02 05:53:06

與蠻力非常相似：計算md5sum並不重要，但是使文件與已知的md5sum相匹配很困難。

在最好的情況下，你正在尋找一個能夠給你一個已知散列（可能通過向二進制數據添加數據）的預映像。

來源

2011-03-15 09:25:41 Piskvor

由於MD5具有良好的分佈，所以很難實現。 bruteforcing最好的辦法是在你的文件中加入一些散列，並將無意義的數據附加到二進制文件的末尾，直到二進制文件與嵌入文件有相同的散列值。

另一方面，如果你想檢查你的二進制文件是否完好無損，你可以通過將你的二進制文件分爲三部分來更好：散列前的二進制部分，散列本身以及後面的部分哈希。連接第一部分和最後一部分，計算md5散列並將其嵌入到二進制文件中。

像這樣（例子）：你想幹什麼就需要在散列算法的一個缺陷是什麼

foo098f6bcd4621d373cade4e832627b4f6bar 
foo | 098f6bcd4621d373cade4e832627b4f6 | bar 
md5(foo+bar) = 3858f62230ac3c915f300c664312c63f 
foo3858f62230ac3c915f300c664312c63fbar

來源

2011-03-15 09:39:19 orlp

。而實際上，MD5 isn't very secure，所以也許可以。但我不明白任何已知的弱點對你想做什麼都有幫助。即使是原像攻擊也無濟於事，它必須是一個「選定的前綴原像攻擊」。

所以我想唯一可行的方法（今天）將是使用蠻力。

如果您正在尋找一種「添加安全性」到二進制文件，截斷哈希，然後使用蠻力。

來源

2011-03-31 08:35:38

這是不正確的。 – rook 2011-04-01 22:12:59

@Rook：究竟是什麼不正確，爲什麼？ – 2011-04-02 19:04:18

這也取決於環境。如果給出了二進制文件，並且只需要在某個地方插入md5，則答案可以是：0。因爲它可能是可能的（並且我假設它可能在幾乎所有情況下都是這樣），因此沒有插入md5產生相同的md5。

如果您有可能修改更多的二進制文件（例如通過填充任意數字的填充空間），唯一可行的方法是強力。

來源

2011-03-31 13:38:11 flolo

爲了做到這一點，你必須找到一個collision。這可以使用the prefixing attack against md5完成。請記住，這是唯一可能的，因爲md5非常壞。這種攻擊有一個time complexity of 2^24.1，這是現代桌面所能達到的。

來源

2011-04-01 22:06:38 rook

您需要找到衝突，但不是典型的衝突（相同的MD5散列），而是散列碼和（選定）部分消息的衝突。這很難。 – 2011-04-02 19:08:55

這可以在恆定時間內解決。

包含所有可能的MD5摘要的文件包含該文件的摘要。

來源

2011-04-02 09:18:48

雖然，假設MD5被定義爲大於2^64的消息，這是長度填充的大小。 – 2011-04-02 09:21:49

RFC 1321沒有提到限制。 :) http://tools.ietf.org/html/rfc1321 – 2011-04-02 09:30:34

我認爲這是一個有趣的關注點，但假設你的文件不能包含所有可能的MD5哈希值？ – atx 2011-04-02 09:44:43