基于云计算的密码恢复系统模型构建

张清忠

(黎明职业大学 信息与电子工程学院，福建 泉州 362000)

密码恢复[1]技术是密码分析的一个分支，密码恢复在计算机取证等方面起到了关键作用，其发展受到了越来越多的关注.暴力破解是密码恢复采用的主要方法，其主要思想是穷举密码空间，遍历该空间直到找到密码.但是由于密码强度的增加，密码空间越来越大，这为密码恢复造成了很大的困难.采用暴力破解(brute force)进行密码恢复需要搜索巨大的密码空间，使用Hadoop[2]平台搭建密码恢复私有云系统，能够更有效地在较短时间内进行密码恢复.Hadoop是一个使用MapReduce编程模型和处理大数据数据集的开源软件框架.Hadoop的核心包括一个称为Hadoop分布式文件系统(HDFS)以及一个MapReduce[3]编程模型的处理部分.Hadoop将大文件分解成较小的文件块，并将它们分布在集群中的节点上.然后它将打包的代码传输到各个节点中以进行数据并行处理.为了提高密码恢复的效率，本文构建了一个基于云计算的密码恢复系统模型，采用了Hadoop计算模型，将巨大的密码空间分成若干小的密码空间.并将该密码恢复系统实现后，对其进行性能评估.

1 云计算与Hadoop

云计算(cloud computing)[4]采用了分布式计算(Distributed Computing)的模式，将单个计算机无法完成的大规模计算任务分成多个小规模的子任务，网络中的节点对这些小任务进行计算后，将结果汇总给用户.采用暴力破解(brute force)进行密码恢复需要搜索巨大的密码空间，使用Hadoop平台搭建密码恢复私有云系统，能够更有效地在较短时间内进行密码恢复.

Hadoop是一个使用MapReduce编程模型和处理大数据数据集的开源软件框架.

Hadoop的核心包括一个称为Hadoop分布式文件系统(HDFS)以及一个MapReduce编程模型的处理部分.Hadoop将大文件分解成较小的文件块，并将它们分布在集群中的节点上.然后它将打包的代码传输到各个节点中以进行数据并行处理.

(1)Hadoop分布式文件系统

HDFS是用Java编写的用于Hadoop框架的分布式、可扩展和可移植的文件系统.每个数据库通过网络使用特定的HDFS块协议来提供数据块.文件系统使用TCP/IP套接字进行通信.客户端使用远程过程调用(RPC)来进行通信.HDFS将大型文件存储到在多台机器上，它通过在多个主机之间存储冗余数据来实现可靠性(数据冗余值默认为3，即数据存储在3个节点上：两个在同一个机架上，另一个存储在不同的机架上).数据节点可以进行相互通信，通过移动数据的副本，维持节点间的负载均衡.

(2)MapReduce

图1 MapReduce工作流程

MapReduce是一个编程模型，能够在集群上通过使用并行分布式算法处理大数据.MapReduce程序由两个部分组成：执行过滤和排序的Map()部分以及执行摘要操作的Reduce()部分.MapReduce工作流程如图1所示.

2 基于云计算的密码恢复系统模型

2.1 类n进制数

有这样一组数字集合：[0,1,2]、[00,01,02]、[10,11,12]等等，这些组合是由集合{0,1,2}中的数字组成的.这些数字集合的形式类似于三进制数，但是并不是严格的三进制数.与三进制数相比，它们包括从零开始的数字.在这里将称这些数字定义为类三进制数.类n进制数的形式化定义如下所示：令集合S为S={ai|ai∈Zn,0≤i≤n}.其中，将n定义为基数.一个类n进制数就是由集合S的元素所组成的组合.将类三进制数转换为十进制数字的过程如下：如果X是一个L长度的类n进制数，即X={XL-1XL-2XL-3…X1X0}，假设Y是十进制数，则Y=(XL-1*nL-1+nL-1)+(XL-2*nL-2+nL-2)+…+(X0*n0+0).

(1)L=L′

Z=X-X′=

(XL-1*nL-1+nL-1)+(XL-2*nL-2+nL-2)+…+(X0*n0+0)-

ZL-1ZL-2…Z1Z0

由此可知，Z是一个n进制数.

