你真的了解MD5嗎？

導(dǎo)語?|?日常開發(fā)中，在用到簽名的地方我們基本上總是可以看到MD5的身影。但是你真的了解它嗎？本文將以探索的思路帶你走進(jìn)MD5。

在日常開發(fā)中，在用到簽名的地方，我們經(jīng)常可以看到會有一個token，一般而言這個token是經(jīng)過約定的MD5規(guī)則生成的，生成的php代碼一般如下（其中salt是約定的一個鹽值，提高簽名token的安全性）：

$token = md5(salt . code)

可以發(fā)現(xiàn)token都是一個長字符串，由數(shù)字和字母構(gòu)成的，例如：365e3982a117a192f5d7c9882b3d1df1。仔細(xì)研究token，我們就會發(fā)現(xiàn)token中的英文字母只有a~f，大膽猜想一下：token中的每個字母或者數(shù)字是不是一個十六進(jìn)制的數(shù)呢？還有一點，每次md5生成的值的長度好像都是那么長，仔細(xì)一數(shù)發(fā)現(xiàn)是32位，那是不是：每個MD5生成的值都是一個長度為32位，每一位都是一個十六進(jìn)制數(shù)字而組成的字符串呢？

經(jīng)過我們的“研究”，我們有了以下兩個大膽的猜想：

• MD5生成的值長度是固定的。

• 如果設(shè)置為十六進(jìn)制輸出，那么MD5的結(jié)果長度是32。如果按照一位十六進(jìn)制占4位來算，MD5的結(jié)果長度固定為128bits。

沒有什么問題是看源碼或者官方API文檔不能解決的！為了驗證我們的猜想，經(jīng)過研究MD5的官方原稿，總結(jié)原理如下：

MD5原稿：

https://datatracker.ietf.org/doc/html/rfc1321

MD5算法的整體流程如上圖所示，主要分為4步：處理原文、設(shè)置初始值、循環(huán)加工、拼接結(jié)果。

（一）處理原文

處理原文就是一個關(guān)鍵詞：補(bǔ)位，此處的補(bǔ)位有兩個地方需要補(bǔ)。那具體怎么補(bǔ)位呢？

• 補(bǔ)填充位

首先需要對原文補(bǔ)填充位，使得帶填充位后的長度對512取余為448。填充位怎么補(bǔ)呢？首位是1其余的各位都是0，如下圖所示：

到這里，我們就會有兩個問題：

• 為什么是對512取余，而且為什么補(bǔ)位要補(bǔ)到對512取余后為448？

  
  

• 如果原文的長度本來就是對512取余是448呢，是不是就不需要進(jìn)行填充位的填補(bǔ)了？

首先我們來解決第2個問題：假設(shè)原文長度為len，且mod(len, 512) = 448，則需要再補(bǔ)充512位的填充位。假設(shè)填充位長度為appendLen，則有偽代碼：

if(mod(len, 512) < 448) {  appendLen = 448 - mod(len, 512);} else {  appendLen = 448 + 512 - mod(len, 512);}

至于第1個問題，我們接著往下看：

• 補(bǔ)數(shù)據(jù)長度

這里需要補(bǔ)64位的原文長度，我們會發(fā)現(xiàn)，補(bǔ)充齊64位后，整體的長度就是512的整數(shù)倍了。這里就可以回答上面的第一個問題了：MD5是一種基于block的算法，要求每次處理的block都是512bits。64位的數(shù)據(jù)長度，即最長可以是2^64 。那如果原文的長度len > 2^64呢？則取len的低階64位進(jìn)行填充。

此時的數(shù)據(jù)是16字（32位）的整數(shù)倍，用M[0，...，N-1]表示此時的數(shù)據(jù)，其中N為16的倍數(shù)。如下圖所示：

（二）設(shè)置初始值

MD5的結(jié)果是是由4個初始值A(chǔ)、B、C、D經(jīng)過不斷演變得到。MD5的官方實現(xiàn)中，A、B、C、D的初始值如下（16進(jìn)制）：

A=0x01234567
B=0x89abcdef
C=0xfedcba98
D=0x76543210

到這里，其實我們就會發(fā)現(xiàn)我們一開始的猜想基本上就被驗證了。MD5的結(jié)果長度確實是固定的，并且長度是128位。那具體是怎么演變得到的呢？

（三）循環(huán)加工

