彩虹表在MySQL密碼破解中的運(yùn)用研究

莊小妹

(廣東培正學(xué)院計(jì)算機(jī)科學(xué)與工程系，廣東廣州 510830)

?

彩虹表在MySQL密碼破解中的運(yùn)用研究

莊小妹

(廣東培正學(xué)院計(jì)算機(jī)科學(xué)與工程系，廣東廣州 510830)

本文運(yùn)用Cain和RainbowCrack兩種工具生成MySQLSHA1彩虹表，并對(duì)兩種工具進(jìn)行了比較。通過(guò)實(shí)驗(yàn)分析可知，兩個(gè)工具結(jié)合使用是生成MySQL彩虹表的最佳方案，而密碼的破解使用RainbowCrack要優(yōu)于Cain。同時(shí)，本文探討了彩虹表鏈長(zhǎng)、鏈數(shù)和磁盤空間之間的關(guān)系，研究了影響彩虹表生成時(shí)間的參數(shù)，分析了影響彩虹表密碼破解時(shí)間的因素。

時(shí)間-內(nèi)存平衡法；彩虹表；MySQL；數(shù)據(jù)庫(kù)密碼破解

滲透測(cè)試技術(shù)是目前網(wǎng)絡(luò)安全的熱門技術(shù)，密碼破解是滲透測(cè)試中經(jīng)常遇到的環(huán)節(jié)。在獲得hash值的情況下，如何破解MySQL數(shù)據(jù)庫(kù)的密碼是網(wǎng)絡(luò)攻防中的常見(jiàn)問(wèn)題。MySQL密碼的破解主要有三種方法：字典法、暴力破解法和彩虹表方法。其中，字典法速度快，但命中概率比較低；暴力破解法所需時(shí)間比較長(zhǎng)；彩虹表方法結(jié)合兩者的優(yōu)勢(shì)，提供了一種有效的快速破解MySQL密碼的方法。本文主要討論基于彩虹表的MySQL數(shù)據(jù)庫(kù)密碼的破解，破解了MySQL數(shù)據(jù)庫(kù)密碼，就能通過(guò)正常途徑來(lái)訪問(wèn)數(shù)據(jù)庫(kù)，一方面可以直接對(duì)數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)行操作，另一方面可以提升權(quán)限。因此，探討MySQL密碼的破解在網(wǎng)絡(luò)攻防過(guò)程中有重要的意義[1]。

1 時(shí)間-內(nèi)存平衡法和彩虹表

彩虹表其實(shí)就是某種hash值的集合，但它的奇妙之處在于：它并不是明文和其hash值簡(jiǎn)單的一一對(duì)應(yīng)表，因?yàn)檫@樣的表需要巨大的磁盤空間作為代價(jià)。事實(shí)上，彩虹表存儲(chǔ)是經(jīng)過(guò)某種變換的“hash”值，經(jīng)過(guò)變換，磁盤空間大為減少，而根據(jù)這些值可以巧妙破解密碼。彩虹表的生成和破解都需要使用時(shí)間-內(nèi)存平衡法。

1.1 時(shí)間-內(nèi)存平衡法

最早的時(shí)間-內(nèi)存平衡法(Time-Memory Trade-Off)是Martin Hellman在1980年提出的[2]，現(xiàn)在一般簡(jiǎn)稱為時(shí)空折中方法或者是TMTO方法。其中，有一個(gè)函數(shù)是特別重要的，那就是歸約函數(shù)(Reduce Function)，通常簡(jiǎn)稱為R函數(shù)，R函數(shù)的作用是將hash值映射為明文。假設(shè)H表示hash函數(shù)，M表示明文，h表示hash值，則h=H(M)，而R(h)=M1，M與M1并沒(méi)有相似之處。如果從一個(gè)明文出發(fā)，先散列，對(duì)生成散列值歸約，對(duì)歸約的明文再散列，再歸約，如此反復(fù)多次，則得到一條明文與散列值交替的數(shù)據(jù)鏈。然后，僅記錄數(shù)據(jù)鏈的第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)，即相當(dāng)于存儲(chǔ)了整條鏈的信息，從而大大地減少了磁盤空間[3]。

