用MD5加密為何不再安全了呢？

MD5(Message-Digest Algorithm 5) ，是一種使用廣泛的信息摘要算法，是在1992年由美國(guó)的密碼學(xué)家羅納德·李維斯特首次提出。

為什么有人認(rèn)為是可以用來(lái)加密，有人卻認(rèn)為是散列呢？到底為什么呢？

MD5到底是什么？

那么MD5算法到底是什么？我們可以將MD5算法看做是一臺(tái)處理機(jī)器，可以將計(jì)算機(jī)中種任意的數(shù)據(jù)放入這臺(tái)機(jī)器中，然后經(jīng)過(guò)這臺(tái)機(jī)器處理之后，就會(huì)產(chǎn)生一個(gè)固定長(zhǎng)度為128比特的MD5加密的值，傳入這個(gè)機(jī)器的可以是字符串，也可以是一張圖片，還可以是一段視頻。

可以看出來(lái)上面的這個(gè)操作是一個(gè)典型的哈希函數(shù)式的操作方式，可以將任意的數(shù)據(jù)內(nèi)容變成一個(gè)固定長(zhǎng)度的散列值，同一個(gè)輸入，得到的輸出結(jié)果始終是相同的，而不同的輸入，得到的輸出結(jié)果也是一樣的。

根據(jù)這樣的特性，我們可以用它來(lái)驗(yàn)證一個(gè)文件是否被修改過(guò)了，或者是可以用它來(lái)完成用戶登錄操作用戶名和密碼的計(jì)算等等。

但是就是這樣一個(gè)被廣泛使用的加密算法，卻被人證明已經(jīng)不再安全了。這到底是怎么回事呢？

MD5到底做了什么？

為什么MD5算法已經(jīng)被證明不再安全了，但是還是有很多人在使用呢？這就要從MD5算法的原理講起了。

MD5算法生成一個(gè)MD5的值，可以分為三個(gè)步驟。

填充對(duì)齊
分塊
多輪壓縮

填充對(duì)齊

我們知道在計(jì)算機(jī)中存儲(chǔ)的數(shù)據(jù)最終都是以二進(jìn)制的0和1的方式進(jìn)行存儲(chǔ)的。那么當(dāng)我們拿到一個(gè)數(shù)據(jù)之后第一步需要做的事情就是對(duì)數(shù)據(jù)進(jìn)行補(bǔ)齊。

舉個(gè)例子，假設(shè)我們得到了715個(gè)Bit的數(shù)據(jù)那么這個(gè)時(shí)候，就需要將其補(bǔ)齊為512的整數(shù)倍數(shù)，這里我們發(fā)現(xiàn)715Bit離1024Bit比較近，那么，就需要補(bǔ)上309個(gè)Bit，讓其達(dá)到1024Bit。然后在用于補(bǔ)齊的數(shù)據(jù)中最后的64Bit用來(lái)表示原始數(shù)據(jù)的大小。中間剩余的位置從原始數(shù)據(jù)開(kāi)始計(jì)算，第一個(gè)位置填1，其余的位置全部是0。

當(dāng)然有一種情況，假設(shè)，原始數(shù)據(jù)大小就是接近了1024這個(gè)時(shí)候并不能填充64個(gè)Bit來(lái)表示原始數(shù)據(jù)大小那么該怎么辦呢？那么這個(gè)時(shí)候，就需要將其補(bǔ)齊到下一個(gè)512的倍數(shù)，這個(gè)也就是1536Bit，然后再按照上面的方法進(jìn)行補(bǔ)齊。

那么也就是說(shuō)無(wú)論最終數(shù)據(jù)的大小是多少，只要無(wú)法保證上述條件的滿足，就需要進(jìn)行補(bǔ)齊，即使得到的數(shù)據(jù)恰好是512的整數(shù)倍數(shù)，我們依然也要進(jìn)行上述的操作。補(bǔ)齊之后，就需要進(jìn)行第二步操作分塊。

分塊

