基于异构计算集群的密码口令破解系统设计与实现

张冬芳 管磊 戴晓苗 杨亚星

摘   要：针对当前密码口令破解功能单一、破解算法种类不足、效率低下等技术问题，从基于GPU的多策略散列算法并行计算技术、基于ASIC的复杂密码破解技术和基于异构计算集群的多种计算资源调度技术三个方面展開研究，在此基础上构建多手段密码口令破解服务平台，实现密码破解的大复杂度运算和高速破解。

关键词：密码破解;异构集群

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

Abstract： Aiming at the technical problems of single password cracking function， insufficient types of cracking algorithms and low efficiency， this paper studies the parallel computing technology of GPU-based multi-strategy hash algorithm， ASIC-based complex password cracking technology and heterogeneous computing cluster-based multi-computing resource scheduling technology. And based on this studies， A design idea is proposed on Constructing a multi-means password cracking service platform to achieve large complexity and high-speed password cracking operation.

Key words： password cracking; heterogeneous cluster

1 引言

互联网的飞速发展带动了计算机犯罪的发展，尤其是近几年网络的高速发展，利用计算机和网络进行计算机犯罪的问题越来越严重，在打击网络犯罪的过程中，为了获得侦察线索、提取电子证据，经常需要通过技术手段破解重点对象的各种登录密码或文件密码。此外，间谍组织、敌对分子以及国家安全危害分子，在传递、存储信息时一般都会采用各种加密技术，而加密算法的多样性使信息解密处理变得更为复杂，导致加密信息的破解难度大大增加，进而导致通过网络攻防手段辛苦获取的情报信息失去利用价值，功亏一篑。因此，密码口令破解技术研究成为网络空间安全的重要研究课题。

密码口令破解现有技术普遍存在功能单一、破译密码种类较少的缺点，并且在算法实现上通常采用暴力破解的方式，效率低下且破解效果不理想，因此密码口令破解工作迫切需要高性能、大规模的科学计算，需要异构的多种计算资源共同完成计算问题。基于此，本文以GPU和ASIC为基础，利用GPU的高灵活性，结合ASIC的高性能，通过异构计算集群调度技术，构建多手段密码口令破解在线服务系统，解决当前密码破解成功率低、支持破解算法少、破解时间长等难题。

2 国内外现状

目前，国际上可用于常见信息系统口令破解的成熟技术主要分为两类：基于纯软件的破解技术和基于FPGA技术开发的硬件破解系统。纯软件系统主要有美国Access Data公司的Password Recovery Tool Kit （PRTK）和Distributed Network Attack （DNA）软件，俄罗斯Elcom Soft公司的Distributed Password Recovery软件。这些软件具有三个共同的弱点：（1）受限于主机性能，运算速度慢;（2）破译能力较弱，实战性能较差;（3）无法满足高复杂度的密码口令破译。

基于FPGA技术的硬件破解系统主要有Tableau公司的TACC1441硬件加速器和ICS公司的Cobra硬件加速器。相对于纯软件系统，这些产品的性能有较大提高，但考虑到网络密码破译所必需的巨大运算量，以上产品仍然难以达到实战要求，并且价格昂贵，大规模集成成本过高，商业化推广价值有限。

另外，现有技术普遍存在着功能单一、支持密码种类较少的缺点，并且在算法实现上通常采用暴力破解的方式，效率低下，造成了密码破解工作投入较大财力，却难以取得理想的应用效果。

3 方案设计

口令破解问题的最大困难在于口令的搜索空间非常庞大，对计算的能力要求很高。由于口令破解中每个计算任务之间基本上没有相关性，通信开销小，也基本上对I/O没有太大要求，因此非常适合于GPU和ASIC等大规模数据并行执行部件实现，为口令破解提供了重要的计算能力保障。

系统以中小规模GPU破解机集群和ASIC破解机集群为硬件平台，构建基于B/S架构网站系统、并行计算平台（DCR）、oclhashcat口令破解软件为一体的高效口令破解系统。实现对单机口令破解软件oclhashcat的多机并行化计算，使用基于真实口令集合自动学习的掩码攻击和碾压攻击等两种破解策略，实现对多种算法的高效破解。系统的整体架构如图1所示。

