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