因?yàn)橥ㄟ^(guò)數(shù)據(jù)補(bǔ)齊操作，已經(jīng)將數(shù)據(jù)補(bǔ)齊成了512的整數(shù)倍，所以就一定可以將這些數(shù)據(jù)以512的大小分為若干的數(shù)據(jù)塊，而我們知道MD5值最后的輸出是一個(gè)128Bit的固定大小。作者將這128個(gè)Bit分成了四個(gè)部分。并且通過(guò)幻數(shù)為這四個(gè)部分設(shè)置了初始值。

為什么是幻數(shù)呢？原因很簡(jiǎn)單就是為了讓你猜不到。

這樣分塊也就完成了。接下來(lái)就是多輪壓縮了。

多輪壓縮

經(jīng)過(guò)上面的操作，我們可以將數(shù)據(jù)最終分成兩個(gè)大塊，并且我們將其中一個(gè)大塊數(shù)據(jù)拿出來(lái)，與上面128Bit的四個(gè)分塊的值，這里我們標(biāo)記位A、B、C、D四個(gè)值，然后分別用這四個(gè)值與數(shù)據(jù)塊分別進(jìn)行一系列的或與非以及移位運(yùn)算。這個(gè)過(guò)程總共進(jìn)行四輪。然后每輪壓縮操作之后，就需要分別更新A、B、C、D的值，那么經(jīng)過(guò)四輪計(jì)算之后四個(gè)值一共被更新了十六次。

完成壓縮操作之后，就將A、B、C、D四個(gè)值按照順序放回到原來(lái)的位置上，這個(gè)時(shí)候散列值就被更新完成了。

這個(gè)過(guò)程之所以被稱(chēng)為是壓縮，實(shí)際上就是將512Bit的數(shù)據(jù)變成了128Bit四個(gè)位置中的某個(gè)位置，從512到128，信息被壓縮了。所以整個(gè)的過(guò)程被稱(chēng)為是壓縮。

然后繼續(xù)用第二個(gè)大塊重復(fù)上述的工作，這個(gè)時(shí)候唯一不同的就是128Bit的四個(gè)數(shù)據(jù)值變成了第一個(gè)大塊數(shù)據(jù)計(jì)算之后的結(jié)果。

如果后續(xù)的大塊數(shù)據(jù)還有很多，那么操作還是跟上面的操作是一樣的。

當(dāng)我們完成了所有數(shù)據(jù)的壓縮操作，那么散列值就被更新成了最終的結(jié)果。整個(gè)MD5加密算法的實(shí)現(xiàn)過(guò)程是有點(diǎn)復(fù)瑣碎的，但是理解起來(lái)并不是太復(fù)雜。即使使用比較復(fù)雜的面向?qū)ο蟮木幊陶Z(yǔ)言也可以在百行代碼之內(nèi)實(shí)現(xiàn)它。

既然我們知道了MD5算法的實(shí)現(xiàn)細(xì)節(jié)，那么接下來(lái)我們就來(lái)看看MD5是如何被攻破的？

MD5是如何被攻破的？

在進(jìn)行攻擊之前，首先要搞清楚的就是攻擊目標(biāo)是什么？不然攻擊也就沒(méi)有意義了。根據(jù)上面的分析我們知道MD5就是一個(gè)產(chǎn)生MD5值的計(jì)算函數(shù)，而并非對(duì)數(shù)據(jù)進(jìn)行了加密。所以對(duì)于MD5的攻擊，其實(shí)并非是通過(guò)一個(gè)密鑰去進(jìn)行解密。

這個(gè)很容易理解，密文之所以能成為密文，前提肯定是信息沒(méi)有損失，如果有損失的話就無(wú)法通過(guò)密文獲取到明文了。顯然MD5并不是這樣。

