张冬芳 管磊 戴晓苗

摘   要：当前网络犯罪越来越严重，破解犯罪嫌疑人计算机中的的密码信息则需要技术支持。文章研究了彩虹表的构造原理、破解密码口令的过程，并结合MIC众核协处理器强大的计算能力，设计实现了密码口令破解彩虹表查找系统，并行化的设计提高了彩虹表的生成速度，归约函数的设计提高了明文查找成功率。

关键词：密码破解;彩虹表;众核协处理器;并行化

中图分类号： TP393.0          文献标识码：A

Abstract： At present， cyber crimes are becoming more and more serious. It requires technical support to crack the password information in the suspect's computer. In this paper， the construction principle of rainbow table and the process of password cracking are studied. Combined with the powerful computing power of MIC， a password cracking system based on rainbow table lookup is designed and realized. The design of parallelization improves the generation speed of rainbow table， and the design of reduction function improves the success rate of plaintext search.

Key words： password cracking; rainbow table; many integrated core; parallelization

1 引言

哈希算法可以將任意长度的二进制值串通过一定的映射规则映射为固定长度的二进制值串。被广泛应用于密码学领域。对于一个优秀的哈希算法需要具备三个特点：（1）单向性—通过哈希值无法反向推到出原始数据;（2）对输入数据极其敏感—两个即使只有1bit差异的输入数据，其对应的散列值会有很大的不同;（3）碰撞几率极小—如果两个散列值不同，那么其对应的原始数据也是不相同的。哈希算法有非常多的应用，比如安全加密、唯一标识、数据校验、分布式存储等。

穷举法和查表法通常被用于破解哈希函数。穷举法，顾名思义，就是需要将所有可能的结果进行列举，具体地说，遍历明文空间，然后使用哈希算法求出明文空间中的每一个密码的哈希值，最后将哈希值与密文进行比对，其计算量非常大，破解密码口令的时间非常久。查表法是从预先保存好的明文组合与哈希值的映射中，通过密文查找对应的明文来破解密码口令。虽然查表法的破解速度高于穷举法，但其对存储空间的要求极大。结合穷举法和查表法存在的特点，Hellman[1]和Oechslin[2]等人提出了彩虹表（Rainbow Table），这种方法既保证了密码口令的破解速度，又降低了存储空间，是一种实用且有效的技术。为有效且高效地破解密码口令，本文提出了彩虹表查找系统的设计与实现方案。

2 相关工作

Hellman于1980年首次提出了基于时空权衡（Time-Memory Trade-Off，TMTO）的表方法。这种方法分为两个阶段，即预计算阶段和在线阶段。为了建立密文空间与明文空间的映射，引入了可以用于交替地计算明文和密文的规约函数从而形成一个链表，链表的首节点和末尾节点被记录存储，而大量的首节点-末尾节点又组成了一张表，但由于规约函数与密文-明文映射非一一对应，会导致哈希碰撞问题的出现[1]。Rivest于1982年改进了Hellman的方法，为了降低链的重合率，他引入了区分点（Distinguished Points）[3]。Oechslin于2003年，在Hellman的方法的基础上提出了彩虹表（Rainbow Table），他将Hellman方法中每次计算都使用相同的规约函数，改为每次计算时采用不同的规约函数，显著地降低了链的重合率[2]。2009年Thing在彩虹表的基础上，改进了TMTO方法，将存储首节点和末尾节点改为只存储末尾节点值，通过相应的数学运算来获得首节点，因此减少了表的存储空间[4]。2012年，梁艳等人提出了基于生成元的彩虹表，该方法根据常用的口令设置方法减少长口令的生成空间过滤掉不满足要求的口令，从而降低了表的存储空间[5]。2015年张悦等人设计了基于HBase的彩虹表MD5哈希密码解密系统，其引入Map/Reduce框架与HBase，为完成计算与存储，MD5彩虹表的生成和查找分配给集群节点，并使用HBase实现彩虹表的存储，明显地提高了彩虹表的生成速度和破解密码的效率[6]。2017年王伟兵等人在经典彩虹表的算法基础上，提出了构造分布式完美彩虹表的思路，通过MPI了并行编程接口，将彩虹表分布存储于集群中的每台计算机中。在破解阶段，通过集群中的多台计算机并行计算，可以明显地加快和提高密码破解的速度和有效率[7]。

