摘 要：當(dāng)前網(wǎng)絡(luò)犯罪越來(lái)越嚴(yán)重，破解犯罪嫌疑人計(jì)算機(jī)中的的密碼信息則需要技術(shù)支持。文章研究了彩虹表的構(gòu)造原理、破解密碼口令的過(guò)程，并結(jié)合MIC眾核協(xié)處理器強(qiáng)大的計(jì)算能力，設(shè)計(jì)實(shí)現(xiàn)了密碼口令破解彩虹表查找系統(tǒng)，并行化的設(shè)計(jì)提高了彩虹表的生成速度，歸約函數(shù)的設(shè)計(jì)提高了明文查找成功率。

　　關(guān)鍵詞：密碼破解;彩虹表;眾核協(xié)處理器;并行化

　　1 引言

　　哈希算法可以將任意長(zhǎng)度的二進(jìn)制值串通過(guò)一定的映射規(guī)則映射為固定長(zhǎng)度的二進(jìn)制值串。被廣泛應(yīng)用于密碼學(xué)領(lǐng)域。對(duì)于一個(gè)優(yōu)秀的哈希算法需要具備三個(gè)特點(diǎn)：(1)單向性—通過(guò)哈希值無(wú)法反向推到出原始數(shù)據(jù);(2)對(duì)輸入數(shù)據(jù)極其敏感—兩個(gè)即使只有1bit差異的輸入數(shù)據(jù)，其對(duì)應(yīng)的散列值會(huì)有很大的不同;(3)碰撞幾率極小—如果兩個(gè)散列值不同，那么其對(duì)應(yīng)的原始數(shù)據(jù)也是不相同的。哈希算法有非常多的應(yīng)用，比如安全加密、唯一標(biāo)識(shí)、數(shù)據(jù)校驗(yàn)、分布式存儲(chǔ)等。

　　窮舉法和查表法通常被用于破解哈希函數(shù)。窮舉法，顧名思義，就是需要將所有可能的結(jié)果進(jìn)行列舉，具體地說(shuō)，遍歷明文空間，然后使用哈希算法求出明文空間中的每一個(gè)密碼的哈希值，最后將哈希值與密文進(jìn)行比對(duì)，其計(jì)算量非常大，破解密碼口令的時(shí)間非常久。查表法是從預(yù)先保存好的明文組合與哈希值的映射中，通過(guò)密文查找對(duì)應(yīng)的明文來(lái)破解密碼口令。雖然查表法的破解速度高于窮舉法，但其對(duì)存儲(chǔ)空間的要求極大。結(jié)合窮舉法和查表法存在的特點(diǎn)，Hellman[1]和Oechslin[2]等人提出了彩虹表(Rainbow Table)，這種方法既保證了密碼口令的破解速度，又降低了存儲(chǔ)空間，是一種實(shí)用且有效的技術(shù)。為有效且高效地破解密碼口令，本文提出了彩虹表查找系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)方案。

　　2 相關(guān)工作

　　Hellman于1980年首次提出了基于時(shí)空權(quán)衡(Time-Memory Trade-Off，TMTO)的表方法。這種方法分為兩個(gè)階段，即預(yù)計(jì)算階段和在線階段。為了建立密文空間與明文空間的映射，引入了可以用于交替地計(jì)算明文和密文的規(guī)約函數(shù)從而形成一個(gè)鏈表，鏈表的首節(jié)點(diǎn)和末尾節(jié)點(diǎn)被記錄存儲(chǔ)，而大量的首節(jié)點(diǎn)-末尾節(jié)點(diǎn)又組成了一張表，但由于規(guī)約函數(shù)與密文-明文映射非一一對(duì)應(yīng)，會(huì)導(dǎo)致哈希碰撞問(wèn)題的出現(xiàn)[1]。Rivest于1982年改進(jìn)了Hellman的方法，為了降低鏈的重合率，他引入了區(qū)分點(diǎn)(Distinguished Points)[3]。Oechslin于2003年，在Hellman的方法的基礎(chǔ)上提出了彩虹表(Rainbow Table)，他將Hellman方法中每次計(jì)算都使用相同的規(guī)約函數(shù)，改為每次計(jì)算時(shí)采用不同的規(guī)約函數(shù)，顯著地降低了鏈的重合率[2]。2009年Thing在彩虹表的基礎(chǔ)上，改進(jìn)了TMTO方法，將存儲(chǔ)首節(jié)點(diǎn)和末尾節(jié)點(diǎn)改為只存儲(chǔ)末尾節(jié)點(diǎn)值，通過(guò)相應(yīng)的數(shù)學(xué)運(yùn)算來(lái)獲得首節(jié)點(diǎn)，因此減少了表的存儲(chǔ)空間[4]。2012年，梁艷等人提出了基于生成元的彩虹表，該方法根據(jù)常用的口令設(shè)置方法減少長(zhǎng)口令的生成空間過(guò)濾掉不滿足要求的口令，從而降低了表的存儲(chǔ)空間[5]。2015年張悅等人設(shè)計(jì)了基于HBase的彩虹表MD5哈希密碼解密系統(tǒng)，其引入Map/Reduce框架與HBase，為完成計(jì)算與存儲(chǔ)，MD5彩虹表的生成和查找分配給集群節(jié)點(diǎn)，并使用HBase實(shí)現(xiàn)彩虹表的存儲(chǔ)，明顯地提高了彩虹表的生成速度和破解密碼的效率[6]。2017年王偉兵等人在經(jīng)典彩虹表的算法基礎(chǔ)上，提出了構(gòu)造分布式完美彩虹表的思路，通過(guò)MPI了并行編程接口，將彩虹表分布存儲(chǔ)于集群中的每臺(tái)計(jì)算機(jī)中。在破解階段，通過(guò)集群中的多臺(tái)計(jì)算機(jī)并行計(jì)算，可以明顯地加快和提高密碼破解的速度和有效率[7]。

