基于HBase的彩虹表MD5哈希密碼解密*

張 悅

（深圳職業(yè)技術(shù)學(xué)院 電子與通信工程學(xué)院，廣東 深圳 518055）

基于HBase的彩虹表MD5哈希密碼解密*

張 悅

（深圳職業(yè)技術(shù)學(xué)院 電子與通信工程學(xué)院，廣東 深圳 518055）

基于時間-內(nèi)存平衡（Time-Memory Trade-Off）技術(shù)的彩虹表已經(jīng)成為破解MD5哈希（HASH）密碼的有效手段，但由于彩虹表文件龐大，彩虹表的生成、存儲和分析使用都十分復(fù)雜和耗時．本文提出使用HBase作為彩虹表存儲和分析使用的技術(shù)方案，實驗驗證了該方案的可行性和有效性．

彩虹表；Hash函數(shù)；HBase

信息安全領(lǐng)域中，哈希（HASH）函數(shù)是被廣泛應(yīng)用的關(guān)鍵技術(shù)，主要包括文件加密和校驗、數(shù)字簽名和證書、密碼鑒權(quán)等．哈希函數(shù)的原理是一個將任意長度的輸入或內(nèi)容映射到固定長度的摘要（哈希值）的過程，哈希函數(shù)有很多種，主要包括MDx和SHA 2類，其中MD5使用較為廣泛．

哈希密碼解密則是哈希函數(shù)的反過程，是由固定長度的哈希值反向獲取原始密碼原文的過程，即：對于給出的一個q，反算出一個p來滿足q = H(p)．哈希函數(shù)的最大特點(diǎn)是不可逆性，即哈希密碼的解密是不可以使用一個特定函數(shù)反算出來的，因此獲取哈希密碼解密的方法只可能有2種方式：窮舉暴力破解法和查表法．然而，由于原始密碼p長度和復(fù)雜性等的不確定性，2種破解方法都有很大的局限性．窮舉暴力破解法設(shè)計的計算量大且破解時間長到無法忍受；查表法要求提前窮舉密碼的可能性并計算存儲對應(yīng)表，其時間和存儲量也可能無法承擔(dān)．彩虹表（Rainbow Tables）技術(shù)結(jié)合了以上2種方法的優(yōu)點(diǎn)，通過增加一些運(yùn)算量來換取節(jié)省查詢表的存儲空間，目前已經(jīng)成為哈希密碼解密方面最有效和實用的技術(shù)．本文引入云計算和HBase來提高彩虹表的運(yùn)算和存儲能力．

1 彩虹表技術(shù)

彩虹表技術(shù)最早源于1980年Hellman提出的時間-內(nèi)存平衡（Time-Memory Trade-Off，簡稱TMTO）經(jīng)典表[1]，之后TMTO技術(shù)得到不斷地研究和改進(jìn)，2003年Oechslin對經(jīng)典的TMTO改進(jìn)后，正式命名為彩虹表[2]．

1.1 Hellman TMTO經(jīng)典表算法和彩虹表

理論上講，對于一個密碼破解過程，假設(shè)密碼空間是N，執(zhí)行的操作次數(shù)為T，占用存儲空間為M，那么使用窮舉法需要：T=N，M=1；使用查表法需要：T=1，M=N．

Hellman經(jīng)過研究，使用Hellman TMTO經(jīng)典表算法，破解過程可以得到簡化．他的核心思想是對應(yīng)于原哈希函數(shù)引入了一個截短函數(shù)R函數(shù)（Reduction Function），產(chǎn)生一個從密文空間到密鑰空間的映射．這種算法實際上是利用鏈表進(jìn)行破解的過程，但這個過程中可能會出現(xiàn)誤報的問題，也叫誤警或Hash沖突．誤報是指當(dāng)找到了某個鏈尾匹配時，而密鑰卻不在此鏈尾對應(yīng)的鏈中．發(fā)生誤報有2種情況，第一種情況是由于鏈與鏈之間會有碰撞合并的現(xiàn)象，即同一個表中的幾條鏈有相同的鏈尾；第二種情況是不同表中的幾條鏈也可能有相同的鏈尾．誤報的根本原因是R截短函數(shù)并不是完全一一映射，不同的鏈結(jié)點(diǎn)可能在經(jīng)過R函數(shù)計算之后得到的值相等，從而造成了多條鏈合并．表的規(guī)模越大，鏈與鏈之間互相合并的可能性就增大．因此鏈合并的情況越多，產(chǎn)生誤報的可能性就增加，破解的成功率也就降低．因此R函數(shù)的選擇也非常重要．