3 彩虹表算法

彩虹表（Rainbow Table）技术可以理解成一种针对哈希算法的破解技术。其核心思想是按一定的规则将密文映射为明文空间中的口令，这个规则称之为归约函数（）。

3.1 彩虹表的生成

在彩虹表的构造阶段，首先使用哈希算法将明文空间中的一个口令映射为密文，然后再使用规约函数，将密文映射为另一明文，使用哈希函数、规约函数依次迭代，得到，，，，…，，，，和分别是该条链的首节点和末尾节点，将这两个节点都存储下来。多条彩虹链构成了彩虹表：

其中，表示明文空间中的s条文明，H表示要破解的哈希函数，表示规约函数，s和k是算法的参数，不同的参数值将直接影响彩虹表的存储空间及密码破解时间。

3.2 基于彩虹表的密码口令破解

对某一已知密文C来说，想要得到其对应的密文，可按三个流程步骤进行。

步骤一：对密文C使用规约函数，计算出明文，检索彩虹表，如果末尾节点中包含，则说明C对应的明文可能存在于该条彩虹链中，从该链的首节点开始进行哈希函数、归约函数依次迭代，若链中存在与C相等，那么上一步的计算结果则为C对应的正确明文，破解成功。

步骤二：如果在末尾节点中未找到，则以为起点，依次使用哈希函数和规约函数计算一次得到明文，按步骤一流程在查找末尾节点，若未找到则重复步骤二继续查找。

步骤三：当重复次数大于彩虹表中的链条总数时，说明该密文C未存储在该彩虹表中，破解失败。

基于彩虹表的密码口令破解过程流程步骤，如图1所示。

4 系统设计

4.1 基于MIC集群的彩虹表的生成

4.1.1 系统总体框架

众核协处理器（Many Integrated Core，MIC）是Intel公司针对高性能并行计算而设计的协处理器，其拥有非常强大的计算性能，可以给程序应用提供强大的并行度[8]。彩虹表的生成和查询就是基于MIC而设计实现的。生成系统主要包含四个硬件结构：PC端、管理服务器、MIC服务器和存储服务器，生成系统框架如图2所示。

其中，PC终端依照搜索空间表达式、算法等发布指定的任务文件。管理服务器收到终端发来的任务文件后，平均分配需要计算的任务给各个MIC服务器。MIC服务器具备多块MIC卡设备，可以进行并行计算来生成彩虹表的子表。存储服务器接收到各个MIC服务器发来的子表，对这些子表的数据进行一致性检测、完整性检测，并存储起来。

系统实现了三层并行，即节点间并行、节点上并行和MIC卡上的并行。

节点间并行：采用MPI技术实现并行。对于需要生成规模很大的彩虹表，使用MIC集群，MIC管理节点将彩虹表的计算空间平均分配给每一个独立的计算节点，彩虹表链末尾节点的生成任务则由这些独立的计算节点共同完成。

节点上并行：采用Pthread多线程库函数实现并行。MIC计算服务器具有多块MIC卡设备，检测函数可检测MIC节点上MIC卡设备的块数，有多少块就开启多少个线程，并将任务均分给每一个线程来共同完成。

MIC卡上的并行：采用OpenMP技术实现并行。MIC的众核具有非常厉害的计算能力，只需保留一个核心来进行任务的调度，其余的核心均可用来计算，除此之外，每个核心可以开启4个线程进行并行计算。

4.1.2 彩虹表结构设计