　　3 彩虹表算法

　　彩虹表(Rainbow Table)技術(shù)可以理解成一種針對(duì)哈希算法的破解技術(shù)。其核心思想是按一定的規(guī)則將密文映射為明文空間中的口令，這個(gè)規(guī)則稱之為歸約函數(shù)()。

　　3.1 彩虹表的生成

　　在彩虹表的構(gòu)造階段，首先使用哈希算法將明文空間中的一個(gè)口令映射為密文，然后再使用規(guī)約函數(shù)，將密文映射為另一明文，使用哈希函數(shù)、規(guī)約函數(shù)依次迭代，得到，，，，…，，，，和分別是該條鏈的首節(jié)點(diǎn)和末尾節(jié)點(diǎn)，將這兩個(gè)節(jié)點(diǎn)都存儲(chǔ)下來(lái)。多條彩虹鏈構(gòu)成了彩虹表：

　　其中，表示明文空間中的s條文明，H表示要破解的哈希函數(shù)，表示規(guī)約函數(shù)，s和k是算法的參數(shù)，不同的參數(shù)值將直接影響彩虹表的存儲(chǔ)空間及密碼破解時(shí)間。

　　3.2 基于彩虹表的密碼口令破解

　　對(duì)某一已知密文C來(lái)說(shuō)，想要得到其對(duì)應(yīng)的密文，可按三個(gè)流程步驟進(jìn)行。

　　步驟一：對(duì)密文C使用規(guī)約函數(shù)，計(jì)算出明文，檢索彩虹表，如果末尾節(jié)點(diǎn)中包含，則說(shuō)明C對(duì)應(yīng)的明文可能存在于該條彩虹鏈中，從該鏈的首節(jié)點(diǎn)開(kāi)始進(jìn)行哈希函數(shù)、歸約函數(shù)依次迭代，若鏈中存在與C相等，那么上一步的計(jì)算結(jié)果則為C對(duì)應(yīng)的正確明文，破解成功。

　　步驟二：如果在末尾節(jié)點(diǎn)中未找到，則以為起點(diǎn)，依次使用哈希函數(shù)和規(guī)約函數(shù)計(jì)算一次得到明文，按步驟一流程在查找末尾節(jié)點(diǎn)，若未找到則重復(fù)步驟二繼續(xù)查找。

　　步驟三：當(dāng)重復(fù)次數(shù)大于彩虹表中的鏈條總數(shù)時(shí)，說(shuō)明該密文C未存儲(chǔ)在該彩虹表中，破解失敗。

　　基于彩虹表的密碼口令破解過(guò)程流程步驟，如圖1所示。

　　4 系統(tǒng)設(shè)計(jì)

　　4.1 基于MIC集群的彩虹表的生成

　　4.1.1 系統(tǒng)總體框架

