基于MPI的并行密碼恢復框架

蔣璐瑾

(湖南省婦幼保健院信息中心，湖南 長沙 410011)

0 引言

密碼是保護保密數(shù)據(jù)的重要手段，對稱密鑰加解密算法雖然安全度不高，但是具有使用方便的優(yōu)點。因此，對稱密鑰加解密方法至今仍然被廣泛使用。用戶可以將數(shù)據(jù)用一個密鑰進行處理，并把加密后的數(shù)據(jù)發(fā)送到接收端，在接收端用戶再用同樣的密鑰解密。如果加密數(shù)據(jù)在傳輸過程被獲取，解密方在不知道加密密鑰的情況下，需要通過幾百萬次、甚至幾百萬億次的嘗試才可能破解密碼，此種方法也稱為“暴力破解”。在沒有任何密碼破解提示的情況，使用當前的單機系統(tǒng)，很難在有限時間內(nèi)破解一個加密文件。

基于字典(Dictionary-based Password Recovery)的密碼破解技術[1-4]通過嘗試一個密碼字典中的所有密碼來破解加密數(shù)據(jù)。密碼字典通常由熟悉的名稱、常用單詞、簡單字符序列等組成，針對由大量密碼組成的密碼字典，順序地測試每個密碼是一種很費時的工作。但是，此類計算具有天然的并行性，因為各個密碼的測試是相互獨立的，這些測試可以并行執(zhí)行。因此基于字典的密碼恢復技術易于被高性能計算機并行執(zhí)行。

一個大的密碼字典通常會提高破解密碼的可能性。但是，這也提高了計算復雜性?；谟脩裘艽a的可能概率分布，Weir[2]設計了一個自動生成字典的系統(tǒng)。基于特殊字符和數(shù)字出現(xiàn)的概率，該系統(tǒng)首先分析訓練密碼集合，從而決定生成密碼的不同語法的概率。此方法可以根據(jù)已知的密碼集合，分析出密碼生成的概率，從而派生出可能的未知密碼集合。生成的密碼集合以預測的可能性的概率從高到低排序。JtR[5]是一個開源的軟件包，該軟件包設計的目的是破解具有特殊格式的密碼，例如基于MD5和SHA-1的加密密碼。這個工具對于恢復忘記的密碼和弱密碼很有用。此外JtR還支持基于字典的攻擊。馬爾科夫鏈也可以用來進行數(shù)據(jù)解密[6]，某些情況下性能優(yōu)于JtR和暴力破解。在實際應用過程中，馬爾科夫過程比JtR更有效果。馬爾科夫過程的另一個突出的優(yōu)點是它可以在一個確定的時間完成。

在高性能計算領域，有很多基于MPI(Message Passing Interface，消息傳遞接口)或OpenMPI的工具集[7-15]。Foster[16]首 先 提 出 了 網(wǎng) 格 計 算 技 術，MPICHG是一種基于網(wǎng)格的MPI實現(xiàn)。基于分布式提供的志愿計算資源，Bernaschi[4]設計了一種面向松耦合系統(tǒng)結構的密碼破解框架。該框架把異構的節(jié)點分為不同類型節(jié)點，第1層是根節(jié)點，第2層和第3層是計算節(jié)點，不同層次的計算節(jié)點的功能不同。Pellicer[17]基于 BOINC 系統(tǒng)結構，設計了一種面向MD4算法的密碼搜索算法。

本文設計并實現(xiàn)了一個基于MPI的并行密碼恢復框架P2RF(Parallel Password Recovery Framework)。該框架把需要解密的數(shù)據(jù)和候選密鑰在任務級分布到不同的計算節(jié)點上，計算節(jié)點再根據(jù)節(jié)點計算資源配置的不同把計算分布到計算資源上。本文使用多種實驗測試集分析了P2RF的內(nèi)存占用和執(zhí)行時間情況，針對不同的測試集合分析了其任務分布和內(nèi)存占用的策略。

1 P2RF框架的設計與實現(xiàn)

1.1 框架設計