TMTO破解hash值的基本思想是：如果hash值在彩虹表的某條鏈上，則由該散列值出發(fā)，經(jīng)過(guò)若干次的歸約、散列、歸約，得到的結(jié)果應(yīng)與該鏈最后一個(gè)節(jié)點(diǎn)的值相等。而由該鏈的第一個(gè)節(jié)點(diǎn)出發(fā)，經(jīng)過(guò)一系列交替的散列和歸約，應(yīng)可重新生成該散列值并找到散列前的明文，從而實(shí)現(xiàn)破解[3]。

1.2 彩虹表

TMTO方法在所有的鏈上使用了同一個(gè)歸約函數(shù)，這使得不同的鏈上可能產(chǎn)生碰撞，即不同的輸入產(chǎn)生同一個(gè)輸出，降低了破解的效率。2003年，Oechslin對(duì)TMTO方法作相對(duì)簡(jiǎn)單的修改，即在鏈上的不同位置使用不同的歸約函數(shù)[4]，采用Oechslin的方法生成的鏈表就是彩虹表，雖然是簡(jiǎn)單的修改，效果卻是顯著的，因?yàn)樗鼫p少了碰撞的發(fā)生，提高了破解的效率。

1.3 彩虹表的應(yīng)用

目前，彩虹表破解密碼已經(jīng)是世界上最為先進(jìn)的破解方法，已有多個(gè)文獻(xiàn)探討彩虹表在不同的密碼破解中的應(yīng)用。其中，李超[5]研究了彩虹表用于破解PDF文檔的密碼，破解速度比暴力破解快了50000倍；方海英[6]提到彩虹表用于破解Word文檔的密碼；李筱筱[7]探討了彩虹表用于破解PowerPoint文檔密碼。可見(jiàn)，彩虹表在密碼破解領(lǐng)域得到廣泛的應(yīng)用。

2 MySQL用戶密碼的加密

MySQL速度快、體積小、功能強(qiáng)大，而且是一種開(kāi)源的數(shù)據(jù)庫(kù)系統(tǒng)，也是很多WEB站點(diǎn)后臺(tái)所采用的數(shù)據(jù)庫(kù)系統(tǒng)。MySQL的每一個(gè)表由三個(gè)文件組成，分別是.frm文件、.myd文件和.myi文件。連接MySQL的用戶名和密碼信息存儲(chǔ)在USER表中。打開(kāi)user.myd可查看root用戶的密碼，該密碼經(jīng)過(guò)SHA1加密獲得。MySQL實(shí)際上是使用了兩次SHA1夾雜一次unhex的方式對(duì)用戶密碼進(jìn)行了加密，具體的算法可以用公式表示，即password_str=concat(’*’,SHA1(unhex(SHA1(password))))，得到41位密碼[8]，把*刪除后，密碼是40位。本文MySQLSHA1密碼的破解是指40位密碼的破解。

3 基于彩虹表的MySQL用戶密碼的破解

3.1 彩虹表的獲得方法

彩虹表的獲得方法主要有三種：一是通過(guò)互聯(lián)網(wǎng)下載；二是花錢購(gòu)買；三是使用工具生成。互聯(lián)網(wǎng)下載的彩虹表大都是基于MD5或者是NTLM hash或LM hash的。例如，開(kāi)源項(xiàng)目ophcrack提供的彩虹表有table-xp-free-small，table-xp-free-fast，table-xp-special。這幾個(gè)彩虹表能夠迅速恢復(fù)或破解密碼長(zhǎng)度小于14位的Windows密碼，但對(duì)于破解md5、SHA1的密碼或MySQL數(shù)據(jù)庫(kù)的密碼則無(wú)能為力。有些彩虹表的大小可達(dá)上百G，在網(wǎng)速不理想的情況下，時(shí)間的成本也是相當(dāng)可觀的。由于MySQL使用的哈希算法是SHA1，而從互聯(lián)網(wǎng)下載的SHA1彩虹表一般是rti，這并不是破解工具Cain和RainbowCrack所支持的格式。因此，使用工具生成彩虹表是破解MySQL密碼的一個(gè)最佳的方案。

