莊小妹

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

?

彩虹表在MySQL密碼破解中的運用研究

莊小妹

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

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

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

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

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

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

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

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

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

1.2 彩虹表

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

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

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

2 MySQL用戶密碼的加密

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

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

3.1 彩虹表的獲得方法

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

3.2 彩虹表的生成方法

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

表1 實驗環(huán)境

3.3 彩虹表生成工具比較

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

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

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

表2 Cain與RainbowCrack功能的比較

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

表3 Cain與RainbowCrack生成彩虹表時間的比較

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

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

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

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

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

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

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

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

獲得MySQL用戶密碼的hash值后，就可以利用Cain或RainbowCrack進行破解。Cain的破解比較簡單，因為它提供的是一種圖形操作界面，可以直接復(fù)制hash值進行破解，也可以通過ODBC將hash值導(dǎo)入進行破解。破解所使用的彩虹表可以是Cain生成的，也可以是RainbowCrack生成的。破解成功后，兩種工具都顯示破解所使用的時間。

表6 破解時間的比較

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

4 結(jié)論

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

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

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

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

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

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

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

[7]李筱筱.GPU異構(gòu)系統(tǒng)上針對PowerPoint的彩虹表攻擊實現(xiàn)[J].北京電子科技學(xué)院學(xué)報,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]簡玲,徐賽賽,邱衛(wèi)東,等.基于GPU的高性能彩虹表生成[J].信息安全與通信保密,2015(2):102-108.

[10]李聰,葉猛,江舟,等.基于分布式GPU的彩虹表密碼攻擊系統(tǒng)[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年度校級科研項目“彩虹表技術(shù)原理及應(yīng)用”(15pzxmyb020)。

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

TP309.2

A

2095-7602(2016)10-0047-05