P2RF框架由3部分組成:根節(jié)點、計算節(jié)點、字典文件，如圖1所示。根節(jié)點和計算節(jié)點集合可以是獨立的物理節(jié)點也可以是網(wǎng)格上的虛擬節(jié)點，字典文件存儲在文件系統(tǒng)中，可以在本地磁盤中也可以在磁盤陣列中。

圖1 P2RF框架設計

加密數(shù)據(jù)破解的基本步驟為:

1)把密碼字典和加密數(shù)據(jù)分布到不同的節(jié)點;

2)每個節(jié)點根據(jù)分布到自己的密碼字典，解密加密數(shù)據(jù)，通過CRC校驗判斷密碼的有效性;

3)如果發(fā)現(xiàn)正確的密碼，則程序停止并報告。

根節(jié)點的功能是從字典文件中讀取字典，然后派發(fā)到計算節(jié)點，根節(jié)點讀取是采用非阻塞讀取的方式，把字典文件中的數(shù)據(jù)分批讀入到根節(jié)點的主存中，根節(jié)點再把數(shù)據(jù)以非阻塞的方式發(fā)送到計算節(jié)點。因此，根節(jié)點開辟了多塊緩沖區(qū)，這些緩沖區(qū)順序地被字典文件數(shù)據(jù)填滿，當數(shù)據(jù)被發(fā)送到計算節(jié)點后，緩沖區(qū)被標記為空閑，等待下次被字典文件數(shù)據(jù)填滿。

計算節(jié)點使用雙緩沖從根節(jié)點接收字典數(shù)據(jù)，當緩沖數(shù)據(jù)到達后，把數(shù)據(jù)發(fā)派到計算線程或加速器上(這些都稱為可執(zhí)行部件Process Element，PE)，這些可執(zhí)行部件根據(jù)收到的字典密鑰，進行對加密數(shù)據(jù)的解密操作，通過比較校驗和判斷該密鑰是否為正確的密鑰，當計算節(jié)點找到了正確的密鑰，就把正確的密鑰報告給根節(jié)點，此時，根節(jié)點發(fā)送結束通知信息給所有的計算節(jié)點。如果一個計算節(jié)點嘗試了所有的密鑰都沒有找到正確的密鑰，則發(fā)送請求給根節(jié)點，讓根節(jié)點發(fā)送新的字典給自己。如果一個計算節(jié)點在測試本次的密鑰集合過程中，收到了根節(jié)點已經(jīng)尋找到正確密鑰的通知，則該計算節(jié)點等待當前密鑰的判斷結束后，立即退出程序。

1.2 框架實現(xiàn)

圖2 P2RF框架根節(jié)點功能實現(xiàn)

框架包括2個部分:根節(jié)點的實現(xiàn)和計算節(jié)點的實現(xiàn)，根節(jié)點和計算節(jié)點間的通信采用MPI通信庫實現(xiàn)。圖2給出了根節(jié)點的功能實現(xiàn)，系統(tǒng)初始化后，根節(jié)點處于等待狀態(tài)，等待計算節(jié)點發(fā)送的請求，如果計算節(jié)點計算完成當前需要處理的密鑰，則向根節(jié)點發(fā)出請求，如果根節(jié)點發(fā)現(xiàn)字典已經(jīng)處理完成，則說明當前字典沒有找到正確的密鑰，那么就向計算節(jié)點發(fā)送計算完成的指令，計算節(jié)點收到該指令后即退出;如果仍然有沒有處理完成的密鑰，則繼續(xù)發(fā)送密鑰給計算節(jié)點，計算節(jié)點收到密鑰后，解密這批密鑰的正確性;如果一個計算節(jié)點找到了正確的密鑰，則發(fā)通知給根節(jié)點，根節(jié)點收到通知后，會等待沒有完成的計算節(jié)點，當計算節(jié)點發(fā)送下一階段的請求后，則通知它計算已經(jīng)完成，找到了正確的密鑰。

1.3 任務調(diào)度模塊