3.2 彩虹表的生成方法

彩虹表用于破解密碼是很快速的，但生成彩虹表的時(shí)間通常是很漫長(zhǎng)的，一般根據(jù)明文的空間、明文的長(zhǎng)度以及生成彩虹表的參數(shù)不同而變化。生成彩虹表的參數(shù)主要有三個(gè)：鏈的長(zhǎng)度、鏈的數(shù)目以及彩虹表的個(gè)數(shù)。為了縮短彩虹表生成的時(shí)間，目前多數(shù)采用GPU的方式來(lái)生成彩虹表。簡(jiǎn)玲[9]比較了普通計(jì)算機(jī)與GPU生成彩虹表的時(shí)間，從中可以看出，GPU生成彩虹表的時(shí)間大為減少，但該方法的成本昂貴。李聰[10]提供了一種基于分布式彩虹表的生成方法，但此方法比較復(fù)雜且步驟多。在普通的計(jì)算機(jī)環(huán)境下，使用現(xiàn)成工具生成彩虹表是最為快捷的方法，生成彩虹表的工具目前主要有Cain和RainbowCrack。本文的實(shí)驗(yàn)環(huán)境如表1所示。

表1 實(shí)驗(yàn)環(huán)境

3.3 彩虹表生成工具比較

Cain是一個(gè)免費(fèi)的密碼破解軟件，它提供了能夠生成彩虹表的工具Winrtgen。Winrgen運(yùn)行在Windows系統(tǒng)，能夠生成的彩虹表類型很多，包括MD5、NTLM hash、MySQLSHA1等。該工具支持的明文空間包括數(shù)字、小寫字母、大寫字母、混合字母、特殊符號(hào)、所有字符等。Winrtgen生成彩虹表的優(yōu)點(diǎn)是：使用方便；對(duì)明文的長(zhǎng)度沒(méi)有限制；可預(yù)測(cè)生成彩虹表的時(shí)間以及該彩虹表用于密碼破解的時(shí)間；還提供了彩虹表占用空間的大小以及破解的成功率；當(dāng)調(diào)整彩虹表鏈長(zhǎng)以及鏈的個(gè)數(shù)時(shí)，這些預(yù)測(cè)的數(shù)據(jù)都自動(dòng)變化和顯示。

RainbowCrack是一個(gè)開(kāi)源的工具，其主要作用是實(shí)現(xiàn)Philippe Oechslin的時(shí)間內(nèi)存平衡法。與Cain不同，RainbowCrack所提供功能主要通過(guò)命令行的方式來(lái)實(shí)現(xiàn)，其中rtgen.exe的作用是生成彩虹表，rtsort.exe的作用是對(duì)彩虹表排序，rcrack.exe是利用彩虹表破解hash值。rtgen所支持的hash算法封裝在alglib0.dll中。

rtgen所支持的明文類型存放在文本文件charset.txt中，rtgen所生成的彩虹表的格式是rt，這個(gè)文件必須經(jīng)過(guò)rtsort處理后才能用于破解，否則提示格式不正確。排序后的彩虹表能更好地進(jìn)行匹配。通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，rtsort不僅可以處理rtgen所生成的彩虹表，而且也可以處理Cain所生成的彩虹表。不過(guò)，Cain所生成的彩虹并不需要排序處理，直接可以用于破解。Cain與RainbowCrack功能的比較如表2所示。

表2 Cain與RainbowCrack功能的比較

從CPU占用率可以看出，Cain生成彩虹表是用單線程來(lái)實(shí)現(xiàn)的。為了比較Cain與RainbowCrack生成彩虹表的效率，使用同一臺(tái)計(jì)算機(jī)分別生成了一個(gè)8位的明文空間為數(shù)字的MySQL彩虹表和長(zhǎng)度為6位的數(shù)字+小寫字母的MySQLSHA1彩虹表，結(jié)果如表3所示。

表3 Cain與RainbowCrack生成彩虹表時(shí)間的比較