這一步是整個算法最重要的一步。話不多說，先上圖：

圖中，ABCD就是哈希值的四個分組，每一次循環(huán)都會讓舊的ABCD產(chǎn)生新的ABCD。一共進(jìn)行多少次循環(huán)呢？由處理后的原文長度決定。

假設(shè)經(jīng)過第一步處理原文之后的長度為M，則主循環(huán)次數(shù)L=M÷512，每個主循環(huán)中包含512÷32*4=64次子循環(huán)，分為4組16次。上面這張圖表達(dá)的是一次子循環(huán)的流程。

其中F是一個非線性函數(shù)。MD5用到的非線性函數(shù)有下面四種，4組循環(huán)中依次使用FGHI。

F(X，Y，Z) =(X&Y) | ((~X) & Z)
G(X，Y，Z) =(X&Z) | (Y & (~Z))
H(X，Y，Z) =X^Y^Z
I(X，Y，Z)=Y^(X|(~Z))

其中Mi為原文的一個分組，長度為32bits，每次循環(huán)所用到的分組編號不同，會交替使用到M0到M15中的數(shù)據(jù)。

而Ki則是一個32bits的常量，具體的計算公式如下：

Ki=floor(2^64*sin(i)) i的范圍是1~64，單位是弧度

而<<循環(huán)移位！而移多少位，則如下：

[7，12，17，22 ]
[5，9，14，20]
[4，11，16，23]
[6，10，15，21]

第一組16次循環(huán)中依次使用【7，12，17，22】，使用4次，以此類推。所以經(jīng)過一次循環(huán)后可以發(fā)現(xiàn)(其中=左邊為新，等號右邊全部使用舊的abcd)：

a=d
b=(F(b，c，d)+Mi+Ki)<<c=a
d=c

而一次主循環(huán)的4組16次子循環(huán)依次如下：

第一輪

FF(a，b，c，d，M0，7，0xd76aa478)
FF(d，a，b，c，M1，12，0xe8c7b756)
FF(c，d，a，b，M2，17，0x242070db)
FF(b，c，d，a，M3，22，0xc1bdceee)
FF(a，b，c，d，M4，7，0xf57c0faf)
FF(d，a，b，c，M5，12，0x4787c62a)
FF(c，d，a，b，M6，17，0xa8304613)
FF(b，c，d，a，M7，22，0xfd469501)
FF(a，b，c，d，M8，7，0x698098d8)
FF(d，a，b，c，M9，12，0x8b44f7af)
FF(c，d，a，b，M10，17，0xffff5bb1)
FF(b，c，d，a，M11，22，0x895cd7be)
FF(a，b，c，d，M12，7，0x6b901122)
FF(d，a，b，c，M13，12，0xfd987193)
FF(c，d，a，b，M14，17，0xa679438e)
FF(b，c，d，a，M15，22，0x49b40821)

第二輪

GG(a，b，c，d，M1，5，0xf61e2562)
GG(d，a，b，c，M6，9，0xc040b340)
GG(c，d，a，b，M11，14，0x265e5a51)
GG(b，c，d，a，M0，20，0xe9b6c7aa )
GG(a，b，c，d，M5，5，0xd62f105d)
GG(d，a，b，c，M10，9，0x02441453)
GG(c，d，a，b，M15，14，0xd8a1e681)
GG(b，c，d，a，M4，20，0xe7d3fbc8)
GG(a，b，c，d，M9，5，0x21e1cde6)
GG(d，a，b，c，M14，9，0xc33707d6)
GG(c，d，a，b，M3，14，0xf4d50d87)
GG(b，c，d，a，M8，20，0x455a14ed)
GG(a，b，c，d，M13，5，0xa9e3e905)
GG(d，a，b，c，M2，9，0xfcefa3f8)
GG(c，d，a，b，M7，14，0x676f02d9)
GG(b，c，d，a，M12，20，0x8d2a4c8a)

第三輪

