基于云計算的密碼恢復系統(tǒng)模型構建

張清忠

(黎明職業(yè)大學 信息與電子工程學院，福建 泉州 362000)

密碼恢復[1]技術是密碼分析的一個分支，密碼恢復在計算機取證等方面起到了關鍵作用，其發(fā)展受到了越來越多的關注.暴力破解是密碼恢復采用的主要方法，其主要思想是窮舉密碼空間，遍歷該空間直到找到密碼.但是由于密碼強度的增加，密碼空間越來越大，這為密碼恢復造成了很大的困難.采用暴力破解(brute force)進行密碼恢復需要搜索巨大的密碼空間，使用Hadoop[2]平臺搭建密碼恢復私有云系統(tǒng)，能夠更有效地在較短時間內進行密碼恢復.Hadoop是一個使用MapReduce編程模型和處理大數(shù)據數(shù)據集的開源軟件框架.Hadoop的核心包括一個稱為Hadoop分布式文件系統(tǒng)(HDFS)以及一個MapReduce[3]編程模型的處理部分.Hadoop將大文件分解成較小的文件塊，并將它們分布在集群中的節(jié)點上.然后它將打包的代碼傳輸?shù)礁鱾€節(jié)點中以進行數(shù)據并行處理.為了提高密碼恢復的效率，本文構建了一個基于云計算的密碼恢復系統(tǒng)模型，采用了Hadoop計算模型，將巨大的密碼空間分成若干小的密碼空間.并將該密碼恢復系統(tǒng)實現(xiàn)后，對其進行性能評估.

1 云計算與Hadoop

云計算(cloud computing)[4]采用了分布式計算(Distributed Computing)的模式，將單個計算機無法完成的大規(guī)模計算任務分成多個小規(guī)模的子任務，網絡中的節(jié)點對這些小任務進行計算后，將結果匯總給用戶.采用暴力破解(brute force)進行密碼恢復需要搜索巨大的密碼空間，使用Hadoop平臺搭建密碼恢復私有云系統(tǒng)，能夠更有效地在較短時間內進行密碼恢復.

Hadoop是一個使用MapReduce編程模型和處理大數(shù)據數(shù)據集的開源軟件框架.

Hadoop的核心包括一個稱為Hadoop分布式文件系統(tǒng)(HDFS)以及一個MapReduce編程模型的處理部分.Hadoop將大文件分解成較小的文件塊，并將它們分布在集群中的節(jié)點上.然后它將打包的代碼傳輸?shù)礁鱾€節(jié)點中以進行數(shù)據并行處理.

(1)Hadoop分布式文件系統(tǒng)

HDFS是用Java編寫的用于Hadoop框架的分布式、可擴展和可移植的文件系統(tǒng).每個數(shù)據庫通過網絡使用特定的HDFS塊協(xié)議來提供數(shù)據塊.文件系統(tǒng)使用TCP/IP套接字進行通信.客戶端使用遠程過程調用(RPC)來進行通信.HDFS將大型文件存儲到在多臺機器上，它通過在多個主機之間存儲冗余數(shù)據來實現(xiàn)可靠性(數(shù)據冗余值默認為3，即數(shù)據存儲在3個節(jié)點上：兩個在同一個機架上，另一個存儲在不同的機架上).數(shù)據節(jié)點可以進行相互通信，通過移動數(shù)據的副本，維持節(jié)點間的負載均衡.

(2)MapReduce

圖1 MapReduce工作流程

MapReduce是一個編程模型，能夠在集群上通過使用并行分布式算法處理大數(shù)據.MapReduce程序由兩個部分組成：執(zhí)行過濾和排序的Map()部分以及執(zhí)行摘要操作的Reduce()部分.MapReduce工作流程如圖1所示.

2 基于云計算的密碼恢復系統(tǒng)模型

2.1 類n進制數(shù)