在參數(shù)相同的情況下，RainbowCrack生成的時(shí)間大大少于Cain所花費(fèi)的時(shí)間，但RainbowCrack并不能預(yù)測(cè)破解成功率，也不能預(yù)算生成彩虹表所需要的時(shí)間以及破解所需要的時(shí)間。根據(jù)以上的實(shí)驗(yàn)分析發(fā)現(xiàn)，在普通計(jì)算機(jī)的環(huán)境下，兩個(gè)工具的結(jié)合是最優(yōu)的，即先通過(guò)Cain設(shè)置好彩虹表的參數(shù)并且進(jìn)行預(yù)算，再通過(guò)RainbowCrack執(zhí)行彩虹表的生成。成功生成彩虹表后，RainbowCrack顯示實(shí)際所使用的時(shí)間。

3.4 影響彩虹表的占用空間和生成時(shí)間的因素分析

彩虹表的生成不僅要考慮時(shí)間的成本，還要考慮磁盤空間以及破解的成功率以及破解的時(shí)間。關(guān)于破解的成功率，Oechslin在他的論文中給出一個(gè)計(jì)算公式，而生成時(shí)間和磁盤空間可通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)其中的規(guī)律。表4顯示使用Cain生成MySQLSHA1彩虹表時(shí)，彩虹表的鏈長(zhǎng)、鏈數(shù)與占用磁盤空間關(guān)系。

表4 鏈長(zhǎng)、鏈數(shù)與磁盤空間的關(guān)系

從表4的第一行和第二行可以看出，當(dāng)鏈數(shù)不變的情況下，即使鏈長(zhǎng)發(fā)生了變化，占用的空間并沒(méi)有變化；從第三行和第四行可以看出，在鏈長(zhǎng)x鏈數(shù)(即總節(jié)點(diǎn)數(shù))不變情況下，鏈數(shù)越大，磁盤空間越大；從第五行和第六行可以看出，當(dāng)鏈數(shù)增加為原來(lái)的10倍時(shí)，磁盤的空間也增加為原來(lái)的10倍，可見(jiàn)彩虹表占用空間只與鏈數(shù)有關(guān)，與鏈長(zhǎng)無(wú)關(guān)。

表5 鏈長(zhǎng)、鏈數(shù)與生成時(shí)間和破解時(shí)間的關(guān)系

從表5可以看出，當(dāng)鏈長(zhǎng)x鏈數(shù)(即總的節(jié)點(diǎn)數(shù))不變時(shí)，無(wú)論鏈長(zhǎng)與鏈數(shù)如何變化，生成的時(shí)間基本相同，可見(jiàn)生成表的時(shí)間與總節(jié)點(diǎn)數(shù)相關(guān)。彩虹表的生成也必須考慮破解的時(shí)間，在總節(jié)點(diǎn)數(shù)不變的情況下，鏈長(zhǎng)越短，破解的時(shí)間越短，而付出的代價(jià)是磁盤空間越大。時(shí)間與空間此消彼長(zhǎng)，這也正符合了時(shí)空折中算法的描述。

3.5 基于彩虹表的MySQL密碼的破解

獲得MySQL用戶密碼的hash值后，就可以利用Cain或RainbowCrack進(jìn)行破解。Cain的破解比較簡(jiǎn)單，因?yàn)樗峁┑氖且环N圖形操作界面，可以直接復(fù)制hash值進(jìn)行破解，也可以通過(guò)ODBC將hash值導(dǎo)入進(jìn)行破解。破解所使用的彩虹表可以是Cain生成的，也可以是RainbowCrack生成的。破解成功后，兩種工具都顯示破解所使用的時(shí)間。

表6 破解時(shí)間的比較

從表6可以看出，RainbowCrack的破解時(shí)間與Cain并無(wú)太大的區(qū)別，而Cain提供的是一種圖形操作界面，從而使用更為方便。在破解失敗時(shí)，RainbowCrack給出的提示更快一些。有時(shí)Cain還會(huì)發(fā)生彩虹表讀取失敗的情況，穩(wěn)定性稍遜。所以，破解時(shí)使用RainbowCrack是一種更優(yōu)的方案。

4 結(jié)論

