基于異構計算集群的密碼口令破解系統設計與實現

張冬芳 管磊 戴曉苗 楊亞星

摘? ?要：針對當前密碼口令破解功能單一、破解算法種類不足、效率低下等技術問題，從基于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.