在并行程序執(zhí)行過程中，任務調(diào)度的作用是控制循環(huán)并行結構的執(zhí)行。P2RF框架專門設計了調(diào)度模塊，可以通過調(diào)度去控制解密任務的調(diào)度和分配，從而適應不同的使用情況，提高性能。P2RF框架的調(diào)度模塊支持3種工作模式:靜態(tài)調(diào)度、動態(tài)調(diào)度和用戶指導的調(diào)度。

1)靜態(tài)調(diào)度。

系統(tǒng)默認采用的是靜態(tài)調(diào)度方式。靜態(tài)調(diào)度的關鍵輸入?yún)?shù)為chunk，表示一個線程執(zhí)行的默認子任務數(shù)目(需要解密的密碼空間)，當需要執(zhí)行的子任務數(shù)目為 N，執(zhí)行計算的線程數(shù)為 M時，[0，chunk-1]的chunk次的迭代是在第1個線程上運行，[chunk，2*chunk-1]是在第2個線程上運行，依次類推。該任務分配過程是靜態(tài)確定的，不會因為運行的情況改變。如果chunk沒有指定，只是指定采用靜態(tài)類型，那么系統(tǒng)使用子任務數(shù)/線程數(shù)作為chunk的值，這樣每個線程執(zhí)行的子任務數(shù)目就是一樣的。

2)動態(tài)調(diào)度。

動態(tài)調(diào)度的子任務分配是依賴于運行狀態(tài)動態(tài)確定的，所以哪個線程上將會運行哪些子任務是無法像靜態(tài)調(diào)度一樣事先預料的。對于動態(tài)調(diào)度，沒有chunk參數(shù)的情況下，每個線程按先執(zhí)行完先分配的方式執(zhí)行Iter個子任務，比如，剛開始，線程1先啟動，那么會為線程1分配Iter個子任務開始去執(zhí)行，然后，可能線程2啟動了，那么為線程2分配Iter個子任務，假設這時候線程0和線程3沒有執(zhí)行完，而線程1的子任務已經(jīng)執(zhí)行完，可能會繼續(xù)為線程1分配Iter個子任務。所以，動態(tài)分配的結果是無法事先知道的，這些都是取決于系統(tǒng)的資源、線程的調(diào)度等。

3)用戶指導的調(diào)度。

用戶指導的調(diào)度類似于動態(tài)調(diào)度，但每次分配的子任務數(shù)目不同，開始分配的數(shù)目比較大，以后逐漸減小。chunk表示每次分配的子任務數(shù)目的最小值，由于每次分配的子任務數(shù)目會逐漸減少，當減少到chunk時，分配的子任務數(shù)目將不再減少。

運行過程中，程序員可以通過設置 P2RF_SCHED_TYPE環(huán)境變量，來配置任務調(diào)度策略，其語法是 export P2RF_SCHED_TYPE=“type，chunk”。其中，type 可以是 static、dynamic、guided，chunk 可以選擇設置為正整數(shù)。

2 實驗結果和分析

為了驗證P2RF框架的有效性，在表1所示平臺上測試了P2RF框架的性能，測試用例采用大小為16 kB的加密Word文檔。該平臺的每個計算節(jié)點有2個CPU，每個CPU有6個計算核心，每個計算節(jié)點有12個核。

表1 實驗平臺介紹

實驗結果如圖3所示，本實驗的調(diào)度策略是static，chunk=2048。從圖3可知，系統(tǒng)平均每秒的解密次數(shù)隨著計算節(jié)點數(shù)目的增加近似線性增長(根節(jié)點不參與計算過程)，例如2個節(jié)點的時候，框架的解密能力是11850次/s，32個節(jié)點的時候，系統(tǒng)解密能力是365000次/s?？梢娤到y(tǒng)的擴展性是線性可擴展的。