(2)L>L′

此时，X′的长度比X短，需要在X′的高位补上L-L′个-1.

Z=X-X′=

XL-1*nL-1+nL-1+XL-2*nL-2+nL-2+…+X0*n0+0-

XL-1*nL-1+nL-1+XL-2*nL-2+nL-2+…+XL′*nL′+nL′+

2.2 系统模型

图2 分布式密码恢复流程

密码恢复模型的基本思想是将构成密码字符集的字符看成是类n进制数，其基数是字符集的大小.所以，密码就会被映射成一个类n进制数.当划分搜索空间时，我们只是对类n进制数进行操作.例如，如果字符集是{a,b,c,0,7,1,9,D}，并且密码由字符集中的字符组成，我们可以将字符视为类n进制数的元素，相应的集合是{0，1，2，3，4，5，6，7}.该模型通过逐步尝试所有候选密码来实现密码恢复.该模型可以均匀划分出不同长度的密码搜索空间，能够实现节点之间的数据独立性，具有较小的通信开销.此外，该模型灵活易用，仅仅需要少量的时间来计算子空间的边界并生成下一个候选密码.算法的另一个关键是处理密码长度的变化.密码恢复模型的实现过程如图2所示.

图3 密码字符集的处理过程

步骤1：将原始密码字符集的元素顺序打乱，然后将字符集的每个元素映射为相应的数字.随机选择搜索的初始密码和结束密码.例如，对于密码字符集charset={a,b,c,0,1,！}，其处理过程如图3所示.

步骤2：获取密码搜索空间的所有候选密码.利用结束密码索引减去初始密码索引可以得到整个密码搜索空间(如公式1所示).

-153440--1-102510632-1-1

(1)

当计算不同长度密码的数量时，我们需要注意密码数量的变化.例如，如果字符集是小写的，从“a”到“z”的密码数是26，“aa”到“zz”的数字是262；从“aaa”到“zzz”的数字是263.令初始密码的长度为l1，结束密码的长度为l2.

步骤3：服务器将候选密码的整个空间划分为子任务(子空间)，计算每个子任务的初始密码和结束密码，并将其分配到每个节点.如果子任务的数值大于原子任务的数值，它将继续分配，直到数值小于或等于原子任务的数值.

步骤4：计算节点从起初始密码生成每个索引候选密码其基于增量模式的分布式任务，将其转换为真实的密码并将其破解.如果计算节点是并行设备，则可以根据DMPC将任务分为若干部分进行破解.

2.3 性能评估

为了评估模型的性能，将密码恢复模型实现在Hadoop分布式平台上，并同时利用密码恢复模型恢复MD5[5]加密算法的密码.

实验中使用了不同的密码字符集，对比了使用配置GPU[6]的单个普通PC以及使用分布式密码恢复模型来进行密码恢复的所需的时间，实验结果如表1所示.实验结果显示，本文的密码恢复模型性能优秀.

表1 实验结果

3 结论

为了提高密码恢复的效率，本文构建了一个基于云计算的密码恢复系统模型，这是一个通用的密码破解模型.它可以用来破解各种算法加密的密码.它也可以被应用到GPU上并发地进行破解.该模型在数据独立性、较低的交换和设施等方面取得了较好的效果.该模型采用了Hadoop计算模型，将巨大的密码空间分成若干小的密码空间.我们将该密码恢复系统实现后，对其进行性能评估.实验结果显示本文的模型能够大大减少密码恢复的时间，提高密码恢复的效率.

[1] 蒋秉天,邱卫东,李萍.基于云计算的密码恢复系统模型[J].信息安全与通信保密,2011(4):47-49.

[2] WHITE T.Hadoop:the definitive guide[M].O’Reilly Media,Inc.，2012.

[3] DEAN J,GHEMAWAT S.MapReduce:simplified data processing on large clusters[C].ACM,2008.

[4] HAYES B.Cloud computing[J].Communications of the Acm,2008,51(7):9-11.

[5] RIVEST R.The MD5 message-digest algorithm[M].RFC Editor,1992.

[6] BOLZ J,FARMER I,GRINSPUN E,et al.Sparse matrix solvers on the GPU[C]∥ ACM SIGGRAPH.ACM,2003:917.