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

张 悦

（深圳职业技术学院 电子与通信工程学院，广东 深圳 518055）

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

张 悦

（深圳职业技术学院 电子与通信工程学院，广东 深圳 518055）

基于时间-内存平衡（Time-Memory Trade-Off）技术的彩虹表已经成为破解MD5哈希（HASH）密码的有效手段，但由于彩虹表文件庞大，彩虹表的生成、存储和分析使用都十分复杂和耗时．本文提出使用HBase作为彩虹表存储和分析使用的技术方案，实验验证了该方案的可行性和有效性．

彩虹表；Hash函数；HBase

信息安全领域中，哈希（HASH）函数是被广泛应用的关键技术，主要包括文件加密和校验、数字签名和证书、密码鉴权等．哈希函数的原理是一个将任意长度的输入或内容映射到固定长度的摘要（哈希值）的过程，哈希函数有很多种，主要包括MDx和SHA 2类，其中MD5使用较为广泛．

哈希密码解密则是哈希函数的反过程，是由固定长度的哈希值反向获取原始密码原文的过程，即：对于给出的一个q，反算出一个p来满足q = H(p)．哈希函数的最大特点是不可逆性，即哈希密码的解密是不可以使用一个特定函数反算出来的，因此获取哈希密码解密的方法只可能有2种方式：穷举暴力破解法和查表法．然而，由于原始密码p长度和复杂性等的不确定性，2种破解方法都有很大的局限性．穷举暴力破解法设计的计算量大且破解时间长到无法忍受；查表法要求提前穷举密码的可能性并计算存储对应表，其时间和存储量也可能无法承担．彩虹表（Rainbow Tables）技术结合了以上2种方法的优点，通过增加一些运算量来换取节省查询表的存储空间，目前已经成为哈希密码解密方面最有效和实用的技术．本文引入云计算和HBase来提高彩虹表的运算和存储能力．

1 彩虹表技术

彩虹表技术最早源于1980年Hellman提出的时间-内存平衡（Time-Memory Trade-Off，简称TMTO）经典表[1]，之后TMTO技术得到不断地研究和改进，2003年Oechslin对经典的TMTO改进后，正式命名为彩虹表[2]．

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

理论上讲，对于一个密码破解过程，假设密码空间是N，执行的操作次数为T，占用存储空间为M，那么使用穷举法需要：T=N，M=1；使用查表法需要：T=1，M=N．

Hellman经过研究，使用Hellman TMTO经典表算法，破解过程可以得到简化．他的核心思想是对应于原哈希函数引入了一个截短函数R函数（Reduction Function），产生一个从密文空间到密钥空间的映射．这种算法实际上是利用链表进行破解的过程，但这个过程中可能会出现误报的问题，也叫误警或Hash冲突．误报是指当找到了某个链尾匹配时，而密钥却不在此链尾对应的链中．发生误报有2种情况，第一种情况是由于链与链之间会有碰撞合并的现象，即同一个表中的几条链有相同的链尾；第二种情况是不同表中的几条链也可能有相同的链尾．误报的根本原因是R截短函数并不是完全一一映射，不同的链结点可能在经过R函数计算之后得到的值相等，从而造成了多条链合并．表的规模越大，链与链之间互相合并的可能性就增大．因此链合并的情况越多，产生误报的可能性就增加，破解的成功率也就降低．因此R函数的选择也非常重要．

Hellman TMTO经典表算法有其不可回避的缺点，即当同一个表中的某2个节点链碰撞以后，这2条链就合并了，从而造成破解成功率降低的问题．2003年Oechslin发表了对经典Hellman TMTO表的改进算法[2]，使得2条链中的节点即使碰撞也不会合并，并将此表正式命名为彩虹表．

与传统Hellman TMTO做法不同的是，在彩虹链的生成过程中，不再使用同一个R函数，而是对每条链的每个节点都使用不同的R函数，因此就很难发生碰撞了，这样就使得彩虹表的破解效率大大提高．

1.2 MD5彩虹表

彩虹表破解密码也有其局限性，其成功实施依赖2个要点：

1）要破解的密码系统使用的哈希函数是简单的、可以快速计算的；

2）要破解的密码系统没有采用 salt 机制．

哈希函数如 MD5满足这种要求，可以通过彩虹表进行解密．