為了分析解密數(shù)據(jù)大小對解密速率的影響，在32節(jié)點的平臺上，使用不同大小的解密數(shù)據(jù)測試了P2RF的解密速率。實驗結果如圖4所示，當解密數(shù)據(jù)規(guī)模為128 kB時，解密速率可達68萬次，基本上為數(shù)據(jù)規(guī)模為256 kB時的2倍，這說明2點:首先，P2RF框架的并行效率較好，通信不會引入冗余的開銷;其次，P2RF選擇的串行解密算法的計算復雜度是O(N)量級的，其運算時間和被解密數(shù)據(jù)的大小正相關。但是，當數(shù)據(jù)規(guī)模逐漸變大時，例如在4096 kB時，解密速率只有2萬6千次，這是因為最后一級共享Cache不能容納所有線程的訪存工作集合，出現(xiàn)了一定的Cache失效，導致了系統(tǒng)性能的下降。

圖4 P2RF框架解密速率分析圖

3 結束語

本文設計了一個基于MPI的并行密碼恢復框架P2RF，該框架把需要解密的數(shù)據(jù)和候選密鑰在任務級分布到不同的計算節(jié)點上，計算節(jié)點再根據(jù)節(jié)點計算資源配置的不同把計算分布到計算資源上。實驗結果表明:P2RF的擴展性隨著節(jié)點的增多而線性擴展。

[1] Grama A，Karypis G，Kumar V，et al Introduction to Parallel Computing[M].2nd Edition.Addison Wesley，2003.

[2] Weir M，Aggarwal S，de Medeiros B，et al.Password cracking using probabilistic context-free grammars[C]//Proceedings of the 30th IEEE Symposium on Security and Privacy.2009:391-405.

[3] Dell’Amico M，Michiardi P，Roudier Y.Password strength:An empirical analysis[C]//Proceedings of the 29th IEEE Conference on Computer Communications.2010:1-9.

[4] Bernaschi M，Bisson M，Gabrielli E，et al.An architecture for distributed dictionary attacks to cryptosystems[J].Journal of Computers，2009，4(5):378-386.

[5] Peslyak A.John the Ripper[DB/OL].http://www.openwall.com/john/，2013-05-30.

[6] Marechal S.Advances in password cracking[J].Journal in Computer Virology，2008，4(1):73-81.

[7] 張華杰.基于MPI的并行算法的研究[D].金華:浙江師范大學，2010.

[8] Wilkinson B，Allen M.并行程序設計[M].陸鑫達，等譯.北京:機械工業(yè)出版社，2005.

[9] Li Kuan-Ching，Chang Hsun-Chang，Yang Chao-Tung，et al.On construction of a visualization toolkit for MPI parallel programs in cluster environments[C]//Proceedings of the 9th International Conference on Advanced Information Networking and Applications.2005，2:211-214.

[10] Panda D K，Ni L M.Special issue on workstation clusters and network-based computing[J].Journal of Parallel and Distributed Computing，1997，40(1):1-3.

[11] Desai N，Bradshaw R，Lusk A，et al.MPI cluster system software[C]//Proceedings of the 11th European PVM/MPI Users’Group Meeting.2004:277-286.

[12] 都志輝.高性能計算并行編程技術:MPI并行程序設計[M].北京:清華大學出版社，2001.

[13] Chong Yong-Kim，Hwang Kai.Performance analysis for four memory consistency models for multithreaded multiprocessors[J].IEEE Transactions on Parallel and Distributed Systems，1995，6(10):1085-1099.

[14] Hockney R W.The Science of Computer Benchmarking[Z].The Society for Industrial and Applied Mathematics，Philadelphia，1996.

[15] 李繼民，馬力，王風先.PC機群系統(tǒng)的關鍵技術[J].河北大學學報(自然科學版)，2002，22(1):55-58.

[16] Foster I，Karonis N T.A grid-enabled MPI:Message passing in heterogeneous distributed computing systems[C]//Proceedings of the 1998 ACM/IEEE Conference on Supercomputing.1998.

[17] Pellicer S，Pan Yi，Guo Minyi.Distributed MD4 password hashing with grid computing package BOINC[C]//Proceedings of the 3rd International Conference on Grid and Cooperative Computing.2004:679-686.