張清忠

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

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

1 云計(jì)算與Hadoop

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

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

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

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

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

(2)MapReduce

圖1 MapReduce工作流程

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

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

2.1 類n進(jìn)制數(shù)

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

(2)L>L′

此時(shí)，X′的長度比X短，需要在X′的高位補(bǔ)上L-L′個(gè)-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 分布式密碼恢復(fù)流程

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

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

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

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

-153440--1-102510632-1-1

(1)

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

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

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

2.3 性能評估

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

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

表1 實(shí)驗(yàn)結(jié)果

3 結(jié)論

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

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