彩虹表的配置文件包括八个部分：算法（生成的表使用何种散列函数）、搜索空间表达式、彩虹表链长、彩虹表链数、首个起始点的值、起始点值递增步数、块大小、彩虹表生成需使用计算节点的数量。

在原有配置文件的信息的基础上，彩虹表的子表还添加了用于记录子表节点号的头文件，需要生成的块数及已生成的块数等信息。这种设计有利于解决由计算节点失效带来的问题，一旦计算节点失效，可以根据子表中头文件里的信息从中断计算的地方恢复任务。

4.1.3 规约函数设计

规约函数是建立起密文到明文之间的映射的桥梁，他的设计对整个彩虹表的成功率至关重要。该系统将缩减函数和转换函数相结合定义归约函数，主要阶段包括缩减和明文转换。

缩减函数可将密文通过与特殊的掩码值进行一系列的与、或、位移等固定操作，获取固定的索引值。在MIC上利用MIC内嵌原语使缩减函数可以完成16路的并行缩减操作。

转换函数可以凭借缩减函数得到的索引值，将其映射到字符空间来转换成相对应的明文。为优化传统的转换函数，减小求于操作的时延，因此在MIC端和GPU端采用与、异或、移位方法。

4.2 基于MIC的彩虹表在线查找

彩虹表的在线查找需要用到的结构：PC终端、MIC计算服务器和存储节点，具体的查找框架如图3所示。

PC终端将任务文件信息发送给MIC计算服务器;MIC计算服务器接收任务信息后对该信息进行解析，生成彩虹链的末尾节点并发送给存储服务器;存储服务器接收到末尾节点信息后索引末尾节点对应的首节点，并将匹配到的首节点返回给MIC计算服务器;MIC计算服务器接收到首节点信息后进行以该节点为首节点的哈希函数、规约函数迭代计算，生成链进行密码口令破解，并将破解结果返回给PC终端;PC终端接收查询结果，查找结束。

5 结束语

本文首先对彩虹表的基本原理进行分析，包含彩虹表的构造方法和破解密码口令的彩虹表法。基于MIC强大的计算性能，提出了利用MIC集群实现并行的彩虹表生成和在线查找。彩虹表的生成实现了节点间并行、节点上并行和MIC卡上并行。大大提高了彩虹表的生成速度。结合缩减函数和转换函数定义规约函数提高明文查找成功率。该系统将在公安机关开展应用测试。接下来将重点研究基于彩虹表的破解速度与彩虹表的大小和彩虹链的长度之间的关系。

参考文献

[1] Hellman M E.A cryptanalytic time-memory trade-off[J].Information Theory， IEEE Transactions on，1980，26（4）： 401-406.

[2] Oechslin P.Making a faster cryptanalytic time-memory trade-off[M] // Advances in Cryp-tology-CRYPTO 2003.Springer Berlin Heidelberg，2003： 617-630.

[3] Dorothy Denning.Cryptography and Data Security[M].Boston， Massachusetts， USA： Addison-Wesley，1982：100.

[4] Thing V L L， Ying H M.A novel time-memory trade-off method for password recovery[J].Digital Investigation， 2009， 6： S114-S120.

[5] 梁艷，张琛岭，邱卫东.基于生成元的彩虹表[J].信息安全与通信保密，2012 （12）： 85-87.

[6] 张悦.基于HBase的彩虹表MD5哈希密码解密[J].深圳职业技术学院学报，2015，1： 005.

[7] 王伟兵，文伯聪.基于彩虹表技术的分布式密码破解研究[J].中国人民公安大学学报（自然科学版）， 2017，23（01）：79-84.

[8] Intel Corporation.Intel? Many Integrated Core Architecture -  Advanced[EB/OL].http：//www.intel.com/content/www/us/en/architecture-and-technology/many-integrated-core/intel-many-integrated-core-architecture.html， 2017.