多手段密码口令在线服务平台包括硬件设备和软件系统，其中硬件设备包括GPU破解机集群、ASIC破译机集群;软件系统包括基于GPU的散列算法并行计算子系统、基于ASIC的复杂密码破解子系统以及基于异构计算集群的多资源调度子系统。

3.1 基于GPU的散列算法并行计算子系统

在分析研究常见散列算法特点基础上，开展基于GPU的散列算法开发流程，设计并实现基于GPU体系结构的模块化散列算法库;利用GPU上SM资源动态划分、存储器访问优化、指令流优化等优化技术，研究典型散列算法并行计算关键技术，设计并实现基于GPU的散列算法并行计算平台模型。

3.2 基于ASIC的复杂密码破解子系统

针对复杂密码的计算需求，基于ASIC的高性能实现高复杂度密码破解算法设计与实现，采用网络化总体架构，应用密码技术的多项最新研究成果，结合专用密码库，设计并实现针對Office、PDF等文档类、WinZip、7Zip、RAR等压缩包类密码口令的密码破解系统。

3.3 基于异构计算集群的多资源调度子系统

针对GPU和ASIC的异构性，吸收各个并行计算编程模型的优点，进行异构计算集群的管理节点设计、计算节点架构设计和调度节点架构设计，最终形成一套适用于特定类型计算作业的异构计算集群调度系统。

4 技术路线

4.1 基于GPU的散列算法并行计算子系统构建

4.1.1 总体架构设计

基于GPU CUDA技术针对散列算法提出一种软件处理结构，能够适应任何散列算法的开发，该软件总体结构由GPU-CPU数据接口、公共接口库模块、基础算法库模块、复杂算法库模块四部分组成，其中GPU-CPU数据接口由CPU提供，其余模块均在GPU上。

在CPU中，GPU-CPU数据接口主要提供对明文、密文、通配符、字典单词的处理信息以及散列算法所需要的字段信息，并把这些信息传给GPU的常数存储器，这部分主要为GPU散列算法提供必要的常用预处理信息，提高系统的整体性能。而在GPU中，公共接口库模块主要提供读取明文，明文填充通配符，以及返回结果明文。

基础算法库模块主要提供一些基本简单散列算法的计算内核，复杂算法库模块主要针对一些特殊复杂的散列算法根据GPU架构进行重构并提供一些特殊功能模块，方便开发后续的复杂散列算法。

4.1.2 CPU和GPU上算法库的通用接口设计

为了满足各种散列算法和系统的兼容性及可操作性，同时考虑CUDA相关优化技术，将CPU和GPU的通用接口设计成两个部分，一个是GPU任务接口，另一个是明文获取接口。

GPU任务接口主要包含明文的处理信息如填充通配符集、掩码、明文字长以及密文信息、Salt信息等，由于散列算法的操作流程常常对明文和密文做大量操作，常数存储器相对于局部存储器开销小，读取速度快，对GPU的性能有着明显的优化作用，因此在GPU端主要通过常数存储器来存储上述信息。

4.1.3 公共接口库的设计与实现

公共接口库实际上是对明文、密文、返回结果进行相应的操作，这部分对于所有散列算法来说是一个共享的外围操作，为了满足公共接口库的实用性、可扩展性同时兼顾系统的性能，所有的公共接口库均以宏的形式出现。公共接口库的设计包括五部分内容。

（1） 明文的读取：通过分析常见散列算法的原理研究，发现许多复杂的散列算法都是基于MD4、MD5这种基本的散列算法开发的，有些散列算法读取明文需要在明文后加0x80，因此需设计两种读取明文方式，以满足不同算法置换明文的方式。

（2） 字符的填充：由于明文中有通配符所以要获取最终的明文需要star字符对明文进行填充操作，其中star字符是1～4个字节，由于star最长为4个字节，所以把每个star存为一个字，但这有可能会引起明文填充跨字的问题，可以通过fill_star（star_index）这个宏来解决。该宏主要负责将star_charset[i]的内容填充到block对应的字中。