Hellman TMTO經(jīng)典表算法有其不可回避的缺點(diǎn)，即當(dāng)同一個表中的某2個節(jié)點(diǎn)鏈碰撞以后，這2條鏈就合并了，從而造成破解成功率降低的問題．2003年Oechslin發(fā)表了對經(jīng)典Hellman TMTO表的改進(jìn)算法[2]，使得2條鏈中的節(jié)點(diǎn)即使碰撞也不會合并，并將此表正式命名為彩虹表．

與傳統(tǒng)Hellman TMTO做法不同的是，在彩虹鏈的生成過程中，不再使用同一個R函數(shù)，而是對每條鏈的每個節(jié)點(diǎn)都使用不同的R函數(shù)，因此就很難發(fā)生碰撞了，這樣就使得彩虹表的破解效率大大提高．

1.2 MD5彩虹表

彩虹表破解密碼也有其局限性，其成功實施依賴2個要點(diǎn)：

1）要破解的密碼系統(tǒng)使用的哈希函數(shù)是簡單的、可以快速計算的；

2）要破解的密碼系統(tǒng)沒有采用 salt 機(jī)制．

哈希函數(shù)如 MD5滿足這種要求，可以通過彩虹表進(jìn)行解密．

彩虹表的核心思想是使用不同的R截短函數(shù)，具體是在所有鏈中節(jié)點(diǎn)k的不同位置j處使用一系列不同的截短函數(shù)Rj（1≤j≤t-1，t為鏈長）．對于MD5算法，每一次計算Rj時，先取128bit的MD5值的低4個字節(jié)，加上彩虹表索引和當(dāng)前節(jié)點(diǎn)k的位置j，生成值只取低位部分27bit并分成3個9bit段，再處理成512字節(jié)字符集的索引，最終生成影射到N（明文空間）上的R值．MD5的R函數(shù)，處理流程如圖1所示．

生成MD5彩虹表的過程中，在不同的鏈中，不同的位置出現(xiàn)碰撞，鏈不需要合并，只有在相同的位置j出現(xiàn)碰撞，這2個鏈才需要合并．

圖1 MD5的R函數(shù)處理流程圖

2 HBase

HBase - Hadoop Database，是Apache Hadoop云項目的1個子項目，它與其它項目一起構(gòu)成了Hadoop的整個生態(tài)，如圖2所示．

HBase是一種列數(shù)據(jù)庫，它基于Hadoop的分布式存儲和分布式運(yùn)算架構(gòu)，是一個具有分布式、高性能、高可靠性、高擴(kuò)展性的數(shù)據(jù)存儲系統(tǒng)．它特別適合非結(jié)構(gòu)化數(shù)據(jù)存儲，以及特別龐大的數(shù)據(jù)存儲，Hadoop本身具有豐富的訪問接口，可以方便地對HBase進(jìn)行管理、訪問和應(yīng)用編程．

對HBase應(yīng)用編程的方法是采用Hadoop的并行運(yùn)算模型MapReduce[3]，如圖3所示．

圖2 Hadoop 生態(tài)系統(tǒng)

HBase與Hadoop無縫集成，提供了豐富的編程API，可以方便地使用MapReduce對HBase Table的操作進(jìn)行編程，我們只要開發(fā)MapReduce Job就可以了．

3 HBase應(yīng)用于MD5彩虹表生成和密碼破解

3.1 HBase應(yīng)用于彩虹表的優(yōu)勢

主要表現(xiàn)在2個方面：首先，HBase基于Hadoop分布式基礎(chǔ)架構(gòu)，有良好的分布式性能和分布式擴(kuò)展性，適應(yīng)于彩虹表的龐大存儲規(guī)模．其次，應(yīng)用HBase能通過Map/Reduce的強(qiáng)大分布處理能力，對彩虹表的生成和破解提供優(yōu)秀的運(yùn)算性能保證．

3.2 MD5彩虹表生成

MD5彩虹表的生成是一個耗時間耗資源耗存儲的過程，時間耗費(fèi)主要是在計算彩虹鏈時不斷地計算哈希值的過程中，另外生成彩虹表需要很大的存儲空間，比如對10位全字符空間的MD5，其彩虹表所需的存儲空間要根據(jù)鏈長而變化，但一定需要TB級的存儲．

