MD5摘要算法的幾種破解方法！

MD5 算法暴力破解的幾種方法

前言

昨天微信群里又熱鬧了起來(lái)，我一看消息，原來(lái)是有人在討論：“如果突然有一天 MD5 算法被破解了，可逆了怎么辦？”

其中有些網(wǎng)友表示，這題我會(huì)。

“如果它被破解了，我 35 歲之后就有事干了”

“如果可逆了，全宇宙最強(qiáng)的壓縮算法就誕生了，任意字節(jié)數(shù)據(jù)都可以壓縮到128bits”

“根據(jù)摘要就能把論文全文推導(dǎo)出來(lái)，碉堡了”

...

群消息刷了很多，都在帶薪摸魚(yú)，卻沒(méi)人討論，具體怎么破解。所以，今天我就來(lái)獻(xiàn)丑一下，淺談一下 MD5 怎么樣“破解”，大家輕噴！

逆向是不可能逆向的

在正式介紹 MD5 “破解”的方法前，先說(shuō)明一點(diǎn)：目前我們沒(méi)辦法把 MD5 字符串還原回對(duì)應(yīng)的原文。道理很簡(jiǎn)單，任意長(zhǎng)度的數(shù)據(jù)經(jīng)過(guò) MD5 處理后，所包含的信息量已經(jīng)大大減少。要是可以還原的話，那 MD5 豈不是成為最強(qiáng)的壓縮算法了？？

所以，目前所謂的“破解”指的就是“碰撞”。即找到一個(gè)原文，算出來(lái)的 MD5 碼和已知的 MD5 碼一樣。接下來(lái)介紹一些常見(jiàn)的破解方法。

暴力碰撞：窮舉法&字典法

小標(biāo)題上寫(xiě)了兩種方法：窮舉法和字典法。但是我認(rèn)為它們的本質(zhì)是一樣的，都是利用計(jì)算機(jī)的資源嘗試碰撞已知的 MD5 碼。這里就放在一起了。

窮舉法非常簡(jiǎn)單，就是不停地嘗試各種字符的排列組合，看哪一個(gè)組合的 MD5 碼能對(duì)上。可惜缺點(diǎn)是太耗費(fèi)時(shí)間了。我們舉個(gè)栗子，假設(shè)我們要破解一個(gè) 6 位大小寫(xiě)字母和數(shù)字混合的密碼，那么一共有 種組合。這個(gè)數(shù)的大小超過(guò) 500 億。

只考慮大小寫(xiě)字母和數(shù)字，每一位有 62 種可能，那么 8 位密碼的排列組合就是 62 的 8 次方，218340105584800，約等于二百萬(wàn)億！

既然計(jì)算如此費(fèi)時(shí)，能不能考慮「把計(jì)算結(jié)果以映射表的形式存放起來(lái)，一個(gè)蘿卜一個(gè)坑」，一個(gè)原文對(duì)應(yīng)著一個(gè) MD5 碼呢？可以呀！這就是傳說(shuō)中的“字典法”。將已知的 MD5 碼查表，直接反查出原文。

字典法體現(xiàn)了算法設(shè)計(jì)的“以空間換時(shí)間”的思想。「缺點(diǎn)是比較耗費(fèi)空間。不過(guò)現(xiàn)在硬盤(pán)的價(jià)格變得白菜價(jià)了，空間開(kāi)銷不算什么。」

所以，簡(jiǎn)單且常見(jiàn)的密碼，如果用了 MD5 加密，會(huì)被暴力的很快。況且現(xiàn)在量子計(jì)算機(jī)要來(lái)了，等量子計(jì)算機(jī)發(fā)展到和我們現(xiàn)在的普通筆記本大小，MD5 被暴力的就更快了，說(shuō)不定就是分分鐘的事。

給大家推薦一個(gè)用字典法破解 MD5 的網(wǎng)站：https://www.cmd5.com/password.aspx

時(shí)間和空間的折中：哈希鏈表&彩虹表法

如果說(shuō)窮舉法太耗費(fèi)時(shí)間，字典法太耗費(fèi)存儲(chǔ)空間的話，我們能不能考慮在時(shí)間消耗和空間消耗之間折中呢？我們可以考慮用鏈表將一系列有意義的原文和 MD5 碼串起來(lái)。

