彩虹表在MySQL密码破解中的运用研究

庄小妹

(广东培正学院计算机科学与工程系，广东广州 510830)



彩虹表在MySQL密码破解中的运用研究

庄小妹

(广东培正学院计算机科学与工程系，广东广州 510830)

本文运用Cain和RainbowCrack两种工具生成MySQLSHA1彩虹表，并对两种工具进行了比较。通过实验分析可知，两个工具结合使用是生成MySQL彩虹表的最佳方案，而密码的破解使用RainbowCrack要优于Cain。同时，本文探讨了彩虹表链长、链数和磁盘空间之间的关系，研究了影响彩虹表生成时间的参数，分析了影响彩虹表密码破解时间的因素。

时间-内存平衡法；彩虹表；MySQL；数据库密码破解

渗透测试技术是目前网络安全的热门技术，密码破解是渗透测试中经常遇到的环节。在获得hash值的情况下，如何破解MySQL数据库的密码是网络攻防中的常见问题。MySQL密码的破解主要有三种方法：字典法、暴力破解法和彩虹表方法。其中，字典法速度快，但命中概率比较低；暴力破解法所需时间比较长；彩虹表方法结合两者的优势，提供了一种有效的快速破解MySQL密码的方法。本文主要讨论基于彩虹表的MySQL数据库密码的破解，破解了MySQL数据库密码，就能通过正常途径来访问数据库，一方面可以直接对数据库中的数据进行操作，另一方面可以提升权限。因此，探讨MySQL密码的破解在网络攻防过程中有重要的意义[1]。

1 时间-内存平衡法和彩虹表

彩虹表其实就是某种hash值的集合，但它的奇妙之处在于：它并不是明文和其hash值简单的一一对应表，因为这样的表需要巨大的磁盘空间作为代价。事实上，彩虹表存储是经过某种变换的“hash”值，经过变换，磁盘空间大为减少，而根据这些值可以巧妙破解密码。彩虹表的生成和破解都需要使用时间-内存平衡法。

1.1 时间-内存平衡法

最早的时间-内存平衡法(Time-Memory Trade-Off)是Martin Hellman在1980年提出的[2]，现在一般简称为时空折中方法或者是TMTO方法。其中，有一个函数是特别重要的，那就是归约函数(Reduce Function)，通常简称为R函数，R函数的作用是将hash值映射为明文。假设H表示hash函数，M表示明文，h表示hash值，则h=H(M)，而R(h)=M1，M与M1并没有相似之处。如果从一个明文出发，先散列，对生成散列值归约，对归约的明文再散列，再归约，如此反复多次，则得到一条明文与散列值交替的数据链。然后，仅记录数据链的第一个节点和最后一个节点，即相当于存储了整条链的信息，从而大大地减少了磁盘空间[3]。

TMTO破解hash值的基本思想是：如果hash值在彩虹表的某条链上，则由该散列值出发，经过若干次的归约、散列、归约，得到的结果应与该链最后一个节点的值相等。而由该链的第一个节点出发，经过一系列交替的散列和归约，应可重新生成该散列值并找到散列前的明文，从而实现破解[3]。

1.2 彩虹表

TMTO方法在所有的链上使用了同一个归约函数，这使得不同的链上可能产生碰撞，即不同的输入产生同一个输出，降低了破解的效率。2003年，Oechslin对TMTO方法作相对简单的修改，即在链上的不同位置使用不同的归约函数[4]，采用Oechslin的方法生成的链表就是彩虹表，虽然是简单的修改，效果却是显著的，因为它减少了碰撞的发生，提高了破解的效率。

1.3 彩虹表的应用

目前，彩虹表破解密码已经是世界上最为先进的破解方法，已有多个文献探讨彩虹表在不同的密码破解中的应用。其中，李超[5]研究了彩虹表用于破解PDF文档的密码，破解速度比暴力破解快了50000倍；方海英[6]提到彩虹表用于破解Word文档的密码；李筱筱[7]探讨了彩虹表用于破解PowerPoint文档密码。可见，彩虹表在密码破解领域得到广泛的应用。

2 MySQL用户密码的加密

MySQL速度快、体积小、功能强大，而且是一种开源的数据库系统，也是很多WEB站点后台所采用的数据库系统。MySQL的每一个表由三个文件组成，分别是.frm文件、.myd文件和.myi文件。连接MySQL的用户名和密码信息存储在USER表中。打开user.myd可查看root用户的密码，该密码经过SHA1加密获得。MySQL实际上是使用了两次SHA1夹杂一次unhex的方式对用户密码进行了加密，具体的算法可以用公式表示，即password_str=concat(’*’,SHA1(unhex(SHA1(password))))，得到41位密码[8]，把*删除后，密码是40位。本文MySQLSHA1密码的破解是指40位密码的破解。