（3） 基于树的批量结果匹配：通过分析发现，对于基础散列算法如MD4、MD5、SHA-1来说，当任务文件中有多条密文需要匹配时，若采用传统的IF比较方式会严重影响系统的性能。因此，拟利用基于比较相似度的思想设计一种树批量结果匹配的方法来减少开销提高系统的性能：假设密文是由64个字节组成，则提取前16个字节进行比较，如果前16个字节匹配不成功，后48个字节就不用匹配，这样可以极大减少开销。

（4）单词的变换：由于复杂散列算法计算强度高，导致其性能低下，对于较大的明文空间计算时间过长，所以需要采取一种基于字典的方式来减少破解的时间，增加破解的可能性。而单词转换主要功能是对字典明文进行变换预处理，CPU端先把字典的单词存储在Plaintext数组中，然后从CPU端复制到GPU端的in_data数组中，此时GPU上获取的明文即为字典单词。

（5） 结果返回：对于系统传进来的明文，散列算法对其运算后得到相应的散列值，将该值与预匹配的密文散列值匹配，如果结果匹配说明已经成功得到正确明文，即把匹配结果存放在Result结构中，并把Result结构传到CPU中输出。Result结构主要包含匹配标志，匹配的线程号、明文和密文。

4.1.4 基础算法库的设计与实现

基础算法库主要支持基本散列算法（MD4、MD5、SHA-1）的并行版本，将其封装在GPU基础算法库接口，从而在实现复杂散列算法时，可直接调用这些算法宏库得到相应复杂散列算法的散列值。

为了提升整个系统的性能，遵照循环展开、使用宏定义、变量标量化三个优化原则进行基础算法库的设计。因此，MD4、MD5、SHA-1算法库的具体实现较为复杂，为控制篇幅这里不做说明。

4.2 基于ASIC的复杂密码口令破解技术研究

4.2.1 复杂密码口令破解平台硬件体系建设

硬件体系采用网络化总体架构，由服务器和破译机构成。服务器包括破译服务器、数据库服务器和任务管理服务器。平台可配置多台破译机，破译机采用标准高4U、支持8个破解加速卡槽位的机箱。每个机箱内配置一块主控板，最多可部署8块破解加速卡，采用2个12伏1600W电源供电。

（1） 破译机硬件设计与实现

破译机硬件由包括破解加速卡和主控板构成，每块破解加速卡由ASIC破译芯片以及各种控制单元组成。

破解加速卡：破解加速卡采用模块化设计，板上放置32个ASIC破译芯片、电源管理单元、逻辑控制单元。通过QSPI控制接口与主控板连接，进行数据和控制指令的传输。

ASIC破译芯片：ASIC破译芯片是整个硬件平台的最小计算单元，采用统一框架结构设计，可以对Rar、WinZip、7Zip、Office、WPA等常用密码进行高速破译，并支持对MD4、MD5、SHA-1、SHA-256等常见Hash算法及其各种变形算法的破解。

主控板：每个破译机配置一个ARM主控板，负责破译机的地址分配、授权设置等日常管理工作以及任务数据的收发和芯片运行控制。主控板上集成双核ARM CPU芯片，主频800MHz，板载1G内存和32M Flash，集成SD卡、显示串口、标准千兆以太网接口和8个QSPI接口。

破译服务器可以通过网络访问破译机的主控板，实现任务分配、状态查询、破译结果接收等功能;管理客户端可对主控板的IP地址、授权信息等参数进行配置，并允许用户进行系统升级、板载口令库更新等操作。

（2） 复杂密码口令破解平台模块功能设计

复杂密码口令破解平台由破译任务管理模块、破译服务模块、破译数据库和破译机组成，模块之间使用高速网络交换机进行互联。

破译任务管理模块：部署于任务管理服务器上的Web应用程序，是平台的人机交换接口，可实现破译任务管理、破译数据库维护、平台配置、平台用户管理功能，可监控各破译机状态。

破译服务模块：部署于破译服务器上，实现破译任务分发、破译结果接收、破译结果验证、获取破译机状态、破译机配置等功能。

