編者按：本文作者為北師大的大三學生張俏，女 Geek，在 CSDN 等各大網站的用戶數據被洩露之後，她就 MD5 加密問題寫下此文，發表了自己的看法，如果有讀者想要跟作者進一步探討，可以在新浪微博@阿豆拉。
MD5為現在應用最廣泛的 Hash 算法之一，在 1992 年由 MIT 的 Ronald L. Riverst 提出，由 MD4 演化而來。該算法廣泛應用於互聯網網站的用戶數據加密，能夠將用戶密碼加密為 128 位的長整數。
數據庫並不明文存儲用戶密碼，而是在用戶登錄時將輸入密碼字符串進行 MD5 加密，與數據庫中所存儲的 MD5 值匹配，從而降低密碼數據庫被盜取後用戶損失的風險。
但由於 Hash 碰撞的存在，MD5加密的數據並不安全，可以由生成相同 Hash 值的字符串破解，所以提出了加入隨機數 salt 的 MD5 加密方法，一定程度上增大了字典攻擊的難度。
問題提出
前一陣在新浪微博上，有一個人發布了這樣一條微博：“出道互聯網安全常識數學題……假設你的網站所有用戶密碼都是md5加密（單向散列，非可逆）的，假設你網站有10萬會員，如果你的用戶庫丟了，會有多少會員密碼被破解？想想看。”當時我的一位朋友認為 10 萬個密碼全部都會被破解，我卻不這樣認為，因為根據我的先驗知識：
MD5 加密算法在互聯網應用中廣泛被使用，MD5不是簡單的古典加密算法，不能通過逆向 Decrypt 解密，只能通過 Hash 碰撞破解（Hack）；
我曾經看過對同一個字符串進行 MD5 加密的結果，產生結果是隨機的字符串（後來經過查找資料發現我所看到的不是簡單的 MD5 加密，而是加鹽後的結果）；
MD5 用作密碼加密算法並不是絕對安全的，因為可能產生 Hash 碰撞，簡單密碼的 MD5 加密可以通過彩虹表查找到；
我曾見過幾個破解 MD5 加密的網站（http://www.cmd5.com/），大多數的做法是先免費為用戶暴力破解，積累起足夠的數據庫可以破解簡單密碼後，解密服務便開始收費，所以 MD5 密碼的破解不應該那麼簡單。
在經過對這個問題激烈的討論過後，沒過多久便發生了 CSDN 的數據庫洩露事件，600萬條數據庫記錄被任意傳播。緊接著天涯論壇的數據庫也洩露了，2000萬條數據庫記錄被證實幾乎均可以登錄。而這兩個網站的數據庫中所保存的用戶密碼都沒有經過加密，即為明文存儲的。這種事情的發生更加證實了對網站數據庫中所保存的用戶密碼進行加密的重要性。
現今流行的對用戶密碼加密算法中，MD5加密是最為廣泛使用的算法之一。
背景知識
對於散列函數h(x)，必須滿足下列特性[1]：
壓縮：對於給定輸入x，輸出長度y=h(x)很小；
效率：對於給定輸入x，計算y=h(x)很容易；
單向：該散列函數H是一個單向函數，即對於幾乎所有的x，已知H(x)的值y求x是不可行的；
弱無碰撞：已知x，求出x’使得H(x’)==H(x)在計算上是不可行的；
強無碰撞：對於任意x≠x’，H(x’)==H(x)在計算上是不可行的。
MD5的全稱是 Message-Digest Algorithm 5，在 1991 年由 MIT 的 Ronald L. Riverst 提出，由 MD4 演化而來，最終生成 128 位（4個 32 位的 16 進制數）的信息摘要算法。[2] MD5算法是一個不可逆的字符串變換算法，即看到源程序和算法描述，也無法將一個 MD5 的值變換回原始的字符串。
1993年，Den Boer 和 Bosselaers 給出了一個有限的“偽碰撞”結果；
1996年，MD5算法的設計被發現有缺陷，雖然當時並未被證明該缺陷是致命的，密碼學專家建議使用其它加密算法（如 SHA-1）。
2004年，MD5算法被證明不安全，原因是會產生 Hash 碰撞。[3]
2007年，研究人員發現使用 Chosen-prefix Collision 方法，可以使包含惡意代碼的程序產生合法的 MD5 值。
2008年，研究人員發現了產生相同 MD5 Hash 值的兩個可執行文件。
以上實例證明，MD5算法的安全性並不高，不能應用於對安全性要求很高的 SSL 加密及數字簽名之中。目前最被推薦的 Hash 加密算法應為 SHA-2加密算法。
MD5算法描述
MD5算法針對不定長的輸入，可以輸出固定 128 位長度的加密信息。MD5以 512 位來分組輸入的信息，每一分組又被劃分為 16 個 32 位子分組，經過算法流程最終生成四個 32 位數據聯合成為 128 位的散列。算法的具體過程如下[4]：
信息進行填充，使其位長對 512 求余的結果等於 448。將信息的長度擴展至N*512+448，其中N為一個非負整數，N可以是零。填充的方法為在信息的後面填充一個 1 和無數個0，直到滿足條件。
在這個結果後面附加一個以 64 位二進制表示的填充前信息長度。經過這兩步的處理，現在的信息的位長=N*512+448+64=(N+1)*512，即長度恰好是 512 的整數倍。這樣做的原因是為滿足後面處理中對信息長度的要求。MD5中有四個 32 位被稱作鏈接變量（Chaining Variable）的整數參數，他們的初始值分別為：A=0×67452301，B=0xefcdab89，C=0x98badcfe，D=0×10325476。
進入算法的四輪主循環運算。循環的次數是信息中 512 位信息分組的數目。主循環有四輪，每輪循環都很相似。第一輪進行 16 次操作。每次操作對a、b、c和d中的其中三個作一次非線性函數運算，然後將所得結果加上第四個變量，文本的一個子分組和一個常數。再將所得結果向左環移一個不定的數，並加上a、b、c或d中之一。最後用該結果取代a、b、c或d中之一。
經過四輪逐位運算完成之後，將A、B、C、D分別加上a、b、c、d。然後用下一分組數據繼續運行算法，最後的輸出是A、B、C和D的級聯。
存在問題
雖然 MD5 為單向 Hash 加密，是不可逆的，但根據鴿巢原理，MD5算法所產生的 32 位輸出所能夠表示的空間大小為 1632，即當樣本大於 1632≈3.4 × 1038時就會產生 Hash 碰撞。由這一結論可知，我們可以生成大量密碼樣本的哈希值，得到密碼和哈希值的一一對應關系，然後根據這個對應關系反查就可以得到哈希值所對應的密碼。但在破解密碼的 MD5 值之前，我們需要預先計算出大量數據所對應的 MD5 值。
而在互聯網應用方面，如果如文章開始所提出的問題一樣，只是對用戶密碼進行簡單 MD5 加密，是有可能通過查表入侵用戶賬戶的（盡管密碼可能不是用戶的原始密碼）。然而對於強密碼來說，通過暴力窮舉破解 MD5 值的代價也是相當大的。但根據統計結論[5]，有相當多的用戶會使用弱密碼[6]，因此可以根據統計規律建立簡單密碼所對應的 MD5 值表，從而入侵使用簡單密碼的用戶賬戶。
改進方法
由於對於密碼學 Hash 函數還需要的特性是具有雪崩效應，或者嚴格雪崩效應。其目標是對於輸入任何小的改動將使輸出變化很大。理想情況下改變任何輸入所得到的輸出結果都不相關，那麼攻擊者尋找碰撞就必須進行窮舉搜索[1]。由於 MD5 算法的這一效應，我們可以在用戶密碼創建時生成一個隨機字符串（稱之為 Salt，在另一個數據表或數據庫中存儲）與用戶口令連接在一起，然後再用散列函數對這個字符串進行 MD5 加密，之後將 MD5 加密結果結果存入數據庫中。如果 Salt 值的數目足夠大的話，它實際上就消除了對常用口令采用的字典式攻擊，因為黑客不可能在數據庫中存儲那麼多 Salt 和用戶密碼組合後的 MD5 值。當然，如果黑客獲得了數據庫的所有信息（包括 Salt 表），他們仍可以對單個用戶的密碼進行暴力枚舉破解。但將每個密碼後加一隨機串，無疑增加了暴力枚舉的難度，且不存在弱口令的問題了。更加安全的做法是，我們可以給每個密碼設置一個隨機的 Salt 值，這樣即使使用暴力枚舉破解了一個用戶的密碼，也很難再破解其他用戶的密碼了。
除了給 MD5 算法加鹽，其它的增強用戶密碼安全性的主動措施有使用更加耗時的加密算法，這樣使破解的時間也大大增加了；或者更換更安全的加密算法如 SHA-2算法；還可以像 Twitter 一樣強制用戶使用復雜密碼等等。
結論
回到文章起始提出的問題，如果我的網站存有 10 萬 MD5 密碼的數據庫落入了黑客手中，根據最近對 CSDN 密碼洩露事件的統計規律：600萬賬號中有 239 萬個賬號和其它賬號的密碼相同[5]，進行最樂觀的假設，假設這些賬號使用的都是弱密碼，且我們手中有所有這些弱密碼所對應的明文信息，則約有 40% 的密碼將被破解。對於文章起始處提出的問題來說，就是約 4 萬名用戶的密碼將被破解。而進行較保守的假設，以 CSDN 事件中排名前 10 的弱密碼為例，共有 748350 人使用了排名前 10 的弱密碼，比例為0.1%，假設真實使用排名前 1000 的弱密碼的人數為 100*0.1%=10%，且我們手中有 80% 的弱密碼所對應的明文信息，則對於文章起始處提出的問題來說，就是約 8 千名用戶的密碼將被破解。由此可見，只對用戶密碼進行簡單的 MD5 加密並不能保證全部用戶的密碼安全，大約會有 8000~40000名用戶的密碼將被查表破解。
（該估計方法存在一定問題：由於本人並未找到更好的基於真實情況的弱密碼使用統計結論，且沒有 CSDN 所洩露的數據庫，只能以果殼網的數據為基准，並且由於國殼網所提供的數據量很小，估計方法也並不准確，只是進行粗略估計，最終結果只是一個定性結論。該問題還可以進行定量的後續研究。）
