數學上：能否實現在文件中保存文件自己的MD5值?

01-14

能否實現在文件中保存文件自己的MD5值?

知乎終於可以上傳 gif 圖片了

這張圖片展示了自己的 md5 值：

f5ca4f935d44b85c431a8bf788c0eaca

不知道知乎會不會對圖片進行壓縮，原始圖片地址：https://shells.aachen.ccc.de/~spq/md5.gif

相關鏈接：

Hacker News：An animated GIF that shows its own MD5
Reddit：Animated GIF displaying its own MD5 hash ? r/programming

文中討論區也大致解釋了圖片的生成原理。

1979 年 Ralph Merkle 博士發表了關於單向函數構造抗碰撞的信息摘要論文 R.C. Merkle. Secrecy, authentication, and public key systems. （PS：後來博士轉而去研究奈米科技以及人體冷凍技術）

(圖片來源維基百科：Merkle-Damg?rd construction)

Merkle 就是 MDx 中的 M，另一 D 是丹麥人 Ivan Damg?rd。（伊萬？？？）

在 13 年後的 1992 年，Ronald Rivest 發表了 MD5 演算法，用於改進之前的 MD、M1、...、M4 演算法。

通過再仔細觀察上面的圖就很容易發現，MDx 族演算法是一種基於塊的流式演算法。

---------------

我們回到這張神奇的 gif 圖上，本質是一種碰撞攻擊 Herding Hash Functions and the Nostradamus Attack https://eprint.iacr.org/2005/281.pdf。

王小雲的差分攻擊演算法雖然可以找到 MD5 的消息碰撞對，但是她找到的碰撞消息對是一組隨機比特字元，碰撞消息對沒有語義。而前綴構造碰撞演算法可以構造出只有尾部不同的兩個文件。

（圖片來源見水印）

如果我們找到一個碰撞，可以用兩個不同的值然後給他們分別附加數據後可以計算出相同的值：

在原始的 MD5 碰撞基礎上，計算兩個消息 M1 和 M2，有 H(M1) = H(M2)，其中函數 H(x) 是計算哈希值函數。Stevens 擴展了該研究，並且找到了一種方法，使兩個已知值 P1 和 P2 通過附加位元組產生碰撞。

使用前綴 P1 和 P2，他能夠證明如何找到 S1 和 S2，使得 H(P1 | S) = H(P2 | S2)。

而這張圖使用了類似的方式，在評論中有人提到：

1. Generate a gif for each possible digit in the first column

2. Append collision blocks to each gif to make a 16 way collision
3. Repeat for each digit
4. Hash the final product
5. Replace each digit with the correct digit

如果想自己構造要給碰撞程序，可以參考這個鏈接：Create your own MD5 collisions。

0 更新日誌

2014.11.20下午17:45，第一版回答。感謝 @徐釀泉， @bhuztez ， @肖劍等人在討論區的討論，這些討論啟發了我對此問題的回答。

2014.11.20晚上20:50，第二版回答。感謝 @之幽在線下與我的討論，讓我對這個問題有了更深刻的認識，並補充了答案。

2014.11.20晚上22:00，第三版答案。因為問題重定向到了是否存在一個字元串，它的md5值是其自身？，因此我在那邊的回答進行了第三版的修改。感謝 @玄星指出了我答案中的TYPO，第三版答案主要是修改答案中的TYPOs。

===============================分割線===============================

謝邀。

這個題有點意思，開始的時候我也把這個問題想簡單了。深入思考以後，這個問題還是一個比較有趣的問題呢。題主的問題其實問的比較模糊，我覺得在回答問題之前首先要確切定義一下題主的問題，然後分別予以回答。

題注的問題是：能否實現在文件中保存文件自己的MD5值？我們進一步對問題進行精練，這個問題一種有2種可能的理解：

By @bhuztez ：找到一個值 $x^*$ 使得 $x^* = MD5(x^*)$ 。
By @徐釀泉：找到三個值 $x^* in {0,1}^{*},y_1={0,1}^*,y_2={0,1}^*$ ，使得 $x^* = y_1 || MD5(x^*) || y_2$

這裡需要解釋一下，因為文件存儲過程中，文件名本身也將作為文件的內容之一，所以 @bhuztez 給出的類似用git裡面將MD5值當做文件名存儲內容，我認為並不是題主想要的答案，雖然這個方法可行，一定存在並且非常容易實現。在此，我認為文件名也需要包含在MD5的計算過程中，所以這種情況我考慮在第2種可能的解裡面。下面分別予以回答。

1. @徐釀泉的理解

這個問題的答案我想 @肖劍的評論已經給出的很清楚了，鏈接為：http://stackoverflow.com/questions/235785/is-there-an-md5-fixed-point-where-md5x-x。我們可以稍微翻譯和理解一下這個答案。答案的解釋如下：

（1）x*的條件。

因為對於任意的輸入x，MD5(x)的值都是128bit（即： $forall x, MD5(x) in {0,1}^{128}$ ），因此如果我們能找到一個滿足題目條件的值，則必有 $x^* in {0,1}^{128}$ 。

（2）滿足要求的x*是否存在。

假定MD5的輸出分布是均勻的（當然這只是一個假設了，實際上MD5的輸出並非嚴格均勻），因此對於任意x的輸入，其輸出滿足條件的概率為 $(1 - frac{1}{2^{128}})$ ，那麼對於任意x的輸入，其輸出不滿足條件的概率為 $1-(1 - frac{1}{2^{128}})$ 。那麼，對於所有 $x in {0,1}^{128}$ ，其輸出都不滿足條件的概率即為 $1-(1 - t)^{t}$ ，其中t=2^128。我們知道， $[mathop {lim }limits_{x o infty } {left( {1 - x} ight)^x} = 1/e]$ ，並且2^128確實是一個相對來說非常大的數，因此存在的概率為 $[{ ext{1 - 1/e}} approx { ext{63}}{ ext{.21\% }}]$ 。