HH(a，b，c，d，M5，4，0xfffa3942)
HH(d，a，b，c，M8，11，0x8771f681)
HH(c，d，a，b，M11，16，0x6d9d6122)
HH(b，c，d，a，M14，23，0xfde5380c)
HH(a，b，c，d，M1，4，0xa4beea44)
HH(d，a，b，c，M4，11，0x4bdecfa9)
HH(c，d，a，b，M7，16，0xf6bb4b60)
HH(b，c，d，a，M10，23，0xbebfbc70)
HH(a，b，c，d，M13，4，0x289b7ec6)
HH(d，a，b，c，M0，11，0xeaa127fa)
HH(c，d，a，b，M3，16，0xd4ef3085)
HH(b，c，d，a，M6，23，0x04881d05)
HH(a，b，c，d，M9，4，0xd9d4d039)
HH(d，a，b，c，M12，11，0xe6db99e5)
HH(c，d，a，b，M15，16，0x1fa27cf8)
HH(b，c，d，a，M2，23，0xc4ac5665)

第四輪

II(a，b，c，d，M0，6，0xf4292244)
II(d，a，b，c，M7，10，0x432aff97)
II(c，d，a，b，M14，15，0xab9423a7)
II(b，c，d，a，M5，21，0xfc93a039)
II(a，b，c，d，M12，6，0x655b59c3)
II(d，a，b，c，M3，10，0x8f0ccc92)
II(c，d，a，b，M10，15，0xffeff47d)
II(b，c，d，a，M1，21，0x85845dd1)
II(a，b，c，d，M8，6，0x6fa87e4f)
II(d，a，b，c，M15，10，0xfe2ce6e0)
II(c，d，a，b，M6，15，0xa3014314)
II(b，c，d，a，M13，21，0x4e0811a1)
II(a，b，c，d，M4，6，0xf7537e82)
II(d，a，b，c，M11，10，0xbd3af235)
II(c，d，a，b，M2，15，0x2ad7d2bb)
II(b，c，d，a，M9，21，0xeb86d391)