有這樣一組數(shù)字集合：[0,1,2]、[00,01,02]、[10,11,12]等等，這些組合是由集合{0,1,2}中的數(shù)字組成的.這些數(shù)字集合的形式類似于三進制數(shù)，但是并不是嚴格的三進制數(shù).與三進制數(shù)相比，它們包括從零開始的數(shù)字.在這里將稱這些數(shù)字定義為類三進制數(shù).類n進制數(shù)的形式化定義如下所示：令集合S為S={ai|ai∈Zn,0≤i≤n}.其中，將n定義為基數(shù).一個類n進制數(shù)就是由集合S的元素所組成的組合.將類三進制數(shù)轉換為十進制數(shù)字的過程如下：如果X是一個L長度的類n進制數(shù)，即X={XL-1XL-2XL-3…X1X0}，假設Y是十進制數(shù)，則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進制數(shù).

(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 系統(tǒng)模型

圖2 分布式密碼恢復流程

密碼恢復模型的基本思想是將構成密碼字符集的字符看成是類n進制數(shù)，其基數(shù)是字符集的大小.所以，密碼就會被映射成一個類n進制數(shù).當劃分搜索空間時，我們只是對類n進制數(shù)進行操作.例如，如果字符集是{a,b,c,0,7,1,9,D}，并且密碼由字符集中的字符組成，我們可以將字符視為類n進制數(shù)的元素，相應的集合是{0，1，2，3，4，5，6，7}.該模型通過逐步嘗試所有候選密碼來實現(xiàn)密碼恢復.該模型可以均勻劃分出不同長度的密碼搜索空間，能夠實現(xiàn)節(jié)點之間的數(shù)據獨立性，具有較小的通信開銷.此外，該模型靈活易用，僅僅需要少量的時間來計算子空間的邊界并生成下一個候選密碼.算法的另一個關鍵是處理密碼長度的變化.密碼恢復模型的實現(xiàn)過程如圖2所示.

圖3 密碼字符集的處理過程

步驟1：將原始密碼字符集的元素順序打亂，然后將字符集的每個元素映射為相應的數(shù)字.隨機選擇搜索的初始密碼和結束密碼.例如，對于密碼字符集charset={a,b,c,0,1,！}，其處理過程如圖3所示.

步驟2：獲取密碼搜索空間的所有候選密碼.利用結束密碼索引減去初始密碼索引可以得到整個密碼搜索空間(如公式1所示).

-153440--1-102510632-1-1

(1)

當計算不同長度密碼的數(shù)量時，我們需要注意密碼數(shù)量的變化.例如，如果字符集是小寫的，從“a”到“z”的密碼數(shù)是26，“aa”到“zz”的數(shù)字是262；從“aaa”到“zzz”的數(shù)字是263.令初始密碼的長度為l1，結束密碼的長度為l2.

步驟3：服務器將候選密碼的整個空間劃分為子任務(子空間)，計算每個子任務的初始密碼和結束密碼，并將其分配到每個節(jié)點.如果子任務的數(shù)值大于原子任務的數(shù)值，它將繼續(xù)分配，直到數(shù)值小于或等于原子任務的數(shù)值.

步驟4：計算節(jié)點從起初始密碼生成每個索引候選密碼其基于增量模式的分布式任務，將其轉換為真實的密碼并將其破解.如果計算節(jié)點是并行設備，則可以根據DMPC將任務分為若干部分進行破解.

2.3 性能評估

為了評估模型的性能，將密碼恢復模型實現(xiàn)在Hadoop分布式平臺上，并同時利用密碼恢復模型恢復MD5[5]加密算法的密碼.

實驗中使用了不同的密碼字符集，對比了使用配置GPU[6]的單個普通PC以及使用分布式密碼恢復模型來進行密碼恢復的所需的時間，實驗結果如表1所示.實驗結果顯示，本文的密碼恢復模型性能優(yōu)秀.

表1 實驗結果

3 結論

為了提高密碼恢復的效率，本文構建了一個基于云計算的密碼恢復系統(tǒng)模型，這是一個通用的密碼破解模型.它可以用來破解各種算法加密的密碼.它也可以被應用到GPU上并發(fā)地進行破解.該模型在數(shù)據獨立性、較低的交換和設施等方面取得了較好的效果.該模型采用了Hadoop計算模型，將巨大的密碼空間分成若干小的密碼空間.我們將該密碼恢復系統(tǒng)實現(xiàn)后，對其進行性能評估.實驗結果顯示本文的模型能夠大大減少密碼恢復的時間，提高密碼恢復的效率.

[1] 蔣秉天,邱衛(wèi)東,李萍.基于云計算的密碼恢復系統(tǒng)模型[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.