彩虹表的核心思想是使用不同的R截短函数，具体是在所有链中节点k的不同位置j处使用一系列不同的截短函数Rj（1≤j≤t-1，t为链长）．对于MD5算法，每一次计算Rj时，先取128bit的MD5值的低4个字节，加上彩虹表索引和当前节点k的位置j，生成值只取低位部分27bit并分成3个9bit段，再处理成512字节字符集的索引，最终生成影射到N（明文空间）上的R值．MD5的R函数，处理流程如图1所示．

生成MD5彩虹表的过程中，在不同的链中，不同的位置出现碰撞，链不需要合并，只有在相同的位置j出现碰撞，这2个链才需要合并．

图1 MD5的R函数处理流程图

2 HBase

HBase - Hadoop Database，是Apache Hadoop云项目的1个子项目，它与其它项目一起构成了Hadoop的整个生态，如图2所示．

HBase是一种列数据库，它基于Hadoop的分布式存储和分布式运算架构，是一个具有分布式、高性能、高可靠性、高扩展性的数据存储系统．它特别适合非结构化数据存储，以及特别庞大的数据存储，Hadoop本身具有丰富的访问接口，可以方便地对HBase进行管理、访问和应用编程．

对HBase应用编程的方法是采用Hadoop的并行运算模型MapReduce[3]，如图3所示．

图2 Hadoop 生态系统

HBase与Hadoop无缝集成，提供了丰富的编程API，可以方便地使用MapReduce对HBase Table的操作进行编程，我们只要开发MapReduce Job就可以了．

3 HBase应用于MD5彩虹表生成和密码破解

3.1 HBase应用于彩虹表的优势

主要表现在2个方面：首先，HBase基于Hadoop分布式基础架构，有良好的分布式性能和分布式扩展性，适应于彩虹表的庞大存储规模．其次，应用HBase能通过Map/Reduce的强大分布处理能力，对彩虹表的生成和破解提供优秀的运算性能保证．

3.2 MD5彩虹表生成

MD5彩虹表的生成是一个耗时间耗资源耗存储的过程，时间耗费主要是在计算彩虹链时不断地计算哈希值的过程中，另外生成彩虹表需要很大的存储空间，比如对10位全字符空间的MD5，其彩虹表所需的存储空间要根据链长而变化，但一定需要TB级的存储．

我们构建一个私有云平台，采用HBase作为彩虹表的存储方式，采用Map/Reduce编程框架对彩虹表的生成过程进行编程，使用C语言编程，通过构建Map/Reduce Job任务来调用此核心C程序来生成彩虹表．因此，彩虹表的生成过程中，运算和存储任务会自动分配给云的各个计算节点上进行并行处理，处理的结果即彩虹表链直接写入预定义的HBase表中．这种并行处理机制实现了对彩虹表生成过程的加速．具体的处理模型如图4所示．

图4 彩虹表MapRduc处理

MD5彩虹表生成过程中，链表的长度选择也很重要，选择长了，可以节约存储，但会增加运算量和运算时间．试验中我们选择不同的链表长度，结果也反应了这一点．

3.3 MD5彩虹表密码破解

由于彩虹表存储空间巨大，因此使用HBase存储就能发挥其优势，在密码破解时，同样采用Map/Reduce任务方式进行，采用C语言编程，用Map/Reduce Job任务调用此C程序完成对HBase的搜索，这种方式实际上是调用云上各个计算节点并行对HBase中的彩虹表进行查询比对及处理，可以更快地完成密码破解工作．MD5 Hash的破解流程如图5所示.

图5 MD5 Hash破解流程

4 实验结果

实际实验中，我们搭建了12个节点的Hadoop集群环境，使用1个节点作为NameNode和JobTracker，即云主控机，其它11个节点均做DataNode和TaskTracker，每个节点的具体配置如下：

CPU：至强 E5-2403 (1.80GHz)

内存：2GB

硬盘：2TB

Hadoop：1.1

彩虹表存储于HBase中．

实验中，先生成一个明文长度为1～8位由字母和数字组成的128bit MD5彩虹表，链表长度设定为2000，再随机选取一些hash值来进行破解，并对多次试验结果进行统计分析．实验及分析对比结果见表1．很明显，采用HBase的MD5彩虹表生成和破解的速度有明显优势，且节点越多速度越高．

表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

*项目来源：深圳职业技术学院校级科研基金资助项目（编号：2213K3180029）

张悦（1968-），女，江苏人，硕士，副教授，主要研究方向：数据通信．