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

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

前言

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

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

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

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

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

...

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

逆向是不可能逆向的

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

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

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

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

窮舉法非常簡單，就是不停地嘗試各種字符的排列組合，看哪一個組合的 MD5 碼能對上?？上秉c是太耗費時間了。我們舉個栗子，假設(shè)我們要破解一個 6 位大小寫字母和數(shù)字混合的密碼，那么一共有 種組合。這個數(shù)的大小超過 500 億。

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

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

字典法體現(xiàn)了算法設(shè)計的“以空間換時間”的思想。「缺點是比較耗費空間。不過現(xiàn)在硬盤的價格變得白菜價了，空間開銷不算什么?！?/strong>

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

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

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

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

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

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

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

?

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

?

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

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

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

文字描述起來太過復(fù)雜，還是用圖列舉一個 demo。

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

差分攻擊

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

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

后記

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

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