　　眾核協(xié)處理器(Many Integrated Core，MIC)是Intel公司針對(duì)高性能并行計(jì)算而設(shè)計(jì)的協(xié)處理器，其擁有非常強(qiáng)大的計(jì)算性能，可以給程序應(yīng)用提供強(qiáng)大的并行度[8]。彩虹表的生成和查詢就是基于MIC而設(shè)計(jì)實(shí)現(xiàn)的。生成系統(tǒng)主要包含四個(gè)硬件結(jié)構(gòu)：PC端、管理服務(wù)器、MIC服務(wù)器和存儲(chǔ)服務(wù)器，生成系統(tǒng)框架如圖2所示。

　　其中，PC終端依照搜索空間表達(dá)式、算法等發(fā)布指定的任務(wù)文件。管理服務(wù)器收到終端發(fā)來(lái)的任務(wù)文件后，平均分配需要計(jì)算的任務(wù)給各個(gè)MIC服務(wù)器。MIC服務(wù)器具備多塊MIC卡設(shè)備，可以進(jìn)行并行計(jì)算來(lái)生成彩虹表的子表。存儲(chǔ)服務(wù)器接收到各個(gè)MIC服務(wù)器發(fā)來(lái)的子表，對(duì)這些子表的數(shù)據(jù)進(jìn)行一致性檢測(cè)、完整性檢測(cè)，并存儲(chǔ)起來(lái)。

　　系統(tǒng)實(shí)現(xiàn)了三層并行，即節(jié)點(diǎn)間并行、節(jié)點(diǎn)上并行和MIC卡上的并行。

　　節(jié)點(diǎn)間并行：采用MPI技術(shù)實(shí)現(xiàn)并行。對(duì)于需要生成規(guī)模很大的彩虹表，使用MIC集群，MIC管理節(jié)點(diǎn)將彩虹表的計(jì)算空間平均分配給每一個(gè)獨(dú)立的計(jì)算節(jié)點(diǎn)，彩虹表鏈末尾節(jié)點(diǎn)的生成任務(wù)則由這些獨(dú)立的計(jì)算節(jié)點(diǎn)共同完成。

　　節(jié)點(diǎn)上并行：采用Pthread多線程庫(kù)函數(shù)實(shí)現(xiàn)并行。MIC計(jì)算服務(wù)器具有多塊MIC卡設(shè)備，檢測(cè)函數(shù)可檢測(cè)MIC節(jié)點(diǎn)上MIC卡設(shè)備的塊數(shù)，有多少塊就開(kāi)啟多少個(gè)線程，并將任務(wù)均分給每一個(gè)線程來(lái)共同完成。

　　MIC卡上的并行：采用OpenMP技術(shù)實(shí)現(xiàn)并行。MIC的眾核具有非常厲害的計(jì)算能力，只需保留一個(gè)核心來(lái)進(jìn)行任務(wù)的調(diào)度，其余的核心均可用來(lái)計(jì)算，除此之外，每個(gè)核心可以開(kāi)啟4個(gè)線程進(jìn)行并行計(jì)算。

　　4.1.2 彩虹表結(jié)構(gòu)設(shè)計(jì)

　　彩虹表的配置文件包括八個(gè)部分：算法(生成的表使用何種散列函數(shù))、搜索空間表達(dá)式、彩虹表鏈長(zhǎng)、彩虹表鏈數(shù)、首個(gè)起始點(diǎn)的值、起始點(diǎn)值遞增步數(shù)、塊大小、彩虹表生成需使用計(jì)算節(jié)點(diǎn)的數(shù)量。

　　在原有配置文件的信息的基礎(chǔ)上，彩虹表的子表還添加了用于記錄子表節(jié)點(diǎn)號(hào)的頭文件，需要生成的塊數(shù)及已生成的塊數(shù)等信息。這種設(shè)計(jì)有利于解決由計(jì)算節(jié)點(diǎn)失效帶來(lái)的問(wèn)題，一旦計(jì)算節(jié)點(diǎn)失效，可以根據(jù)子表中頭文件里的信息從中斷計(jì)算的地方恢復(fù)任務(wù)。

　　4.1.3 規(guī)約函數(shù)設(shè)計(jì)

　　規(guī)約函數(shù)是建立起密文到明文之間的映射的橋梁，他的設(shè)計(jì)對(duì)整個(gè)彩虹表的成功率至關(guān)重要。該系統(tǒng)將縮減函數(shù)和轉(zhuǎn)換函數(shù)相結(jié)合定義歸約函數(shù)，主要階段包括縮減和明文轉(zhuǎn)換。