我們構(gòu)建一個私有云平臺，采用HBase作為彩虹表的存儲方式，采用Map/Reduce編程框架對彩虹表的生成過程進(jìn)行編程，使用C語言編程，通過構(gòu)建Map/Reduce Job任務(wù)來調(diào)用此核心C程序來生成彩虹表．因此，彩虹表的生成過程中，運(yùn)算和存儲任務(wù)會自動分配給云的各個計算節(jié)點(diǎn)上進(jìn)行并行處理，處理的結(jié)果即彩虹表鏈直接寫入預(yù)定義的HBase表中．這種并行處理機(jī)制實現(xiàn)了對彩虹表生成過程的加速．具體的處理模型如圖4所示．

圖4 彩虹表MapRduc處理

MD5彩虹表生成過程中，鏈表的長度選擇也很重要，選擇長了，可以節(jié)約存儲，但會增加運(yùn)算量和運(yùn)算時間．試驗中我們選擇不同的鏈表長度，結(jié)果也反應(yīng)了這一點(diǎn)．

3.3 MD5彩虹表密碼破解

由于彩虹表存儲空間巨大，因此使用HBase存儲就能發(fā)揮其優(yōu)勢，在密碼破解時，同樣采用Map/Reduce任務(wù)方式進(jìn)行，采用C語言編程，用Map/Reduce Job任務(wù)調(diào)用此C程序完成對HBase的搜索，這種方式實際上是調(diào)用云上各個計算節(jié)點(diǎn)并行對HBase中的彩虹表進(jìn)行查詢比對及處理，可以更快地完成密碼破解工作．MD5 Hash的破解流程如圖5所示.

圖5 MD5 Hash破解流程

4 實驗結(jié)果

實際實驗中，我們搭建了12個節(jié)點(diǎn)的Hadoop集群環(huán)境，使用1個節(jié)點(diǎn)作為NameNode和JobTracker，即云主控機(jī)，其它11個節(jié)點(diǎn)均做DataNode和TaskTracker，每個節(jié)點(diǎn)的具體配置如下：

CPU：至強(qiáng) E5-2403 (1.80GHz)

內(nèi)存：2GB

硬盤：2TB

Hadoop：1.1

彩虹表存儲于HBase中．

實驗中，先生成一個明文長度為1～8位由字母和數(shù)字組成的128bit MD5彩虹表，鏈表長度設(shè)定為2000，再隨機(jī)選取一些hash值來進(jìn)行破解，并對多次試驗結(jié)果進(jìn)行統(tǒng)計分析．實驗及分析對比結(jié)果見表1．很明顯，采用HBase的MD5彩虹表生成和破解的速度有明顯優(yōu)勢，且節(jié)點(diǎn)越多速度越高．

表1 實驗及分析對比結(jié)果

[1] Hellman M E. A cryptanalytic time-memory trade off[J]．IEEE Transaction on Information Theory, 1980，IT-26：401-406．

[2] Philippe Oechslin. Making a faster cryptanalytic timememory trade-off[C]//Annual International Cryptology Conference(CRYPTO), Advances in Cryptography, Lecture Notes in Computer Science, 2003，279：617-630．

[3] Lars George. HBase: The Definitive Guide[M]. O’REILLY, Media Inc, 2011．

Deciphering Rainbow Table MD5 Hash Password Based on HBase

ZHANG Yue

（School of Electronic and Communication Engineering, Shenzhen Polytechnic, Shenzhen, Guangdong 518055, China）

Rainbow Tables has become an effective approach for deciphering MD5 hash password based on time-Memory trade-off technology. However, rainbow table file is beleaguered with huge size, complication and time-consuming in producing, storing and analyzing Rainbow Tables. A new approach for storing and analyzing Rainbow Tables based on HBase is proposed, and the lab experiments verified its feasibility and effectiveness.

Rainbow tables; Hash; HBase

TP311

A

1672-0318（2015）01-0018-05

10.13899/j.cnki.szptxb.2015·01, 004

2014-08-28

*項目來源：深圳職業(yè)技術(shù)學(xué)院校級科研基金資助項目（編號：2213K3180029）

張悅（1968-），女，江蘇人，碩士，副教授，主要研究方向：數(shù)據(jù)通信．