密碼口令破解彩虹表查找系統(tǒng)設(shè)計與實現(xiàn)

張冬芳 管磊 戴曉苗

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

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

中圖分類號： TP393.0 ? ? ? ? ?文獻(xiàn)標(biāo)識碼：A

Abstract： At present， cyber crimes are becoming more and more serious. It requires technical support to crack the password information in the suspect's computer. In this paper， the construction principle of rainbow table and the process of password cracking are studied. Combined with the powerful computing power of MIC， a password cracking system based on rainbow table lookup is designed and realized. The design of parallelization improves the generation speed of rainbow table， and the design of reduction function improves the success rate of plaintext search.

Key words： password cracking; rainbow table; many integrated core; parallelization

1 引言

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

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

2 相關(guān)工作

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

3 彩虹表算法

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

3.1 彩虹表的生成

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

本文首先對彩虹表的基本原理進(jìn)行分析，包含彩虹表的構(gòu)造方法和破解密碼口令的彩虹表法?；贛IC強大的計算性能，提出了利用MIC集群實現(xiàn)并行的彩虹表生成和在線查找。彩虹表的生成實現(xiàn)了節(jié)點間并行、節(jié)點上并行和MIC卡上并行。大大提高了彩虹表的生成速度。結(jié)合縮減函數(shù)和轉(zhuǎn)換函數(shù)定義規(guī)約函數(shù)提高明文查找成功率。該系統(tǒng)將在公安機(jī)關(guān)開展應(yī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é)報，2015，1： 005.

[7] 王偉兵，文伯聰.基于彩虹表技術(shù)的分布式密碼破解研究[J].中國人民公安大學(xué)學(xué)報（自然科學(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.