破译数据库：部署于数据库服务器，保存破译使用的口令库及平台的配置、用户、破译任务等各类数据。

破译机：接收破译服务模块发送的任务数据，进行密码高速破译，并将破译结果发送到破译服务模块，可根据破译服务模块命令上传运行状态数据。

4.2.2 复杂密码口令破解平台软件体系建设

系统软件包括破译机操作系统、网络通信协议、破译服务等。

（1） 破译机操作系统

每台破译机的ARM主控板上运行独立的ASIC芯片操作系统，负责主控板的应用程序加载，提供各类外设的驱动，完成系统和破解加速卡的初始化。

ASIC芯片操作系统主要功能有任务管理、时间管理、信号量、消息队列、内存管理、记录功能、软件定时器、协程等。破译机操作系统对系统任务的数量没有限制，既支持优先级调度算法也支持轮换调度算法，多个任务可以分配相同的优先权，优先级可继承，可满足破译机功能和性能的需要。

ASIC芯片操作系统的开发与实现以委托开发的形式交由外部人员实现。

（2） 网络通信协议优化开发

为了适应从破译服务器到破译机的数据传输、文件收发、从管理终端到破译机的管理命令下达、固件上传等功能要求，基于TCP/IP协议开发优化的FA-2平台网络通信协议。协议共包含三类。

破译资源发现协议：基于TCP和UDP协议，可进行破译机的广播查询、破译机计算卡等资源获取、查询破译机和计算卡等资源的当前状态。

破译任务协议：基于TCP协议，以保证收发数据的完整可靠，可进行破译任务数据的传输、当前破译状态获取、破译结果和校验结果的获取。

破译机管理协议：基于TCP协议，以保证文件传输的可靠性，可进行文件上传下载、固件刷新、破译机参数配置等。

（3） 破译服务

破译服务部署于破译服务器，使用TCP/IP协议与破译机进行通信，将各类数据集中保存于破译数据库中。破译服务主要实现几项功能。

破译文件识别：可以自动识别系统支持的待破译文件格式，并提取待破译文件的特征数据保存于数据库中。

破译任务分发：读取破译数据库中的任务数据和破译机资源数据，根据任务优先级智能分配破译资源，通过网络将破译任务分发到这些资源中。

破译结果接收：接收破译机运算结果，保存于破译数据库中。

破译结果验证：对可能出现伪口令的破译任务结果进行验证。

获取破译机状态：通过UDP广播发现本网中的所有破译机，将其信息保存于数据库;发送查询命令获取破译机及其破解加速卡的配置情况、当前工作状态。

破译机配置：发送配置命令配置破译机的IP地址、授权地址、管理密码等参数;上传下载破译机板载的口令库。

（4） 管理服务系统

使用Java实现，运行于Tomcat服务器，实现了破译管理系统-应用程序版的功能。

4.2 基于异构计算集群的多种计算资源调度

异构计算集群调度系统主要包括三种节点：管理节点、调度节点和计算节点。

4.3.1 管理节点

管理节点负责对整个系统进行管理和监控。管理节点为用户提供易用的控制命令，方便用户在系统中进行作业维护。它将向调度节点发送对应的请求，并将调度节点处理的结果直观地展示给用户。通过管理节点，用户可以快速获取系统中作业运行状态和完成情况等信息。由于管理节点只是进行简单地命令发送及结果的展示等操作，并不需要复杂地计算，故一般使用主流的个人计算机即可。

4.3.2 调度节点

调度节点是整个异构计算集群系统的核心。它需要负责处理来自管理节点的用户请求，对用户提交的作业进行管理，又需要对集群中所有的计算节点进行管理，并向其发送节點任务，处理其回复的结果报文。鉴于调度节点需要处理大量的节点任务，维护集群中所有的计算节点信息，通常使用机架式服务器。

4.3.3 计算节点