在MySQL用戶密碼的破解方法中，彩虹表方法的破解是最快的。但MySQLSHA1彩虹表并不適合從互聯(lián)網(wǎng)下載，需要用戶自己生成。彩虹表的生成主要設(shè)置鏈長(zhǎng)和鏈數(shù)。通過(guò)對(duì)Cain和RainbowCrack兩個(gè)工具的實(shí)驗(yàn)和比較分析，發(fā)現(xiàn)Cain能較好地預(yù)算彩虹表的生成時(shí)間、磁盤占用空間、破解成功率和破解時(shí)間，但生成表的時(shí)間較長(zhǎng)；而RainbowCrack因?yàn)椴捎枚嗑€程，生成彩虹表的時(shí)間比Cain大為減少。可得出Cain+RainbowCrack是一個(gè)最佳的生成MySQLSHA1彩虹表的方案。彩虹表占用空間只與鏈數(shù)有關(guān)，與鏈長(zhǎng)無(wú)關(guān)。在鏈長(zhǎng)x鏈數(shù)的值不變的情況下，鏈長(zhǎng)越短則破解時(shí)間越快，而鏈數(shù)越大，則占用空間越大。

[1]陳小兵,范淵,孫立偉.Web滲透及技術(shù)實(shí)戰(zhàn)案例解析[M].北京:電子工業(yè)出版,2012:66-67.

[2]蘇烈華,李恒訓(xùn),李鎖雷.基于時(shí)空折中算法的密碼分析系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].信息網(wǎng)絡(luò)安全,2013(5):42-46.

[3]王小鑒,廖曉峰,黃宏宇.基于歸約函數(shù)數(shù)量裁減的彩虹表技術(shù)改進(jìn)[J].計(jì)算機(jī)程,2013(7):156-160.

[4]榮凱,邱衛(wèi)東,李萍.基于彩虹表的hash攻擊研究[J].信息安全與通信保密,2011(4):74-76.

[5]李超,陳丹偉.基于彩虹表的PDF文檔口令破解研究[J].計(jì)算機(jī)應(yīng)用與軟件,2012(10):137-139.

[6]方海英.基于時(shí)空折衷算法的Word文檔破解研究[D].杭州:杭州電子科技大學(xué),2009.

[7]李筱筱.GPU異構(gòu)系統(tǒng)上針對(duì)PowerPoint的彩虹表攻擊實(shí)現(xiàn)[J].北京電子科技學(xué)院學(xué)報(bào),2013(4):85-91.

[8]cenalulu.關(guān)于MySQL密碼你應(yīng)該知道的那些事[EB/OL].(2015-02-27)[2016-01-04].http://cenalulu.github.io/MySQL/myall-about-MySQL-password,2015-2-27.

[9]簡(jiǎn)玲,徐賽賽,邱衛(wèi)東,等.基于GPU的高性能彩虹表生成[J].信息安全與通信保密,2015(2):102-108.

[10]李聰,葉猛,江舟,等.基于分布式GPU的彩虹表密碼攻擊系統(tǒng)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用,2015(7):69-73.

Application of Rainbow Table in MySQL Password Cracking

ZHUANG Xiao-mei

(Department of Computer Science and Engineering,Guangdong Peizheng College,Guangzhou Guangdong 510830,China)

Use Cain and RainbowCrack tools to generate MySQLSHA1Rainbow tables,including comparisons of the two tools. It is the best scheme of generating MySQL Rainbow tables to use the two tools both through experimental analysis. RainbowCrack is more benefit than Cain when cracking MySQL password by Rainbow table. The relations between storage spaces and the length of Rainbow table were discussed as well as the counts of Rainbow table;the influence of various parameters on time of generating Rainbow table was studied,as well as the time of cracking password.

Time-Memory Trade-Off ；Rainbow Table；MySQL；database password cracking

2016-05-15

廣東培正學(xué)院2014-2015年度校級(jí)科研項(xiàng)目“彩虹表技術(shù)原理及應(yīng)用”(15pzxmyb020)。

莊小妹(1973- )，女，講師，碩士，從事信息安全研究。

TP309.2

A

2095-7602(2016)10-0047-05