其中FF(a，b，c，d，Mi，s，Ki)表示a=b+((F(b，c，d)+Mi+Ki)<<

（四）拼接結(jié)果

最終經(jīng)過L次主循環(huán)之后，將每次主循環(huán)之后的結(jié)果拼接在一起便得到了MD5的最終結(jié)果。

研究完原理之后，我們會發(fā)現(xiàn)，MD5有一個非常重要的特性：不可逆。因為在上述FGHI操作中，是有部分信息丟失的，沒有辦法通過結(jié)果反推得到原文。而其實這樣也給MD5帶來一個好處：即使在原文中稍微改動一點，得到的MD5結(jié)果也會截然不同，所以很適合用于簽名中，偽造篡改的成本很高。

所以進(jìn)而引發(fā)了一個爭論：MD5是加密算法嗎？如果從加解密角度看，加密之后沒有辦法通過一定手段解密得到原文，MD5不屬于加密算法。

其次，由于MD5的結(jié)果長度是固定的，所以MD5的結(jié)果是有限的，但是原文是無限的。所以MD5算法不是嚴(yán)格意義上的一對一的，是多對一。即：存在原文A和B，且A≠B，但是MD5(A)=MD5(B)的可能。

既然如此，就引出了MD5的破解方法：找到一個原文B，使得原文B的MD5值和原文A的MD5值相同（其中找到的B可能就是A，也可能不是A，但是“殊途同歸”）

（一）暴力破解

暴力破解有兩個極端：一個是時間復(fù)雜度極高的窮舉法；另一個是空間復(fù)雜度極高的字典法。

• 窮舉法

窮舉法的思路十分簡單，就是不斷窮舉嘗試，直到找到一個原文B使得MD5值與原本A的MD5值相同。就以6位明文為例（字母和數(shù)字組成），一共就有62^6=56800235584種組合。可想而知如果明文長度加長，這種方法的時間復(fù)雜度有多高。

• 字典法

既然每個原文的MD5值都是固定的，那把所有的MD5值記下來，然后通過匹配去定位到原文。這就是字典法。同理可見，該方法的空間復(fù)雜度極高。

（二）哈希列表&彩虹表

暴力破解法走了兩個極端的路，那有沒有折中的方法呢？有！接下來介紹一下哈希列表及其優(yōu)化彩虹表。

• 哈希列表

哈希列表其實是暴力破解兩個方法的一個折中，即考慮用鏈表將一系列有關(guān)聯(lián)的原文和MD5值串聯(lián)起來，僅存儲“頭”和“尾”。

構(gòu)造這樣的鏈表前，我們先介紹兩個函數(shù)：哈希函數(shù)H(x)和衰減函數(shù)R(x)。其中H(x)是生成信息摘要的哈希函數(shù)，可以是MD5，也可以是其他信息摘要算法。R(x)是從信息摘要轉(zhuǎn)換成字符串的衰減函數(shù)。

注意：H(x)的值域是R(x)的定義域，R(x)的值域是H(x)的定義域。但是注意R(x)不是H(x)的反函數(shù)。

哈希鏈表的原理就是：將原文不停的使用H(x)和R(x)交替進(jìn)行k次運算，然后再將原文和運算結(jié)果以鏈表的形式存儲起來，得到節(jié)點個數(shù)為2K+1的鏈表。實際存放時，只存放最開始的原文和最后生成的字符串。具體如下(圖中數(shù)據(jù)僅為說明原理)：

假設(shè)我們現(xiàn)在要破解的值為2c5e1873，經(jīng)過R(x)計算得到了lknegc，說明我們尋找的原文就在以abcdef為首，lknegc為尾的鏈表中。那么我們從abcdef開始經(jīng)過一系列計算發(fā)現(xiàn)opyntf的H(x)值為2c5e1873，那么我們便找到了2c5e1873的原文是opyntf。

簡單來說，哈希鏈表代表了一組映射關(guān)系，其中每組包含K對映射，但只存儲了首尾兩個字符串。這樣存儲空間只是字典法的K分之一，代價就是破解時運算次數(shù)提高了K倍，這就是空間和時間之間的取舍。

但是！哈希鏈表有一個致命的缺陷：衰減函數(shù)R(x)的可靠性。盡管R(x)在設(shè)計時已經(jīng)盡可能的使其結(jié)果均勻分布了，但是仍然無法避免碰撞的情況發(fā)生。如下圖示例：

現(xiàn)在我們拿到5c38d215，想要得到它的原文，經(jīng)過一系列運算之后得到結(jié)果lknegc，但是我們會發(fā)現(xiàn)5c38d215并不在abcdef，lknegc的鏈表中。這樣我們就沒辦法通過對abcdef進(jìn)行一系列運算得到5c38d215的原文。

有人會說，那就再記錄一個鏈表，存放有5c38d215值的，假設(shè)首尾分別為burnlf和lknegc。但是我們會發(fā)現(xiàn)，這樣就導(dǎo)致了冗余存儲，本身兩個鏈表可以存2K個映射，但是由于重復(fù)的存在，實際上不足2K。

那有沒有避免碰撞的方法呢？由此便誕生了彩虹表。注意：彩虹表也僅是降低碰撞的概率，不能完全避免。

• 彩虹表

彩虹表是在哈希鏈表上進(jìn)行改進(jìn)得來的，將R(x)改進(jìn)，用R1(x)到Rk(x)一共k個衰減函數(shù)替代。這樣一來雖然仍然可能碰撞，但是碰撞只會發(fā)生在鏈表中的一節(jié)，大大減小了重復(fù)存儲的幾率。

（三）差分攻擊

還有更厲害的破解方法就是差分攻擊，王小云教授當(dāng)初使用查分攻擊算法連續(xù)攻破MD5和SHA-1等，該方法的關(guān)鍵是如何尋找差分和差分路徑，此處不做過多介紹，想要深入了解的可以由參考文獻(xiàn)入門開始探究。

參考文獻(xiàn)

1.MD5算法原理及其實現(xiàn)

2.漫畫：什么是MD5算法？

3.MD5算法

4.維基百科 MD5

5.張裔智，趙毅，湯小斌，《MD5算法研究》，計算機(jī)科學(xué)，2008,Vol.35 No.7

6.MD5算法如何破解

7.MD5破解的幾種方法

8.周林，韓文報，王政，《Hash差分攻擊算法研究》，計算機(jī)科學(xué)，2010，Vol.37 No.9

9.差分攻擊

韓雄飛

騰訊運營開發(fā)工程師

騰訊運營開發(fā)工程師，畢業(yè)于同濟(jì)大學(xué)。目前負(fù)責(zé)騰訊天美部分游戲業(yè)務(wù)的營銷活動開發(fā)工作，有豐富的游戲運營活動開發(fā)經(jīng)驗。

超實用教程！一探Golang怎樣踐行Clean Architecture？

高并發(fā)場景下，6種方案，保證緩存和數(shù)據(jù)庫的最終一致性！

顛覆Kafka的統(tǒng)治，新一代云原生消息系統(tǒng)Pulsar震撼來襲！

七年激蕩！Serverless的下一站將去往何方？