（3）如果存在，如何尋找x*。

尋找方式似乎沒有多項式解法。我們至少知道，找到 $x^* = MD5(x^*)$ 也就找到了MD5的一個碰撞。因此，尋找這個值的演算法難度至少大於找到MD5碰撞的難度。不過現在已經知道，對於任意給定的x，找到一個值y，使得MD5(x)=MD5(y)已經不是一個非常困難的問題。所以我們不敢妄下結論是否一定能夠成立。不過至少知道如果x*存在，那麼一定能夠找得到。

2. @徐釀泉的理解

（1）x*的條件。

我們可以類似地得到，如果我們能找到滿足題目條件的值，那麼x*的位數至少大於等於128。

（2）滿足要求的x*是否存在。

經過一定的討論，我們可以得出如下推理。我們設想一個簡單的情況，我們只在MD5(x)前面補項，題目變為了：找到兩個值 $x^* in {0,1}^{*},y={0,1}^*$ ，使得 $x^* = y || MD5(x^*)$ 。同樣假設MD5的輸出是均勻分布的，那麼MD5(x*)與x*的後128位嚴格相等的概率是 $(1 - frac{1}{2^{128}})$ ，其輸出都不滿足條件的概率即為 $1-(1 - t)^{t cdot t$ ，其中t=2^128，t"=2^l，且l是y的比特長度。注意到，這個概率式指數上變大了，這是因為所有可能的情況又2^128變成了2^{128+l}。前面我們知道當t=2^128時，概率約為1-1/e。而新的概率式可以寫為 $1-(1 - t)^{t cdot t$ 。因此，隨著t的增大，這個等式的概率將逐漸趨近於1。舉個例子，當l也為128時，t" = t = 2^128，概率結果變為了 $1-(1/{e^2}) approx 86.4\%$ 。

如果考慮在後面補位，也能得到類似的結論。如果前面後面都補位的話，也可以等價地思考，結論就是：隨著允許補位的y_1，y_2的長度變長，存在解的概率也將逐漸趨近於1。由於我們只要找到一個滿足條件的y即可，則最終的概率結果會更高，但是似乎不能嚴格取到1.

（3）如果存在，如何尋找x*。

與上面的相同，尋找方式似乎沒有多項式解法。

===============================分割線===============================

2014.11.20晚上20:50補充答案。

在線下， @之幽和我對此問題進行了深入的討論。他通過構造的形式證明了一定存在這樣的x，使得x = y_1 || MD5(x) || y_2。在此我用一個等價形式描述 @之幽的構造。在我的證明中，對於l變長，存在x的概率趨近於1，但是應該不能取到1.然而， @之幽的構造是正確的，他找到了一個必然解。對此我需要說明為何其構造與我的證明有違背的地方。

@之幽的等價構造如下。考慮一個子串x，其構造形式如下：

$[x = underbrace {0 ldots 00}_{128}parallel underbrace {0 ldots 01}_{128}parallel underbrace {0 ldots 10}_{128}parallel cdots parallel underbrace {1 ldots 10}_{128}parallel underbrace {1 ldots 11}_{128}]$

也就是說，x為從全0到全1的全部128倍比特串的拼接。由於 $MD5(x)in {0.1}^{128}$ ，因此x中必然存在一個子串，使得這個子串等於MD5(x)，這樣就構造出了滿足題目條件的x。

這個子串既然一定能夠構造，那麼為何與我給出的證明有矛盾之處呢？這是因為l的取值已經不是一個多項式值了。我們注意到，x的長度為128*2^{128}，這個子串的長度使得t"遠遠大於t，因此我答案中的概率取值式子就不成立了。

但是，這個構造有個小問題，就是x的長度太長，以至於我們不能認為其能用多項式長度的存儲空間來表示。因此，MD5演算法的輸入不為多項式長度，在這種情況下，我們也就不能認為MD5本身是一個多項式函數了。當然了，這也反映出了計算機科學與數學之間的Gap，即多項式與指數的區別。

進一步補充，既然一定存在這樣的x，我們能否用多項式時間找到這樣的x 呢？ @之幽給我看了這樣一個鏈接：MD5原理說明_WuD1873_新浪博客。其中一段重要的說明如下：

2007年，Marc Stevens，Arjen K. Lenstra和Benne de Weger進一步指出通過偽造軟體簽名，可重複性攻擊MD5演算法。研究者使用前綴碰撞法（chosen-prefix collision），使程序前端包含惡意程序，利用後面的空間添上垃圾代碼湊出同樣的MD5 Hash值。

也就是說，這個演算法以x作為輸入，構造了x||y，使得MD5(x) = MD5(x || y)。這個構造雖然與題目的描述不太一樣，不過也是一個有價值的引用了。其原文引用為：

Marc Stevens, Arjen K. Lenstra, Benne de Weger: Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities. EUROCRYPT 2007: 1-22。

當然能啊，你把所有可能的 32 位十六進位串拼成一個超長的文本文件，裡面必然有它的 MD5

不動點定理？

看了幾位大神的數學分析，學習了！

我想擴展一下問題的話，就應該是：

能不能發明一種方法，使得其MAC（不具體限定演算法），位於此文件中某個地方（包含即可，但是要求明確給出MAC的具體位置）。

提出這樣的問題，求索一種可以一般化的「單文件」發布MAC的方法，應該能找到不錯的應用場景