宏觀上來(lái)看，MD5加密之后一個(gè)500M的數(shù)據(jù)被最終壓縮成了128個(gè)Bit，然后你想用128Bit的數(shù)據(jù)恢復(fù)500M的數(shù)據(jù)，傻子才會(huì)相信呢？從微觀的角度上來(lái)看，很明顯我們?cè)谶M(jìn)行補(bǔ)齊操作和分塊操作以及后來(lái)的數(shù)據(jù)壓縮操作的過(guò)程中明顯已經(jīng)改變的數(shù)據(jù)信息本身，顯然是無(wú)法直接進(jìn)行恢復(fù)的。這也就導(dǎo)致MD5值的生成過(guò)程是一個(gè)不可逆的過(guò)程。

那么我們還攻擊個(gè)啥呢？

破解MD5的秘密？

上面我們知道了，MD5值是通過(guò)一個(gè)消息數(shù)據(jù)計(jì)算得到的，并且在數(shù)學(xué)中我們也知道，如果是一個(gè)標(biāo)準(zhǔn)的一次函數(shù)f(x)=x這種形式的話，那么一個(gè)x就對(duì)應(yīng)一個(gè)y的值。也就是說(shuō)一個(gè)消息也就對(duì)應(yīng)了一個(gè)唯一的MD5的值。

假設(shè) hello 對(duì)應(yīng)的MD5值是123aba123dddaa3，那么也就是說(shuō)在hello不變的情況下，MD5的值也是不會(huì)發(fā)生變化的。但是真的是這樣么？

上面我們提到任意的輸入都會(huì)得到一個(gè)唯一的輸出，其實(shí)這句話包含了兩個(gè)限定條件。

輸出位數(shù)的大小是固定的128Bit，也就是說(shuō)MD5值是有范圍大小的，從0到2的128次方。
輸入是任意的，也就是說(shuō)輸入的數(shù)據(jù)是沒(méi)有邊界的，也就是說(shuō)是無(wú)窮。

那么在數(shù)學(xué)概念上來(lái)講，假設(shè)有100個(gè)房子，也就是說(shuō)MD5值已經(jīng)被窮舉了，那么有500個(gè)人，很顯然，肯定會(huì)有多個(gè)人住一個(gè)房子呀，也就是說(shuō)很明顯，一個(gè)MD5的值可以對(duì)應(yīng)多個(gè)輸入的結(jié)果呀！

這樣一來(lái)，上面我們假設(shè)的f(x)=x 的函數(shù)操作就是有問(wèn)題的。那么既然產(chǎn)生了哈希沖突了，在MD5中稱(chēng)為是碰撞，那么既然無(wú)窮對(duì)有界，那么對(duì)應(yīng)的無(wú)窮也應(yīng)該是無(wú)窮個(gè)。只不過(guò)，由于數(shù)據(jù)處理的緣故，我們無(wú)法找到產(chǎn)生碰撞的數(shù)據(jù)罷了。起碼作者在設(shè)計(jì)MD5的時(shí)候可能還沒(méi)有想到這一點(diǎn)。

所以顯然就不存在通過(guò)MD5值進(jìn)行逆向的操作了。

既然一個(gè)MD5對(duì)應(yīng)了無(wú)窮的消息，那么我們是否可以找到一個(gè)或者是我們可以窮舉的幾個(gè)能夠產(chǎn)生這樣的MD5值的消息呢？很顯然，這只是在理論上可行。但實(shí)際操作上，這是不行的，窮舉就是一個(gè)不可能完成的操作，畢竟數(shù)量級(jí)再那里放著2的128次方，相當(dāng)于大海撈針。

真的沒(méi)有辦法了么？

是不是就沒(méi)有辦法了呢？

假設(shè)我們給定了一個(gè)消息“Hello World！”，那么它對(duì)應(yīng)的MD5值我們是可以知道的。那么我們可不可以再找到另外的一個(gè)MD5值與之相同的數(shù)據(jù)呢？在MD4中，面對(duì)一些弱口令的時(shí)候，這種方式是可行的，但是在MD5中，這種方式還是有點(diǎn)難度的。

其實(shí)讓MD5破防的真正原因其實(shí)是下面的這個(gè)操作。

實(shí)驗(yàn)室給出的破解方式？

