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