要構(gòu)造這樣的鏈表，我們需要兩個(gè)函數(shù)：哈希函數(shù) H(x)和衰減函數(shù)（reduction function）R(x)。哈希函數(shù)可以是 MD5，也可以是其他的消息摘要算法。H(x) 的值域是 R(x) 的定義域，R(x)  的值域是 H(x)的定義域。「R(x)不是H(x)的反函數(shù)。」

將一個(gè)原文不停地使用 H(x) 和 R(x) 交替進(jìn)行運(yùn)算  k次，再將原文本身和運(yùn)算結(jié)果以鏈表的形式串接起來(lái)，就可以得到結(jié)點(diǎn)個(gè)數(shù)為 2k+1 的鏈表。實(shí)際存放的時(shí)候只存放首端和末端兩個(gè)原文即可。「這種鏈表叫做“哈希鏈表”，體現(xiàn)了算法設(shè)計(jì)的“時(shí)空權(quán)衡”（Space and Time Tradeoffs）。」

舉個(gè)栗子，假設(shè)原文s=abcabc，經(jīng)過(guò) 2 次交替運(yùn)算，得到以下的鏈表：

?

abcabc->H(x)->3C8B0D7A->R(x)->eopmca->H(x)->7E9F216C->R(x)->rapper

?

以上數(shù)據(jù)均為舉例編造的，僅為說(shuō)明原理使用。那我們存放這個(gè)鏈表的時(shí)候，只需要記錄 abcabc 和 rapper 兩個(gè)原文即可。

假設(shè)我們要破解的摘要值（哈希鏈表的 H(x) 不一定是 MD5 算法，這里用更準(zhǔn)確的說(shuō)法代替 MD5 碼）是 7E9F216C，經(jīng)過(guò) R(x) 運(yùn)算得到 rapper，說(shuō)明我們要尋找的原文就在以 rapper 為末端的哈希鏈表中。從首端開(kāi)始經(jīng)過(guò)多次運(yùn)算，我們發(fā)現(xiàn) eopmca 的摘要值就是 7E9F216C。于是就反查出 7E9F216C 對(duì)應(yīng)的原文是 eopmca。

「如果在生成哈希鏈表的時(shí)候依次使用多個(gè)不一樣的 R(x)，此時(shí)的哈希鏈表就是“彩虹表”。」

文字描述起來(lái)太過(guò)復(fù)雜，還是用圖列舉一個(gè) demo。

這里再給大家推薦一個(gè)已經(jīng)計(jì)算好的彩虹表：http://project-rainbowcrack.com/table.htm

差分攻擊

上面介紹的窮舉法、字典法和彩虹表法都是暴力破解，適用于任何的消息摘要算法。真正意義上 MD5 算法的破解，是 2004 年山東大學(xué)王小云教授提出的 MD5 碰撞方法。她所用到的方法正是差分攻擊。

這種方法概括起來(lái)說(shuō)是這樣的：給定一個(gè) 1024 位的原文 M1，加上一個(gè)特定的常數(shù)得到的新的明文 M2。M1 和 M2 的 MD5 碼是一樣的。（這里大家可以去找具體的論文）這個(gè)特定的常數(shù)到底是怎么找出來(lái)的？筆者當(dāng)時(shí)在查閱原始文獻(xiàn)的時(shí)候也不清楚。因此后來(lái)的研究者開(kāi)始對(duì)怎么樣差分進(jìn)行了各種各樣的研究。具體的方法比較復(fù)雜，我就這里就不再贅述，班門(mén)弄斧了。

后記

其實(shí)還有一種破解 MD5 的方法——長(zhǎng)度擴(kuò)展攻擊。不過(guò)這種方法是在一定條件下（破解加鹽之后產(chǎn)生的 MD5 碼）才能用的。這種方法由 MD5 分塊計(jì)算的特性而來(lái)。

如果，我是說(shuō)如果。你能逆轉(zhuǎn)破解成功，你一定會(huì)獲得圖靈等計(jì)算機(jī)大獎(jiǎng)。大大的解放數(shù)據(jù)存儲(chǔ)能力，任何數(shù)據(jù)都可以用一段字符串表示。