　　縮減函數(shù)可將密文通過(guò)與特殊的掩碼值進(jìn)行一系列的與、或、位移等固定操作，獲取固定的索引值。在MIC上利用MIC內(nèi)嵌原語(yǔ)使縮減函數(shù)可以完成16路的并行縮減操作。

　　轉(zhuǎn)換函數(shù)可以憑借縮減函數(shù)得到的索引值，將其映射到字符空間來(lái)轉(zhuǎn)換成相對(duì)應(yīng)的明文。為優(yōu)化傳統(tǒng)的轉(zhuǎn)換函數(shù)，減小求于操作的時(shí)延，因此在MIC端和GPU端采用與、異或、移位方法。

　　4.2 基于MIC的彩虹表在線查找

　　彩虹表的在線查找需要用到的結(jié)構(gòu)：PC終端、MIC計(jì)算服務(wù)器和存儲(chǔ)節(jié)點(diǎn)，具體的查找框架如圖3所示。

　　PC終端將任務(wù)文件信息發(fā)送給MIC計(jì)算服務(wù)器;MIC計(jì)算服務(wù)器接收任務(wù)信息后對(duì)該信息進(jìn)行解析，生成彩虹鏈的末尾節(jié)點(diǎn)并發(fā)送給存儲(chǔ)服務(wù)器;存儲(chǔ)服務(wù)器接收到末尾節(jié)點(diǎn)信息后索引末尾節(jié)點(diǎn)對(duì)應(yīng)的首節(jié)點(diǎn)，并將匹配到的首節(jié)點(diǎn)返回給MIC計(jì)算服務(wù)器;MIC計(jì)算服務(wù)器接收到首節(jié)點(diǎn)信息后進(jìn)行以該節(jié)點(diǎn)為首節(jié)點(diǎn)的哈希函數(shù)、規(guī)約函數(shù)迭代計(jì)算，生成鏈進(jìn)行密碼口令破解，并將破解結(jié)果返回給PC終端;PC終端接收查詢結(jié)果，查找結(jié)束。

　　5 結(jié)束語(yǔ)

　　本文首先對(duì)彩虹表的基本原理進(jìn)行分析，包含彩虹表的構(gòu)造方法和破解密碼口令的彩虹表法?；贛IC強(qiáng)大的計(jì)算性能，提出了利用MIC集群實(shí)現(xiàn)并行的彩虹表生成和在線查找。彩虹表的生成實(shí)現(xiàn)了節(jié)點(diǎn)間并行、節(jié)點(diǎn)上并行和MIC卡上并行。大大提高了彩虹表的生成速度。結(jié)合縮減函數(shù)和轉(zhuǎn)換函數(shù)定義規(guī)約函數(shù)提高明文查找成功率。該系統(tǒng)將在公安機(jī)關(guān)開(kāi)展應(yīng)用測(cè)試。接下來(lái)將重點(diǎn)研究基于彩虹表的破解速度與彩虹表的大小和彩虹鏈的長(zhǎng)度之間的關(guān)系。

　　參考文獻(xiàn)

　　[1] Hellman M E.A cryptanalytic time-memory trade-off[J].Information Theory， IEEE Transactions on，1980，26(4)： 401-406.

　　[2] Oechslin P.Making a faster cryptanalytic time-memory trade-off[M] // Advances in Cryp-tology-CRYPTO 2003.Springer Berlin Heidelberg，2003： 617-630.

　　[3] Dorothy Denning.Cryptography and Data Security[M].Boston， Massachusetts， USA： Addison-Wesley，1982：100.

　　[4] Thing V L L， Ying H M.A novel time-memory trade-off method for password recovery[J].Digital Investigation， 2009， 6： S114-S120.

　　[5] 梁艷，張琛嶺，邱衛(wèi)東.基于生成元的彩虹表[J].信息安全與通信保密，2012 (12)： 85-87.

　　[6] 張悅.基于HBase的彩虹表MD5哈希密碼解密[J].深圳職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2015，1： 005.

　　[7] 王偉兵，文伯聰.基于彩虹表技術(shù)的分布式密碼破解研究[J].中國(guó)人民公安大學(xué)學(xué)報(bào)(自然科學(xué)版)， 2017，23(01)：79-84.

　　[8] Intel Corporation.Intel? Many Integrated Core Architecture - Advanced[EB/OL].http：//www.intel.com/content/www/us/en/architecture-and-technology/many-integrated-core/intel-many-integrated-core-architecture.html， 2017

　　推薦閱讀：網(wǎng)絡(luò)安全工程師的論文文獻(xiàn)