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

張 悅

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

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

張 悅

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

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

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

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

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

1 彩虹表技術

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

1.1 Hellman TMTO經典表算法和彩虹表

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

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

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

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

1.2 MD5彩虹表

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

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

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

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

彩虹表的核心思想是使用不同的R截短函數(shù)，具體是在所有鏈中節(jié)點k的不同位置j處使用一系列不同的截短函數(shù)Rj（1≤j≤t-1，t為鏈長）．對于MD5算法，每一次計算Rj時，先取128bit的MD5值的低4個字節(jié)，加上彩虹表索引和當前節(jié)點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個子項目，它與其它項目一起構成了Hadoop的整個生態(tài)，如圖2所示．

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

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

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

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

3 HBase應用于MD5彩虹表生成和密碼破解

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

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

3.2 MD5彩虹表生成

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

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

圖4 彩虹表MapRduc處理

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

3.3 MD5彩虹表密碼破解

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

圖5 MD5 Hash破解流程

4 實驗結果

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

CPU：至強 E5-2403 (1.80GHz)

內存：2GB

硬盤：2TB

Hadoop：1.1

彩虹表存儲于HBase中．

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

表1 實驗及分析對比結果

[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è)技術學院校級科研基金資助項目（編號：2213K3180029）

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