我們不需要給定MD5值，也不需要去找到對(duì)應(yīng)的消息，我們只需要制定一個(gè)規(guī)則，而這個(gè)規(guī)則就是能夠由兩個(gè)消息，產(chǎn)生同一個(gè)MD5就可以了。那么這個(gè)時(shí)候，操作就簡(jiǎn)單多了。例如一個(gè)二次函數(shù)就會(huì)出現(xiàn)兩個(gè)X值對(duì)應(yīng)一個(gè)Y值的情況呀！我們不需要找到無(wú)數(shù)個(gè)，只需要找到兩個(gè)即可。當(dāng)然這只是一個(gè)簡(jiǎn)單的例子。

那么如何是實(shí)現(xiàn)這個(gè)操作呢？

第一步、就是找到能夠產(chǎn)生局部碰撞的結(jié)果。
第二步、通過(guò)局部碰撞結(jié)果找到差分值。
第三步、通過(guò)差分路徑，通過(guò)消息修改，得到結(jié)果
第四步、通過(guò)消息修改來(lái)得到最終的碰撞結(jié)果。

很抽象，與產(chǎn)生MD5值的過(guò)程相比，這個(gè)過(guò)程看似簡(jiǎn)單，實(shí)則非常復(fù)雜。實(shí)際上這也會(huì)是信息安全領(lǐng)域的一個(gè)關(guān)鍵，打破這個(gè)規(guī)則往往要比制定這個(gè)規(guī)則要復(fù)雜的多得多。

當(dāng)然上面的操作只是在實(shí)驗(yàn)室給出的操作。但是在真實(shí)的工程使用場(chǎng)景中來(lái)看，這種方式到底有什么用途呢？

雖然可以找到最終的碰撞值，但是這個(gè)碰撞值是通過(guò)差分路徑和消息的修改而得到的，所以說(shuō)，最終得到的值也只是一個(gè)值罷了，在工程上并沒(méi)有實(shí)際的用處，但事實(shí)并非如此。

到此為止，我們知道MD5已經(jīng)不再安全了，

MD5安全問(wèn)題利用

假設(shè)，通過(guò)選擇前綴方式，生成了兩個(gè)MD5值相同，但是執(zhí)行效果完全不同的軟件，這個(gè)時(shí)候，通過(guò)MD5校驗(yàn)之后并不會(huì)發(fā)現(xiàn)兩個(gè)文件會(huì)有什么異常，但是你在選擇的時(shí)候，正好就選擇了哪個(gè)帶有木馬病毒的文件，這個(gè)時(shí)候，就會(huì)出現(xiàn)安全問(wèn)題了。

在如果，張三和李四，以MD5作為某個(gè)關(guān)鍵文件的真?zhèn)悟?yàn)證方式，那么很明顯通過(guò)選擇前綴的方式張三可以提前就制作出來(lái)兩個(gè)MD5值相同的文件，這樣在兩個(gè)文件內(nèi)容完全是不一樣的，但是MD5值卻是一樣的，最終產(chǎn)生的結(jié)果就是被騙了？

那么什么是選擇前綴呢？

理解起來(lái)其實(shí)非常簡(jiǎn)單，在上面的內(nèi)容中，我們知道了，如果一個(gè)文件大小如果正好是512的話，那么很顯然，需要進(jìn)行補(bǔ)齊操作，這個(gè)時(shí)候按照規(guī)則，補(bǔ)齊之后，文件后面跟的內(nèi)容正好就是一串沒(méi)有意義的文件。那么如何讓這個(gè)文件產(chǎn)生一個(gè)MD5值一樣的其他文件呢？

通過(guò)上面的方式，我們可以知道，在大批量的數(shù)據(jù)中去找碰撞的話有點(diǎn)難度，不妨我們讓文件內(nèi)容是一樣，只讓其中的一部分?jǐn)?shù)據(jù)發(fā)生變化。這樣可以很容易就找到碰撞了，這就有點(diǎn)類(lèi)似于，我們將一個(gè)函數(shù)的定義域給縮小了，這樣在這個(gè)小范圍定義域中去找到一個(gè)碰撞值，就會(huì)很簡(jiǎn)單了。