计算节点是整个异构计算集群的计算资源，主要负责完成调度节点发送的节点任务。计算节点可以通过高速互联网络或交换机与调度节点相连，而各个计算节点间并不了解对方的情况。集群中所有的计算节点统一由调度节点进行管理。计算节点上会配置一个或多个计算设备，这些计算设备既可以是GPU计算卡，也可以是MIC计算卡，甚至是CPU。计算设备的单卡性能及计算节点所拥有的计算设备数量将是影响计算节点的整体性能的主要因素。由于计算节点需要不间断计算数量众多的节点任务，拟采用机架式服务器。

4.3.4 調度节点与计算节点的网络接口设计

调度节点主要使用TCP和UDP协议与计算节点进行交互。调度节点通过向计算节点发送网络数据包的方式控制计算节点进行任务的计算。同样，计算节点通过发送网络数据包告知调度节点其运行情况和计算结果。

TCP协议可靠性高，但其占用的网络带宽较高，建立连接时的开销也高，适合用于传输可靠性要求高的数据，可能被重复使用的数据。UDP协议可靠性低，但其相对TCP协议占用的网络带宽较低，没有建立连接时的开销，适合用于传输可靠性要求较低，一次性使用的数据。其可靠性由系统中的其他容错性设计来保证。

在调度节点与计算节点交互的数据包中，有些在传输过程中不允许出现丢失，数据包中的内容可能会被重复使用，如计算节点登录报文、计算作业的原始信息等。对于这些数据包，系统使用TCP协议来防止传输时数据出现丢失。

在调度节点与计算节点交互的过程中，有些数据包则对传输的可靠性要求相对不那么高，只被使用一次，如节点任务报文、计算结果报文、心跳报文等。对于这类报文，系统使用UDP协议来进行传输，以此来降低系统的网络开销。虽然UDP协议可能会导致节点任务的丢失，但通常出现丢失的情况较小，且系统的容错性设计使得系统可以在出现节点任务丢失情况下对其进行重发。

5 实验数据

系统破解率测试当前最常见的MD5为测试样本，破解策略采用暴力破解方式。目前，已测试MD5密文数约138万条，其中约1017万条破解成功，破解率为73.34%;测试Half-MD5密文数约7.5万条，其中约6.5万条破解成功，破解率为86.73%，破解率情况如表1所示。

6 结束语

本文以GPU和ASIC为基础，开展基于GPU的多策略散列算法并行计算技术研究和基于ASIC的复杂密码破解技术研究。在此基础上，通过异构计算集群调度技术，利用GPU的高灵活性，结合ASIC的高性能，构建分布式、多手段密码破解在线服务平台，形成高效率、高精准、体系化、规模化破解资源池，同时研发多手段密码口令破解在线服务平台，实现密码口令、破解的大复杂度运算和高速破解功能，并在公安机关开展应用测试。

参考文献

[1] Zaharia M， Das T， Li H， et al. Discretized streams： an efficient and fault-tolerant model for stream processing on large clusters[C]. Proceedings of the 4th USENIX conference on Hot Topics in Cloud Ccomputing. USENIX Association， 2012： 10-10.

[2] Zaharia M， Chowdhury M， Das T， et al. Fast and interactive analytics over Hadoop data with Spark[J]. USENIX; login， 2012， 37（4）： 45-51.

[3] 李凯.GPU上散列算法库的研究与实现[D].广州： 华南理工大学， 2013.

[4] 张娜，明平洲，王加昌，等.多GPU加速在高性能数值计算中的应用[A].中国核动力研究设计院核反应堆系统设计技术重点实验室，2014-07.

[5] 申飞. SHA系列算法安全性的统计分析[D]. 郑州：解放军信息工程大学，2011.

[6] Netty project. Netty：Home[EB/OL].https：//netty.io/，2017-04-01.

[7] Wikipedia. Discrete Fourier transform[EB/OL].https：//en.wikipedia.org/wiki/Discret e_Fourier_transform， 2017-03-24.

[8] Wikipedia. K-means Clustering[EB/OL].https：//en.wikipedia.org/wiki/K-means_clusteri ng， 2017-04-09.

[9] Toshniwal A， Taneja S， Shukla A， et al. Storm @Twitter[J]. Acm Sigmod International Conference on Manageme， 2014：147-156.