3 基于彩虹表的MySQL用户密码的破解

3.1 彩虹表的获得方法

彩虹表的获得方法主要有三种：一是通过互联网下载；二是花钱购买；三是使用工具生成。互联网下载的彩虹表大都是基于MD5或者是NTLM hash或LM hash的。例如，开源项目ophcrack提供的彩虹表有table-xp-free-small，table-xp-free-fast，table-xp-special。这几个彩虹表能够迅速恢复或破解密码长度小于14位的Windows密码，但对于破解md5、SHA1的密码或MySQL数据库的密码则无能为力。有些彩虹表的大小可达上百G，在网速不理想的情况下，时间的成本也是相当可观的。由于MySQL使用的哈希算法是SHA1，而从互联网下载的SHA1彩虹表一般是rti，这并不是破解工具Cain和RainbowCrack所支持的格式。因此，使用工具生成彩虹表是破解MySQL密码的一个最佳的方案。

3.2 彩虹表的生成方法

彩虹表用于破解密码是很快速的，但生成彩虹表的时间通常是很漫长的，一般根据明文的空间、明文的长度以及生成彩虹表的参数不同而变化。生成彩虹表的参数主要有三个：链的长度、链的数目以及彩虹表的个数。为了缩短彩虹表生成的时间，目前多数采用GPU的方式来生成彩虹表。简玲[9]比较了普通计算机与GPU生成彩虹表的时间，从中可以看出，GPU生成彩虹表的时间大为减少，但该方法的成本昂贵。李聪[10]提供了一种基于分布式彩虹表的生成方法，但此方法比较复杂且步骤多。在普通的计算机环境下，使用现成工具生成彩虹表是最为快捷的方法，生成彩虹表的工具目前主要有Cain和RainbowCrack。本文的实验环境如表1所示。

表1 实验环境

3.3 彩虹表生成工具比较

Cain是一个免费的密码破解软件，它提供了能够生成彩虹表的工具Winrtgen。Winrgen运行在Windows系统，能够生成的彩虹表类型很多，包括MD5、NTLM hash、MySQLSHA1等。该工具支持的明文空间包括数字、小写字母、大写字母、混合字母、特殊符号、所有字符等。Winrtgen生成彩虹表的优点是：使用方便；对明文的长度没有限制；可预测生成彩虹表的时间以及该彩虹表用于密码破解的时间；还提供了彩虹表占用空间的大小以及破解的成功率；当调整彩虹表链长以及链的个数时，这些预测的数据都自动变化和显示。

RainbowCrack是一个开源的工具，其主要作用是实现Philippe Oechslin的时间内存平衡法。与Cain不同，RainbowCrack所提供功能主要通过命令行的方式来实现，其中rtgen.exe的作用是生成彩虹表，rtsort.exe的作用是对彩虹表排序，rcrack.exe是利用彩虹表破解hash值。rtgen所支持的hash算法封装在alglib0.dll中。

rtgen所支持的明文类型存放在文本文件charset.txt中，rtgen所生成的彩虹表的格式是rt，这个文件必须经过rtsort处理后才能用于破解，否则提示格式不正确。排序后的彩虹表能更好地进行匹配。通过实验发现，rtsort不仅可以处理rtgen所生成的彩虹表，而且也可以处理Cain所生成的彩虹表。不过，Cain所生成的彩虹并不需要排序处理，直接可以用于破解。Cain与RainbowCrack功能的比较如表2所示。

表2 Cain与RainbowCrack功能的比较

从CPU占用率可以看出，Cain生成彩虹表是用单线程来实现的。为了比较Cain与RainbowCrack生成彩虹表的效率，使用同一台计算机分别生成了一个8位的明文空间为数字的MySQL彩虹表和长度为6位的数字+小写字母的MySQLSHA1彩虹表，结果如表3所示。

表3 Cain与RainbowCrack生成彩虹表时间的比较

在参数相同的情况下，RainbowCrack生成的时间大大少于Cain所花费的时间，但RainbowCrack并不能预测破解成功率，也不能预算生成彩虹表所需要的时间以及破解所需要的时间。根据以上的实验分析发现，在普通计算机的环境下，两个工具的结合是最优的，即先通过Cain设置好彩虹表的参数并且进行预算，再通过RainbowCrack执行彩虹表的生成。成功生成彩虹表后，RainbowCrack显示实际所使用的时间。

