MD5加密算法在數據庫安全的應用與查表攻擊
MD5為現在應用最廣泛的Hash算法之一，在1992年由MIT的RonaldL.Riverst提出，由MD4演化而來。該算法廣泛應用于互聯網網站的用戶數據加密，能夠將用戶密碼加密為128位的長整數。數據庫并不明文存儲用戶密碼，而是在用戶登錄時將輸入密碼字符串進行MD5加密，與數據庫中所存儲的MD5值匹配，從而降低密碼數據庫被盜取后用戶損失的風險。
但由于Hash碰撞的存在，MD5加密的數據并不安全，可以由生成相同Hash值的字符串破解，所以提出了加入隨機數salt的MD5加密方法，一定程度上增大了字典攻擊的難度。
問題提出
前一陣在新浪微博上，有一個人發布了這樣一條微博：“出道互聯網安全常識數學題……假設你的網站所有用戶密碼都是md5加密（單向散列，非可逆）的，假設你網站有10萬會員，如果你的用戶庫丟了，會有多少會員密碼被破解？想想看。”當時我的一位朋友認為10萬個密碼全部都會被破解，我卻不這樣認為，因為根據我的先驗知識：
（1）MD5加密算法在互聯網應用中廣泛被使用，MD5不是簡單的古典加密算法，不能通過逆向Decrypt解密，只能通過Hash碰撞破解（Hack）；
（2）我曾經看過對同一個字符串進行MD5加密的結果，產生結果是隨機的字符串（后來經過查找資料發現我所看到的不是簡單的MD5加密，而是加鹽后的結果）；
（3）MD5用作密碼加密算法并不是絕對安全的，因為可能產生Hash碰撞，簡單密碼的MD5加密可以通過彩虹表查找到；
（4）我曾見過幾個破解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-DigestAlgorithm5，在1991年由MIT的RonaldL.Riverst提出，由MD4演化而來，最終生成128位（4個32位的16進制數）的信息摘要算法。[2]MD5算法是一個不可逆的字符串變換算法，即看到源程序和算法描述，也無法將一個MD5的值變換回原始的字符串。
1993年，DenBoer和Bosselaers給出了一個有限的“偽碰撞”結果；
1996年，MD5算法的設計被發現有缺陷，雖然當時并未被證明該缺陷是致命的，密碼學專家建議使用其它加密算法（如SHA-1）。
2004年，MD5算法被證明不安全，原因是會產生Hash碰撞。[3]
2007年，研究人員發現使用Chosen-prefixCollision方法，可以使包含惡意代碼的程序產生合法的MD5值。
2008年，研究人員發現了產生相同MD5Hash值的兩個可執行文件。
以上實例證明，MD5算法的安全性并不高，不能應用于對安全性要求很高的SSL加密及數字簽名之中。目前最被推薦的Hash加密算法應為SHA-2加密算法。
MD5算法描述
MD5算法針對不定長的輸入，可以輸出固定128位長度的加密信息。MD5以512位來分組輸入的信息，每一分組又被劃分為16個32位子分組，經過算法流程最終生成四個32位數據聯合成為128位的散列。算法的具體過程如下[4]：
（1）信息進行填充，使其位長對512求余的結果等于448。將信息的長度擴展至N*512+448，其中N為一個非負整數，N可以是零。填充的方法為在信息的后面填充一個1和無數個0，直到滿足條件。
（2）在這個結果后面附加一個以64位二進制表示的填充前信息長度。經過這兩步的處理，現在的信息的位長=N*512+448+64=(N+1)*512，即長度恰好是512的整數倍。這樣做的原因是為滿足后面處理中對信息長度的要求。MD5中有四個32位被稱作鏈接變量（ChainingVariable）的整數參數，他們的初始值分別為：A=0×67452301，B=0xefcdab89，C=0x98badcfe，D=0×10325476。
（3）進入算法的四輪主循環運算。循環的次數是信息中512位信息分組的數目。主循環有四輪，每輪循環都很相似。第一輪進行16次操作。每次操作對a、b、c和d中的其中三個作一次非線性函數運算，然后將所得結果加上第四個變量，文本的一個子分組和一個常數。再將所得結果向左環移一個不定的數，并加上a、b、c或d中之一。最后用該結果取代a、b、c或d中之一。
（4）經過四輪逐位運算完成之后，將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所泄露的數據庫，只能以果殼網的數據為基準，并且由于國殼網所提供的數據量很小，估計方法也并不準確，只是進行粗略估計，最終結果只是一個定性結論。該問題還可以進行定量的后續研究。）
編者按：本文作者為北師大的大三學生張俏，女Geek，在CSDN等各大網站的用戶數據被泄露之后，她就MD5加密問題寫下此文，發表了自己的看法，如果有讀者想要跟作者進一步探討，可以在新浪微博@阿豆拉。
【編輯推薦】