3.4 影响彩虹表的占用空间和生成时间的因素分析

彩虹表的生成不仅要考虑时间的成本，还要考虑磁盘空间以及破解的成功率以及破解的时间。关于破解的成功率，Oechslin在他的论文中给出一个计算公式，而生成时间和磁盘空间可通过实验发现其中的规律。表4显示使用Cain生成MySQLSHA1彩虹表时，彩虹表的链长、链数与占用磁盘空间关系。

表4 链长、链数与磁盘空间的关系

从表4的第一行和第二行可以看出，当链数不变的情况下，即使链长发生了变化，占用的空间并没有变化；从第三行和第四行可以看出，在链长x链数(即总节点数)不变情况下，链数越大，磁盘空间越大；从第五行和第六行可以看出，当链数增加为原来的10倍时，磁盘的空间也增加为原来的10倍，可见彩虹表占用空间只与链数有关，与链长无关。

表5 链长、链数与生成时间和破解时间的关系

从表5可以看出，当链长x链数(即总的节点数)不变时，无论链长与链数如何变化，生成的时间基本相同，可见生成表的时间与总节点数相关。彩虹表的生成也必须考虑破解的时间，在总节点数不变的情况下，链长越短，破解的时间越短，而付出的代价是磁盘空间越大。时间与空间此消彼长，这也正符合了时空折中算法的描述。

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

获得MySQL用户密码的hash值后，就可以利用Cain或RainbowCrack进行破解。Cain的破解比较简单，因为它提供的是一种图形操作界面，可以直接复制hash值进行破解，也可以通过ODBC将hash值导入进行破解。破解所使用的彩虹表可以是Cain生成的，也可以是RainbowCrack生成的。破解成功后，两种工具都显示破解所使用的时间。

表6 破解时间的比较

从表6可以看出，RainbowCrack的破解时间与Cain并无太大的区别，而Cain提供的是一种图形操作界面，从而使用更为方便。在破解失败时，RainbowCrack给出的提示更快一些。有时Cain还会发生彩虹表读取失败的情况，稳定性稍逊。所以，破解时使用RainbowCrack是一种更优的方案。

4 结论

在MySQL用户密码的破解方法中，彩虹表方法的破解是最快的。但MySQLSHA1彩虹表并不适合从互联网下载，需要用户自己生成。彩虹表的生成主要设置链长和链数。通过对Cain和RainbowCrack两个工具的实验和比较分析，发现Cain能较好地预算彩虹表的生成时间、磁盘占用空间、破解成功率和破解时间，但生成表的时间较长；而RainbowCrack因为采用多线程，生成彩虹表的时间比Cain大为减少。可得出Cain+RainbowCrack是一个最佳的生成MySQLSHA1彩虹表的方案。彩虹表占用空间只与链数有关，与链长无关。在链长x链数的值不变的情况下，链长越短则破解时间越快，而链数越大，则占用空间越大。

[1]陈小兵,范渊,孙立伟.Web渗透及技术实战案例解析[M].北京:电子工业出版,2012:66-67.

[2]苏烈华,李恒训,李锁雷.基于时空折中算法的密码分析系统设计与实现[J].信息网络安全,2013(5):42-46.

[3]王小鉴,廖晓峰,黄宏宇.基于归约函数数量裁减的彩虹表技术改进[J].计算机程,2013(7):156-160.

[4]荣凯,邱卫东,李萍.基于彩虹表的hash攻击研究[J].信息安全与通信保密,2011(4):74-76.

[5]李超,陈丹伟.基于彩虹表的PDF文档口令破解研究[J].计算机应用与软件,2012(10):137-139.

[6]方海英.基于时空折衷算法的Word文档破解研究[D].杭州:杭州电子科技大学,2009.

[7]李筱筱.GPU异构系统上针对PowerPoint的彩虹表攻击实现[J].北京电子科技学院学报,2013(4):85-91.

[8]cenalulu.关于MySQL密码你应该知道的那些事[EB/OL].(2015-02-27)[2016-01-04].http://cenalulu.github.io/MySQL/myall-about-MySQL-password,2015-2-27.

[9]简玲,徐赛赛,邱卫东,等.基于GPU的高性能彩虹表生成[J].信息安全与通信保密,2015(2):102-108.

[10]李聪,叶猛,江舟,等.基于分布式GPU的彩虹表密码攻击系统[J].计算机系统应用,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

广东培正学院2014-2015年度校级科研项目“彩虹表技术原理及应用”(15pzxmyb020)。

庄小妹(1973- )，女，讲师，硕士，从事信息安全研究。

TP309.2

A

2095-7602(2016)10-0047-05